徐平, 劉悅

(1. 廣東電網(wǎng)有限責(zé)任公司江門供電局，廣東 江門 529000；2. 東北電力大學(xué) 自動(dòng)化工程學(xué)院，吉林 吉林 132012)

基于改進(jìn)Kruskal算法的變電站機(jī)器人路徑規(guī)劃

徐平1, 劉悅2

(1. 廣東電網(wǎng)有限責(zé)任公司江門供電局，廣東 江門 529000；2. 東北電力大學(xué) 自動(dòng)化工程學(xué)院，吉林 吉林 132012)

鑒于目前中國變電站智能巡檢機(jī)器人多采用磁感應(yīng)線配合射頻識(shí)別技術(shù)的導(dǎo)航方式實(shí)現(xiàn)定點(diǎn)巡視，對(duì)機(jī)器人巡視點(diǎn)的路徑規(guī)劃問題進(jìn)行研究。首先，考慮到精確算法的復(fù)雜性，用近似算法對(duì)巡視路徑進(jìn)行規(guī)劃，以貪心算法和局部搜索思想為主，結(jié)合啟發(fā)式算法對(duì)求最小支撐樹的Kruskal算法進(jìn)行改進(jìn)；然后，用MATLAB軟件編程求出機(jī)器人的最短巡視路徑；最后，用遺傳算法求出最短路徑，并將遺傳算法和改進(jìn)的Kruskal算法下的最短巡視路徑進(jìn)行比較。比較結(jié)果表明：改進(jìn)的Kruskal算法優(yōu)勢明顯，且適用于小規(guī)模變電站巡視路徑規(guī)劃。

變電站智能巡檢；改進(jìn)的Kruskal算法；最短巡視路徑

變電站智能巡檢機(jī)器人能否安全自主運(yùn)行，可靠的導(dǎo)航系統(tǒng)尤為重要。目前，導(dǎo)航方式主要有磁導(dǎo)航、全球定位系統(tǒng)(global position system，GPS)導(dǎo)航、激光導(dǎo)航、慣性導(dǎo)航和構(gòu)建地圖導(dǎo)航等[1-2]，在中國用得最多的是磁導(dǎo)航方式，即在場地鋪設(shè)或者埋藏磁性感應(yīng)線配合射頻識(shí)別(radio frequency identification，RFID)技術(shù)進(jìn)行定位導(dǎo)航。機(jī)器人按照一定的路線行走并實(shí)現(xiàn)定點(diǎn)巡視，因此機(jī)器人的路徑規(guī)劃問題成為研究重點(diǎn)之一。

機(jī)器人從充電室出發(fā)，巡視一周，最后返回充電室，形成一條回路，機(jī)器人的路徑規(guī)劃就是求路程的最小值。這種問題類似于求最短路中的旅行商問題(tranveling salesman problem，TSP)[3]，即某人從任一城市出發(fā)，途徑n個(gè)城市，并且每個(gè)城市只經(jīng)過1次，旅行后回到出發(fā)城市，使得行走路程(或費(fèi)用)最小。針對(duì)TSP有精確算法、近似算法和智能算法，精確算法有運(yùn)籌學(xué)中的線性規(guī)劃法、分支定界法、動(dòng)態(tài)規(guī)劃法等，這些方法雖然能夠求出最優(yōu)解，但是計(jì)算量巨大；隨著智能算法的興起，進(jìn)化算法[4]、遺傳算法[5]、混合遺傳算法、模擬退火算法[6]、退火遺傳算法、蟻群算法[7]、神經(jīng)網(wǎng)絡(luò)算法[8]、禁忌搜索等智能算法也被用到TSP的求解中，且在城市較多時(shí)取得了較好的結(jié)果。

本文根據(jù)變電站的實(shí)際情況，以近似算法中貪心算法和局部搜索的思想為主，考慮改進(jìn)Kruskal算法，通過編寫MATLAB程序[9]實(shí)現(xiàn)路徑規(guī)劃。首先用原始的Kruskal算法根據(jù)權(quán)值矩陣求出路徑的最小支撐樹，然后對(duì)Kruskal算法進(jìn)行改進(jìn)，從各個(gè)巡視點(diǎn)出發(fā)，通過最小完美匹配等方法實(shí)現(xiàn)路徑的規(guī)劃；最后給出算例，對(duì)某變電站進(jìn)行巡視，分別用改進(jìn)的Kruskal算法和遺傳算法[10]求出最短路徑，并對(duì)兩種算法得到的結(jié)果進(jìn)行分析對(duì)比。

1 變電站智能機(jī)器人路徑規(guī)劃建模

1.1 建模原則

變電站智能巡檢機(jī)器人路徑規(guī)劃建模主要遵循以下原則：

a)選擇充電室巡視點(diǎn)作為出發(fā)點(diǎn)和終點(diǎn)；

b)每個(gè)巡視點(diǎn)只經(jīng)過一次；

c)目標(biāo)是使巡視路徑的路程最小。

1.2 目標(biāo)函數(shù)

目標(biāo)函數(shù)為

(1)

式中dij為第i個(gè)巡視點(diǎn)與第j個(gè)巡視點(diǎn)的距離。

1.3 約束條件

1.3.1 約束條件1

約束條件1是保證巡檢機(jī)器人每個(gè)巡視點(diǎn)只巡視一次。

式中n為巡視點(diǎn)的數(shù)量。

1.3.2 約束條件2

約束條件2是保證機(jī)器人在行進(jìn)的過程中，直到返回充電室不形成環(huán)路徑。

式中S為入選進(jìn)規(guī)劃路徑的邊的集合。

2 采用Kruskal算法求最小支撐樹

2.1 Kruskal算法的基本思想

Kruskal算法是一種求賦權(quán)完全圖的最小支撐樹算法，其應(yīng)用的貪婪原則是：首先將所有點(diǎn)與點(diǎn)之間的權(quán)值排序，選擇最小的權(quán)所在的邊作為第一條邊，之后從剩下的邊中選擇一條邊加入到已有邊中，并且保證所選的邊與已有的邊不構(gòu)成環(huán)路，因而生成一棵最小支撐樹。

2.2 Kruskal基本算法

a)對(duì)集合E中各邊的權(quán)由小到大排序，即ω1≤ω2≤…≤ωm且ω1=ω(e1)，其中e1為任選的第一條邊；

b)令ω=0，已選邊集T=?，邊的循環(huán)變量k=1，邊的計(jì)數(shù)變量t=0；

c)若t=n-1，則轉(zhuǎn)步驟f，否則轉(zhuǎn)步驟d；

e)T=T+{ek}(ek為新選入規(guī)劃路徑的第k條邊)，ω=ω+1，k=k+1，t=t+1，轉(zhuǎn)步驟c；

f)輸出T和ω，結(jié)束。

3 采用改進(jìn)的Kruskal算法求最短巡視路徑

3.1 改進(jìn)的Kruskal算法的基本思想

根據(jù)原始的Kruskal算法得出最小支撐樹，其目標(biāo)是得到一條巡視回路，因此從點(diǎn)的度考慮，每個(gè)點(diǎn)的度都應(yīng)為2。在此時(shí)得到的結(jié)果中，點(diǎn)的類型可以分為3類：度大于2的點(diǎn)、度等于2的點(diǎn)、度等于1的點(diǎn)。再通過刪除大邊、找最小完美匹配等方法使得所有點(diǎn)的度都為2，以啟發(fā)式思想找到最短路徑。

3.2 改進(jìn)的Kruskal基本算法

設(shè)mD為第i個(gè)頂點(diǎn)Vi的度。改進(jìn)的Kruskal基本算法的步驟為：

a)根據(jù)權(quán)集，通過Kruskal算法求出最小支撐樹；

b)若mD>2，則對(duì)其連接邊由小到大排序，刪除最大邊；

c)若mD=0，根據(jù)貪心算法思想，則聯(lián)結(jié)各點(diǎn)，若頂點(diǎn)數(shù)為1則聯(lián)結(jié)其最近的mD=1的點(diǎn)；

d)對(duì)于mD=1的點(diǎn)，求最小完美匹配M；

e)將M按照從小到大的順序加到已有支撐樹中，若不產(chǎn)生圈則加入，否則不加入，若結(jié)果中沒有鏈則結(jié)束，否則轉(zhuǎn)步驟d。

4 算例分析

4.1 算例

以某變電站(如圖1所示)為例，變電站共有18個(gè)巡視點(diǎn)，要求智能巡檢機(jī)器人從充電室出發(fā)，將各個(gè)巡視點(diǎn)巡視一周后回到充電室，規(guī)劃最短巡視路徑。運(yùn)用改進(jìn)的Kruskal算法，編寫MATLAB程序，求解最短路徑。另外，作為方法比較，用遺傳算法通過MATLAB軟件編程求最短路徑。為便于路徑的規(guī)劃，建立以充電室為原點(diǎn)的平面直角坐標(biāo)系，將18個(gè)巡視點(diǎn)按照坐標(biāo)的形式表示出來，如圖2所示。綜合考慮變電站現(xiàn)有磁性感應(yīng)線的鋪設(shè)現(xiàn)狀，在路徑規(guī)劃過程中作出如下約束：各個(gè)巡視點(diǎn)之間的路程以實(shí)際巡檢機(jī)器人在磁感應(yīng)線上的路徑為準(zhǔn)，即各個(gè)巡視點(diǎn)距離已知；巡檢原則為只對(duì)目的巡視點(diǎn)進(jìn)行定點(diǎn)巡視，即保證每個(gè)巡視點(diǎn)只巡視一次。

圖1 某變電站巡視點(diǎn)分布

圖2 某變電站巡視點(diǎn)散點(diǎn)圖

4.2 改進(jìn)的Kruskal算法下的最短路徑規(guī)劃

通過Kruskal算法得到最小支撐樹(如圖3所示)，繼而通過改進(jìn)的Kruskal算法得到最短路徑(如圖4所示，路徑連線表示巡視點(diǎn)到下一巡視點(diǎn)，下同)。

圖3 最小支撐樹

圖4 改進(jìn)Kruskal算法下的最短路徑

4.3 遺傳算法下的最短路徑規(guī)劃

設(shè)定迭代次數(shù)為50，適應(yīng)值歸一化淘汰加速指數(shù)為2，交叉概率為0.4，變異概率為0.2，通過編寫MATLAB程序求出此變電站巡視點(diǎn)的最短路徑，結(jié)果如圖5所示。

圖5 遺傳算法下的最短巡視路徑

4.4 結(jié)果分析

對(duì)改進(jìn)的Kruskal算法和遺傳算法得到的最短路徑進(jìn)行對(duì)比，見表1。

表1 2種算法求最短路徑結(jié)果比較

由表1可看到：在此變電站應(yīng)用背景下，本文算法優(yōu)勢較為明顯。

5 結(jié)論

本文針對(duì)目前我國變電站智能巡檢機(jī)器人大多采用磁導(dǎo)航定點(diǎn)巡視的現(xiàn)狀，對(duì)巡視的路徑進(jìn)行規(guī)劃。首先用Kruskal算法求出各巡視點(diǎn)的最小支撐樹;然后從度的角度出發(fā)，對(duì)Kruskal算法進(jìn)行改進(jìn)，運(yùn)用啟發(fā)式思想得到改進(jìn)Kruskal算法下的最短路徑。為便于驗(yàn)證此算法是否更優(yōu)，用遺傳算法通過MATLAB編程求出最短路徑，對(duì)遺傳算法和本文算法下的最短路徑進(jìn)行比較，結(jié)果說明本文算法優(yōu)勢明顯。此方法可配合小規(guī)模變電站的自主導(dǎo)航技術(shù)，通過預(yù)先尋找巡視點(diǎn)路徑，達(dá)到了巡視路徑不經(jīng)任何電力設(shè)備的目的，實(shí)現(xiàn)了變電站智能巡檢機(jī)器人路徑的合理規(guī)劃。

[1] 肖鵬，欒貽青，郭銳，等.變電站智能巡檢機(jī)器人激光導(dǎo)航系統(tǒng)研究[J]. 自動(dòng)化與儀表，2012，(5)：5-9.

XIAO Peng，LUAN Yiqing，GUO Rui，et al. Substation Inspection Robot Intelligent Laser Navigation System Research[J]. Automation and Instrument，2012(5)：5-9.

[2] 李紅梅，王濱海，廖文龍，等.基于地圖匹配的變電站巡檢機(jī)器人激光導(dǎo)航系統(tǒng)設(shè)計(jì)[J]. 制造業(yè)自動(dòng)化，2014，36(1)：52-56.

LI Hongmei，WANG Binhai，LIAO Wenlong，et al. Substation Inspection Robot Based on Map Matching Laser Navigation System Design[J]. Journal of Manufacturing Automation，2014，36(1)：52-56.

[3] LAWLER E L, LENSTRA J K. The Traveling Salesman Problem[M]. Chichete：Wiley，1995.

[4] FOGEL D B. Applying Evolutionary Programming to Selected Taveling Salesman Problems[J]. Cybernetics and System，2011(1)：24-27.

[5] 覃俊，藍(lán)雯飛，蘭華榮.用遺傳算法求解旅行商問題[J]. 中南民族學(xué)院學(xué)報(bào)(自然科學(xué)版)，2011，19(1)：41-42.

QIN Jun，LAN Wenfei，LAN Huarong. Using Genetic Algorithm to Solve Traveling Salesman Problem[J]. Journal of Zhongnan Institute for Nationalities(Natural Sciences)，2011，19(1)：41-42.

[6] 高尚.求解旅行商問題的模擬退火算法[J]. 華東船舶學(xué)院學(xué)報(bào)，2013，17(3)：13-16.

GAO Shang. Simulated Annealing Agorithm to Solve Traveling Salesman Problem[J]. Journal of East China Institute of the Ship，2013，17(3)：13-16.

[7] 趙娟平，高憲文，符秀輝.改進(jìn)蟻群優(yōu)化算法求解移動(dòng)機(jī)器人路徑規(guī)劃問題[J]. 南京理工大學(xué)學(xué)報(bào)，2011，35(5)：637-641.

ZHAO Juanping，GAO Xianwen，F(xiàn)U Xiuhui. Ant Colony Optimization Algorithm for Solving the Mobile Robot Path Planning Problem[J]. Journal of Nanjing University of Science and Technology，2011，35(5)：637-641.

[8] TEOH E J, TAN K C, TANG H J, et al. An Asynchronous Recurrent Linear Threshold Network Approach to Solving the Traveling Salesman Problem[J]. Neurocomputing，2008，71(79)：1359-1372.

[9] 胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M]. 北京：高等教育出版社，2004.

[10] 余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用，2008，42(3)：86-89.

YU Youming，LIU Yushu，YAN Guangwei. The Coding Theory and Application of Genetic Algorithm[J]. Computer Engineering and Application，2008，42(3)：86-89.

(編輯 李麗娟)

Path Planning for Substation Robot Based on Improved Kruskal Algorithm

XU Ping1, LIU Yue2

(1.Jiangmen Power Supply Bureau of Guangdong Power Grid Co., Ltd., Jiangmen 529000, China; 2.School of Automation Engineering, Northeast Electric Power University, Jilin, Jilin 132012, China)

In view of current domestic intelligent inspection robots in substations using navigation mode of magnetic induction lines with radio frequency identification (RFID) technology for designated inspection, this paper studies path planning for inspection points. It firstly considers complexity of the precise algorithm and adopts approximate algorithm for planning inspection path. Focusing on greedy algorithm and local search ideas, it combines heuristic algorithm for improving Kruskal algorithm of minimum support tree. Then, by using MATLAB software, it works out the shortest patrol path and finally obtains the shortest path by means of genetic algorithm. Based on comparison of shortest patrol paths calculated by genetic algorithm and the improved Kruskal algorithm, it shows that the improved Kruskal algorithm has more obvious advantage and is more suitable for inspection path planning for small-scale substations.

substation intelligent inspection; improved Kruskal algorithm; the shortest patrol path

2016-07-07

2016-09-09

10.3969/j.issn.1007-290X.2016.12.002

TP242

A

1007-290X(2016)12-0006-04

徐平(1979)，男，山西運(yùn)城人。高級(jí)工程師，工學(xué)碩士，從事電氣工程自動(dòng)化工作。

劉悅(1991)，女，吉林洮南人。在讀碩士研究生，研究方向?yàn)轸敯糇赃m應(yīng)控制。