基于遺傳算法的變電站巡檢機器人任務路徑規劃方法研究

王 銳，莫志超，彭向陽，龐小峰，饒章權

(1.廣東電網有限責任公司 電力科學研究院，廣州 510080;2.中航工業洛陽電光設備研究所，河南 洛陽 471009)

基于遺傳算法的變電站巡檢機器人任務路徑規劃方法研究

王 銳1，莫志超2，彭向陽1，龐小峰1，饒章權1

(1.廣東電網有限責任公司 電力科學研究院，廣州 510080;2.中航工業洛陽電光設備研究所，河南 洛陽 471009)

近年來，隨著變電站巡檢機器人在變電站中的廣泛使用，巡檢機器人路徑規劃問題越來越成為亟待解決的問題;巡檢機器人在已知的拓撲地圖中標記了待執行巡檢任務的停靠點，不同任務需要從初始點出發經過不同的一系列停靠點再返回初始點，如何規劃路徑是機器人面臨的問題;首先分析了路徑規劃面臨的問題，然后通過分析拓撲地圖的特征，對地圖進行等價簡化，再對問題進行建模使用遺傳算法求解巡檢任務路徑規劃的近似最優解;通過仿真實驗證明，提出的基于遺傳算法的路徑規劃方法是可行有效的，為變電站巡檢機器人任務路徑規劃提供了一種有效方法。

變電站機器人；路徑規劃；遺傳算法；進化算法；中國郵差問題

0 引言

近年來，變電站巡檢機器人在變電站巡檢中占有了越來越重要的地位。尤其在少人或無人值守的變電站，巡檢機器人更是擔當了主要角色。巡檢機器人巡航時間受到電池影響，如何提高巡檢效率成為亟待解決的問題。如何在最短時間內完成所下定的巡檢任務成為研究的方向。

巡檢機器人在掃描完變電站環境之后會生成一個無向連通拓撲圖，在拓撲圖的邊上會標記有若干的停靠點。不同任務需要從初始點出發經過不同的若干個停靠點再返回初始點。這是一個近似的中國郵遞員問題[1]。求解此類問題目前研究有以下幾大類算法：1)動態規劃算法[2]，通過尋求優化的搜索算法求得較優的解；2)模擬進化算法，如蟻群算法，遺傳算法，粒子群算法等[3]；3)DNA算法[4]。本文通過對問題分析，提出基于遺傳算法的解決方法，有效解決了巡檢機器人路徑規劃問題。

1 巡檢路徑規劃面臨的問題

1.1 路徑規劃原理

變電站機器人巡檢是按照預先設定好的路徑進行行走，在路徑上有停靠點，機器人到達停靠點停車進行動作。不同任務會選擇不同的停靠點，如何從初始點出發以最短的時間完成任務并返回初始點是本文要研究的目標。由于機器人在停靠點執行動作時間相同，如何以最短的路徑代價通過所有停靠點并返回是問題的核心。

機器人巡檢路徑構成了一個連通無向圖[5]，如圖1所示，表示為G=(V,E)，V表示所有路徑頂點集合，E表示所有路徑集合。使用S表示所有停靠點集合，每個路徑包含若干個停靠點。

圖1 機器人巡檢拓撲圖

機器人巡檢過程中會優先巡檢同一條路徑上所有停靠點。例如任務中含有2和3停靠點，機器人在從初始點出發，巡視2號停靠點之后一定會先巡視3號停靠點。這與中國郵差問題中經過街道一樣。所以可以將機器人巡視要經過的停靠點轉換為需要經過的路徑。本文將路徑上停靠點最小編號作為路徑編號。

1.2 路徑規劃難點

巡檢機器人路徑規劃問題可以總結為求從初始點出發經過圖上選定的若干條路徑并返回初始點的最短代價。即給定一組待巡檢的路徑集合{e1…en}，求出一個集合排列的順序使得從初始點出發按順序經過排列中的路徑然后返回初始點的路徑最短。2個點之間行走路徑按照Floyd算法[6]求解。此問題類似于中國郵差問題[7]，路徑集合{e1…en}的所有排列有n!個，從n!個排列中找到代價最小的排列在n較大時這幾乎不可能。求解最優排列問題可以使用動態規劃算法[8]，窮舉所有可能的解。

1.3 動態規劃算法

動態規劃算法是求取最優解的一種算法。根據機器人當前位置，在圖中進行廣度優先搜索，只保留第一層的搜索結果作為下一巡檢目標的備選集。將機器人移動到備選集中的一個位置，在此位置再進行廣度優先搜索[9]，繼續移動。如圖2所示，當巡檢全部停靠點時，從初始點出發，首先搜索到1和2號停靠點，機器人選擇1號停靠點，在1號停靠點搜索下一個備選集為2、6、10、12號停靠點，重復此過程，可以將所有可行路線遍歷，求出代價最小的路徑。

圖2 機器人巡檢動態規劃算法示意圖

在問題描述中已說明巡檢時會將路徑上所有停靠點一次巡檢，即巡檢2號停靠點是機器人會將3號停靠點巡檢。所以在搜索算法中需要搜索的次數為待巡檢的路徑個數n，每次搜索到的備選集個數約為2～4個。可得算法時間復雜度在2n～4n。在待巡檢路徑n較多時此算法求得最優解需要的時間是不能忍受的，本文提出了基于遺傳算法的求解方法。

2 基于遺傳算法的求解方法

首先通過分析拓撲圖的特征對拓撲圖簡化，減少參與計算的路徑；再根據動態規劃算法給出路徑排列的等價模型；最后給出遺傳算法的選擇、交叉、變異、適應度模型使用遺傳算法進行求解。

路徑規劃方法的具體步驟如圖3所示，首先初始化算法：簡化拓撲圖以減少計算路徑，再使用Flord算法計算點到點最短路徑和代價并存儲到持續存儲；然后根據輸入任務點序列使用本文提出的遺傳算法進行迭代求解；最后輸出最優個體作為最優任務序列。

圖3 路徑規劃方法步驟

2.1 拓撲圖簡化

在機器人巡檢拓撲圖中存在一些“死胡同”，這些“死胡同”總是需要進入再退出。無論何時巡檢“死胡同”內的停靠點，進入、退出的代價是固定的。如圖4所示，13號停靠點在一條“死胡同”中，巡檢13號停靠點必須從圖中空心頂點出發再回到圖中空心頂點，這類在“死胡同”內的停靠點在不同的路徑集合{e1…en}的排列中的代價是固定的，所以在計算最優排列是可以忽略這些點所在的路徑。

圖4 巡檢路徑簡化示意圖

具體算法流程：

1)尋找圖中度為1的頂點，不存在則結束；

2)尋找頂點所在邊的另一頂點(兄弟頂點)；

3)將頂點標記到兄弟頂點；

4)刪除頂點所在邊，返回1)。

如圖4所示，左邊圖經過簡化之后變為右邊的圖。

2.2 路徑排列等價模型

路徑集合{e1…en}的所有排列組合有n!個，但是其中有很多是無效的巡檢序列，例如{e1,e2,e4,e5}集合的一個排列{e1,e4,e2,e5}是一個無效序列，因為從e1到e4的過程必然經過e2,e5中一個。對于{e1,e2,e4,e5}，根據動態規劃算法可知，在e1下一個巡檢路徑只能是e2,e5中一個。

在此本文給出一個轉換算法，將任意排列轉換為符合搜索邏輯的序列。算法過程如下：

1)輸入任意排列E={e1…en}，元素個數為num。初始化n=1，輸出排列R={E(1)}，即將輸入排列第一個加入輸出排列。

2)廣度優先搜索尋找E(n)下一步備選集合B={ei…ej}。

3)C=B-R,即從備選集合移除已存在R中的元素。

4)將C中元素按在E排列中順序排序，將C(1)加入R尾部。n=n+1。

5)若n

6)將E(n)加入R尾部，結束。

例如{e1,e4,e2,e5}，e1之后備選集合為{e2,e5}，e2在{e1,e4,e2,e5}中順序靠前選擇e2。e2之后備選集合為{e5,e4}，e4在{e1,e4,e2,e5}中順序靠前選擇e4。最后得到等價排列為{e1,e2,e4,e5}。

2.3 遺傳算法

首先需要給出一個排列序列的代價。本文路徑長度計算使用Floyd[10]算法求得每對頂點之間的最短路徑，機器人到巡檢序列中一個路徑代價為機器人從當前位置巡檢路徑近處的頂點，再將路徑上停靠點依次巡檢所走的路線總長度。機器人從初始點開始將排列序列所有路徑巡視完并按最短路徑返回初始點，總路線長度為此排列序列的代價。計算一個排列序列的代價總是計算其有效的等價序列的代價。

遺傳算法[11]需要計算每個個體的適應度，此問題中適應度與排列序列代價成反比。本文使用基準對比的方法求得適應度。首先隨機一個基準排列序列，求得其代價作為基準代價；任何一個排列序列的適應度為基準代價除以待求序列的代價。將此方法記為f(R)，R為排列序列。

選擇運算[12]：遺傳算法使用選擇運算來實現對群體中的個體進行優勝劣汰操作。適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。本文采用輪盤賭選擇方法，基本思想：各個體被選中的概率與其適應度函數值大小成正比。設群體大小為n，個體i的適應度通過f(R)求得，記為Fi，則個體i被選中遺傳到下一代群體的概率為：

交叉算子[13]作為遺傳算法重要的部分，2個父個體通過交叉算子產生帶著2個父個體共同信息的子個體。本文采用順序交叉法作為交叉算子。順序交叉法為從父代A隨機選一個編碼子串，放到子代A的對應位置；子代A空余的位置從父代B中按B的順序選取(與己有編碼不重復)。同理可得子代B。如：

父代A: 872 | 139 | 0546

父代B: 983 | 567 | 1420

交叉后：

子代A: 856 | 139 | 7420

子代B: 821 | 567 | 3904

變異算子[14]增加了遺傳算法全局搜索能力，避免遺傳算法陷入局部最優解。本文采用逆轉變異算法，在個體中隨機挑選兩個逆轉點，再將兩個逆轉點間的基因交換。如14527，隨機選擇2,4位置交換變異為12547。

本文增加了精英保留策略[15]，將最優的個體復制到下一代中。遺傳算法具體流程如圖5所示。

圖5 遺傳算法流程圖

遺傳算法首先要設定結束條件，本文設置結束條件為迭代次數100次和不出現更優秀個體次數10次。當超過設定迭代次數或者超過設定不出現更優秀個體次數沒有出現更優秀個體時結束算法。設置交叉概率為90%，即選擇的2個父個體有90%就行交叉產生自個體。設置變異概率為1%，每個個體有1%的概率產生隨機變異。

3 仿真實驗分析

為驗證本文提出的基于遺傳算法求解路徑規劃的有效性，本文利用仿真手段進行驗證。實驗數據在visualstudio2015上使用C#編程仿真得到。實驗所用拓撲圖6所示，路徑權重按照最小權重路徑歸一化結果，如圖6中所示。

圖6 實驗拓撲圖

仿真實驗測試的機器人任務是巡檢停靠點5,6,10,11,12,13,14,15。實驗結果如圖7所示，隨著迭代次數的增加群體評價代價逐漸降低，在迭代20次之后趨于穩定。在迭代30次的群體中取最優個體作為算法的解。本文提出的方法得出的巡檢序列為1,12,13,11,15,14,5,6,10；然后返回初始點。巡檢代價為65。與使用動態規劃求得最優一致，表明本文提出的基于遺傳算法的求解方法是迅速且有效的。

圖7 仿真實驗結果圖

本文通過與基于改進遺傳算法的機器人路徑規劃與仿真[16]所提出的算法進行對比，實驗結果如圖,8所示，實驗表明本文通過拓撲圖的簡化和路徑等價模型減少了求解的迭代次數，可以更加迅速地收斂到最優解。

圖8 對比實驗圖

通過實際運行本算法在路徑教較少情況下總是能找到最優解，在路徑較多的情況下也可以找到比較良好的解，充分滿足了變電站巡檢機器人任務路徑規劃的需求。

4 結束語

本文首先分析研究了變電站巡檢機器人任務路徑規劃的問題，將其抽象為路徑排序問題。通過分析動態規劃算法，得出其時間復雜度高不適用于解決此問題；然后根據變電站巡檢路徑拓撲圖的特點，將圖進行簡化減少了參與計算的路徑個數，減少計算復雜度；再根據動態規劃的方式給出路徑排列的等價模型；最后建立遺傳算法模型對問題進行求解。通過仿真實驗分析得出：本文提出的基于遺傳算法的路徑規劃方法有效解決了變電站巡檢機器人任務路徑規劃問題。

[1] 高敬振, 高 勃. 中國郵遞員問題50年[J]. 運籌學學報, 2013, 17(1):17-28.

[2] 費 蓉, 崔杜武. 中國郵遞員問題的動態規劃算法研究[J]. 計算機研究與發展, 2005, 42(2):294-299.

[3] 嚴 露. 粒子群算法研究與應用[D]. 成都:電子科技大學, 2013.

[4] 李 瑋, 王 雷. 中國郵遞員問題的DNA計算[J]. 計算機應用, 2009, 29(7):1880-1883.

[5] Kay E. Graph Theory with Applications[M]. London: Macmillan, 1976.

[6] Floyd R W. Algorithm 97: Shortest path[J]. Communications of the Acm, 1962, 5(6):345-345.

[7] 管梅谷.關于中國郵遞員問題研究和發展的歷史回顧[J]. 運籌學學報，2015,19(3)：1-7.

[8] Coaker P B. Applied Dynamic Programming[M]. Princeton: Princeton University Press, 1962.

[9] Eckstein D M. Parallel processing using depth-first search and Breadth First search[J]. Algorithm Synthesis A Comparative Study, 1977:8-23.

[10] 石為人, 王 楷. 基于Floyd算法的移動機器人最短路徑規劃研究[J]. 儀器儀表學報, 2009, 30(10):2088-2092.

[11] 武廣號, 文 毅. 遺傳算法及其應用[M]. 北京:人民郵電出版社, 1996.

[12] 鐘求喜, 謝 濤, 陳火旺. 遺傳算法中解個體的生存策略[J]. 計算機工程與科學, 2000, 22(1):14-17.

[13] 熊 軍, 高敦堂, 沈慶宏,等. 遺傳算法交叉算子性能對比研究[J]. 南京大學學報:自然科學版, 2004, 40(4):432-437.

[14] 鄺航宇, 金 晶, 蘇 勇. 自適應遺傳算法交叉變異算子的改進[J]. 計算機工程與應用, 2006, 42(12):93-96.

[15] 朱 燦, 梁昔明. 一種多精英保存策略的遺傳算法[J]. 計算機應用, 2008, 28(4):939-941.

[16] 李 剛, 魚佳欣, 郭道通,等. 基于改進遺傳算法的機器人路徑規劃與仿真[J]. 計算技術與自動化, 2015(2):24-27.

ResearchofSubstationInspectionRobotpathPlanningMethodBasedonGeneticAlgorithm

WangRui1,MoZhichao2,PengXiangyang1,PangXiaofeng1,RaoZhangquan1

(1.Electric Power Research Institute of Guangdong Power Grid Co., Ltd., Guangzhou 510080, China;2.AVIC Luoyang Electro-optical Equipment Research Institute, Luoyang 471009, China)

In recent years, substation inspection robot is widely used in substations, but inspection robot path planning problem is a serious problem. Inspection robot has marked task stops in topology map, different tasks require starting from the initial point and through a series of stops and then returns to the initial point, how to planning the path is a problem. First, this paper analyzes the path planning problems, second proposed a map equivalent deformation method by analyzing the topological map features, finally used the genetic algorithm to calculate the approximate optimal solution. Simulation results show the method based on genetic algorithm this paper proposed is an effective method to solve substation inspection robot path planning problem.

substation inspection robot; path planning;genetic algorithm; evolutionary algorithm; Chinese postman problem

2016-10-22；

2016-11-21。

王 銳(1988-)，男，湖北潛江市人，工學碩士，工程師，主要從事變電站機器人智能巡檢及高電壓試驗研究工作。

彭向陽(1971-)，男，湖北黃岡市人，工學碩士，教授級高級工程師，長期從事輸電線路及高電壓技術工作。

1671-4598(2017)04-0153-03DOI：10.16526/j.cnki.11-4762/tp

TP

A