基于EMSDBO算法的無人機三維航跡規劃

摘 要：

針對無人機（unmanned aerial vehicle， UAV）三維航跡規劃問題，提出一種增強型多策略蜣螂算法的UAV航跡規劃方法。首先，將飛行接近率和響應時間的動態約束添加到威脅成本代價中，并考慮UAV轉彎性能的影響，建立三維任務空間模型與航跡代價函數。其次，在蜣螂算法中引入偏移估計策略、變螺旋搜索策略、準反向學習策略和逐維變異策略，提高算法的全局尋優能力和收斂速度。最后，給出了改進算法在三維環境下航跡規劃的仿真結果。結果表明：綜合考慮UAV機動性能和轉彎性能，規劃出的路徑可以更加安全有效地避開危險源。相比其他算法，改進算法的尋優能力更好，規劃的航跡質量更優。

關鍵詞：

無人機; 路徑規劃; 飛行接近率; 蜣螂優化算法

中圖分類號：

V 249

文獻標志碼： A""" DOI：10.12305/j.issn.1001-506X.2024.05.28

Three-dimensional path planning of UAV based on EMSDBO algorithm

SUI Dong， YANG Zhenyu*， DING Songbin， ZHOU Tingting

（College of Civil Aviation， Nanjing University of Aeronautics and Astronautics， Nanjing 211106， China）

Abstract：

In view of the unmanned aerial vehicle （UAV） three-dimensional path planning problem， an enhanced multi-strategy dung beetle algorithm of UAV path planning is proposed. Firstly， constraints on the flight proximity rate and response time are introduced and added to the threat cost， considering the influence of UAV turning performance， a three-dimensional task space model and trajectory cost function are established. Secondly， the dung beetle algorithm is enhanced by introducing offset estimation strategy， variable spiral search strategy， quasi-inverse learning strategy， and dimensional mutation strategy to improve the algorithm’s global optimization capability and convergence speed. Finally， simulation results of the improved algorithm for three-dimensional trajectory planning in an environment are presented. Results demonstrate that by considering both the maneuverability and turning performance of the UAV， the planned path can safely and efficiently avoid hazards. Compared to other algorithms， the enhanced multi-strategy dung beetle algorithm shows better optimization capability and generates higher-quality trajectories.

Keywords：

unmanned aerial vehicle （UAV）; path planning; flight proximity rate; dung beetle optimizer algorithm

0 引 言

由于無人機技術的飛速發展以及具有的成本效益和靈活優勢，無人機技術在軍事和民用領域得到了廣泛的應用，如物流配送、搜尋援救、農業生產、輔助通信等領域［1-3］。目前小型無人機多采用電池供電，攜帶的能源有限，執行任務的時間也有限［4］。因此，如何找到一條低能耗、高覆蓋、無碰撞的路徑，是無人機在路徑規劃領域面臨的關鍵問題。無人機三維路徑規劃可以看作是一個典型的復雜多約束全局優化問題［5］，即在綜合考慮任務需求和無人機性能約束的前提下在起點和終點之間搜索出較優的飛行路徑。

常見的路徑規劃算法有A*算法［6］、概率路線圖（pro-babilistic road map， PRM）算法［7］、快速探索隨機樹（rapidly expanding random tree， RRT）算法［8］、人工勢場法［9］、Dijkstra方法［10］等。傳統的路徑規劃方法雖然在數學理論上已經相當成熟，但在求解多目標無人機三維路徑規劃問題時，容易被局部最優解的問題制約。近年來，隨著隨機搜索理論的發展，許多新興群智能算法已經成功應用于路徑規劃問題，例如傳統的粒子群算法［11］、遺傳算法［12］，還有新提出的人工蜂群算法［13］、灰狼算法［14-15］、蝙蝠算法［16］等。目前無人機三維航跡規劃問題主要問題存在于建模的合理性和安全性以及在復雜地理環境下算法的求解精度和全局尋優能力。在建模改進方面，文獻［16］根據危險源的數量和與危險源的距離對子路徑進行分割，通過威脅權重因子分別計算子路徑的威脅代價;文獻［17］采用雙層路徑規劃方法，在底層建立馬爾可夫決策過程控制無人機沿航路的運動，將無人機控制分成不同的離散動作，設定獎勵函數來減少碰撞的風險。上述研究中的建模過程中，在考慮避障時，多是以與障礙物間的距離作為判斷條件，而在實際中更應綜合考慮無人機機動性能和轉彎性能，從而規劃出一條更加安全且符合實際的路徑。在算法改進方面，文獻［18］提出一種球形向量的粒子群優化算法，引入球面坐標向量的仰角和方位角實現對無人機的俯仰角和轉向角的性能約束，顯著地減少搜索空間;文獻［19］提出一種多機制協同優化的灰狼算法，引入邊界更新的處理機制，并結合高斯變異和螺旋策略的擾動機制，增強算法跳出局部最優解和全局尋優的能力。但由于三維路徑規劃問題搜索空間較大、約束條件較多，上述改進在一定程度上有助于提高算法的路徑規劃質量，但也受限于傳統算法本身的特性。

本文在建模改進上，基于碰撞避讓的思想，在避障時引入飛行接近率和響應時間的概念，根據飛行接近率動態設置相應的最小安全距離，并考慮其實際轉彎性能;在算法改進方面，在蜣螂優化（dung beetle optimizer， DBO）算法［20］的基礎上進行策略改進，提出一種增強型的多策略DBO（enhanced multi-strategy DBO， EMSDBO）算法，在標準函數和建立的無人機三維航跡模型進行仿真驗證。實驗結果表明，在保證快速安全尋優的前提下，改進的算法能夠規劃得到更優的無人機飛行航跡。

1 無人機航跡規劃

1.1 問題描述

航跡規劃最主要的目的就是在已知飛行區域內生成一條能夠在規定時間內從起飛點S到達目標點D、且安全避開飛行區域危險源的最優路徑。本文將真實的環境中存在的危險源N簡化設定為圓柱體模型，數量為T。首先引用球坐標系，將坐標向量與無人機偏轉角與俯仰角之間產生相互關系［18］，在縮小搜索空間的同時也綜合考慮了無人機的性能約束;然后，通過隨機產生一組滿足約束的離散航跡點（Ω1，Ω2，…，Ωn），將位置轉換到笛卡爾坐標系后，并采用B樣條曲線進行航跡平滑處理最終得到一條滿足約束的航跡，如圖1所示。下面將對球坐標系轉換和航跡平滑曲線分別進行介紹。

（1） 球坐標系轉換

無人機航跡規劃應當考慮無人機的性能參數，本文采用球坐標系對無人機偏轉角和俯仰角進行約束。在球坐標系（ρ，，φ）中，其中ρ表示航段的距離，表示俯仰角，表示偏轉角。路徑中包含n個航路點，在得到球坐標下的航路點坐標Ω后，需要先將坐標轉換到笛卡爾坐標系下的位置P，P=（p1，p2，…，pn），其中第i個航路點的坐標pi=（xi，yi，zi），在笛卡爾坐標系下的位置更新方式如下所示：

3 仿真與驗證

本文實驗均在Intel Core i7CPU， 3.00 GHz，16 GB內存，Windows10（64位）的測試環境中進行。實驗首先將改進的EMSDBO算法和其他優化算法進行對比，驗證改進算法的優越性;然后，將不同改進策略進行對比，進行不同引進策略的有效性分析;最后，在本文建立無人機航跡規劃模型中，將EMSDBO算法和其他路徑規劃算法在相同條件下進行三維航跡規劃仿真，驗證該算法在航跡規劃中的有效性。

3.1 標準函數測試

為了驗證改進算法的性能，將本文改進的EMSDBO算法與灰狼優化（grey wolf optimizer， GWO）算法［31］、北方蒼鷹優化（northern goshawk optimization， NGO）算法［32］、WOA和DBO算法在測試函數上進行比較。實驗選取了6種基準測試函數，測試函數的維度和搜索范圍如表2所示。其中f1～f4是單峰基準測試函數，f5～f6是多峰基準測試函數。各個算法種群數均設為30，迭代次數為500，為了降低實驗的偶然性，增加實驗結果的說服力，將各個算法分別在6種基準測試函數上分別獨立運行50次，計算求得函數的最優值、平均值和標準差。得到的數據結果如表3所示，不同優化算法在6種基準測試函數上的收斂曲線圖如圖3所示。

由函數收斂曲線圖和實驗結果可以直觀地看出，改進后的EMSDSO算法在不同測試函數中尋優能力均表現較好。相較于其他四種算法，在單峰測試函數f1～f4上EMSDSO的求解精度更好且收斂速度更快;在多峰測試函數f5～f6上EMSDSO跳出局部最優的能力更強。由此看出，上文提出改進策略是有效的，且EMSDBO的求解效果和魯棒性一致要比其他算法好且更加穩定，具有較強的尋優能力。

3.2 改進策略分析

為了進一步證明上述幾種不同改進策略對DBO算法性能的提升作用，本文選取單策略改進算法進行對比，即只引進偏移估計策略的ODBO、只引進變螺旋搜索策略的SDBO、只引進自適應準反向學習策略的QDBO和只引進混合逐維變異策略的VDBO。將4種單策略改進算法和DBO、EMSDBO在測試函數進行尋優對比，實驗結果如表4所示。

由表中數據可知，在函數f1～f2的尋優過程中，QDBO中采用的反向學習策略起決定性作用，其他策略對于函數的尋優也有一定的輔助作用。在函數f3～f4的尋優過程中所有改進策略均不同程度的提高了算法的尋優性能，其中逐維變異策略在函數f3上的尋優貢獻占主導，變螺旋搜索策略在函數f4上的尋優貢獻占主導，但多策略融合起來對于算法的尋優性能提升效果最佳。在函數f7～f8的尋優過程中，各種改進策略的算法均能找到函數最優值。通過上述數據的對比可以發現，各個改進策略對于算法尋優性能的提升均提供了不同程度的幫助。

3.3 實驗參數設置

通過讀取數字高程模型（digital elevation model， DEM）地圖來獲得真實的地形數據，對應于真實環境中山區地形。本文DEM數據由ALOSPALSAR數據庫得到，根據DEM得到高程點，并將其均勻地離散在1 000×1 000的坐標空間內。x軸表示東經，x∈［0，1 000］，y軸表示北緯，y∈［0，1 000］，z軸表示每一個坐標點（x，y）的真實高度。仿真實驗參數和約束條件設置如表5所示。

威脅代價計算通常是以到危險源的距離作為評價指標，建立以固定最小距離的場景1和場景2用于與本文場景進行比較。場景1是將與危險源的避障最小距離設置為固定10 m;場景2是將與危險源的避障最小距離設置為固定60 m;將上述兩場景與本文添加了最小響應時間和飛行接近率的動態約束場景進行仿真實驗對比，飛行速度均取v2。種群數量設為150，迭代次數為200。無人機的起點坐標為（150，200，100），終點坐標為（950，700，100）。危險源參數（xt，yt，rt）=（550，450，150）。

然后，采用EMSDBO算法、球形矢量粒子群優化（spherical vector-based particle swarm optimization， SPSO）算法［18］、改進麻雀搜索算法［33］（modified sparrow search algorithm， CASSA）以及DBO共四種算法進行航跡仿真算法對比實驗，同樣種群數量設為150，迭代次數為200。起點和終點坐標分別為（200，50，100）和（1 000，720，200）。危險源坐標（xj，yj，rj）設置為［（340，230，40），（230，500，60），（430，400，50），（380，640，40），（560，220，50），（705，395，60），（580，600，60），（830，240，40），（800，650，50），（920，480，50）］。

3.4 實驗結果分析

3種威脅場景下的飛行路徑如圖4所示，實線表示危險源邊界，虛線表示危險區域邊界。重復50次實驗求得3種場景下的平均最小響應時間、平均航程距離和平均威脅代價，如表6所示。場景1當與危險源固定避障距離設定較小時，雖然航程代價相比于本文場景減少了4.0%，但同時威脅成本代價增加了34.9%，且該場景下的平均響應時間為1.23 s，此時響應時間過小，會增加與危險源發生碰撞的風險。而場景2與危險源固定避障距離設定較大時，雖然威脅代價相比于本文場景減少了37.5%，但同時航程距離增加了4.9%，該場景下平均響應時間為11.48 s，此時會使規劃路徑距離不必要的增加，造成不必要的能源浪費。本文場景引入飛行接近率和響應時間的概念，相較于場景1和場景2，平均最小響應時間為5.68 s，響應時間較為充足且合理，航程距離與威脅代價也較為適中，說明考慮了飛行接近率的影響，通過設定合適的最小響應時間，添加接近距離的動態約束，并且綜合考慮無人機的機動性能和轉彎性能，會使規劃的路徑更加合理、安全且符合實際。

然后是進行4種不同航跡規劃算法在本文場景下的航跡對比，不同算法規劃的三維航跡圖和航跡俯視圖分別如圖5和圖6所示。可以看出，相較于其他算法，EMSDBO算法規劃的路徑更加光滑并且航程距離相對較短，規劃的航跡質量更優，在多障礙物的環境下能夠以合適的轉彎率和飛行接近率更安全的通過危險區域附近，盡可能減少了威脅代價，更符合實際飛行情況。

4種算法的收斂曲線如圖7所示，從迭代曲線圖中可以發現，EMSDBO算法求解精度更高，規劃的路徑質量更高，收斂速度更快。4種算法各進行50次實驗后得到的平均結果如表7所示，SPSO算法存在尋路失敗的情況，算法的收斂精度和穩定性均較差;CASSA算法的收斂精度差，但穩定性較好;DBO算法求解穩定性較好，但收斂精度較差，同時也存在尋路失敗的情況。EMSDBO算法規劃的航跡，相比SPSO算法、CASSA算法和DBO算法，其在航跡距離方面分別下降了11.9%、13.4%和10.9%;在路徑光滑方面相比下降了37.4%、43.4%和36.6%;在高度變化方面相比下降了27.7%、27.9%和36.4%;在威脅代價方面相比SPSO和CASSA下降了14.6%和28.1%。圖8是4種算法總代價函數的箱線圖結果，圖中實線代表中值線，虛線代表均值線。總代價函數的平均值相比SPSO、CASSA和DBO分別下降了14.1%、15.0%和12.7%。由此可以說明EMSDBO規劃出的航跡長度冗余少，沒有頻繁的高度變化，路徑的光滑程度更好，航跡的質量更優，且算法的穩定性更好。

4 結束語

本文在解決無人機航跡規劃問題時，以航跡距離、光滑程度、高度變化、威脅成本作為評價指標，引入飛行接近率與響應時間的概念，并綜合考慮無人機機動性能和轉彎性能，最大程度地避免與危險源的碰撞可能，使得規劃的路徑更為安全。在求解航跡規劃問題時，本文提出的EMSDBO算法，在DBO的基礎上，引入了偏移估計策略、變螺旋搜索策略、自適應準反向學習策略和混合變異策略等多種改進策略，以增加種群多樣性，提高算法的全局尋優能力和收斂速度。仿真實驗結果表明：相比于只考慮與危險源的距離，考慮飛行接近率與轉彎率的影響會使得生成的飛行路徑更加安全且合理;改進后的算法具有更強的全局搜索能力，能夠穩定地規劃出一條可行且安全的飛行路徑。未來的工作將從兩個方面繼續開展，在本文的基礎上首先進行動態環境下的無人機三維路徑的實時重規劃，同時探索無人機群的協同路徑規劃方法。

參考文獻

［1］ CHAO D， WU Q H. Survey of layered architecture in large-scale FANETs［J］. Computer Science， 2020， 47（9）： 226-231.

［2］ 趙暢， 劉允剛， 陳琳， 等. 面向元啟發式算法的多無人機路徑規劃現狀與展望［J］. 控制與決策， 2022， 37（5）： 1102-1115.

ZHAO C， LIU Y G， CHEN L， et al. Research and development trend of multi-UAV path planning based on metaheuristic algorithm［J］. Control and Decision， 2022， 37（5）： 1102-1115.

［3］ 楊旭， 王銳， 張濤. 面向無人機集群路徑規劃的智能優化算法綜述［J］. 控制理論與應用， 2020， 37（11）： 2291-2302.

YANG X， WANG R， ZHANG T. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization［J］. Control Theory amp; Applications， 2020， 37（11）： 2291-2302.

［4］ ZENG Y， ZHANG R. Energy-efficient UAV communication with trajectory optimization［J］. IEEE Trans.on Wireless Communications， 2017， 16（6）： 3747-3760.

［5］ AGGARWAL S， KUMAR N. Path planning techniques for unmanned aerial vehicles： a review， solutions， and challenges［J］. Computer Communications， 2020， 149（1）： 270-299.

［6］ WANG H B， YIN P H， ZHENG W， et al. Mobile robot path planning based on improved A* algorithm and dynamic window method［J］. Robot， 2020， 42（3）： 92-99.

［7］ LI W M， WANG L， ZOU A W， et al. Path planning for UAV based on improved PRM［J］. Energies， 2022， 15（19）： 7267-7283.

［8］ MIN Y， LUO J J， WANG M M， et al. Coordinated path planning by integrating improved RRT*and quartic spline［J］. Chinse Journal of Mechanics，2020， 52（4）： 1024-1034.

［9］ QI B K， LI M Q， YANG Y， et al. Research on UAV path planning obstacle avoidance algorithm based on improved artificial potential field method［J］. Journal of Physics： Conference Series， 2021， 1948（1）： 012060.

［10］ JIANG C K， LI Z， PAN S B， et al. Collision-free path planning of AGVs based on improved dijkstra algorithm［J］. Computer Science， 2020， 47（8）： 272-277.

［11］ WANG Y H， WANG S M. UAV path planning based on improved particle swarm optimization［J］. Computer Engineering amp; Science， 2020， 42（9）： 1690-1696.

［12］ CAO Y， WEI W Y， BAI Y， et al. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm［J］. Cluster Computing， 2019， 22（1）： 5175-5184.

［13］ ZHANG X M， HU Y J， LI W G， et al. Mission planning of multi base UAV based on improved artificial bee colony algorithm［J］. Journal of Physics： Conference Series， 2020， 1550（3）： 32072-32096.

［14］ JARRAY R， AL-DHAIFALLAH M， REZK H， et al. Parallel cooperative coevolutionary grey wolf optimizer for path planning problem of unmanned aerial vehicles［J］. Sensors， 2022， 22（5）： 1826-1848.

［15］ 劉志強， 何麗， 袁亮， 等. 采用改進灰狼算法的移動機器人路徑規劃［J］. 西安交通大學學報， 2022， 56（10）： 49-60.

LIU Z Q， HE L， YUAN L， et al. Path planning of mobile robot based on TGWO algorithm［J］. Journal of Xi’an Jiaotong University， 2022， 56（10）：49-60.

［16］ LIN N， TANG J C， LI X W， et al. A novel improved bat algorithm in UAV path planning［J］. Computers， Materials amp; Continua， 2019， 61（1）： 323-344.

［17］ YU W W， LIU J， ZHOU J. A novel sparrow particle swarm algorithm （SPSA） for unmanned aerial vehicle path planning［J］. Scientific Programming， 2021， 2021（1）： 5158304.

［18］ PHUNG M D， HA Q P. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization［J］. Applied Soft Computing， 2021， 107（1）： 107376-107395.

［19］ ZHAI L Z， FENG S H. A novel evacuation path planning method based on improved genetic algorithm［J］. Journal of Intelligent amp; Fuzzy Systems， 2022， 42（3）： 1813-1823.

［20］ XUE J K， SHEN B. Dung beetle optimizer： a new meta-heuristic algorithm for global optimization［J］. The Journal of Supercomputing， 2023， 79： 7305-7336.

［21］ GUO J J， YUAN W C， DANG X Z， et al. Cable force optimization of a curved cable-stayed bridge with combined simulated annealing method and cubic B-Spline interpolation curves［J］. Engineering Structures， 2019， 201（1）： 109813.

［22］ 張洪海， 鄒依原， 張啟錢， 等. 未來城市空中交通管理研究綜述［J］. 航空學報， 2021， 42（7）： 82-106.

ZHANG H H， ZOU Y Y， ZHANG Q Q， et al. Future urban air mobility management： review［J］. Acta Aeronautica et Astronautica Sinica， 2021， 42（7）： 82-106.

［23］ 張軍峰， 蔣海行， 武曉光， 等. 基于BADA及航空器意圖的四維航跡預測［J］. 西南交通大學學報， 2014， 49（3）： 553-558.

ZHANG J F， JIANG H X， WU X G， et al. 4D trajectory prediction based on BADA and aircraft intent［J］. Journal of Southwest Jiaotong University， 2014， 49（3）： 553-558.

［24］ JIANG H， DENG J H， CHEN Q S. Olfactory sensor combined with chemometrics analysis to determine fatty acid in stored wheat［J］. Food Control， 2023， 153： 109942-109961.

［25］ WU C L， FU J C， HUANG X R， et al. Lithium-ion battery health state prediction based on VMD and DBO-SVR［J］. Energies， 2023， 16（10）： 3993-4012.

［26］ ZHU F， LI G S， TANG H， et al. Dung beetle optimization algorithm based on quantum computing and multi-strategy fusion for solving engineering problems［J］. Expert Systems with Applications， 2024， 236（1）： 121219-121237.

［27］ HAUSCHILD M， PELIKAN M. An introduction and survey of estimation of distribution algorithms［J］. Swarm and evolutionary computation， 2011， 1（3）： 111-128.

［28］ MIRJALILI S， LEWIS A. The whale optimization algorithm［J］. Advances in Engineering Software， 2016， 95（1）： 51-67.

［29］ WANG H， WU Z J， RAHNAMAYAN S， et al. Enhancing particle swarm optimization using generalized opposition-based learning［J］. Information Sciences， 2011， 181（20）： 4699-4714.

［30］ ZHANG X M， WANG D D， FU Z H， et al. Novel biogeography-based optimization algorithm with hybrid migration and global-best Gaussian mutation［J］. Applied Mathematical Mo-delling， 2020， 86（1）： 74-91.

［31］ MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer［J］. Advances in Engineering Software， 2014， 69（1）： 46-61.

［32］ DEHGHANI M， HUBALOVSKY S， TROJOVSKY P. Nor-thern goshawk optimization： a new swarm-based algorithm for solving optimization problems［J］. IEEE Access， 2021， 9（1）： 162059-162080.

［33］ LIU G Y， SHU C， LIANG Z W， et al. A modified sparrow search algorithm with application in 3D route planning for UAV［J］. Sensors， 2021， 21（4）： 1224-1245.

作者簡介

隋 東（1971—），男，副教授，博士，主要研究方向為空域規劃與安全性分析。

楊振宇（1998—），男，碩士研究生，主要研究方向為無人機路徑規劃和空域網絡運行。

丁松濱（1964—），男，教授，博士，主要研究方向為飛機性能與安全工程。

周婷婷（1998—），女，碩士研究生，主要研究方向為空域網絡運行研究。