考慮無人機(jī)桿塔巡視避障的兩階段路徑優(yōu)化

(武漢大學(xué) 電氣與自動化學(xué)院，武漢 430072)

0 引言

隨著無人機(jī)在輸電線路桿塔精細(xì)化巡視中的應(yīng)用，為克服傳統(tǒng)由作業(yè)人員將無人機(jī)帶至待巡檢桿塔放飛進(jìn)行巡檢存在的不足，提高巡檢流程自動化程度，節(jié)省人力投入，全自動無人機(jī)巡視已成為該領(lǐng)域的發(fā)展重點(diǎn)。如何在巡檢過程中，使續(xù)航里程固定的無人機(jī)在續(xù)航里程內(nèi)盡可能多地巡視輸電線路桿塔，優(yōu)化桿塔巡視路徑，提高巡視工作效率是值得研究的問題。

文獻(xiàn)[1]提出了用遺傳算法對于巡視路徑中障礙規(guī)避的路徑優(yōu)化，文獻(xiàn)[2]提出在三維平面建立柱狀障礙空間，提出結(jié)合支持向量回歸算法和A*算法原理的避障路徑規(guī)劃算法，但是無人機(jī)的全自動精細(xì)化巡視通常需要經(jīng)過多個線路桿塔，在避障算法基礎(chǔ)上還需要完善巡視路徑的規(guī)劃。對于無人機(jī)巡視桿塔的次序，文獻(xiàn)[3]基于窮舉法和人工比較研究了確定桿塔最優(yōu)巡檢路徑的方法，但是該方法沒有考慮無人機(jī)如何在巡視過程中避開桿塔間障礙的路徑優(yōu)化。文獻(xiàn)[4-5]綜述了無人機(jī)在輸電線路巡檢中的應(yīng)用。文獻(xiàn)[6]利用人工勢場法提出了面向無人機(jī)巡視避障和擴(kuò)大巡視面積的規(guī)劃方法，但該方法需要無人機(jī)搭載雷達(dá)的應(yīng)用場景，并且規(guī)劃目標(biāo)是巡視面積擴(kuò)大，而不是巡視路徑優(yōu)化，與電力系統(tǒng)無人機(jī)的全自動精細(xì)化巡視需求還存在差異。文獻(xiàn)[7-13]關(guān)注的是沒有特定場景的無人機(jī)路徑規(guī)劃和協(xié)同任務(wù)問題，可以為無人機(jī)巡檢桿塔路徑規(guī)劃提供啟發(fā)。基于此，本文圍繞無人機(jī)全自動精細(xì)化巡視輸電線路的桿塔巡視路徑和桿塔間避障路徑的雙重優(yōu)化問題開展研究。

通過將無人機(jī)巡視桿塔的次序優(yōu)化視為旅行商問題(TSP)，利用地圖上桿塔坐標(biāo)位置，分別用動態(tài)規(guī)劃算法和模擬退火算法優(yōu)化經(jīng)過不同拍攝點(diǎn)的次序，比較兩種算法的效果。傳統(tǒng)的求解TSP問題的方法是啟發(fā)式算法(比如模擬退火算法)，在本文中提出將確定性算法即動態(tài)規(guī)劃算法引入無人機(jī)路徑的規(guī)劃之中，論證了動態(tài)規(guī)劃算法相對于啟發(fā)式算法的優(yōu)越之處。對于巡視的桿塔間避障路徑優(yōu)化，通過使無人機(jī)與地面保持確定的相對高度，把地圖上超過無人機(jī)飛行高度的物體作為障礙點(diǎn)標(biāo)注，將三維路徑規(guī)劃轉(zhuǎn)化為二維路徑規(guī)劃，并用人工勢場法進(jìn)行避障最優(yōu)路徑求解。在此基礎(chǔ)上，基于兩種路徑優(yōu)化的結(jié)合，提出了面向無人機(jī)全自動化精細(xì)化巡視輸電線路桿塔的路徑規(guī)劃方法。最后，通過仿真驗(yàn)證了所提巡視路徑規(guī)劃算法的有效性。

1 無人機(jī)基于雙調(diào)巡航線路的路徑優(yōu)化

無人機(jī)經(jīng)過所有的拍攝點(diǎn)并回到起點(diǎn)，可以等價(jià)為旅行商問題(Traveling Salesman Problem, TSP)，屬于NP完全問題。由于該問題在多項(xiàng)式時間難以求得全局最優(yōu)解，因此通常采用具有隨機(jī)性的啟發(fā)式算法求解。這種求解雖然存在通用性強(qiáng)，在多數(shù)情況下都能在有限時間內(nèi)搜索得到巡航路線的較短路徑的特點(diǎn)，但求解結(jié)果對啟發(fā)式算法相關(guān)參數(shù)設(shè)置具有敏感性，并且求解TSP的時間復(fù)雜度較大。針對利用啟發(fā)式算法求解無人機(jī)巡視路徑TSP的不足，通過在無人機(jī)巡航路徑中，增加要求無人機(jī)沿單方向離開，再沿單方向返回的約束，將原來路徑優(yōu)化的TSP轉(zhuǎn)化為具有雙調(diào)歐幾里得特性的TSP，進(jìn)而將包含大規(guī)模巡視桿塔的路徑優(yōu)化轉(zhuǎn)化為多個僅包含兩個巡視桿塔間最優(yōu)路徑優(yōu)化的子問題，從而在利用動態(tài)規(guī)劃法快速求解兩個桿塔間的最優(yōu)巡視路徑的基礎(chǔ)上，基于各子問題最優(yōu)解構(gòu)造初始優(yōu)化問題的最優(yōu)解。

用點(diǎn)集V={v1,v2,…,vn}表示無人機(jī)需要巡視的各桿塔，dij表示桿塔v1和v2間的距離。同時利用0-1指示變量xij表示優(yōu)化的巡視路徑是否經(jīng)過vi和vj兩個桿塔間，xij=1表示經(jīng)過，xij=0表示不經(jīng)過。在二維平面上建立直角坐標(biāo)系，把路徑上各桿塔按橫坐標(biāo)從小到大的順序排列，并要求無人機(jī)按圖1所示路徑優(yōu)化方法，先按橫坐標(biāo)單調(diào)遞增的路徑前進(jìn)，再按橫坐標(biāo)單調(diào)遞減的路徑返回出發(fā)點(diǎn)。

圖1 無人機(jī)基于雙調(diào)歐幾里得TSP的巡視路徑優(yōu)化原理

依據(jù)上述雙調(diào)歐幾里得TSP的巡視路徑優(yōu)化方法，可建立如下優(yōu)化數(shù)學(xué)模型。

(1)

式中，第一個等式約束保證了無人機(jī)離開一個頂點(diǎn)剛好一次，第二個等式約束保證了無人機(jī)到達(dá)一個頂點(diǎn)剛好一次，第三個不等式約束保證了路徑中沒有子回路。第四個約束條件為指示變量，用以表明無人機(jī)是否經(jīng)過兩點(diǎn)間路徑，第五個不等式約束條件用以規(guī)定無人機(jī)在兩段路徑上單向運(yùn)動。

由于原TSP優(yōu)化解的解空間會隨著巡視桿塔數(shù)量的增加呈指數(shù)規(guī)律增大，并且該整數(shù)規(guī)劃問題具有變量維數(shù)多，無法用分支定界法等常用的求解整數(shù)規(guī)劃問題的求解器求解的特點(diǎn)。因此將TSP轉(zhuǎn)化為式(1)所示的雙調(diào)歐幾里得TSP后，其優(yōu)化求解具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即覆蓋一個點(diǎn)集的最短路徑是覆蓋其子集的最短路徑的延伸，原問題的最優(yōu)解包含其子問題的最優(yōu)解?；诖?，可利用下述自底向上的動態(tài)規(guī)劃求解方法在多項(xiàng)式時間內(nèi)找到最優(yōu)解。

定義圖1中i點(diǎn)到j(luò)點(diǎn)的雙調(diào)路徑PATHij為從Pi從右往左到P1(最左邊的點(diǎn))，再從P1從左往右到PJ的最短路徑。該動態(tài)規(guī)劃問題的子問題即為求解任意兩點(diǎn)間最短雙調(diào)路徑PATHij。當(dāng)i和j分別為1，2時最短雙調(diào)路徑明顯為兩點(diǎn)間直接路徑。在此基礎(chǔ)上從左往右依次把所有巡視桿塔加入到路徑中，按照上述原則對加入的桿塔繼續(xù)求最短的雙調(diào)路徑，并在輔助矩陣中保存子問題的最優(yōu)解。在求解PATHmn時，需利用PATHij(i

構(gòu)造解的規(guī)則為:

如果j=i:

PATHij=min{PATHi,1+di,1,PATHi,2+di,2,...,PATHi,i-1+di,i-1}

如果j=i-1:

PATHij=min{PATHi-1,1+di,1,PATHi-1,2+di,2,...,PATHi-2,i-1+di,i-2}

如果j

PATHij=PATHi-1,j+di-1,i

2 無人機(jī)桿塔巡視路徑的避障優(yōu)化

通常在優(yōu)化的無人機(jī)巡視路徑上會存在已知和未知的障礙物，并且因?yàn)槲粗系K物的坐標(biāo)和體積不能事先確定，所以對這類障礙物的避讓，需要通過增設(shè)無人機(jī)的光學(xué)或聲學(xué)預(yù)警傳感器，由無人機(jī)控制系統(tǒng)做出實(shí)時避障操作。本文考慮的是兩個桿塔間優(yōu)化巡視路徑上存在諸如樹木等自然或人為已知障礙物，因此需要在優(yōu)化無人機(jī)巡視路徑的基礎(chǔ)上，進(jìn)一步優(yōu)化無人機(jī)在無人操縱的情況下自動避開路徑中已知障礙物并到達(dá)目標(biāo)桿塔的巡視路徑，以提高無人機(jī)巡線效率的安全高效性。

2.1 避障的優(yōu)化數(shù)學(xué)模型

用坐標(biāo)點(diǎn)集{P1(x1,y1),P2(x2,y2),…,Pn(xN,yN)}表示優(yōu)化的無人機(jī)巡視路徑中相鄰兩個桿塔之間的直線飛行路徑，則路徑上相鄰兩個坐標(biāo)點(diǎn)間的歐氏距離如式(2)所示。

(2)

令無人機(jī)在巡視路徑上對已知障礙物的歐氏距離不小于指定的安全距離，則可建立式(3)所示優(yōu)化數(shù)學(xué)模型。

(3)

st.|OmPn|

式中，Om(xm,ym)表示兩個桿塔之間已知障礙物的坐標(biāo)；N表示確定無人機(jī)路徑所需的坐標(biāo)點(diǎn)數(shù)量，dsafe表示避障要求的安全距離。

2.2 基于人工勢場法的優(yōu)化避障路徑求解

對于巡視路徑中如樹木等點(diǎn)狀障礙物，可用單個障礙坐標(biāo)表示，對于具有較大障礙范圍的飛行障礙物，可通過均勻選取多個障礙坐標(biāo)表示禁飛范圍，以確保無人機(jī)能夠按照式(3)所示避障優(yōu)化模型，確定無人機(jī)繞開巡視路徑上的障礙區(qū)域。

針對避障路徑優(yōu)化數(shù)學(xué)模型存在搜索空間較大且約束條件和目標(biāo)函數(shù)非線性，難以用傳統(tǒng)的數(shù)學(xué)優(yōu)化算法求解的問題，本文研究了基于人工勢場法進(jìn)行尋優(yōu)的方法。該方法將巡視路徑的目標(biāo)點(diǎn)作為勢能最低點(diǎn)，障礙點(diǎn)作為勢能最高點(diǎn)。勢能大小為標(biāo)量，巡視路徑范圍內(nèi)各點(diǎn)由來自目標(biāo)點(diǎn)的引力勢能和障礙點(diǎn)的斥力勢能構(gòu)成，兩種勢能取決于該點(diǎn)離障礙物和目標(biāo)點(diǎn)的距離，對象靠近目標(biāo)點(diǎn)時引力勢能減小，靠近障礙點(diǎn)時斥力勢能急劇增大，遠(yuǎn)離障礙點(diǎn)達(dá)到一定距離時對象不再受障礙點(diǎn)影響，即不存在斥力勢能，以免造成避障路徑尋優(yōu)的頻繁抖動。式(4)和式(5)分別是引力勢能和斥力勢能[14]的計(jì)算表達(dá)式：

(4)

(5)

式中，U1和U2分別是引力勢能和斥力勢能；α和β分別為根據(jù)經(jīng)驗(yàn)選取的比例系數(shù)；ρ0為障礙點(diǎn)斥力勢能起作用的最大歐氏距離；ρ1為當(dāng)前巡視坐標(biāo)點(diǎn)到目標(biāo)點(diǎn)的歐氏距離；ρ2為當(dāng)前巡視坐標(biāo)點(diǎn)到障礙點(diǎn)的歐氏距離。

為了滿足對象與障礙距離大于安全距離的約束條件，應(yīng)滿足:

(7)

在程序運(yùn)行時一般選取參數(shù)β>5α，此時應(yīng)選取ρ0≥3dsafe即可滿足安全約束。

在確定巡視路徑范圍內(nèi)各點(diǎn)勢能后，就可以構(gòu)建無人機(jī)巡視范圍內(nèi)的勢能場，這樣無人機(jī)在勢能場中的前進(jìn)方向就會受到由目標(biāo)點(diǎn)引力勢能和障礙點(diǎn)斥力勢能共同作用的虛擬力影響。將無人機(jī)巡視路徑定義為式(6)所示的各點(diǎn)勢場的梯度方向，就可以使無人機(jī)沿著各點(diǎn)勢能下降最快的方向，以最快的速度趨向于目標(biāo)點(diǎn)并遠(yuǎn)離障礙點(diǎn)，從而使選擇的運(yùn)動路徑即可同時滿足到目標(biāo)點(diǎn)路徑最短同時保持距離障礙點(diǎn)一定安全距離的要求。

圖2 勢能大小及勢能梯度方向示意圖

確定勢場函數(shù)和步長后，從一個點(diǎn)出發(fā)得到的路徑就是確定的，在一個點(diǎn)和下一個點(diǎn)之間選擇勢場梯度作為運(yùn)動方向可能得到次優(yōu)解，為了提高算法的最優(yōu)解求解性能，在每一步增加隨機(jī)擾動，多次運(yùn)行圖3所示尋優(yōu)程序后，基于所得到的優(yōu)化解集，以得到最終優(yōu)化解。

圖3 基于人工勢場法的避障路徑優(yōu)化求解流程圖

3 仿真研究

利用MATLAB分別編寫基于動態(tài)規(guī)劃算法求解雙調(diào)歐幾里得旅行商問題、基于人工勢場法求解避障最優(yōu)路徑的程序，在此基礎(chǔ)上形成考慮無人機(jī)桿塔巡視避障的兩階段路徑優(yōu)化程序，并分別開展以下對比仿真研究。

3.1 無人機(jī)桿塔巡視路徑的優(yōu)化

圖4所示為某輸電桿塔巡視區(qū)域，利用所研究基于動態(tài)規(guī)劃求解雙調(diào)TSP問題確定的無人機(jī)最優(yōu)巡視桿塔路徑如圖4所示。利用基于模擬退火啟發(fā)式算法(Simulated Annealing，SA)求解TSP的無人機(jī)巡視桿塔最優(yōu)路徑如圖5所示。

圖4 基于動態(tài)規(guī)劃算法求解雙調(diào)TSP確定的最優(yōu)路徑

圖5 基于模擬退火算法求解TSP確定的最優(yōu)路徑

表1 兩種巡視路徑優(yōu)化方法的比較

表1對比了兩種方法用于求解最優(yōu)路徑的三個指標(biāo)。結(jié)合圖4和圖5的路徑優(yōu)化仿真結(jié)果可知，雖然利用模擬退火算法求解TSP確定的桿塔巡視路徑與利用動態(tài)規(guī)劃法求解雙調(diào)TSP確定的桿塔巡視路徑相似，由于雙調(diào)TSP要求無人機(jī)沿著一個方向離開起點(diǎn)，再沿著相反方向返回，所基于雙調(diào)TSP問題確定的無人機(jī)巡視路徑，具有轉(zhuǎn)向次數(shù)和轉(zhuǎn)角較小的特點(diǎn)，有利于避免無人機(jī)巡視過程中的頻繁大幅度轉(zhuǎn)向，提高了無人機(jī)巡視桿塔效率和安全性。

3.2 無人機(jī)避障路徑的優(yōu)化

選取圖4確定的桿塔巡視路徑中兩個相鄰桿塔間障礙物較多的路徑作為仿真對象，規(guī)劃兩個桿塔之間的最優(yōu)避障路徑。圖6給出了利用圖3所示尋優(yōu)方法確定的避障路徑。由圖可見，利用所研究的基于勢場法求解最優(yōu)避障路徑可有效避免無人機(jī)巡視路徑中的障礙物。

由于人工勢場法在每一步都會沿著勢能降落最快的方向前進(jìn)，本質(zhì)上是一種貪心算法，容易陷入局部最優(yōu)，所以要給算法增加隨機(jī)擾動，多次運(yùn)行，使之脫離局部最優(yōu)。進(jìn)而基于多次尋優(yōu)的避障路徑長短確定最優(yōu)的避障路徑。圖7對比圖6給出了避障路徑在施加擾動多次尋優(yōu)后確定的最優(yōu)路徑。

3.3 考慮巡視路徑避障的兩階段桿路徑優(yōu)化

圖8為無人機(jī)擬巡視輸電線路的桿塔及巡視范圍內(nèi)的障礙點(diǎn)空間位置布局圖。圖9為采用本文提出的兩階段巡視路徑優(yōu)化方法確定的無人機(jī)巡視路徑。路徑規(guī)劃結(jié)果不僅表明所提兩階段優(yōu)化方法能在有效減小無人機(jī)巡視過程中的轉(zhuǎn)向次數(shù)和轉(zhuǎn)向角度，而且能確定有效避免飛行途中障礙物的最經(jīng)濟(jì)飛行線路，有利于提高自動化巡視的安全性、擴(kuò)大巡視范圍。

圖8 巡輸電桿塔與障礙物位置示意圖

圖9 基于兩階段優(yōu)化的無人機(jī)巡視路徑圖

4 結(jié)束語

隨著無人機(jī)技術(shù)的進(jìn)步，全自動化的無人機(jī)精細(xì)化巡檢桿塔逐漸變得可行，而巡檢線路規(guī)劃是無人機(jī)自動化巡檢過程中重要的一環(huán)，關(guān)乎巡檢的效率和安全性。本文提出了基于兩階段優(yōu)化確定無人機(jī)巡視桿塔考慮避障的路徑優(yōu)化方法。該方法通過動態(tài)規(guī)劃算法優(yōu)化無人機(jī)經(jīng)過桿塔的次序，通過人工勢場法規(guī)劃無人機(jī)在兩個桿塔之間避開障礙物的飛行路徑。該方法確定的巡視路徑具有巡視路徑短、無人機(jī)在巡視過程中轉(zhuǎn)向少且轉(zhuǎn)向角度小、能按照安全距離要求有效避開障礙點(diǎn)的特點(diǎn)。