關(guān) 健，劉 悅

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

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

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

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

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

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

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

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

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

1.1 巡視原則

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

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

2)每個(gè)巡視點(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個(gè)巡視點(diǎn)，j為第j個(gè)巡視點(diǎn)，ωij為第i個(gè)巡視點(diǎn)與第j個(gè)巡視點(diǎn)的距離。

約束條件：

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

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

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

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

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

2 蟻群算法

2.1 蟻群算法基本原理

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

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

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

將m只螞蟻放在n個(gè)巡視點(diǎn)上，單獨(dú)的一只螞蟻根據(jù)下面的狀態(tài)概率公式來(lái)選擇下一個(gè)行進(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，螞蟻個(gè)體計(jì)數(shù)k=1，巡視點(diǎn)計(jì)數(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ù)概率選擇公式選擇下一個(gè)巡視點(diǎn)，修改螞蟻k的禁忌表，將下一個(gè)巡視點(diǎn)放入禁忌表中，并且進(jìn)行局部信息素更新。巡視點(diǎn)計(jì)數(shù)num=num+1，轉(zhuǎn)step3，否則轉(zhuǎn)step5。

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

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

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

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

3 算例仿真

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

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

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

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

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

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

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

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

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

設(shè)定種群的個(gè)數(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)行對(duì)比，如表1所示。

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

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

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

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

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

4 結(jié) 語(yǔ)

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

[1] 魏玉虎，王庫(kù).基于履帶式巡檢機(jī)器人的自動(dòng)導(dǎo)航系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].北京：中國(guó)農(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] 成偉明，唐振民，趙春霞，等.移動(dòng)機(jī)器人路徑規(guī)劃中的圖方法應(yīng)用綜述[J].工程圖學(xué)學(xué)報(bào),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ì)場(chǎng)函數(shù)的機(jī)器人動(dòng)態(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é)報(bào),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ì)算機(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)化算法求解移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題[J].南京理工大學(xué)學(xué)報(bào)，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] 李國(guó)勇,李維民.人工智能及其應(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