面向變電站機器人巡檢路徑規劃中的算法研究

王秀麗，周 鵬，侯靜楠，王仕俊，林 霞

1.山西大學 電力工程系，太原030013

2.國網甘肅省電力公司 經濟技術研究院，蘭州730050

3.國網山西省電力公司，太原030021

目前變電站的巡查中，無人化逐漸成為一種趨勢，巡檢機器人的應用將越來越廣泛。文獻[1]中介紹了當前巡檢機器人的發展現狀，指出了當前仍然存在的問題，比如巡檢路徑的問題。文獻[2]中提出使用AMCL（Adaptive Monte Carlo Localization）算法進行定位，但分類討論的情況不夠充分。文獻[3]中提出使用A*算法，但該算法在計算過程中當存在多個最小值時不能保證路徑最優，存在局部最優問題。文獻[4]中提出改進的Dijkstra算法，該算法具有全局最優的特點，但時間復雜度高，耗時長。文獻[5]中提出改進的遺傳算法，效率提高但也存在一定問題，即精度存在偏差，路徑不一定最優。

在巡檢車或巡檢機器人巡視的路徑規劃中，可以將該問題看作是旅行商問題（Traveling Salesman Problem，TSP），目前有很多智能算法，比如動態規劃法、分支限界法、Dijkstra 算法、A*算法、蟻群算法、模擬退火算法、遺傳算法等，前兩種主要適用于小規模的TSP，后三種主要適用于大規模的TSP。

在變電站巡檢機器人巡視的路徑規劃當中主要解決三種問題：（1）全局巡檢，即從出發點到目標點（即為返回點）的正常巡視，在本文中采用一種新的算法完成；（2）多點巡檢，即固定設備巡視，采用Dijkstra 算法和遺傳算法相結合的方式使其通過規劃能順利經過必須巡視的設備；（3）單點巡檢，即突發情況巡視及應急返回，采用Dijkstra算法來完成該任務。

主要針對以上三種情況分別做了設計和仿真驗算。

1 變電站建模

在對變電站的分析中，選取具有典型代表的矩形網狀分布模型，如圖1所示。

圖1 變電站模型

根據以上思路，作如下假設：

定義一個典型的變電站Sr,c,g，設存在r行，c列設備組，每組g臺設備分別在設備中心靠近道路側及道路分支處選取點作為特征點，如圖1所示。

對于一個變電站Sr,c,g，定義特征點集：

對于所有特征點之間的道路有邊集：

E={所有道路}

定義圖Gr,c,g=(V,E),Gr,c,g可以用于表示變電站設備區的道路結構。

從變電站的布局特點不難得到，圖Gr,c,g有以下特點：

（1）Gr,c,g是無向無環的；

（2）Gr,c,g是加權的，權重反映相鄰頂點間的距離；

（3）Gr,c,g是連通的，且沒有孤立點；

（4）?v∈V,4 ≥deg(v)≥2。

同時可以發現，對于任意大小的變電站模型，均可認為是圖2最小單元的重復。

圖2 最小單元示意圖

故對某一變電站的研究可以推廣到所有的同類變電站。下文將以變電站S4,5,3為例探究變電站路徑的規劃算法，模擬地圖以某一中型變電站設備區作為模擬對象，地圖大小6 900×2 250 px，比例尺1 m=100 px。地圖共設有操作柜60 臺，分為20 組，4 行5 列分布。每臺設備周圍均有多個巡檢點。所有模擬路線圖中，巡檢車的進場位置均位于（0，0）位置。

2 全局巡檢中新哈密頓算法的提出

對于全局巡檢問題，很容易想到：巡檢機器人不重復地走完所有的特征點，就可以使巡檢路徑最短。在數學上可以表示為求取圖Gr,c,g的哈密頓回路，由離散數學的知識可以得到，目前還不存在有簡單的判定哈密頓回路存在的充要條件，故只能對此問題做如下分析：

經過圖中所有頂點一次且僅一次的回路稱為哈密頓回路，對應于圖2的哈密頓回路即為繞其所有頂點的外邊框。

再分析如圖3 所示的變電站S2,2,2，也可以很容易地找到一個哈密頓回路，如圖4所示。

圖3 變電站2模型

圖4 對應變電站2模型的哈密頓回路

可以從上看出，對于任意的Sr,c,g都存在哈密頓回路，哈密頓回路可以通過以下歸類來建立。

令起點h0=v0,j0，對于起點為h0的回路H，其中的任一點都滿足以下兩種狀況：

（1）當n=0 時有：

式中，hn為屬于回路H當中的任一節點。

（2）當n≠0 且令hn=va,b（a為當前巡視節點所處的行數，b為當前巡視節點所處的列數，且a,b均大于等于0），此時有以下幾種情況：

若0

若a>0 ∧amod 3=0 ∧bmod(g+2)=1 ∨(amod 3 ≠0 ∧bmod(g+2)=g+1)，此時有：

若(amod 3=2 ∧bmod(g+2))?{0,g+1}∨(a=3r-1 ∧bmod(g+2))=0，此時有：

若a>0 ∧amod 3=0 ∧dmod(g+2)?{0,1}，此時有：

若a=0 ∧b>0，此時有：

由上對S4,5,3進行路徑規劃，得出巡檢機器人的全局巡檢路徑如圖5 所示，巡檢總長：59 100 px=591 m，×代表起點。

圖5 全局巡檢示意圖

圖6 為全局巡檢流程圖，設定巡視起點h0等于v0,j0，定義一個變電站Sr,c,g，并將其帶入哈密頓回路公式計算，之后進行判斷，若hn=v0,j0，即可輸出全局巡檢的路徑[6-9]。

圖6 全局巡檢的流程圖

對以上新算法與幾種傳統常規方法全局巡檢的結果進行比較的結果，見表1所示。

表1 全局巡檢仿真結果比對

從以上仿真數據結果可以看出，采取的哈密頓新算法具有仿真運算時間相對較短和巡檢路徑相對較優的特點。

3 組合算法的提出

3.1 Dijkstra算法

變電站中的多點巡檢，指對固定設備的巡視，這里主要采用Dijkstra算法和遺傳算法相結合的方式使其通過規劃能順利經過必須巡視的設備。

Dijkstra算法算是基于貪心思想而來，用于單源最短路徑的求取。其原理是將起點到所有點的路徑存儲，經松弛操作后將最短距離的點作為中轉點，并將最短距離更新，直到擴展到終點為止。具體算法思想如圖7所示[10]。

圖7 Dijkstra算法原理圖

3.2 遺傳算法

遺傳算法是一種全局優化概率算法，也是一種搜索啟發式算法，是進化算法的一種。這種啟發式通常用來生成有用的解決方案來優化和搜索問題。遺傳算法的基本運算過程如圖8所示[11]。

圖8 遺傳算法運算過程

3.3 組合算法的思想

為解決運算節點過多而導致遺傳算法中的基因數量和遺傳次數增加的問題，這里提出Dijkstra 算法和遺傳算法相組合的方式，即在初始階段采用Dijkstra算法，求出每兩個目標節點之間的最小路徑，再用遺傳算法求解到達每個目標節點的先后順序。

3.4 組合算法在多點巡檢中的應用

在變電站巡檢過程中，多點巡檢是指對固定設備或重點設備的巡視，主要采用Dijkstra 算法和遺傳算法相組合的方式來應用。以變電站S4,5,3為例探究變電站路徑的規劃算法[12-13]。

（1）電量充足時的多點巡檢仿真

當對重點設備巡檢過程中，電池電量充足時，路徑規劃的流程圖如圖9所示。

圖9 電量充足時多點巡檢的算法流程圖

圖10 為電量充足時多點巡檢路線的仿真結果圖，巡視完的路徑長度：13 252 px=132.52 m。圖中×為變電站巡檢入口，圓點表示重點巡視的變電站設備。

圖10 電量充足時多點巡檢路線仿真結果圖

（2）電量不足需返回充電時的仿真結果

當對重點設備巡檢過程中，電池電量不足需要返回充電。

圖11為一個重新規劃了的多點巡檢路徑圖。圖12中，紅色正方形框代表當巡檢到此點時報警提示電量低，此時按照流程圖中的算法規劃好返回的最短路徑，紅色線代表緊急返回充電的路徑。圖13為充電完成后繼續巡檢剩余重點設備的路徑規劃圖。

圖11 多點路徑巡檢規劃圖

圖12 電量低時的返回路徑規劃圖

圖13 充電完成后繼續巡檢剩余重點設備的路徑規劃圖

所謂單點巡檢，主要指當變電站某處運行出現故障或其他緊急情況時，可通過指派巡檢機器人趕至需巡視地點。這種模式要求響應速度快，可以迅速對異常節點進行查看，讓相關人員迅速獲取異常節點的關鍵數據。當異常解除后或當工作人員認為不需要繼續進行觀察時，巡檢機器人需原路返回之前的位置點繼續執行巡檢任務。單點巡檢中主要使用了Dijkstra算法，圖14為單點巡檢時的算法流程圖，圖15為仿真結果圖，其中藍色點為需要巡檢的單臺設備，巡視結束后沿原路返回[14-15]。

圖14 單點巡檢流程圖

圖15 單點巡檢仿真結果圖

4 結束語

針對變電站的巡檢算法問題進行了研究討論，本文中設定了三種巡檢方式：全局巡檢、多點巡檢和單點巡檢。全局巡檢中，提出了一種基于哈密頓回路的新算法，以一個四行五列，且每組三臺設備的變電站（變電站可以任意設定設備數量和行列數）為例進行了仿真，結果證明該算法比常規方法的計算速度相對更快，巡檢路徑相對更短。多點巡檢和單點巡檢也分別采用相應的算法進行了仿真。本次設計中，創新之處主要體現在全局巡檢的算法選擇。

以上結果表明，針對小規模的TSP 問題，對路徑規劃的情況進行分類，可以選擇出相應的不同算法，以此 達到優化的目的，本文結果證明算法有效可行，但也存在一些問題，比如選取的變電站主要為矩形設計，如為其他形狀時，需要重新修改程序，下一步將繼續針對不同形狀的變電站路徑進行設計，并且找出新提出的算法可以適用的更多的范圍。