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

徐平, 劉悅

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

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

徐平1, 劉悅2

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

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

變電站智能巡檢；改進的Kruskal算法；最短巡視路徑

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

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

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

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

1.1 建模原則

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

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

b)每個巡視點只經(jīng)過一次；

c)目標是使巡視路徑的路程最小。

1.2 目標函數(shù)

目標函數(shù)為

(1)

式中dij為第i個巡視點與第j個巡視點的距離。

1.3 約束條件

1.3.1 約束條件1

約束條件1是保證巡檢機器人每個巡視點只巡視一次。

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

1.3.2 約束條件2

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

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

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

2.1 Kruskal算法的基本思想

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

2.2 Kruskal基本算法

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

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

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

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

f)輸出T和ω，結束。

3 采用改進的Kruskal算法求最短巡視路徑

3.1 改進的Kruskal算法的基本思想

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

3.2 改進的Kruskal基本算法

設mD為第i個頂點Vi的度。改進的Kruskal基本算法的步驟為：

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

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

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

d)對于mD=1的點，求最小完美匹配M；

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

4 算例分析

4.1 算例

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

圖1 某變電站巡視點分布

圖2 某變電站巡視點散點圖

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

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

圖3 最小支撐樹

圖4 改進Kruskal算法下的最短路徑

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

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

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

4.4 結果分析

對改進的Kruskal算法和遺傳算法得到的最短路徑進行對比，見表1。

表1 2種算法求最短路徑結果比較

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

5 結論

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

[1] 肖鵬，欒貽青，郭銳，等.變電站智能巡檢機器人激光導航系統(tǒng)研究[J]. 自動化與儀表，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] 李紅梅，王濱海，廖文龍，等.基于地圖匹配的變電站巡檢機器人激光導航系統(tǒng)設計[J]. 制造業(yè)自動化，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] 覃俊，藍雯飛，蘭華榮.用遺傳算法求解旅行商問題[J]. 中南民族學院學報(自然科學版)，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]. 華東船舶學院學報，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] 趙娟平，高憲文，符秀輝.改進蟻群優(yōu)化算法求解移動機器人路徑規(guī)劃問題[J]. 南京理工大學學報，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] 胡運權.運籌學基礎及應用[M]. 北京：高等教育出版社，2004.

[10] 余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應用[J]. 計算機工程與應用，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)，男，山西運城人。高級工程師，工學碩士，從事電氣工程自動化工作。

劉悅(1991)，女，吉林洮南人。在讀碩士研究生，研究方向為魯棒自適應控制。