復雜環境下無人機全覆蓋路徑規劃混合算法研究

黃迎港 陳鍇 羅文廣

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

關鍵詞：無人機;路徑規劃;復雜環境;全覆蓋;混合算法

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

0? ? 引言

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

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

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

為了解決在復雜環境下的無人機路徑規劃問題，在文獻[17]的基礎上，研究一種基于混合策略的全覆蓋路徑規劃算法。該算法在設計出二維算法的基礎上，再擴展至三維。二維算法主要由綜合運動函數、死區逃離策略、運動優先級策略等構成。

1.1? ?二維算法設計

1.1.1? ? 綜合運動函數

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

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

1）位置函數

對柵格進行賦值可以達到區分不同柵格的目的。設位置函數為[X]，如式（1）：

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

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

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

2）轉向置信函數

為控制無人機的航向，使其趨向未覆蓋區域，設置轉向信度函數[C]，如式（2）：

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

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

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

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

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

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

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

3）綜合運動函數

綜合考慮位置函數及轉向信度函數，重新定義一個綜合運動函數，作為下一飛行節點的選擇依據，其定義為：

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

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

1.1.2? ? ?死區逃離策略

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

1）環形搜索

當無人機陷入死區時，進行環形搜索。如圖5所示，灰色為已覆蓋節點或障礙物，藍色為正在搜索區域，紅色為搜索結束區域。以當前節點與未覆蓋節點之間的最短歐氏距離為半徑進行環形搜索，尋找未覆蓋節點。

2）A-star算法選擇路徑

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

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

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

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

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

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

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

1.1.3? ? ?運動優先級策略

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

1.2? ? 二維全覆蓋路徑規劃流程

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

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

1.3? ? 三維全覆蓋路徑規劃流程

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

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

2? ? 試驗及分析

2.1? ?仿真試驗及分析

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

1）區域覆蓋率

區域覆蓋率（[Cc]）表示為：

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

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

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

2）路徑重復率

路徑重復率[RR]可以表示為：

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

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

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

2.1.1? ? 二維環境仿真試驗

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

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

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

目前全覆蓋路徑規劃任務中使用比較多的方法有單元分解法以及生物激勵神經網絡算法等。使用以上2種算法對本文中的二維模擬地圖進行全覆蓋路徑規劃，使用覆蓋率、路徑長度、路徑重復率、路徑規劃時間以及陷入死區次數作為算法的性能指標，結果如表2所示。通過表中數據可以看出，雖然3種方法的區域覆蓋率都達到了100%，但從其他性能指標來看，本文提出的算法更具優勢。

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

2.1.2? ? 三維環境仿真試驗

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

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

2.2? ?運行測試及分析

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

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

3? ? ?結束語

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

參考文獻

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

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

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

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

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

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

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

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

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

[10]? ?韓忠華，畢開元，楊麗英，等.室內復雜環境下多旋翼無人機動態路徑規劃[J].中國慣性技術學報，2019，27（3）：366-372，377.

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

[12]? ?潘楠，陳啟用，劉海石，等.復雜工業品倉儲環境無人機庫盤任務規劃[J/OL].計算機集成制造系統，2021：1-17[2021-06-30].http：//kns.cnki.net/kcms/detail/11.5946.TP.20210318.0934.006.html.

[13]? ?孫靜，吳碧，許玉堂，等.復雜環境下無人機三維航跡規劃方法研究[J].彈箭與制導學報，2014，34（3）：170-174.

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

[15]? ?唐博文，王智文，胡振寰.基于事件驅動的無人機強化學習避障研究[J].廣西科技大學學報，2019，30（1）：96-102，117.

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

[17]? ?甘文洋，朱大奇.基于行為策略的AUV全覆蓋信度函數路徑規劃算法[J].系統仿真學報，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

（責任編輯：黎? 婭）