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

0 引言

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

(2)

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

(3)

st.|OmPn|

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

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

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

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

(4)

(5)

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

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

(7)

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

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

圖2 勢(shì)能大小及勢(shì)能梯度方向示意圖

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

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

3 仿真研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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