關(guān) 健，劉 悅

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

基于蟻群算法的變電站巡檢機(jī)器人自主導(dǎo)航方法

關(guān) 健1，劉 悅2

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

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

變電站巡檢機(jī)器人；自主導(dǎo)航；路徑規(guī)劃；蟻群算法

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

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

1 變電站巡檢機(jī)器人巡檢原則及建模

1.1 巡視原則

變電站采用巡回的方式進(jìn)行巡檢，即從充電室出發(fā)，對設(shè)定的定點(diǎn)進(jìn)行巡檢，完成任務(wù)后返回充電室，巡視路線形成一條回路。設(shè)計機(jī)器人的最短巡視路徑時需遵循下列原則：

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

2)每個巡視點(diǎn)只巡視一次；

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

1.2 巡視路徑建模

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

目標(biāo)函數(shù)：目標(biāo)為巡視路徑路程最小，即

式中：i為第i個巡視點(diǎn)，j為第j個巡視點(diǎn)，ωij為第i個巡視點(diǎn)與第j個巡視點(diǎn)的距離。

約束條件：

1)保證巡檢機(jī)器人每個巡視點(diǎn)只巡視一次約束為

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

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

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

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

2 蟻群算法

2.1 蟻群算法基本原理

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

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

2.2.1 狀態(tài)概率公式

將m只螞蟻放在n個巡視點(diǎn)上，單獨(dú)的一只螞蟻根據(jù)下面的狀態(tài)概率公式來選擇下一個行進(jìn)的巡視點(diǎn)，此處螞蟻隨機(jī)選擇的依據(jù)是貪婪原則；

2.2.2 局部信息素更新公式

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

其中，ρ∈(0,1)表示信息素?fù)]發(fā)因子。

2.2.3 全局信息素更新公式

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

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

根據(jù)所得路徑，選擇充電室巡視點(diǎn)作為起點(diǎn)，即可得到變電站機(jī)器人的最短巡視路徑。

2.2.4 ACS算法流程

Step1 初始化。螞蟻種群規(guī)模m，一般情況下，種群規(guī)模等于巡視點(diǎn)數(shù)目，巡視點(diǎn)的數(shù)目n，螞蟻個體計數(shù)k=1，巡視點(diǎn)計數(shù)num=1，當(dāng)前迭代次數(shù)Nc=0，最大迭代次數(shù)Ncmax，信息素啟發(fā)因子α，期望啟發(fā)因子β，信息素?fù)]發(fā)因子ρ，信息素強(qiáng)度Q。

Step2 若Nc<=Ncmax，轉(zhuǎn)step3，否則，輸出最短路徑。

Step3 若k>m，轉(zhuǎn)step6，否則轉(zhuǎn)step4。

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

Step5 若num>=n，則k=k+1，轉(zhuǎn)step3。

Step6 此時，螞蟻已經(jīng)巡視完一周，進(jìn)行全局信息素更新，令Nc=Nc+1，轉(zhuǎn)step2[10]。

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

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

3 算例仿真

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

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

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

3.1 用ACS算法對機(jī)器人的巡視路徑進(jìn)行規(guī)劃

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

1)獲取巡視點(diǎn)位置的坐標(biāo)，計算出各個巡視點(diǎn)的歐式距離。

2)用最近鄰法構(gòu)造一個初始解。

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

4)開始算法主循環(huán)。

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

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

3.2 用遺傳算法對機(jī)器人路徑進(jìn)行規(guī)劃

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

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

3.3 結(jié)果分析

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

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

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

現(xiàn)對兩種方法下的巡檢路徑尋優(yōu)水平進(jìn)行分析：

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

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

4 結(jié) 語

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

[1] 魏玉虎，王庫.基于履帶式巡檢機(jī)器人的自動導(dǎo)航系統(tǒng)設(shè)計與實(shí)現(xiàn)[D].北京：中國農(nóng)業(yè)大學(xué)，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ī)器人路徑規(guī)劃中的圖方法應(yīng)用綜述[J].工程圖學(xué)學(xué)報,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] 樊曉平，李雙艷，陳特放.基于新人工勢場函數(shù)的機(jī)器人動態(tài)避障規(guī)劃[J].控制理論與應(yīng)用,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ī)器人避障方法研究[J].武漢工程大學(xué)學(xué)報,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] 胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M].北京：高等教育出版社，2004． HU Yunquan.Fundamentals and application of operations research[M].Beijing：Higher Education Press,2004.

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

[8] 趙娟平，高憲文，符秀輝．改進(jìn)蟻群優(yōu)化算法求解移動機(jī)器人路徑規(guī)劃問題[J].南京理工大學(xué)學(xué)報，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] 李國勇,李維民.人工智能及其應(yīng)用[M].北京: 電子工業(yè)出版社,2009.LI Guoyong,LI Weimin.Artificial intelligence and its application[M].Beijing: Electronic Industry Press,2009.

[10] 段海濱.蟻群算法原理及其應(yīng)用[M].北京: 科學(xué)出版社,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。

關(guān) 健(1993—)，男，工學(xué)學(xué)士，從事輸電線路巡檢及維護(hù)工作。

TM632+.2+TP24

A

2095-6843(2017)04-0319-04