基于改進Fleury算法的無人機巡線路徑規(guī)劃

束慶霏，蔡佳澄，王思凡，肖美岑，何楊陽，陳宇晨

（國網(wǎng)江蘇省電力有限公司張家港供電公司，江蘇 張家港 215600）

0 引言

近年來，在國家數(shù)字新基建、能源互聯(lián)網(wǎng)等戰(zhàn)略需求驅(qū)動下，無人機業(yè)務迎來跨越式的發(fā)展。其中，無人機智能巡線是重點項目。張家港市電網(wǎng)目前共有輸電線路1 711 km，配電線路6 473 km，全社會用電量、工業(yè)電量均名列全省乃至全國前茅。面對如此龐大的體量，無人機自主巡線的必要性得到了大大提高［1-4］。無人機巡線的關鍵技術有很多，如：超低空飛行、超視距巡檢、自主避障、路徑規(guī)劃、遠程自主精準降落技術、抗電磁干擾能力、數(shù)據(jù)安全策略等［5-9］。本文主要研究無人機巡線路徑規(guī)劃問題。

當前國內(nèi)外學者多用啟發(fā)式算法進行路徑規(guī)劃。啟發(fā)式算法是一種基于直觀或經(jīng)驗的局部優(yōu)化算法ADDIN，由大自然的運行規(guī)律或者從具體問題的經(jīng)驗和規(guī)則中總結而出。在無人機路徑規(guī)劃中，啟發(fā)式算法通過計算當前位置到目標點的代價值來進行路徑選擇，當總代價全局最小時，可認為當前路徑為全局最優(yōu)路徑。常用的啟發(fā)式算法有模擬退火算法、虛擬力法、A*算法、勢場法、遺傳算法等。李游等［10］綜合利用最短距離算法，動態(tài)規(guī)劃算法和A*算法，提出了一種智能航線算法模型，可實現(xiàn)變電站復雜條件下的航線規(guī)劃。Linhui Cheng［11］等建立了多基地、可充電續(xù)航多無人機道路巡邏任務分配模型，提出了一種time-priority immune clonal selection 算法，得到最優(yōu)任務點序列，并采用時間優(yōu)先法對任務點序列進行劃分。實驗結果表明，與粒子群優(yōu)化算法和改進的動態(tài)規(guī)劃蟻群算法相比，該算法得到的巡線時間大大減少。崔敬魁［12］利用遺傳算法和蟻群算法尋得符合條件的最優(yōu)巡線路徑。李成雷等［13］基于RRT-connect（快速搜索隨機樹）算法設計了無人機飛行最優(yōu)路徑，經(jīng)驗證，路徑長度接近理論最優(yōu)值。

除了啟發(fā)式路徑規(guī)劃，也有其他方法用于無人機的路徑規(guī)劃。趙甜甜等［14］利用百度導航設計了自動巡航機器人。施孟佶等［15］研究了雙無人機協(xié)同巡檢方案。韋立富等［16］基于三維激光點云數(shù)據(jù)，構建模型，生成航線，并評估高危區(qū)，設置禁飛區(qū)，最終生成可自動往返的飛行路線。Hu等［17］采用北斗導航系統(tǒng)為無人機巡線提供路徑規(guī)劃。曾懿輝等［18］首先通過人工巡檢，記錄關鍵軌跡的經(jīng)緯坐標和無人機飛行俯仰角，當自主巡線時，便可以遵照預定的軌跡和飛行俯仰角進行航拍。陳洪亮等［19］采用基于關鍵坐標點的路徑規(guī)劃算法對配電網(wǎng)線路進行規(guī)劃，確保了無人機巡線的高效性和安全性。

上述研究工作大多因地制宜，研究了當?shù)仉娋W(wǎng)的無人機巡線路徑規(guī)劃，很多并沒有結合實際的線路坐標。本文基于張家港市電網(wǎng)典型線路的桿塔經(jīng)緯坐標，根據(jù)圖論知識，結合中國郵遞員問題的研究方法，采用改進的Fleury 算法進行路徑規(guī)劃。

1 研究方法

本文基于圖論和中國郵遞員問題的研究方法，對張家港市電網(wǎng)的典型輸配電線路進行無人機巡線路徑規(guī)劃。

1.1 數(shù)據(jù)處理

由于桿塔坐標具有保密性，本文征求到8條典型線路的桿塔坐標用于研究。數(shù)據(jù)為Excel 形式，包含了桿塔名稱、桿塔經(jīng)緯坐標等信息，可利用python 語言的pandas 庫讀取Excel，并通過編程得到線路的平面分布圖和線路長度。

桿塔線路分為主線和支線，某些支線又會分出新的支線，所以不能按順序?qū)⑺械狞c連接組成線路。本文采用矩陣理論，設gps是初始值為n×n的零矩陣，n為此線路的桿塔數(shù)量。兩次遍歷所有桿塔，若桿塔i、j間存在線路，則記gps（i，j）=1。張家港市輸配電線路的桿塔數(shù)量大多在100～200，計算量不是很龐大，大概幾秒就能遍歷結束。

識別桿塔間是否存在線路的方法如下：太字甲線35-1-14-1-3 號是桿塔編號樣例，其中，太字甲線為線路名稱，“35”為主線第35 號桿塔，“1-14”為由主線35號桿塔分支出來的第一條支線的第14 號桿塔，“1-3”為由支線14 號桿塔分支出來的第一條支線的3號桿塔。相鄰編號的桿塔在地理位置上也是相鄰的，支線的編號包含了分支節(jié)點編號，因此可通過正則表達式識別出是否存在線路的相鄰桿塔。

同樣，設置n×n的初始零矩陣D，遍歷兩次桿塔坐標，記D（i，j）=Ds，Ds為兩桿塔之間的距離。已知兩點的經(jīng)緯坐標，求兩點之間的距離，計算方法如下。

假設地球是一個完美的球體，半徑為6 371.004 km，記為R。若以0°經(jīng)線為基準，兩點的經(jīng)緯坐標分別為（X1，Y1）和（X2，Y2），則可通過地球表面任意兩點的經(jīng)緯度計算出兩點的地表距離Ds（忽略前地球表面地形帶來的誤差）。張家港市地處北緯31°43′12″—32°02′，東經(jīng)120°21′57″—120°52′，可用式（1）、式（2）計算。

式中：π為圓周率。

1.2 模型建立

1.2.1 建模目標

本文的模型旨在建立一套算法流程，工作人員從PMS3.0系統(tǒng)導出桿塔坐標信息，放入模型后自動運行，最后導出近似最優(yōu)的巡線路徑。算法只能得到近似最優(yōu)路徑，因為實際最優(yōu)路徑需遍歷所有情況，計算機算力達不到。而得到近似最優(yōu)耗時較短，適用于所有的簡單線路和復雜線路，具有較好的應用價值。

1.2.2 算法理論

無人機巡線需遍歷一條線路的主線和所有支線，屬于行遍性問題。典型的行遍性問題有中國郵遞員問題：郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，希望選擇一條行程最短的路線。解決行遍性問題，需參考圖論里的歐拉圖和Fleury算法。

歐拉圖：G是一個由點集和邊集構成的無向圖，經(jīng)過G的每條邊的跡叫做G的Euler跡；閉的Euler 跡叫做Euler 回路；含Euler 回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點出發(fā)每邊恰好通過一次最后回到出發(fā)點的圖，即不重復地行遍所有的邊再回到出發(fā)點。

根據(jù)Fleury算法可得：

1）?v0∈V(G)，令W0=v0。

2）假設跡Wi=v0e1v1…eivi已經(jīng)選定，則按下述方法從E-{e1，…，ei}中選取邊ei+1。

ei+1和vi相關聯(lián)。

除非沒有別的邊可選擇，否則ei+1不是Gi=G-{e1，…，ei}的割邊。所謂割邊是一條刪除后使連通圖不再連通的邊。

3）當?shù)?步不能再執(zhí)行時，算法停止。

本文研究的無人機巡線問題與中國郵遞員問題相近，但有以下不同點：郵遞員需回到起點，而無人機可以使用移動車載平臺，將車載平臺直接停在巡線路徑終點；郵遞員的投遞路徑具有約束性，必須是兩個城鎮(zhèn)之間存在道路才能同行，無人機可在任意兩個桿塔之間飛行。因此，本文對Fleury 算法進行改進，添加隨機選擇的元素，并采用python 編程，得到近似最優(yōu)的無人機巡線路徑。

1.2.3 模型假設

1）一架無人機每次只巡一條線路，不考慮多條線路一起巡視的情況。

2）無人機續(xù)航里程大于整個巡線里程。張家港市大多數(shù)線路的長度小于15 km，滿足無人機的續(xù)航里程（見表1），個別線路較長（最長達20.10 km），可采用移動機載平臺，充電后再繼續(xù)巡航，或采用人工巡線和無人機巡線結合的方式。

3）整個飛行過程暢通無阻，不考慮線路通道周圍的阻礙和兩桿塔直線空間內(nèi)的阻礙。張家港市全境地勢平坦，無山嶺阻礙無人機飛行，線路通道的障礙主要有樹木障礙、交叉線路、路燈障礙等，無人機的感知系統(tǒng)可實現(xiàn)自主避障。

4）飛行環(huán)境是無風環(huán)境，無人機勻速飛行。

5）無人機感知系統(tǒng)（見表1）正常，可始終保持跟蹤導線飛行。

6）無人機定位系統(tǒng)（見表1）正常，可準確定位目標桿塔。

張家港在役無人機的部分參數(shù)見表1，部分缺失數(shù)據(jù)廠家未提供。

表1 張家港在役無人機參數(shù)Table 1 Parameters of in-service UAV in Zhangjiagang

1.2.4 算法流程

1）根據(jù)桿塔經(jīng)緯坐標得到線路分布的平面二維圖。

2）設置n×n的初始零矩陣gps，遍歷所有桿塔，若兩桿塔i、j之間存在線路，則標記gps（i，j）=1。

3）設置n×n的初始零矩陣D，遍歷所有桿塔，計算兩桿塔i、j之間的地表距離Ds，令D（i，j）=Ds。

4）遍歷所有桿塔得到線路的起點和終點。

5）設置空白路徑route，線路的起點（或終點）作為路徑起點，并設置當前桿塔位置state，state初始值為路徑起點，以state 為基準，遍歷所有的桿塔。

若遍歷到桿塔i與桿塔state之間存在線路，即gps（state，i）=1，則將桿塔i加入路徑route，對于存在支線的線路節(jié)點，設置隨機選擇，并將選擇支線的概率設置大一點，選擇支線的概率是選擇主線概率的2～3 倍，因為對于大部分線路，優(yōu)先巡完支線再回到主線繼續(xù)巡線是一個比較好的選擇。同時將gps（state，i）和gps（i，state）更新為0，將當前桿塔位置state更新為i。

若遍歷完所有桿塔，不存在與桿塔state 相連的桿塔，則搜尋state 附近的桿塔，該桿塔需滿足條件：有其他桿塔與之相連。搜尋1～3 個與桿塔state 距離最近的桿塔，并隨機選擇其中一個桿塔i，加入路徑route，同時將gps（state，i）和gps（i，state）更新為0，將當前桿塔位置state更新為i。

6）重復步驟5 的運算，直至gps的所有元素和為0，即無人機巡完所有線路。

7）計算路徑的里程。

8）重復步驟5、6、7，迭代更新無人機巡線里程最短的路徑，將其作為近似最優(yōu)巡線路徑，并導出每一步路徑規(guī)劃。

2 結果分析

本節(jié)選取張家港市電網(wǎng)8條典型線路進行路徑規(guī)劃研究。其中簡單線路3條，復雜線路5條。

2.1 簡單線路分析

簡單線路圖的特點是支路較少，支線較短，能夠明顯看出主線位置，桿塔數(shù)量一般不超過100，見表2。

表2 簡單線路Table 2 Simple lines

對于大德線，如圖1所示，在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為4.179 km，比實際線路長度3.814 km 多出9.5%。從路徑規(guī)劃來看，大多是從主線分支節(jié)點先巡支線，再回到主線。也有從支線直接飛往另一支線，再回到主線，如：大德線51-1-0-1-1 號→大德線53-1-1 號→大德線53號。

圖1 大德線線路示意圖Fig.1 Diagram of Dade line

對于攀華線（見圖2），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為6.497 km，比實際線路長度4.944 km 多出31.4%。從路徑規(guī)劃來看，從主線分支節(jié)點先巡支線，再回到主線。攀華線有一條較長的支線，若將線路的終端（右上角）作為巡線起點，近似最優(yōu)路徑里程為6.538 km，比實際線路長度多出32.2%。主線巡線順序不連續(xù)，巡完較長的支線后，無人機飛至線路首端繼續(xù)巡線，如：攀華線6-1-7號→攀華線1號。巡完主線，再飛往與之不相鄰的支線，如：攀華線6號→攀華線21-1-21-1-1 號。盡管兩種巡線路徑差異很大，但是巡線里程差不多，一般將線路首端作為巡線起點即可。

圖2 攀華線線路示意圖Fig.2 Diagram of Panhua line

對于永旺線（見圖3），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為2.68 km，比實際線路長度2.215 km 多出20.9%。從路徑規(guī)劃來看，大多是從主線分支節(jié)點先巡支線，再回到主線。永旺線近似一個閉環(huán)，可巡完所有主線再巡首端的支線，如：永旺線31號→永旺線2號→永旺線2-1-1號。

圖3 永旺線線路示意圖Fig.3 Diagram of Yongwang line

綜上，對于簡單線路的路徑選擇，在支線端點隨機選擇時，直接選擇最近的桿塔運行結果較為理想，路徑大多沿著按主線順序巡線，產(chǎn)生分歧主要在于不同的支線巡線方法。有時從某一支線端直接飛往另一支線，路徑較優(yōu)；大多數(shù)情況是從支線端直接飛回主線繼續(xù)巡線，路徑較優(yōu)。簡單線路的桿塔數(shù)量、實際長度、計算長度及其誤差見表2。

2.2 復雜線路分析

復雜線路的特點是支線較多，支線長短不一，有的無法明顯識別出主線位置，如萬新線、太字甲線；有的支線過長，如躍進線、萬江甲線、王巷甲線。復雜線路的桿塔數(shù)量一般超過100，有的（如太字甲線）高達200多，見表3。

表3 復雜線路Table 3 Complex lines

對于萬新線（見圖4），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為7.45 km，比實際線路長度5.731 km 多29.9%。由于萬新線支線部分較為復雜，近似成H 狀，支線和主線里程差不多，所以路徑選擇時，可能會跳過某一段主線，主線的巡線順序不連續(xù)，如：萬新線9-1-15號→萬新線26號，萬新線41號→萬新線37號。

圖4 萬新線線路示意圖Fig.4 Diagram of Wanxin line

對于躍進線（見圖5），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為10.083 km，比實際線路長度7.469 km 多34.9%。從路徑選擇來看，主線的巡線順序基本連續(xù)，無人機巡完2條較長的支線再回到主線。近似最優(yōu)的路徑也有一定概率存在重復巡線現(xiàn)象，如：躍進線4號→躍進線3號→躍進線4號→躍進線5號，由于地理位置限制，這是不可避免的。

圖5 躍進線線路示意圖Fig.5 Diagram of Yuejin line

對于萬江甲線（見圖6），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為8.632 km，比實際線路長度6.851 km 多25.9%。萬江甲線存在3 條較長的支線，巡線過程中，無人機直接從支線的一端飛往另一條支線，如：萬江甲線49-1-9-1-1號→萬江甲線70-1-12-1-1 號，無人機巡完2 條支線后再繼續(xù)巡主線。因此，主線巡線順序也是不連續(xù)的。

圖6 萬江甲線線路示意圖Fig.6 Diagram of Wanjiang A-line

對于王巷甲線（見圖7），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為18.613 km，比實際線路長度14.883 km 多25%。王巷甲線線路分布非常不規(guī)則，無人機巡線不完全按照主線順序飛行，有時會從某一支線端部直接飛往另一支線，如：王巷甲線64-1-2-1-7 號→王巷甲線56-1-5 號；甚至從主線直接飛往與之不相連的支線，如：王巷甲線71 號→王巷甲線64-1-4 號，王巷甲線84 號→王巷甲線78-1-2 號。主線巡線順序也不連續(xù)，如：王巷甲線64號→王巷甲線67號。

圖7 王巷甲線線路示意圖Fig.7 Diagram of Wangxiang A-line

對于太字甲線（見圖8），在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想，近似最優(yōu)路徑里程為17.545 km，比實際線路長度13.367 km 多31.2%。太字甲線線路分布也非常復雜，無人機飛行規(guī)律與王巷甲線類似，可能從某一支線端直接飛往另一支線端，如：太字甲線54-2-1 號→太字甲線35-2-1 號；可能從主線飛往與之不相連的支線，如：太字甲線24 號→太字甲線35-1-14-1-3 號；可能從支線飛往與之不相連的主線，如：太字甲線66-1-5號→太字甲線70號。

圖8 太字甲線線路示意圖Fig.8 Diagram of Taizi A-line

綜上，復雜線路的路徑選擇中，在支線端點隨機選擇時，直接選擇最近的桿塔，運行結果較為理想。復雜線路桿塔數(shù)量更多，節(jié)點也更多，需經(jīng)過更多次的迭代，程序運行時間更長。復雜線路的路徑規(guī)劃沒有明顯規(guī)律，一切隨機應變，程序的運行結果已是較好的選擇。復雜線路的桿塔數(shù)量、實際長度、計算長度及其誤差見表3。

2.3 算法評價

以往的研究大多將無人機巡線路徑規(guī)劃當作旅行商問題，即無人機遍歷每個目標點的最短路徑［11-12，20-22］，并未考慮到目標點之間是否存在線路。因此，可遍歷所有的桿塔，但不能完全覆蓋桿塔之間的線路。

本文基于中國郵遞員問題的研究方法，即無人機遍歷每個目標點和相應目標點間線路的最短路徑。根據(jù)本文模型，無人機可近似最優(yōu)地巡視完所有的桿塔和線路。由于線路分布并非歐拉圖，多余巡線不可避免，本方法的誤差為10%～30%，已較為理想。

3 結語

本文針對張家港市電網(wǎng)的典型線路進行了無人機巡線路徑規(guī)劃?；趫D論知識，結合中國郵遞員問題的研究方法，采用改進的Fleury 算法，添加隨機元素（主線分支節(jié)點隨機，支線端點隨機），得到近似最優(yōu)的無人機巡線路徑。根據(jù)程序運行結果得出以下結論。

1）本文的算法程序在導入由PMS3.0系統(tǒng)獲取的桿塔坐標信息后，可很快得到近似最優(yōu)路徑，簡單便捷，實用性強，容錯率高，適用于所有的簡單線路和復雜線路。經(jīng)驗證，程序運行出的巡線里程一般比實際里程多出10%～30%，效果較為理想。

2）對于簡單線路，支線較少且長度較短，巡線路徑一般按照主線桿塔順序，遇到主線分支節(jié)點，一般先巡完支線再回到主線繼續(xù)巡線，偶爾會從某一支線飛往另一支線。

3）對于復雜線路，支線較多且長短不一，巡線不完全按照主線桿塔順序，可能出現(xiàn)以下狀況：從支線端直接飛往另一支線端，從主線飛往不相鄰的支線，從支線飛往不相鄰的主線。

若線路過長，則需要兩臺甚至更多的無人機來完整地巡完一條線路，本文的程序無法自動分割線路供多個無人機巡線。對此，可參照多郵遞員問題：郵局有k（k≥2）位投遞員，同時投遞信件，全城街道都要投遞，完成任務返回郵局，如何分配投遞路線，使得完成投遞任務的時間最早，這將是下一步研究工作的重點。