基于遺傳算法的無人機三維航跡規劃研究

何光勤

摘要：近年來，隨著無人機在各個領域的廣泛應用，無人機的航跡規劃問題成為研究的熱點，本文通過分析地形條件以及無人機自身性能對航跡規劃的影響，研究無人機三維規劃問題。在數字地圖預處理的基礎上，對基準地形以及障礙區域進行建模，建立等效的環境數字地圖，并采用樣條插值法對地形進行平滑處理，降低搜索空間。在此基礎上建立帶有懲罰函數的評價目標，使用遺傳算法完成了無人機的三維航跡規劃。實驗結果表明：遺傳算法不僅能夠完成無人機的規劃任務，生成短而平滑的路徑，而且能夠獲得很好的收斂效果，為各種實際任務提供技術支持。

Abstract： In recent years， with the wide application of Unmanned Aerial Vehicles（UAVs）， flight path planning for UAVs has become a hot research topic. This paper studies the three-dimensional planning for UAVs by considering the terrain conditions and the influence of UAV's performance on the planning. Based on the preprocessing of the digital map， the reference terrain and the obstacle area are modeled， an equivalent environmental digital map is built， and smoothed by the spline interpolation method， which reduces the search space. Moreover， the evaluation target with a penalty function is set and the genetic algorithm was applied to complete the 3D flight path planning for UAVs. The experimental results show that the genetic algorithm can not only complete the planning task for drones， generate a short and smooth path， but also obtain good convergence and provide technical support for various practical missions.

關鍵詞： 無人機;環境建模;路徑規劃;遺傳算法

0? 引言

無人機航跡規劃是無人機應用的關鍵技術之一，它的主要功能是依靠無人機系統自身性能，在脫離人工干預的情況下，根據特定的環境條件，自動搜尋出一條從起始點到目標點的最優路徑，使得無人機能夠安全高效的完成特定任務[1]。無人機路徑規劃是NP難問題，如何對其進行更好的規劃極具挑戰。為此，各國學者針對此問題做了大量的研究工作。在二維路徑規劃方面，文獻[2-3]應用改進的A*算法對搜索空間進行求解，有效的解決了搜索空間大及搜索復雜度高的問題;文獻[4]對蟻群算法進行研究，提出了適用于無人機航路規劃的優化算法，兼顧最小探測概率以及最短路，生成一條可接受的無人機飛行路徑;文獻[5]對傳統的快速擴展隨機樹（RRT）算法進行改進，采用改進算法（RRT*算法）對無人機路徑進行規劃，獲得了更好的航跡代價值;文獻[6]在傳統人工勢場法的基礎上選取適當的增益系數，解決了目標不可達問題，最終優化出圓滑的最優路徑。文獻[7]提出了一種基于Voronoi圖的航路規劃方法，并結合蟻群算法對無人機航路進行規劃，提升了無人機在多威脅情況下的航路規劃效率。盡管在二維路徑規劃方面已經有了較為成熟的研究成果，但是上述方法忽略了無人機的三維機動能力以及三維搜索空間的復雜度，難以滿足實際需求，故許多學者開始對無人機三維路徑規劃進行研究。文獻[8]引入虛擬地形以消除大量搜索空間，將三維空間降至二維，隨后采用改進的A*算法生成無人機航跡;文獻[9]通過對搜索區域進行網格離散化提出了一種新的無人機三維路徑規劃方法，此法可以在滿足多目標約束的條件下生成較為理想的無人機路徑;文獻[10]提出基于蟻群優化算法的無人機路徑規劃算法獲得了無人機三維路徑;文獻[11]應用粒子群算法和遺傳算法變異算子的思想來改進原始的中心力優化（CFO）算法，提出了一種采用改進的中心力優化（MCFO）對無人機進行路徑規劃，生成了有效的無人機路徑。盡管三維路徑規劃已經有了長足的進展，但是相較于二維路徑規劃，三維路徑規劃考慮了高度限制及地形約束，搜索空間激增，問題的復雜度也呈指數增長。在求解過程中容易遇到陷入局部最優解以及收斂速度慢，甚至無法收斂的問題。

因此，針對無人機三維路徑規劃問題，本文提出了一種適合無人機三維實地飛行的路徑規劃方法。該方法在滿足無人機自身性能約束條件下，對數字地圖進行預處理，完成網格劃分，并在此基礎上，使用遺傳算法對無人機三維航跡進行規劃，最終得到無人機飛行的最優三維路徑。

1? 數字地圖的預處理

對數字地圖進行預處理不僅可以獲得虛擬的客觀環境，為無人機的路徑規劃提供實際的仿真模擬條件，而且可以驗證規劃算法的實用性。地形數據的預處理主要包括數字地圖的獲取、地形信息截取、高程信息提取以及生成經緯高坐標序列4個階段。

根據任務地區的經緯度信息在google earth上進行定位，對該區域范圍進行鎖定，進行地形數據采集，隨后利用google earth 高程信息商業軟件獲取所需高程信息，并最終導出經度、緯度以及高度的坐標信息，以文本形式儲存。

2? 無人機航跡規劃建模

2.1 建立環境模型

2.1.1 基準地形建模

無人機三維航跡規劃問題與任務區域的真實地理環境息息相關。針對任務區域的地形環境進行建模時不僅要考慮明顯的山體特征，還要對地形起伏的基準地形進行考量。由于地形信息的準確度與精細度是影響航路規劃質量的關鍵，故本文采取文獻[12]中的地形模擬函數對真實地形進行建模：

2.1.2? 障礙區域建模

針對障礙區域建模，本研究對較高的自然山體采用山峰模型[13]，具體的數學表達式如下：

其中， z2（x，y）表示每個投影到平面的點坐標（x，y）的高程值，hi表示第i座山的高度，（xi，yi）是第i座山峰的中心坐標，xsi和ysi分別是山峰沿x軸和y軸上的坡度，值越大坡度越大。

由于實際地形起伏較為復雜，考慮到飛機性能以及計算方便，本研究采用三次樣條插值法對實際地形進行平滑處理。具體處理方式如下：

假定x0，xn是兩個端點，要在兩點之間插入n-1個點，需構造形如式（3）的樣條函數s（x），且s（x）滿足插值條件式（4）和式（5）。

2.1.3 等效數字地圖

針對任務區三維空間，本研究利用上述方法分別對基準地形以及障礙區域進行建模，并將其轉換為計算機可以處理的數據類型，然后將地形高程信息與障礙區域高程信息進行融合，建立等效的環境數字地圖，如圖1所示。具體的融合模型如下：

2.2 約束條件

2.2.1 航跡長度

無人機航跡由一系列導航點{xi，yi，zi | i=1，2，…，n}組成，其中（xi，yi，zi）表示第i個導航點的三維坐標取值，（xi，yi，zi）表示起點，（xn，yn，zn）表示終點，基于此，無人機路徑長度值為：當然無人機路徑長度L越短越好。

2.2.2 最低飛行高度

最低飛行高度是指垂直方向上無人機距離障礙物的最小距離。在低空空域進行飛行時，飛行高度h必須滿足h？叟hmin才能保證無人機不會碰撞，其中hmin為最低飛行高度。

2.2.3 最大偏航角

無人機的最大偏航角是指無人機在航路飛行過程中允許的最大轉彎角，其值的大小取決于無人機自身性能以及物理條件。假設相鄰節點坐標分別為（x1，y1，z1）和（x2，y2，z2），最大偏航角為αmax，則滿足：

2.2.4 最大俯仰角

無人機的最大俯仰角是指無人機在爬升以及下降過程中機身縱軸能夠與水平方向達到的最大角度，其值完全取決于無人機縱向性能約束。假設相鄰節點坐標分別為 （x1，y1，z1）和（x2，y2，z2），最大俯仰角為βmax，則滿足：

2.3 航跡評價函數

無人機的三維路徑規劃既要保證飛行任務的順利實施，還要滿足無人機的機動性能限制。綜合考慮無人機的航路長度、最低飛行高度、最大偏航角以及最大俯仰角等的限制，生成一條最短航路。

同時，在無人機路徑規劃過程中，需要考慮避障問題，本研究采用懲罰函數法對不滿足避障要求的導航點進行懲罰，評價函數F定義如下：

其中，pf為懲罰系數，取值為正數，I（xi，yi，zi）為示性函數，當點（xn，yn，zn）滿足避障要求時，I（xi，yi，zi）為0;當點（xn，yn，zn）不滿足避障要求時，I（xi，yi，zi）為1。

3? 遺傳算法

遺傳算法（Genetic Algorithm，GA）是模仿生物進化機制而演變的現代仿生學方法，它是一種隨機全局搜索優化算法。通過種群初始化、染色體的選擇、交叉、變異等操作獲取問題最優解[14]。具體操作步驟如下：

3.1 染色體編碼

在染色體編碼中常用二進制和實數編碼兩種方式，本研究采用實數編碼方式對染色體進行編碼操作，通過unifrnd命令生成0到1之間的隨機數，編碼長度與決策變量個數相同。此種編碼方式精度高，有利于多維空間的搜索。

3.2 個體適應度

個體適應度函數反映了種群染色體的質量，其值大小直接決定了個體能否進入下一代的概率，因此非常關鍵。考慮到本文的評價函數是求解無人機的最短路徑，故選取評價函數的倒數作為個體適應度函數，二者的關系如下：

3.3 選擇

本算法采用輪盤賭與精英保留策略相結合的方法對個體進行選擇，根據個體適應度值進行排序，對排在前1/3的個體采取精英保留策略，其它個體采用輪盤賭選擇，個體被選中的概率為

其中， N為種群個數，Zi為種群適應度值。此種選擇策略既保留了種群最優個體，同時也保證了種群多樣性。

3.4 交叉

考慮到編碼方式為整數編碼，故本算法采用整數交叉法如式（13）對染色體進行交叉操作，產生新的染色體。

3.5 變異

以一定的概率對染色體進行變異操作，增強算法局部搜索能力的同時，保證了種群多樣性。本研究選用單點高斯變異的方法[15]對個體進行變異操作，即在滿足均值為μ，方差為σ2的正態分布里隨機生成一個數來代替原有基因值。具體方法如下：

4? 仿真實驗

實驗中，算法均采用matlab2016a編程實現，運行環境為：win10 專業版、Inter（R）Xeon（R） W-2133 CPU @ 3.6GHz 處理器，64G內存，64位操作系統。

相關參數的設置如下：起始坐標為（25，90，64），目標點坐標為（40，30，2），最大偏航角αmax=60°，最大俯仰角βmax=30°、最低飛行高hmin=60m。在遺傳算法中，種群數量N=50，最大迭代次數I=300，交叉變異概率分別為Pc=0.7，? Pm=0.3。

Matlab仿真結果如圖2-圖4所示，圖2為三維空間航跡規劃圖，圖3為二維空間航跡規劃圖，圖4為評價函數迭代曲線。

5? 總結

針對無人機的三維航跡規劃問題，本文通過對數字地圖預處理，將地形高程信息與障礙區域高程信息進行融合，根據飛行器的性能指標，給出了地圖平滑處理手段，在此基礎上設計帶有懲罰的代價函數，采用傳統遺傳算法對三維地形下的無人機航跡進行航跡規劃，根據仿真結果得出以下結論：

①對實際地形進行平滑處理，可以極大的減小搜索空間，減小算法復雜度;

②遺傳算法具有很好的收斂效果，可以生成短而平滑的航跡，從而高效完成無人機的飛行任務;

③數字地圖的預處理需要借助google earth等軟件協助完成，因此本文提到的算法僅能滿足離線規劃任務需求。

本文的研究重點是無人機靜態的三維航跡規劃問題，在建模時僅將地形障礙以及無人機自身性能作為約束條件，并未考慮實際飛行任務中的氣象條件以及通信條件，在后期工作中將結合實際任務區域的氣象條件以及通信條件等，對無人機的三維動態航跡規劃問題進行研究，以期為無人機的完成飛行任務提供更好的技術支持。

參考文獻：

[1]史紅玉，劉淑芬.基于Voronoi圖的無人機航路改進規劃[J].吉林大學學報，2018，56（4）：945-952.

[2]Szczerba R J， Galkowski P， Glicktein I S， et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems， 2000， 36（3）： 869-878.

[3]馬立.基于改進 A～*算法的無人機動態航跡規劃[J].現代導航，2018，9（1）：60-64.

[4]白俊強，柳長安.基于蟻群算法的無人機航路規劃[J].飛行力學，2005， 23（2）：9-12.

[5] Alejo D ， Cobano J A ， Heredia G ， et al. Efficient Trajectory Planning for WSN Data Collection with Multiple UAVs[J]. Studies in Computational Intelligence， 2015， 604：53-75.

[6]張建英，劉暾.基于人工勢場法的移動機器人最優路徑規劃[J].航空學報：2007，28：183-188.

[7]王壯，劉聰鋒，蔡嘯.一種基于Voronoi圖的航路規劃方法[J].船舶電子對抗：2017，40（4）：76-80.

[8]Qi Z ， Shao Z ， Ping Y S ， et al. An Improved Heuristic Algorithm for UAV Path Planning in 3D Environment[C]// International Conference on Intelligent Human-machine Systems & Cybernetics. IEEE， 2010.

[9]Babel L . Three-dimensional Route Planning for Unmanned Aerial Vehicles in a Risk Environment[J]. Journal of Intelligent & Robotic Systems， 2013， 71（2）：255-269.

[10]Zhang C ， Zhen Z ， Wang D ， et al. UAV Path Planning Method Based on Ant Colony Optimization[C]// Chinese Control & Decision Conference. 2010.

[11]Chen Y ， Yu J ， Mei Y ， et al. Modified central force optimization （MCFO） algorithm for 3D UAV path planning[J]. Neurocomputing， 2016， 171（C）：878-888.

[12]賈廣芝.基于遺傳算法和稀疏A*算法的無人機三維航跡規劃研究[D].南京：南京郵電大學，2017.

[13]馬云紅，張恒，齊樂融.基于改進 A*算法的三維無人機路徑規劃[J/OL].電光與控制http：//kns.cnki.net/kcms/detail/41.1227.tn.20190624.1645.016.html.

[14]李楠，劉朋，鄧人博，張建華.基于改進遺傳算法的無人機三維航路規劃[J].計算機仿真，2017，34（12）：22-25，35.

[15]王寧，魏利勝.一種基于 GA 的新型生物地理學優化算法研究[J/OL].系統仿真學報.http：//kns.cnki.net/kcms/detail/11.3092.v.20190531.1702.025.html.