復(fù)雜環(huán)境下無人機(jī)全覆蓋路徑規(guī)劃混合算法研究

黃迎港 陳鍇 羅文廣

摘? 要：為解決無人機(jī)在被檢物體外形復(fù)雜、多障礙物等環(huán)境下的路徑規(guī)劃問題，提出了一種基于混合策略的全覆蓋路徑規(guī)劃算法，該算法由綜合運(yùn)動函數(shù)、死區(qū)逃離策略、運(yùn)動優(yōu)先級策略組成。綜合運(yùn)動函數(shù)對基于柵格地圖的位置函數(shù)及考慮無人機(jī)能量消耗的轉(zhuǎn)向置信函數(shù)進(jìn)行加權(quán)，并作為下一航點的選擇依據(jù);死區(qū)逃離策略由環(huán)形搜索、A-star算法構(gòu)成;運(yùn)動優(yōu)先級策略設(shè)計為：左優(yōu)先、下優(yōu)先、直優(yōu)先，以降低無人機(jī)遇到障礙物時規(guī)劃路徑纏繞、陷入死區(qū)和節(jié)點重復(fù)問題的發(fā)生概率，使之高效飛行。通過仿真及實機(jī)驗證，結(jié)果表明：所提算法適用于復(fù)雜環(huán)境下的無人機(jī)路徑規(guī)劃，且可有效減少陷入死區(qū)的次數(shù)，降低路徑重復(fù)率，減少路徑規(guī)劃時間。

關(guān)鍵詞：無人機(jī);路徑規(guī)劃;復(fù)雜環(huán)境;全覆蓋;混合算法

中圖分類號：V279.2;TN926? ? ? ? ? DOI：10.16375/j.cnki.cn45-1395/t.2022.01.013

0? ? 引言

近年來，路徑規(guī)劃問題成為無人機(jī)控制領(lǐng)域的研究熱點。全覆蓋路徑規(guī)劃是指無人機(jī)從起點到終點，自主規(guī)劃出一條無碰撞的飛行路徑。常見的方法有：A-star算法、遺傳算法、粒子群算法等。然而上述方法只在特定場景下有效且易陷入局部極小值，導(dǎo)致所得路徑全局性差，無法滿足無人機(jī)日益復(fù)雜的飛行環(huán)境要求[1]。周毅等[2]引入插入算子和刪除算子對遺傳算法（GA）進(jìn)行改進(jìn)，有效減少了航點重疊率，提高了無人機(jī)在巡線工作中的安全性。伍鵬飛等[3]采用混沌蜂群算法（ABC）提升無人機(jī)在復(fù)雜環(huán)境下的死區(qū)逃離能力。此外，通過引入輔助避障力的方法，解決人工勢場法易陷入局部極小值的問題，但當(dāng)環(huán)境變化時需要重新對參數(shù)進(jìn)行整定，未從根本上解決其存在的缺點[4]。以上方法主要采用單一算法并進(jìn)行特定的改進(jìn)，雖能克服傳統(tǒng)算法的一些缺點，但普適性較差。為此，復(fù)雜環(huán)境下的無人機(jī)路徑規(guī)劃研究逐漸向混合算法方向發(fā)展。周克帥等[5]采用全局+局部相結(jié)合的方式，實現(xiàn)動態(tài)環(huán)境下無碰撞路徑規(guī)劃。付興武等[6]利用天牛須算法（BAS）中天牛個體的自尋優(yōu)能力，結(jié)合粒子群算法（PSO）設(shè)計出BAS-PSO路徑規(guī)劃算法，可有效提高粒子的搜索效率，但PSO在解決路徑規(guī)劃問題時易出現(xiàn)早熟現(xiàn)象，算法的整體尋優(yōu)能力提升不夠顯著。王翼虎等[7]將細(xì)菌覓食算法（BFO）引入粒子群優(yōu)化中，避免粒子趨同現(xiàn)象發(fā)生，提高三維環(huán)境下路徑規(guī)劃的覆蓋率。白杰等[8]在分散搜索算法中引入模擬退火算法，提高了分散搜索的全局尋優(yōu)能力，但局部規(guī)劃仍存在局限。柵格地圖在路徑規(guī)劃環(huán)境建模方面應(yīng)用廣泛。郝宗波等[9]采用內(nèi)螺旋覆蓋算法（ISC）實現(xiàn)對室內(nèi)環(huán)境下的全覆蓋路徑規(guī)劃，有效降低遍歷的重復(fù)性，但其并未對復(fù)雜環(huán)境進(jìn)行驗證。韓忠華等[10]通過降維方式提高規(guī)劃效率，降低模型的復(fù)雜度，并采用局部動態(tài)搜索策略改善規(guī)劃過程中的隨機(jī)性。陶德臣等[11]利用圖論學(xué)理論對牛耕往復(fù)式全覆蓋算法進(jìn)行改進(jìn)，在不規(guī)則農(nóng)田環(huán)境下實現(xiàn)全局航線規(guī)劃，但其實現(xiàn)復(fù)雜，難以在線進(jìn)行。潘楠等[12]提出基于差分進(jìn)化算法（DE）優(yōu)化的生命周期群搜索（LSO）算法，在模擬倉庫環(huán)境飛行中延長了飛行路線，提高了無人機(jī)的工作效率。孫靜等[13]提出分層規(guī)劃方法，將PSO與稀疏A-star算法結(jié)合，解決了復(fù)雜環(huán)境下規(guī)劃航線的無碰撞要求。唐俊[14]采用分層拓展的思想對三維環(huán)境進(jìn)行建模，應(yīng)用多層拓展A-star算法實現(xiàn)快速航跡規(guī)劃，提高了三維路徑規(guī)劃的速度并可有效避開障礙物。唐博文等[15]采用事件觸發(fā)方式，簡化強(qiáng)化學(xué)習(xí)避障算法的復(fù)雜度，但其并未驗證復(fù)雜環(huán)境下的避障有效性。

為了解決多旋翼無人機(jī)[16]在復(fù)雜環(huán)境下的全覆蓋路徑規(guī)劃問題，本文提出一種基于混合策略的全覆蓋路徑規(guī)劃算法。在定義位置函數(shù)和建立轉(zhuǎn)向置信函數(shù)的基礎(chǔ)上，設(shè)計用于確定無人機(jī)飛行方向的綜合運(yùn)動函數(shù);應(yīng)用環(huán)形搜索算法和A-star算法制定死區(qū)逃離策略，解決無人機(jī)高效逃離死區(qū)問題;設(shè)置“左優(yōu)先，下優(yōu)先，直優(yōu)先”的運(yùn)動優(yōu)先級策略，解決無人機(jī)飛行遇到障礙物時規(guī)劃路徑纏繞、陷入死區(qū)和節(jié)點重復(fù)飛行問題。將其應(yīng)用到環(huán)境復(fù)雜的橋梁病害檢測路徑規(guī)劃中，驗證該算法的有? ?效性。

1? ? 基于混合策略的全覆蓋路徑規(guī)劃算法

為了解決在復(fù)雜環(huán)境下的無人機(jī)路徑規(guī)劃問題，在文獻(xiàn)[17]的基礎(chǔ)上，研究一種基于混合策略的全覆蓋路徑規(guī)劃算法。該算法在設(shè)計出二維算法的基礎(chǔ)上，再擴(kuò)展至三維。二維算法主要由綜合運(yùn)動函數(shù)、死區(qū)逃離策略、運(yùn)動優(yōu)先級策略等構(gòu)成。

1.1? ?二維算法設(shè)計

1.1.1? ? 綜合運(yùn)動函數(shù)

綜合運(yùn)動函數(shù)包括2個部分：位置函數(shù)及轉(zhuǎn)向信度函數(shù)。位置函數(shù)用于區(qū)分未覆蓋的柵格、已覆蓋的柵格以及障礙物;而轉(zhuǎn)向信度函數(shù)用于引導(dǎo)無人機(jī)向未覆蓋區(qū)域飛行，同時控制轉(zhuǎn)向角度，使路徑趨于平直。

構(gòu)建地圖是進(jìn)行無人機(jī)路徑規(guī)劃的前提條件，常見的方法有柵格法、單元分解法和拓?fù)浞ǖ?。柵格地圖以其簡單有效、表達(dá)能力強(qiáng)的特點得到廣泛應(yīng)用。柵格法就是將無人機(jī)工作環(huán)境劃分為若干個柵格，通過位置函數(shù)對柵格進(jìn)行賦值，進(jìn)行區(qū)域的劃分。柵格大小的選擇是決定路徑規(guī)劃成功與否的關(guān)鍵，過大則地圖分辨率降低，對真實環(huán)境的表達(dá)能力不強(qiáng);過小將增加計算負(fù)擔(dān)，抗干擾性差。根據(jù)橋梁檢測任務(wù)和無人機(jī)橋檢相機(jī)的像素，選用? 1 m×1 m的柵格對地圖進(jìn)行建模。

1）位置函數(shù)

對柵格進(jìn)行賦值可以達(dá)到區(qū)分不同柵格的目的。設(shè)位置函數(shù)為[X]，如式（1）：

[Xi， j=1;該柵格未覆蓋0.5;該柵格已覆蓋?1;該柵格是障礙物]，? ? ? ? ? ? ? ? ?（1）

式中：[i]、[j]表示柵格地圖中第[i]行、第[j]列的柵格。

式（1）對柵格進(jìn)行了分類。飛行路徑即航線由一系列航點構(gòu)成，路徑規(guī)劃就是確定每一個航點的位置。對應(yīng)到柵格地圖中，需要確定每飛行一步所處的柵格坐標(biāo)。例如，圖1所示的每一個運(yùn)行窗口中會有8個與當(dāng)前節(jié)點（圖中[pp]點）相連接的柵格進(jìn)入待選區(qū)域;[pb]表示當(dāng)前節(jié)點[pp]的父節(jié)點（前一個已覆蓋節(jié)點），這2個柵格都已經(jīng)完成了覆蓋（灰色表示），其賦值為0.5;圖中障礙物柵格設(shè)為黑色，賦值為-1;[pn1—pn5]表示未完成覆蓋的柵格（白色表示），賦值為1。圖2顯示了圖1中各個柵格的賦值情況。

2）轉(zhuǎn)向置信函數(shù)

為控制無人機(jī)的航向，使其趨向未覆蓋區(qū)域，設(shè)置轉(zhuǎn)向信度函數(shù)[C]，如式（2）：

[C=1?△?π] ，? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

式中：[△?∈[0， π]]，為航向變化角。

圖3為航向變化角示意圖。

由圖3得航向變化角[△?]：

[△?=arctanypn-yppxpn-xpp-arctanypp-ypbxpp-xpb]，? ? ? ?（3）

式中：[pp（xpp， ypp）]、[pb（xpb， ypb）]及[pn（xpn， ypn）]分別表示當(dāng)前節(jié)點、當(dāng)前節(jié)點的父節(jié)點及未覆蓋節(jié)點。

[△?=0°]，[C]=1為最大，無人機(jī)沿著直線航行，無需轉(zhuǎn)向，消耗能量最少，信度最高;[△?=180°]，無人機(jī)往相反方向航行，轉(zhuǎn)向角度最大，消耗能量最多，應(yīng)該盡量避免。

3）綜合運(yùn)動函數(shù)

綜合考慮位置函數(shù)及轉(zhuǎn)向信度函數(shù)，重新定義一個綜合運(yùn)動函數(shù)，作為下一飛行節(jié)點的選擇依據(jù)，其定義為：

[Yk=Xk+aCk]，[k=1， 2， …， i]，? ? ? ? ? ? （4）

式中：[a∈（0， 1]]，為加權(quán)系數(shù)，此處將其設(shè)為0.5，即在規(guī)劃過程中總是朝著未覆蓋節(jié)點方向行走;? ? [i]的取值取決于與當(dāng)前節(jié)點相連接的未覆蓋點的? ? ?數(shù)量。選取[Yk]值最大的節(jié)點作為下一步移動方向。

1.1.2? ? ?死區(qū)逃離策略

在進(jìn)行上述的路徑規(guī)劃時，可能會產(chǎn)生這樣的情形：與當(dāng)前節(jié)點毗鄰的節(jié)點不存在未覆蓋節(jié)點，都是已覆蓋節(jié)點或障礙物，或者是邊界，這時稱無人機(jī)陷入死區(qū)，如圖4所示。無人機(jī)進(jìn)入死區(qū)后不能按圖3所示的航向變化角方向進(jìn)行下一步飛行，只有逃離死區(qū)后才能繼續(xù)完成覆蓋任務(wù)。為此，設(shè)計死區(qū)逃離策略：當(dāng)無人機(jī)陷入死區(qū)后，使用環(huán)形搜索算法搜索死區(qū)外環(huán)的節(jié)點，尋找未覆蓋的節(jié)點;然后計算各未覆蓋節(jié)點與當(dāng)前節(jié)點的代價值，用A-star算法確定下一節(jié)點。

1）環(huán)形搜索

當(dāng)無人機(jī)陷入死區(qū)時，進(jìn)行環(huán)形搜索。如圖5所示，灰色為已覆蓋節(jié)點或障礙物，藍(lán)色為正在搜索區(qū)域，紅色為搜索結(jié)束區(qū)域。以當(dāng)前節(jié)點與未覆蓋節(jié)點之間的最短歐氏距離為半徑進(jìn)行環(huán)形搜索，尋找未覆蓋節(jié)點。

2）A-star算法選擇路徑

A-star算法是一種典型的啟發(fā)式算法，具有原理簡單、易于代碼實現(xiàn)、適應(yīng)性好等優(yōu)勢，在路徑規(guī)劃領(lǐng)域得到廣泛應(yīng)用。其在搜索過程中，通過比較每一個待選節(jié)點的代價值，選擇代價值最小的節(jié)點作為下一個節(jié)點。

對于能量源有限的無人機(jī)，在復(fù)雜環(huán)境中進(jìn)行路徑規(guī)劃時，需要重點考慮其高效飛行問題。因此，將A-star算法的代價值選擇為“能量消耗”，在這里體現(xiàn)出來的就是“最短飛行距離”，在柵格地圖中則為飛行的“柵格數(shù)”。實際上通過A-star算法就是要選擇“從當(dāng)前節(jié)點到達(dá)該未覆蓋節(jié)點的路徑長度是所有未覆蓋節(jié)點中最短”的節(jié)點，定義為“最近”未覆蓋節(jié)點，如圖6所示。因為“死區(qū)”可能包括障礙物，無人機(jī)需要避開障礙物，環(huán)形搜索到的未覆蓋節(jié)點未必是飛行距離最短的節(jié)點。圖中，按最短歐氏距離（3個柵格）搜索到的未覆蓋節(jié)點為[pn1]，而從當(dāng)前節(jié)點[pp]出發(fā)，到達(dá)[pn1]需要經(jīng)過柵格1、2、3、[pn2]、4、5、6、7、8、9，共飛行11個柵格，“飛行距離”大于“歐氏距離”。按下一個最短歐氏距離（4個柵格）搜索到的未覆蓋節(jié)點[pn2]等（僅以[pn2]說明），從當(dāng)前節(jié)點[pp]出發(fā)，到達(dá)[pn2]只需要經(jīng)過柵格1、2、3，共飛行4個柵格，“飛行距離”等于“歐氏距離”。經(jīng)過2次環(huán)形搜索后，A-star算法找到最佳逃離“死區(qū)”的節(jié)點為[pn2]。通過上述分析，設(shè)計的死區(qū)逃離策略具體步驟如下：

Step 1? ? 按“最短歐氏距離”原則搜索未覆蓋節(jié)點。

Step 2? ? 計算當(dāng)前節(jié)點到未覆蓋節(jié)點的“飛行距離”，獲得其中“最小飛行距離”。

Step 3? “最小飛行距離”是否等于或小于“最短歐氏距離”？如果是，則選擇相應(yīng)節(jié)點為“最近”未覆蓋節(jié)點，無人機(jī)飛向該節(jié)點，逃離“死區(qū)”;反之，則執(zhí)行下一步。

Step 4? “最短歐氏距離”增加一個柵格，轉(zhuǎn)到Step 1，進(jìn)行新一輪搜索。

在上述步驟中，“最小飛行距離”是指所有環(huán)形搜索中的最小值;“最短歐氏距離”是指每次環(huán)形搜索中的值，根據(jù)搜索的具體情況會不斷加大。

1.1.3? ? ?運(yùn)動優(yōu)先級策略

由上述分析可知，綜合運(yùn)動代價函數(shù)能夠?qū)骄€進(jìn)行全覆蓋規(guī)劃，但當(dāng)無人機(jī)遇到障礙物時，更容易陷入死區(qū)。為了逃離死區(qū)而產(chǎn)生節(jié)點重復(fù)飛行，導(dǎo)致規(guī)劃路徑存在冗余航點、路徑重復(fù)率高的缺點。為此，引入運(yùn)動優(yōu)先級策略，規(guī)范無人機(jī)路徑，降低陷入死區(qū)和節(jié)點重復(fù)飛行（重復(fù)率）的概率，使之高效規(guī)劃路徑。運(yùn)動優(yōu)先級策略設(shè)計為：左優(yōu)先，下優(yōu)先，直優(yōu)先。在圖7（a）中，當(dāng)無人機(jī)觸及障礙物邊緣后，若左側(cè)存在未覆蓋區(qū)域，則優(yōu)先覆蓋左側(cè)區(qū)域。在圖7（b）中，當(dāng)無人機(jī)觸及障礙物邊緣時，若下方存在未覆蓋區(qū)域，則優(yōu)先覆蓋下方區(qū)域。在圖7（c）中，下一節(jié)點存在2種選擇，即左側(cè)直行或向左上角運(yùn)動。根據(jù)綜合運(yùn)動代價函數(shù)，將選擇2號柵格作為下一個節(jié)點，但這很可能會造成1號柵格的未覆蓋。根據(jù)運(yùn)動優(yōu)先級策略，優(yōu)先覆蓋1號柵格節(jié)點，減少規(guī)劃路徑纏繞的? ? ? 發(fā)生。

1.2? ? 二維全覆蓋路徑規(guī)劃流程

二維全覆蓋路徑規(guī)劃流程如圖8所示。

對于全覆蓋路徑規(guī)劃問題，關(guān)鍵在于根據(jù)相關(guān)策略確定無人機(jī)的下一個航點位置（節(jié)點）。圖8中，大多數(shù)節(jié)點屬于正常節(jié)點，由綜合運(yùn)動函數(shù)確定;無人機(jī)陷入死區(qū)時，則由死區(qū)逃離策略確定;若無人機(jī)觸及障礙物邊緣，則采用運(yùn)動優(yōu)先級策略確定。當(dāng)所有柵格的賦值都不為1時，即不存在未覆蓋節(jié)點，可認(rèn)為完成了對工作區(qū)域的全覆蓋路徑規(guī)劃。

1.3? ? 三維全覆蓋路徑規(guī)劃流程

無人機(jī)進(jìn)行飛行時處于三維環(huán)境中，因此，需要將二維算法推廣至三維。三維路徑規(guī)劃流程如 圖9所示。

借助等高線的概念，將工作區(qū)域根據(jù)高度值分為若干層（z層），在每一層進(jìn)行二維路徑規(guī)劃。當(dāng)這一層完成全覆蓋后，尋找正上（下）方的節(jié)點作為下一層的起點，若該節(jié)點為障礙物節(jié)點，則尋找“最近”節(jié)點，作為下一層的初始任務(wù)航點。循環(huán)以上步驟，直至三維工作空間完成全覆蓋。

2? ? 試驗及分析

2.1? ?仿真試驗及分析

分別建立二維仿真地圖及三維橋梁抽象地圖，以驗證本文提出的全覆蓋規(guī)劃算法的有效性。在全覆蓋路徑規(guī)劃任務(wù)中，可以利用以下指標(biāo)來評價全覆蓋路徑規(guī)劃策略的性能。

1）區(qū)域覆蓋率

區(qū)域覆蓋率（[Cc]）表示為：

[Cc=NcN×100%]，? ? ? ? ? ? ? ? ? ? ? ? （5）

式中：[Nc]表示無人機(jī)完成覆蓋的柵格個數(shù)，[N]表示所有需要覆蓋的柵格個數(shù)。

以使用無人機(jī)對橋梁進(jìn)行病害檢測為例，檢測范圍是橋梁的全部外表面，重點檢測橋墩外表面、橋板下底面以及橋墩與橋板的連接處。為了避免漏檢現(xiàn)象的發(fā)生，無人機(jī)需要遍歷以上提到的所有區(qū)域，因此，要求算法所規(guī)劃路徑的區(qū)域覆蓋率要達(dá)到100%。

2）路徑重復(fù)率

路徑重復(fù)率[RR]可以表示為：

[RR=NL-NN]，? ? ? ? ? ? ? ? ? ? ? ? ? （6）

式中：[NL]代表無人機(jī)飛行路徑的長度，在柵格地圖中即為其所經(jīng)過的柵格總數(shù)。

在任務(wù)背景下，區(qū)域覆蓋率[Cc=100%]，使得[NL≥N]。由于無人機(jī)續(xù)航能力有限，這就要求[RR]盡可能小，提高工作效率。

2.1.1? ? 二維環(huán)境仿真試驗

在二維環(huán)境中，模擬工作區(qū)域為[25×25]的柵格地圖，其中每一個柵格都賦值為1，用白色表示未覆蓋節(jié)點;或賦值為-1，用黑色表示障礙物節(jié)點，障礙物為隨機(jī)生成。地圖的邊界視為障礙物，標(biāo)記為黑色。初始起點設(shè)置在地圖左下角，顯示為黑色實心圓。在地圖中總計625個網(wǎng)格，其中待覆蓋節(jié)點（白色）504個，障礙物節(jié)點（黑色）121個，仿真地圖如圖10所示。

在二維地圖中，僅使用綜合運(yùn)動函數(shù)進(jìn)行全覆蓋路徑規(guī)劃，其結(jié)果如圖11所示。從圖中可以看出，僅使用綜合運(yùn)動代價函數(shù)可以完成對地圖的全覆蓋，覆蓋率可以達(dá)到100%，但其所規(guī)劃的路徑多次陷入死區(qū)（圖空心小方塊代表陷入死區(qū)的節(jié)點），這就導(dǎo)致了較高的路徑重復(fù)率。為了改善算法性能，將運(yùn)動優(yōu)先級策略加入其中，重新進(jìn)行路徑規(guī)劃，其規(guī)劃結(jié)果如圖12所示，2種方法的對比試驗結(jié)果如表1所示。

2種方法都可達(dá)到區(qū)域全覆蓋率，但加入運(yùn)動優(yōu)先級策略后的路徑重復(fù)率從26.8%降低至10.1%;路徑總長度從639降低至555;陷入死區(qū)次數(shù)從42次降低至26次。由上可知，在加入了運(yùn)動優(yōu)先級策略后，算法所規(guī)劃的路徑較之前有了較大改善，將原本內(nèi)螺旋型的線路更改為現(xiàn)有的往復(fù)式線路，大大減小了路線發(fā)生纏繞及陷入死區(qū)的可能性，同時逃離死區(qū)后的路徑小于之前的路徑重復(fù)率。結(jié)果表明，運(yùn)動優(yōu)先級策略可以有效降低路徑重復(fù)率，縮短路徑長度，有效提升無人機(jī)工作? ? ?效率。

目前全覆蓋路徑規(guī)劃任務(wù)中使用比較多的方法有單元分解法以及生物激勵神經(jīng)網(wǎng)絡(luò)算法等。使用以上2種算法對本文中的二維模擬地圖進(jìn)行全覆蓋路徑規(guī)劃，使用覆蓋率、路徑長度、路徑重復(fù)率、路徑規(guī)劃時間以及陷入死區(qū)次數(shù)作為算法的性能指標(biāo)，結(jié)果如表2所示。通過表中數(shù)據(jù)可以看出，雖然3種方法的區(qū)域覆蓋率都達(dá)到了100%，但從其他性能指標(biāo)來看，本文提出的算法更具優(yōu)勢。

單元分解法在面對復(fù)雜地圖、障礙物較多且分散的情況下，分解產(chǎn)生的子單元數(shù)量會非常大，導(dǎo)致路徑極易陷入死區(qū)。相較于本文算法，其陷入死區(qū)的次數(shù)增加了11次，增加了42.3%，這就導(dǎo)致其路徑重復(fù)率高達(dá)19.6%，比本文算法高出9.5%。生物激勵神經(jīng)網(wǎng)絡(luò)算法的性能高于單元分解法，但該算法設(shè)計比較復(fù)雜且使用微分計算來更新節(jié)點的活性值，與本文直接對柵格進(jìn)行操作相比，計算量大，其路徑規(guī)劃時間相較于本文算法高出了56.5%。

2.1.2? ? 三維環(huán)境仿真試驗

利用無人機(jī)進(jìn)行橋梁病害檢測時，實際工作環(huán)境是一個空中的三維空間。為了使仿真試驗更加貼近實際工作環(huán)境，首先建立一個簡單橋梁模型，包括橋墩及橋板兩部分，橋梁簡易模型如圖13所示。無人機(jī)的工作任務(wù)是拍攝橋梁所有外表面，主要是橋墩外表面以及橋板下表面，因此，無人機(jī)的航線需要遍歷以上地點。使用本文中提出的三維全覆蓋路徑規(guī)劃算法對圖13中的三維橋梁模型進(jìn)行航線規(guī)劃，其結(jié)果如圖14所示。

在圖14中無人機(jī)的初始起點為（3，12，1）。在? z =1層上，從初始起點開始，無人機(jī)沿橋墩外邊沿飛行一圈后，完成了對該高度的全覆蓋;在到達(dá)該層最后一個可達(dá)節(jié)點（4，13，1）后（右側(cè)橋墩暫時無法到達(dá)），開始尋找z =2層的起點，由于（4，13，2）不是障礙物節(jié)點，故將其作為z =2層的起點。重復(fù)以上過程，直到完成所有高度層的二維全覆蓋路徑規(guī)劃。完成對z =6層的覆蓋后，右側(cè)仍存在未覆蓋區(qū)域，因此，尋找距離z =6層終點（12，36，6）最近的下行點（11，35，6），以完成對右側(cè)橋墩的覆蓋，即完成了橋梁模型的三維全覆蓋路徑規(guī)劃。可以看出，本文提出的算法不僅能在二維環(huán)境中規(guī)避障礙物并實現(xiàn)全覆蓋路徑規(guī)劃，而且在三維復(fù)雜環(huán)境下仍具有高效全覆蓋路徑規(guī)劃能力。

2.2? ?運(yùn)行測試及分析

經(jīng)仿真驗證后，將本文提出的全覆蓋規(guī)劃算法嵌入自行開發(fā)的天星GXUST地面站平臺，對位于某大學(xué)東環(huán)校區(qū)內(nèi)的宗元橋進(jìn)行實際路徑規(guī)劃試驗。在實機(jī)航線規(guī)劃中將無人機(jī)視為一個質(zhì)點，不考慮無人機(jī)的大小及外形，同時由于多旋翼無人機(jī)卓越的機(jī)動性能，可以合理假設(shè)在飛行中無人機(jī)可以全方位運(yùn)動，不受轉(zhuǎn)向角及俯仰角的限制。測試過程中由地面站軟件控制無人機(jī)沿規(guī)劃路徑進(jìn)行自主飛行，其地面站界面及路徑規(guī)劃效果如圖15所示。其中，主界面分為：飛行數(shù)據(jù)顯示區(qū)域、飛行命令及控制區(qū)域和航線規(guī)劃及地圖顯示區(qū)域。右側(cè)為本次橋檢任務(wù)自動規(guī)劃的航線，可以看出地面站系統(tǒng)將算法規(guī)劃的任務(wù)航點轉(zhuǎn)化為地理坐標(biāo)（經(jīng)、緯度和高度）形式并進(jìn)行可視化顯示。

該橋?qū)儆趩喂皹?，橋? m，上設(shè)路燈等設(shè)備，故無人機(jī)需對橋面及雙側(cè)橋墩進(jìn)行航線覆蓋，并確保機(jī)體在不與橋體及障礙物碰撞的前提下完成橋梁檢測任務(wù)。圖16為航線細(xì)節(jié)圖。使用直徑? ?70 cm的四旋翼無人機(jī)進(jìn)行實際測試，設(shè)定距飛機(jī)中心80 cm為安全飛行范圍，初始航點1從橋左側(cè)3 m處出發(fā)，按z =1 m依次升高，先對兩側(cè)橋墩進(jìn)行檢測，隨后對橋面進(jìn)行往復(fù)式覆蓋，最終降落在橋面（航點177）。實機(jī)飛行路徑表明，該路徑對橋體的覆蓋率達(dá)到100%、無路徑重復(fù)率且成功避免其陷入死區(qū)。在對該橋梁進(jìn)行實測過程中，路徑規(guī)劃算法能夠根據(jù)待檢橋梁的三維重建模型規(guī)劃出一條滿足實際環(huán)境約束及待檢橋梁類型要求的三維航線，并實現(xiàn)避障功能。

3? ? ?結(jié)束語

本文所提出的全覆蓋路徑規(guī)劃混合算法可適用于復(fù)雜環(huán)境下的無人機(jī)路徑規(guī)劃。通過與單元分解法和生物神經(jīng)算法進(jìn)行比較后可知，該混合算法能高效完成對被檢區(qū)域的路徑規(guī)劃任務(wù)，同時有效縮短航線總里程以提高檢測效率;死區(qū)逃離策略可有效減少陷入死區(qū)的次數(shù);運(yùn)動優(yōu)先級的設(shè)置降低了路徑重復(fù)率，減少了路徑規(guī)劃時間，提高了規(guī)劃算法的效率，并通過實機(jī)測試驗證了該算法在實際復(fù)雜環(huán)境下（橋梁檢測）路徑規(guī)劃的有效性。

參考文獻(xiàn)

[1]? ? ?楊俊成，李淑霞， 蔡增玉.路徑規(guī)劃算法的研究與發(fā)展[J]. 控制工程，2017，24（7）：1473-1480.

[2]? ? ?周毅，李東武，孟浩，等.遺傳算法路徑規(guī)劃在無人機(jī)電力巡線中的應(yīng)用[J].自動化技術(shù)與應(yīng)用，2021，40（2）：29-33.

[3]? ? ?伍鵬飛，李濤，曹廣旭，等.基于改進(jìn)混沌蜂群算法的無人戰(zhàn)斗機(jī)路徑規(guī)劃[J].中國科技論文，2021，16（3）：301-306.

[4]? ? ?韓堯，李少華.基于改進(jìn)人工勢場法的無人機(jī)航跡規(guī)劃[J/OL].系統(tǒng)工程與電子技術(shù)，2021：1-9[2021-06-30].http：//kns.cnki.net/kcms/detail/11.2422.TN.20210531.1117.014.html.

[5]? ? ?周克帥，范平清.改進(jìn)A*算法與人工勢場算法移動機(jī)器人路徑規(guī)劃[J].電子器件，2021，44（2）：368-374.

[6]? ? ?付興武，胡洋.基于改進(jìn)粒子群算法的三維路徑規(guī)劃[J].電光與控制，2021，28（3）：86-89.

[7]? ? ?王翼虎，王思明.基于改進(jìn)粒子群算法的無人機(jī)路徑規(guī)劃[J].計算機(jī)工程與科學(xué)，2020，42（9）：1690-1696.

[8]? ? ?白杰，楊根科，潘常春，等.基于改進(jìn)分散搜索算法的無人機(jī)路徑規(guī)劃[J].上海交通大學(xué)學(xué)報，2011，45（2）：173-178.

[9]? ? ?郝宗波，洪炳镕，黃慶成.基于柵格地圖的機(jī)器人覆蓋路徑規(guī)劃研究[J].計算機(jī)應(yīng)用研究，2007（10）：56-58.

[10]? ?韓忠華，畢開元，楊麗英，等.室內(nèi)復(fù)雜環(huán)境下多旋翼無人機(jī)動態(tài)路徑規(guī)劃[J].中國慣性技術(shù)學(xué)報，2019，27（3）：366-372，377.

[11]? ?陶德臣，祖家奎，高尚文.基于全覆蓋路徑的植保無人直升機(jī)航線規(guī)劃方法與實現(xiàn)技術(shù)[J].電子測量技術(shù)，2020，43（7）：50-55，166.

[12]? ?潘楠，陳啟用，劉海石，等.復(fù)雜工業(yè)品倉儲環(huán)境無人機(jī)庫盤任務(wù)規(guī)劃[J/OL].計算機(jī)集成制造系統(tǒng)，2021：1-17[2021-06-30].http：//kns.cnki.net/kcms/detail/11.5946.TP.20210318.0934.006.html.

[13]? ?孫靜，吳碧，許玉堂，等.復(fù)雜環(huán)境下無人機(jī)三維航跡規(guī)劃方法研究[J].彈箭與制導(dǎo)學(xué)報，2014，34（3）：170-174.

[14]? ?唐俊.顧及復(fù)雜環(huán)境約束的無人機(jī)三維航跡快速規(guī)劃[J].測繪通報，2019（11）：26-30.

[15]? ?唐博文，王智文，胡振寰.基于事件驅(qū)動的無人機(jī)強(qiáng)化學(xué)習(xí)避障研究[J].廣西科技大學(xué)學(xué)報，2019，30（1）：96-102，117.

[16]? ?徐亞妮，羅文廣，張亮.基于FPGA的四軸飛行器飛行控制系統(tǒng)設(shè)計[J].廣西科技大學(xué)學(xué)報，2018，29（3）：50-56.

[17]? ?甘文洋，朱大奇.基于行為策略的AUV全覆蓋信度函數(shù)路徑規(guī)劃算法[J].系統(tǒng)仿真學(xué)報，2018，30（5）：1857-1863.

Hybrid algorithm of UAV full coverage path planning in

complex environment

HUANG Yinggang1，2， CHEN Kai1， LUO Wenguang*1，2

（1.School of Electrical， Electronic and Computer Science， Guangxi University of Science and Technology，

Liuzhou 545616， China; 2. Guangxi Key Laboratory of Automobile Components and Vehicle Technology （Guangxi University of Science and Technology）， Liuzhou 545006， China）

Abstract： A hybrid strategy-based full coverage path planning algorithm is proposed to solve the? ? problem of UAV path planning in environments with complex shapes and multiple obstacles. The? ? ? ? algorithm is composed of comprehensive motion function， dead zone escape strategy， and motion? ? ? priority strategy. The comprehensive motion function weights the position function based on the grid map and the steering confidence function considering the energy consumption of the UAV as the basis for selecting the next waypoint; the dead zone escape strategy is composed of ring search and A-star? ?algorithm; the motion priority strategy design is of left-priority， down-priority and straight-priority to? ?reduce the planned path winding， dead zone and node duplication when the UAV encounters obstacles， enabling it to fly efficiently. The simulation and real machine verification results show that the? ? ? ? ? proposed algorithm is suitable for UAV path planning in complex environments and can effectively? ? ?reduce the number of dead zones， path repetition rate and path planning time.

Key words： unmanned aerial vehicle; path planning; complex environment; full coverage; hybrid? ? ? ? algorithm

（責(zé)任編輯：黎? 婭）