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

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

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

2.國網(wǎng)甘肅省電力公司 經(jīng)濟技術(shù)研究院，蘭州730050

3.國網(wǎng)山西省電力公司，太原030021

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

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

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

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

1 變電站建模

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

圖1 變電站模型

根據(jù)以上思路，作如下假設(shè)：

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

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

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

E={所有道路}

定義圖Gr,c,g=(V,E),Gr,c,g可以用于表示變電站設(shè)備區(qū)的道路結(jié)構(gòu)。

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

（1）Gr,c,g是無向無環(huán)的；

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

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

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

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

圖2 最小單元示意圖

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

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

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

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

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

圖3 變電站2模型

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

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

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

（1）當n=0 時有：

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

（2）當n≠0 且令hn=va,b（a為當前巡視節(jié)點所處的行數(shù)，b為當前巡視節(jié)點所處的列數(shù)，且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進行路徑規(guī)劃，得出巡檢機器人的全局巡檢路徑如圖5 所示，巡檢總長：59 100 px=591 m，×代表起點。

圖5 全局巡檢示意圖

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

圖6 全局巡檢的流程圖

對以上新算法與幾種傳統(tǒng)常規(guī)方法全局巡檢的結(jié)果進行比較的結(jié)果，見表1所示。

表1 全局巡檢仿真結(jié)果比對

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

3 組合算法的提出

3.1 Dijkstra算法

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

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

圖7 Dijkstra算法原理圖

3.2 遺傳算法

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

圖8 遺傳算法運算過程

3.3 組合算法的思想

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

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

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

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

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

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

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

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

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

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

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

圖11 多點路徑巡檢規(guī)劃圖

圖12 電量低時的返回路徑規(guī)劃圖

圖13 充電完成后繼續(xù)巡檢剩余重點設(shè)備的路徑規(guī)劃圖

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

圖14 單點巡檢流程圖

圖15 單點巡檢仿真結(jié)果圖

4 結(jié)束語

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

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