基于遺傳算法的無人機(jī)三維航跡規(guī)劃研究

何光勤

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

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.

關(guān)鍵詞： 無人機(jī);環(huán)境建模;路徑規(guī)劃;遺傳算法

0? 引言

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

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

1? 數(shù)字地圖的預(yù)處理

對數(shù)字地圖進(jìn)行預(yù)處理不僅可以獲得虛擬的客觀環(huán)境，為無人機(jī)的路徑規(guī)劃提供實(shí)際的仿真模擬條件，而且可以驗(yàn)證規(guī)劃算法的實(shí)用性。地形數(shù)據(jù)的預(yù)處理主要包括數(shù)字地圖的獲取、地形信息截取、高程信息提取以及生成經(jīng)緯高坐標(biāo)序列4個(gè)階段。

根據(jù)任務(wù)地區(qū)的經(jīng)緯度信息在google earth上進(jìn)行定位，對該區(qū)域范圍進(jìn)行鎖定，進(jìn)行地形數(shù)據(jù)采集，隨后利用google earth 高程信息商業(yè)軟件獲取所需高程信息，并最終導(dǎo)出經(jīng)度、緯度以及高度的坐標(biāo)信息，以文本形式儲存。

2? 無人機(jī)航跡規(guī)劃建模

2.1 建立環(huán)境模型

2.1.1 基準(zhǔn)地形建模

無人機(jī)三維航跡規(guī)劃問題與任務(wù)區(qū)域的真實(shí)地理環(huán)境息息相關(guān)。針對任務(wù)區(qū)域的地形環(huán)境進(jìn)行建模時(shí)不僅要考慮明顯的山體特征，還要對地形起伏的基準(zhǔn)地形進(jìn)行考量。由于地形信息的準(zhǔn)確度與精細(xì)度是影響航路規(guī)劃質(zhì)量的關(guān)鍵，故本文采取文獻(xiàn)[12]中的地形模擬函數(shù)對真實(shí)地形進(jìn)行建模：

2.1.2? 障礙區(qū)域建模

針對障礙區(qū)域建模，本研究對較高的自然山體采用山峰模型[13]，具體的數(shù)學(xué)表達(dá)式如下：

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

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

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

2.1.3 等效數(shù)字地圖

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

2.2 約束條件

2.2.1 航跡長度

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

2.2.2 最低飛行高度

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

2.2.3 最大偏航角

無人機(jī)的最大偏航角是指無人機(jī)在航路飛行過程中允許的最大轉(zhuǎn)彎角，其值的大小取決于無人機(jī)自身性能以及物理?xiàng)l件。假設(shè)相鄰節(jié)點(diǎn)坐標(biāo)分別為（x1，y1，z1）和（x2，y2，z2），最大偏航角為αmax，則滿足：

2.2.4 最大俯仰角

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

2.3 航跡評價(jià)函數(shù)

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

同時(shí)，在無人機(jī)路徑規(guī)劃過程中，需要考慮避障問題，本研究采用懲罰函數(shù)法對不滿足避障要求的導(dǎo)航點(diǎn)進(jìn)行懲罰，評價(jià)函數(shù)F定義如下：

其中，pf為懲罰系數(shù)，取值為正數(shù)，I（xi，yi，zi）為示性函數(shù)，當(dāng)點(diǎn)（xn，yn，zn）滿足避障要求時(shí)，I（xi，yi，zi）為0;當(dāng)點(diǎn)（xn，yn，zn）不滿足避障要求時(shí)，I（xi，yi，zi）為1。

3? 遺傳算法

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

3.1 染色體編碼

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

3.2 個(gè)體適應(yīng)度

個(gè)體適應(yīng)度函數(shù)反映了種群染色體的質(zhì)量，其值大小直接決定了個(gè)體能否進(jìn)入下一代的概率，因此非常關(guān)鍵?？紤]到本文的評價(jià)函數(shù)是求解無人機(jī)的最短路徑，故選取評價(jià)函數(shù)的倒數(shù)作為個(gè)體適應(yīng)度函數(shù)，二者的關(guān)系如下：

3.3 選擇

本算法采用輪盤賭與精英保留策略相結(jié)合的方法對個(gè)體進(jìn)行選擇，根據(jù)個(gè)體適應(yīng)度值進(jìn)行排序，對排在前1/3的個(gè)體采取精英保留策略，其它個(gè)體采用輪盤賭選擇，個(gè)體被選中的概率為

其中， N為種群個(gè)數(shù)，Zi為種群適應(yīng)度值。此種選擇策略既保留了種群最優(yōu)個(gè)體，同時(shí)也保證了種群多樣性。

3.4 交叉

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

3.5 變異

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

4? 仿真實(shí)驗(yàn)

實(shí)驗(yàn)中，算法均采用matlab2016a編程實(shí)現(xiàn)，運(yùn)行環(huán)境為：win10 專業(yè)版、Inter（R）Xeon（R） W-2133 CPU @ 3.6GHz 處理器，64G內(nèi)存，64位操作系統(tǒng)。

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

Matlab仿真結(jié)果如圖2-圖4所示，圖2為三維空間航跡規(guī)劃圖，圖3為二維空間航跡規(guī)劃圖，圖4為評價(jià)函數(shù)迭代曲線。

5? 總結(jié)

針對無人機(jī)的三維航跡規(guī)劃問題，本文通過對數(shù)字地圖預(yù)處理，將地形高程信息與障礙區(qū)域高程信息進(jìn)行融合，根據(jù)飛行器的性能指標(biāo)，給出了地圖平滑處理手段，在此基礎(chǔ)上設(shè)計(jì)帶有懲罰的代價(jià)函數(shù)，采用傳統(tǒng)遺傳算法對三維地形下的無人機(jī)航跡進(jìn)行航跡規(guī)劃，根據(jù)仿真結(jié)果得出以下結(jié)論：

①對實(shí)際地形進(jìn)行平滑處理，可以極大的減小搜索空間，減小算法復(fù)雜度;

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

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

本文的研究重點(diǎn)是無人機(jī)靜態(tài)的三維航跡規(guī)劃問題，在建模時(shí)僅將地形障礙以及無人機(jī)自身性能作為約束條件，并未考慮實(shí)際飛行任務(wù)中的氣象條件以及通信條件，在后期工作中將結(jié)合實(shí)際任務(wù)區(qū)域的氣象條件以及通信條件等，對無人機(jī)的三維動(dòng)態(tài)航跡規(guī)劃問題進(jìn)行研究，以期為無人機(jī)的完成飛行任務(wù)提供更好的技術(shù)支持。

參考文獻(xiàn)：

[1]史紅玉，劉淑芬.基于Voronoi圖的無人機(jī)航路改進(jìn)規(guī)劃[J].吉林大學(xué)學(xué)報(bào)，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]馬立.基于改進(jìn) A～*算法的無人機(jī)動(dòng)態(tài)航跡規(guī)劃[J].現(xiàn)代導(dǎo)航，2018，9（1）：60-64.

[4]白俊強(qiáng)，柳長安.基于蟻群算法的無人機(jī)航路規(guī)劃[J].飛行力學(xué)，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]張建英，劉暾.基于人工勢場法的移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃[J].航空學(xué)報(bào)：2007，28：183-188.

[7]王壯，劉聰鋒，蔡嘯.一種基于Voronoi圖的航路規(guī)劃方法[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*算法的無人機(jī)三維航跡規(guī)劃研究[D].南京：南京郵電大學(xué)，2017.

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

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

[15]王寧，魏利勝.一種基于 GA 的新型生物地理學(xué)優(yōu)化算法研究[J/OL].系統(tǒng)仿真學(xué)報(bào).http：//kns.cnki.net/kcms/detail/11.3092.v.20190531.1702.025.html.