基于蟻群算法的變電站巡檢機器人自主導航方法

關 健，劉 悅

(1.廣東電網有限公司汕頭供電局，廣東 汕頭 515041； 2.東北電力大學 自動化工程學院，吉林 吉林 132012)

基于蟻群算法的變電站巡檢機器人自主導航方法

關 健1，劉 悅2

(1.廣東電網有限公司汕頭供電局，廣東 汕頭 515041； 2.東北電力大學 自動化工程學院，吉林 吉林 132012)

利用磁導航進行定點的巡檢方法在變電站巡檢智能機器人中應用廣泛，因此機器人的巡視路徑規劃問題應運而生，根據巡視路徑特點，將巡視路徑抽象為旅行商問題。首先，應用蟻群算法對路徑進行規劃；然后，用MATLAB進行了仿真；最后，用遺傳算法規劃路徑以作為對比。結果表明，蟻群算法優勢明顯。

變電站巡檢機器人；自主導航；路徑規劃；蟻群算法

變電站作為電力系統中對電能的電壓和電流進行變換、集中和分配的場所，有著極其重要的地位，因此，開展變電站巡檢以保證電力系統的安全生產及可靠運行具有重要意義。隨著人工智能的迅速發展，變電站的巡檢也由最初的人工巡檢發展到依靠智能巡檢機器人巡檢的階段。在智能巡檢機器人系統中，自主導航系統對于機器人的安全自主運行起著重要作用。目前，導航方式主要有磁導航、GPS導航、激光導航、慣性導航以及構建地圖導航等[1]，國內應用最多的是預先在場地鋪設或者埋藏磁性感應線配合RFID進行定點巡視的磁導航方式。例如，在國網青島供電公司、內蒙古電力有限公司包頭供電局、江蘇省電力公司的巡檢機器人均采用磁導航定點巡檢的方式。

針對這種對固定點巡視的導航方式，變電站機器人的路徑規劃問題凸顯出來。目前對機器人路徑規劃方法很多，例如：柵格法、人工勢場法、遺傳算法、神經網絡法、隨機樹搜索算法、可視圖法等[2-5]。本文根據變電站機器人從充電室出發，對各個巡視點巡視一周后回到出發點的巡檢方式特點，首先，將變電站的路徑規劃問題抽象為一個旅行商(TSP)問題。旅行商問題即設有個城市，某人從任一城市出發，途徑個城市，并且每個城市只經過一次，旅行一周后回到出發城市，使得行走路程(或費用)最小[6-7]。然后，將蟻群算法模型應用于機器人巡視路徑的TSP問題中[8]。最后，通過MATLAB編程仿真，仿真結果顯示該算法能夠很快實現對于智能機器人的路徑規劃。作為對照，應用遺傳算法同樣對機器人的路徑進行規劃，用MATLAB編程進行仿真，進而對兩種算法得到的結果進行了對比。

1 變電站巡檢機器人巡檢原則及建模

1.1 巡視原則

變電站采用巡回的方式進行巡檢，即從充電室出發，對設定的定點進行巡檢，完成任務后返回充電室，巡視路線形成一條回路。設計機器人的最短巡視路徑時需遵循下列原則：

1)選擇充電室巡視點作為出發點和終點；

2)每個巡視點只巡視一次；

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

1.2 巡視路徑建模

設G=(V,E,ω)為賦權完全圖，V={1,2,…,n}，邊(i,j)上的權值矩陣，ωij,i,j=1,2,…,n表示路程矩陣。xij為0-1變量，即

目標函數：目標為巡視路徑路程最小，即

式中：i為第i個巡視點，j為第j個巡視點，ωij為第i個巡視點與第j個巡視點的距離。

約束條件：

1)保證巡檢機器人每個巡視點只巡視一次約束為

式中n為巡視點的數量。

2)保證機器人在行進的過程中，直到返回充電室路徑不形成環約束為

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

針對此問題，巡視路徑即為圖論中解Hamilton圈的問題。若采用精確算法，算法復雜，并且計算量巨大，因此，考慮用人工智能算法求解。在眾多人工智能算法中，蟻群算法具有魯棒性、分布計算性、正反饋等優點，故采用蟻群算法對機器人的行進路徑進行規劃。

2 蟻群算法

2.1 蟻群算法基本原理

蟻群算法最早由意大利學者Dorigo M等提出，他們在對螞蟻的覓食過程中受到啟發，提出了蟻群算法這種新型的模擬進化算法。螞蟻在覓食過程中，蟻群在沒有任何溝通和預知下完成最優路徑的尋找，螞蟻會在其走過的路徑上留下信息素，其他螞蟻會感應這種信息素的存在，從而在越優的路徑上留下更多的信息素，并且在螞蟻動態地進行路徑調整的同時，信息素會不斷揮發，這樣就會使劣勢路徑信息素更少，優勢路徑信息素更多。根據這種正反饋，螞蟻找到最優的路徑。當然，在蟻群算法中，人們用人工的螞蟻來代替生物學中的螞蟻，人工螞蟻也被賦予了一些條件，例如：人工螞蟻有一定的記憶功能，其搜索空間為離散的，其信息素是人為設定的[9]。

2.2 機器人路徑規劃問題的蟻群(ACS)算法

2.2.1 狀態概率公式

將m只螞蟻放在n個巡視點上，單獨的一只螞蟻根據下面的狀態概率公式來選擇下一個行進的巡視點，此處螞蟻隨機選擇的依據是貪婪原則；

2.2.2 局部信息素更新公式

τ(r,s)=(1-ρ)×τ(r,s)+ρ×Δτ(r,s)

其中，ρ∈(0,1)表示信息素揮發因子。

2.2.3 全局信息素更新公式

當所有的螞蟻都完成巡視后，所有的巡視路徑根據下面的全局信息素更新公式更新路徑上的信息素，得出最短路徑：

τij(t+1)=(1-ρ)×τij(t)+Δτij(t)

根據所得路徑，選擇充電室巡視點作為起點，即可得到變電站機器人的最短巡視路徑。

2.2.4 ACS算法流程

Step1 初始化。螞蟻種群規模m，一般情況下，種群規模等于巡視點數目，巡視點的數目n，螞蟻個體計數k=1，巡視點計數num=1，當前迭代次數Nc=0，最大迭代次數Ncmax，信息素啟發因子α，期望啟發因子β，信息素揮發因子ρ，信息素強度Q。

Step2 若Nc<=Ncmax，轉step3，否則，輸出最短路徑。

Step3 若k>m，轉step6，否則轉step4。

Step4 根據概率選擇公式選擇下一個巡視點，修改螞蟻k的禁忌表，將下一個巡視點放入禁忌表中，并且進行局部信息素更新。巡視點計數num=num+1，轉step3，否則轉step5。

Step5 若num>=n，則k=k+1，轉step3。

Step6 此時，螞蟻已經巡視完一周，進行全局信息素更新，令Nc=Nc+1，轉step2[10]。

ACS算法流程圖如圖1所示。

圖1 ACS算法流程圖Fig.1 ACS algorithm flow chart

3 算例仿真

本文以某變電站為例，利用ACS算法對變電站巡檢機器人進行路徑規劃，實現其自主導航的重要前期部分。如圖2所示，此變電站共有18個巡視點，首先，機器人從充電室1出發，然后巡視一周，遍歷所有巡視點，最后回到充電室。為方便路徑的規劃，以充電室為原點，建立平面直角坐標系，根據每個巡視點的坐標，畫出散點圖，如圖3所示。

圖2 某變電站巡視點分布圖Fig.2 Distribution diagram of inspection points in a substation

圖3 某變電站巡視點散點圖Fig.3 Scatter diagram of inspection points in a substation

3.1 用ACS算法對機器人的巡視路徑進行規劃

根據下述步驟，用MATLAB編程求解，得出最短路徑如圖4所示。

1)獲取巡視點位置的坐標，計算出各個巡視點的歐式距離。

2)用最近鄰法構造一個初始解。

3)設定相關參數，設最大迭代次數為2000，信息素因子為1，啟發信息因子為2，局部揮發系數的初值為0.1，全局揮發系數的初值為0.1，選擇概率為0.9，螞蟻數量為18。

4)開始算法主循環。

5)以圖像方式輸出最短巡視路徑。

圖4 蟻群算法下的最短巡視路徑Fig.4 Shortest inspection path in the ant colony algorithm

3.2 用遺傳算法對機器人路徑進行規劃

設定種群的個數為50，迭代次數也為2000，適應值歸一化淘汰加速指數為2，交叉概率為0.4，變異概率為0.2，得到最短路徑如圖5所示。

圖5 遺傳算法下的最短巡視路徑Fig.5 Shortest inspection path in the genetic algorithm

3.3 結果分析

根據上述分別用蟻群算法和遺傳算法得到的最短路徑圖，將結果進行對比，如表1所示。

表1 蟻群算法和遺傳算法最短路徑對比Table 1 Comparison of the shortest path between ant colony algorithm and genetic algorithm

通過表1我們可以清楚的看到，在此變電站的應用背景下，在相同的迭代次數約束下，運用改進的蟻群算法得到的最短路徑總路程為182.1148 m，而應用遺傳算法得到的最短路徑為239.582 m。

現對兩種方法下的巡檢路徑尋優水平進行分析：

1)尋優水平的高低與智能算法的效率有著不可割裂的關系。首先兩種智能算法的迭代次數相同，其次蟻群算法的運行時間要少于遺傳算法。雖然遺傳算法的不同參數設置會對尋優結果有一定的影響，但是尋找更優路徑的代價是程序運行時間的延長。因此，從迭代次數和程序運行時間等智能算法的效率角度來看，蟻群算法優于遺傳算法。

2)尋優水平需結合實際的路徑客觀比較。變電站是一個電氣設備固定的場所，設計的較優路徑經過電氣設備的次數越少就會有效減少施工量，更具有可行性。應用蟻群算法的路徑經過4次電氣設備區，然而，應用遺傳算法幾乎每一步都要經過電氣設備區，因此，從這個角度看，蟻群算法也優于遺傳算法。

4 結 語

針對目前國內變電站智能巡檢機器人多采用磁性感應線配合定點巡檢的自主導航檢測方式，對機器人的巡視路徑進行規劃。機器人從充電室出發，巡視完所有巡視點之后，回到充電室。針對這種類TSP問題，采用蟻群算法進行路徑規劃，之后，用MATLAB編程求解，最后，用遺傳算法在同樣的迭代次數下的結果進行了對比。結果表明，蟻群算法優勢明顯，蟻群算法適用于機器人的路徑規劃，對巡視點多、結構復雜的大型變電站優勢明顯。

[1] 魏玉虎，王庫.基于履帶式巡檢機器人的自動導航系統設計與實現[D].北京：中國農業大學，2012.WEI Yuhu,WANG Ku.Design and realization of automatic navigation system based on tracked inspection robot[D].Beijing: China Agricultural University,2012.

[2] 成偉明，唐振民，趙春霞，等.移動機器人路徑規劃中的圖方法應用綜述[J].工程圖學學報,2008 (4): 6-14.CHENG Weiming,TANG Zhenming,ZHAO Chunxia,et al.A survey of mobile robots path planning using geometric methods[J].Journal of Engineering Graphics,2008 (4): 6-14.

[3] 樊曉平，李雙艷，陳特放.基于新人工勢場函數的機器人動態避障規劃[J].控制理論與應用,2005,22(5): 703-707.FAN Xiaoping,LI Shuangyan,CHEN Tefang.Dynamic obstacle-avoiding path plan for robots based on a new artificial potential field protection[J].Control Theory & Applications,2005,22(5): 703-707.

[4] 孔偉，張彥鐸.基于遺傳算法的自主機器人避障方法研究[J].武漢工程大學學報,2008,30(3): 110-113.KONG Wei,ZHANG Yanduo.Research on the method of obstacle avoidance for automatic robot based on genetic algorithm[J].Journal of Wuhan Institute of Technology,2008,30(3): 110-113.

[5] LI H,YANG S X,SETO M L.Neural-network-based path planning for a multirobot system with moving obstacles[J].IEEE Trans on Systems,Man,and Cybernetics,2009,39(4): 410-419.

[6] 胡運權.運籌學基礎及應用[M].北京：高等教育出版社，2004． HU Yunquan.Fundamentals and application of operations research[M].Beijing：Higher Education Press,2004.

[7] 周康，強小利.求解 TSP 算法[J].計算機工程與應用,2007,43(29): 43-47.ZHOU Kang,QIANG Xiaoli.Algorithm of TSP[J].Computer Engineering and Applications,2007,43(29): 43-47.

[8] 趙娟平，高憲文，符秀輝．改進蟻群優化算法求解移動機器人路徑規劃問題[J].南京理工大學學報，2011，35(5)：637-641． ZHAO Juanping,GAO Xianwen,FU Xiuhui.Improved ant colony optimization algorithm for solving path planning problem of mobile robot[J].Journal of Nanjing University of Science and Technology,2011,35(5): 637-641.

[9] 李國勇,李維民.人工智能及其應用[M].北京: 電子工業出版社,2009.LI Guoyong,LI Weimin.Artificial intelligence and its application[M].Beijing: Electronic Industry Press,2009.

[10] 段海濱.蟻群算法原理及其應用[M].北京: 科學出版社,2005.DUAN Haibin.Ant colony algorithm and its application[M].Beijing: Science Press,2005.

(編輯 陳銀娥)

Autonomous navigation method of substation inspection robot based on ant colony algorithm

Guan Jian1,Liu Yue2

(1.Shantou Power Supply Bureau of Guangdon Electric Power Company Limited,Shantou 515041,China;2.School of Automation Engineering,Northeast Electric Power University,Jilin 132012,China)

The inspection way to fix the points by using magnetic navigation is widely applied in substation intelligent robots.Thus,the problem appears in inspection path planning.According to the characteristics of the inspection path,the path is abstracted as the traveling salesman problem.First,the ant colony algorithm is used to plan the path.Then,the simulation is carried out with MATLAB.Finally,the genetic algorithm is used to plan the path as a contrast.The results show that the ant colony algorithm has obvious advantages.

substation inspection robot; autonomous navigation; path planning; ant colony algorithm

2017-01-06；

2017-04-29。

關 健(1993—)，男，工學學士，從事輸電線路巡檢及維護工作。

TM632+.2+TP24

A

2095-6843(2017)04-0319-04