基于圖論的變電站巡檢機器人全局路徑規(guī)劃

張永濤，李 博，張 甲，劉 濤，豆貝貝

（國網(wǎng)河南省電力公司周口供電公司，河南 周口 466000）

0 引言

經(jīng)過多年的技術(shù)革新和換代，現(xiàn)有變電站巡檢機器人搭載可見光相機、紅外熱像儀等傳感檢測設(shè)備，可實現(xiàn)站內(nèi)設(shè)備外觀檢測、開關(guān)位置觀測、表計讀數(shù)、紅外測溫以及異常狀態(tài)告警、聲音視頻采集等功能，已經(jīng)發(fā)展成為融合視覺模式識別、導(dǎo)航及路徑規(guī)劃、無線傳輸控制及自主充電等眾多技術(shù)于一體的智能型系統(tǒng)［1］。

巡檢機器人除了用于變電站日常巡視外，還可以在高溫、冰雪、雷暴、臺風(fēng)等天氣條件下進行巡檢；在設(shè)備檢修投運后、新設(shè)備24 h 試運行期、系統(tǒng)過負荷以及特殊保供電時期，對某區(qū)域的設(shè)備進行反復(fù)巡檢；還可以實現(xiàn)遠方狀態(tài)識別、遠方異常確認、缺陷定點跟蹤等一系列功能［2］。220 kV 及以上變電站占地面積大，設(shè)備分布廣、數(shù)量多，使用巡檢機器人的優(yōu)勢更加明顯。與人工巡檢相比，機器人巡檢可以有效提高巡檢效率和覆蓋面，降低惡劣天氣下巡視的安全風(fēng)險，巡檢數(shù)據(jù)記錄全面、連續(xù)，有助于后續(xù)分析［3］。機器人巡檢是智能和無人值守巡檢技術(shù)的發(fā)展方向，具有廣闊的發(fā)展空間和應(yīng)用前景［4］。

實際應(yīng)用過程中，部分巡檢機器人的行駛路線并非為最優(yōu)路線，導(dǎo)致巡檢過程不夠高效［5］。考慮到電池續(xù)航能力和行駛速度的限制，為了提高巡檢機器人工作效率，應(yīng)該對其巡檢路線進行優(yōu)化。目前文獻中報道的優(yōu)化方法有3 類：

1）采用智能算法對巡視路線進行優(yōu)化。文獻［6］采用Hopfield 神經(jīng)網(wǎng)絡(luò)算法對巡檢機器人巡視路線進行優(yōu)化，將巡視點與網(wǎng)絡(luò)神經(jīng)元相對應(yīng)，最優(yōu)路徑與網(wǎng)絡(luò)的能量函數(shù)對應(yīng)，得到正常巡視、特殊巡視下巡檢路線優(yōu)化圖。文獻［7］將變電站巡視問題轉(zhuǎn)化為對關(guān)鍵巡視點的遍歷問題，采用蟻群算法對巡視路徑進行優(yōu)化，得到較好的可行解。文獻［8］基于遺傳算法的改進蟻群算法對巡視路線圖進行優(yōu)化，對于異常路線，采用深度優(yōu)先搜索算法，進行巡檢機器人局部路徑規(guī)劃。

2）通過相關(guān)算法獲取任意2 個巡視點之間的最短距離，并將所求距離存入解集合供下一步使用；通過相關(guān)算法（煙花算法、蟻群算法、遺傳算法、模擬退火算法等）對前期解集合中的解進行組合，得到最短巡檢路線的巡視點順序［9-10］。文獻［11］將全局最優(yōu)路徑規(guī)劃分為兩部分，分別為求解任意2 個巡視點之間的最短路徑以及求解使得總路徑最短的巡視點最優(yōu)化排列組合。將改進Dijkstra算法與模擬退火算法相結(jié)合，應(yīng)用于變電站巡檢機器人路徑規(guī)劃。文獻［12］使用Floyd 算法對每對節(jié)點的最短距離進行求解并存儲，利用遺傳算法求解得到最優(yōu)巡檢路線。

3）采用圖論中的Kruskal 算法、Prim 算法求得最小生成樹，對結(jié)果進行調(diào)整以遍歷所有節(jié)點回到原點。圖的遍歷是按照某種規(guī)則訪問圖中各頂點且僅一次的操作，即將網(wǎng)絡(luò)結(jié)構(gòu)按某種規(guī)則線性化的過程。文獻［13］以貪心算法和局部搜索算法思想為主，結(jié)合啟發(fā)式思想算法對最小生成樹的Kruskal 算法進行改進，找到最短巡檢路線；文獻［14］利用改進Prim 算法生成最小生成樹，設(shè)計遍歷算法遍歷最小生成樹，得到最短巡視路線。

上述研究主要是變電站巡檢機器人磁導(dǎo)航方式下的定點巡視路線優(yōu)化，隨著傳感器技術(shù)的發(fā)展和變電站機器人無軌化巡視的趨勢，目前變電站機器人多數(shù)采用激光定位導(dǎo)航系統(tǒng)，激光導(dǎo)航效率更高、更加智能靈活，可以做到智能避讓，維護成本低，改變路線只需要軟件重新設(shè)置，提高了被巡檢目標(biāo)的覆蓋率。針對巡檢機器人全站全巡的路線優(yōu)化問題未見相關(guān)研究。

考慮到巡檢機器人巡視路線優(yōu)化問題與圖論中“中國郵遞員問題”相似，對某變電站巡檢機器人巡視路線的拓撲結(jié)構(gòu)進行分析，構(gòu)造歐拉圖，得到最佳巡視路線圖，研究成果可為變電運維人員及生產(chǎn)廠家提供參考。

1 任務(wù)規(guī)劃流程

根據(jù)變電站內(nèi)需要巡視設(shè)備的類型和項目，設(shè)定巡檢任務(wù)點，并根據(jù)不同的巡檢任務(wù)，規(guī)劃巡檢路線，任務(wù)規(guī)劃包括點位選擇、任務(wù)設(shè)置和巡檢路徑規(guī)劃3 個部分。

1.1 點位選擇

機器人巡檢點位的設(shè)定要求多角度、全方位覆蓋變電站范圍內(nèi)所有設(shè)備，做到不漏設(shè)備、不漏點。除了通過預(yù)先設(shè)定的分類選擇巡檢點位外，還可以通過不同字段和接線圖畫面進行選擇。

1.2 任務(wù)設(shè)置

巡檢機器人任務(wù)設(shè)置要結(jié)合巡檢任務(wù)耗時和巡檢時間段合理安排。

巡檢任務(wù)耗時。單次巡檢時間不應(yīng)超過機器人的續(xù)航時間，2 個任務(wù)之間需要間隔充裕的時間進行充電。

設(shè)定巡檢時間。例行巡檢應(yīng)安排在白天進行，為提高機器人的運行可靠性，建議減少正午高溫時開展巡檢任務(wù)；應(yīng)盡量在陰天、夜間負荷高峰時開展紅外測溫，以提高數(shù)據(jù)的準(zhǔn)確性［15］。

1.3 路徑規(guī)劃

巡檢機器人接收到用戶的巡檢任務(wù)后，生成1條以充電房位置為路線起點和終點，包含各個巡視點的最優(yōu)巡檢路線。

優(yōu)化的路線可以降低機器人巡檢時間，節(jié)省機器人電力消耗，提高機器人巡檢效率。根據(jù)巡視點的數(shù)量，路徑優(yōu)化方法可分為3 類：

1）單一巡視點。主要用于缺陷定點跟蹤、應(yīng)急事故特巡和應(yīng)急輔助操作。這類問題的目標(biāo)是求變電站內(nèi)兩點間的最短距離，常見優(yōu)化方法有Dijkstra算法、Floyd 算法等。

2）多個巡視位置。此類問題即求從充電房出發(fā)經(jīng)過各個巡視點且僅一次回到原點的最短距離，比較成熟的方法有兩種，一是根據(jù)巡視點的位置采用貪婪算法求得最小生成樹，設(shè)計遍歷算法求得最佳路線；二是求解任意兩個巡視點之間的最短距離并存儲，求解使得總路徑最短的巡視點最優(yōu)化排列組合。

3）全站全巡。該問題將點的優(yōu)化問題轉(zhuǎn)化為線的優(yōu)化問題，下文將重點介紹。

2 路徑規(guī)劃實現(xiàn)

巡檢機器人在變電站內(nèi)有專用的行駛路線，假設(shè)在巡視路線上的任何位置機器人都可以轉(zhuǎn)向或倒行。

變電站巡檢機器人路徑規(guī)劃建模遵循原則為：選擇充電室作為出發(fā)點和終點；每條巡視路線至少巡視1 次；巡視路線的總路程最小。

通常，1 個220 kV 變電站大概有3 000～4 000 個巡檢點位，1 個110 kV 變電站大概有800 個巡檢點位［2］。某220 kV 變電站巡視路線如圖1 所示［4］，每條線路上分布著數(shù)量不等的巡視點。

2.1 模型建立

圖1 某變電站巡檢機器人巡視路線

變電站巡視道路構(gòu)成一個非連通圖，其拓撲結(jié)構(gòu)由5 個環(huán)形結(jié)構(gòu)和6 個樹枝形結(jié)構(gòu)組成，如圖2所示，線上的數(shù)字代表巡檢道路的長度。圖中直線代表巡視路線，節(jié)點代表路線交叉、轉(zhuǎn)折處，或者是“斷頭路”的終點。

圖2 巡視路線拓撲結(jié)構(gòu)

巡檢機器人遇到樹枝形結(jié)構(gòu)巡視路線時，最優(yōu)的方法總是先進去再退出，為了簡化計算，可以將這類分支就近收縮到相鄰節(jié)點上，此時，線路u—b 成為橋，連接上、下不同的2 個環(huán)形結(jié)構(gòu)，如圖3 所示。

2.2 模型求解

巡檢路線的優(yōu)化問題也轉(zhuǎn)化為“中國郵遞員問題”，即從一點出發(fā)，經(jīng)過所有路線，返回原點，求總路程最小的方案［16］。中國郵遞員問題的求解方法包括構(gòu)造歐拉圖和畫出歐拉環(huán)游。

圖3 巡視路線簡化結(jié)果

2.2.1 構(gòu)造歐拉圖

根據(jù)歐拉定理，如果一個連通圖要一筆畫成（即從一點出發(fā)，經(jīng)過所有的邊且僅一次，又回到原點），則圖中每一個節(jié)點出發(fā)的邊數(shù)均為偶數(shù)。能夠滿足上述要求的圖稱為歐拉圖。

尋找邊數(shù)為奇數(shù)的節(jié)點，并進行兩兩配對，增加重復(fù)邊，文獻中介紹的常見配對方案包括3 種［17-18］。方案Ⅰ是尋找距離最近的兩點進行連接，如果重復(fù)邊小于所在回路權(quán)值和的一半，將重復(fù)邊保留下來，剩下的節(jié)點繼續(xù)配對；方案Ⅱ是尋找距離最短的兩點進行配對，并去掉上述節(jié)點的關(guān)聯(lián)邊，剩余節(jié)點按照上述方法進行配對；方案Ⅲ是求解所有奇度節(jié)點的最小生成樹，然后根據(jù)規(guī)則進行調(diào)整。

配對成功與否驗證方法為：將連通圖中的重復(fù)邊權(quán)值求和，如果小于總權(quán)值的一半則為可行解；如果連通圖中每個閉合圈重復(fù)邊的權(quán)值都小于該閉合圈總權(quán)值的一半，則為最優(yōu)解。本文采用方案Ⅰ進行求解，方案Ⅱ、Ⅲ主要適用于奇度節(jié)點數(shù)量較多的情形，且存在一定的局限性。

對圖3（a）進行分析，w、t 點的邊數(shù)為3，兩者需要配對，由于w—x—t 路線和大于w—s—t 路線，w、t兩點通過w—s—t進行連接，如圖4（a）所示，配對后圖中各點的邊數(shù)均為偶數(shù)，重復(fù)路線和約占整個回路的22%，滿足要求。

對圖3（b）進行分析，b、f、g、l 的邊數(shù)均為奇數(shù)，遵循重復(fù)邊最小原則，把奇數(shù)點的邊數(shù)改為偶數(shù)。其中，g、l 兩點配對，經(jīng)過g—h—l 路線權(quán)值最小，成功配對；同理，f、b 兩點通過f—a—b 進行配對，如圖4（b）所示，重復(fù)路線權(quán)值和約占整個回路的28%，經(jīng)驗證上述重復(fù)邊為最優(yōu)解。

2.2.2 畫出歐拉環(huán)游

給定一個歐拉圖，如果某條路線可以經(jīng)過所有的邊僅一次，則稱該回路為歐拉環(huán)游。通常采用Fleury 算法進行求解，設(shè)G 為一無向歐拉圖，按照“除非別無選擇，否則不走回頭路，不過獨木橋”的原則，求其歐拉回路的步驟為：

1）v 代表點，e 代表線，任取G 中一頂點v0，令P0=v0；

2）假設(shè)沿Pi=v0e1v1e2v2…eivi走到頂點vi，按下述方法從E（G）-｛e1，e2，…，ei｝中選ei+1：

a）ei+1與vi相關(guān)聯(lián)；

b）除非無別的邊可供選擇，否則ei+1不應(yīng)該是Gi=G-｛e1，e2，…，ei｝中的橋。

3）當(dāng)2）不能再進行時算法停止。

求得的歐拉回路如圖4 所示，圖中各節(jié)點排列順 序 為u—z—y—w—s—t—x—w—s—u 與a—f—e—i—j—k—l—h—g—h—l—m—c—b—g—f—a—b—a，各個連通圖的歐拉回路不止一條。

圖4 路徑優(yōu)化結(jié)果

2.2.3 優(yōu)化結(jié)果分析

變電站在規(guī)劃階段應(yīng)把巡檢機器人巡檢工作考慮在內(nèi)，設(shè)備的選擇與安裝應(yīng)減少巡視盲區(qū)，安措圍欄樁的設(shè)置應(yīng)不影響非檢修間隔的巡檢工作，巡檢路線盡量采用迂回方式，減少斷頭路，以提高機器人的巡檢效率。對原巡檢道路進行改造，采用奇偶點圖上作業(yè)法對度為奇數(shù)的節(jié)點進行配對，新的拓撲結(jié)構(gòu)如圖5 所示，線上的數(shù)字代表新鋪設(shè)道路的長度。

圖5 巡檢道路改造后的拓撲結(jié)構(gòu)

巡檢道路改造前，巡檢機器人巡視路線為a—f—e—d—e—i—n—i—j—o—j—k—p—k—l—m—c—b—g—h—l—h—g—f—g—b—r—q—r—u—v—u—z—y—w—s—t—x—w—x—t—u—r—b—a，路線總長度430 m。對斷頭路進行改造后，巡視路線為a—d—e—f—e—i—j—i—n—o—j—k—p—k—l—h—g—h—l—m—c—b—g—f—a—q—r—q—s—w—s—t—x—w—y—z—u—t—u—v—u—r—b—a，路線總長度384 m，與優(yōu)化前減少10.7%，證明了算法的有效性。

2.3 多巡檢機器人協(xié)同作業(yè)

多個巡檢機器人配合作業(yè)，要結(jié)合設(shè)備區(qū)的位置、巡檢道路的設(shè)置，合理選擇充電房的位置，以提高巡視效率。按照工作范圍進行分區(qū)，分區(qū)方法為［19］：

1）按照線路分割。把一個作業(yè)區(qū)分成若干段邊不重復(fù)的子線路，每一段線路由一個巡檢機器人進行巡視，線路分割如圖6 所示。首先，從充電房到子線路的起點，將該路線上的設(shè)備巡視完成后到達終點，最后從終點返回充電房。從充電房到達巡視路線的過程中，巡檢機器人不進行巡視任務(wù)。

2）按照回路分割。把回路切割成若干段邊不重復(fù)的子回路，將子回路距離充電房最近的點與充電房進行連接，如圖7 所示，該方案適合回路較多且界限清晰的情形。模型中線路u—b 連接兩個連通圖，適用于回路分割。

圖6 線路分割

圖7 回路分割

4 結(jié)語

通過對某220 kV 變電站巡檢機器人巡視路線的拓撲結(jié)構(gòu)進行改造，運用奇偶點圖上作業(yè)法，得到最佳巡檢路線。研究成果可用于變電站內(nèi)設(shè)備檢修時巡檢路線的規(guī)劃、新建變電站巡檢道路的設(shè)計、變電站舊巡檢道路的改造等。當(dāng)變電站內(nèi)“田形”路線較多時，奇數(shù)節(jié)點的配對以及配對后的驗證問題需要進一步研究。