基于改進蟻群算法的飛機航路規(guī)劃研究

梁潔雅，田衛(wèi)萍，楊志堅

（北方自動控制技術(shù)研究所，太原 030006）

0 引言

由于戰(zhàn)場環(huán)境復(fù)雜多變，飛機航路規(guī)劃問題是飛機執(zhí)行作戰(zhàn)任務(wù)時需要提前規(guī)劃的基本問題［1］。航路規(guī)劃在飛機實施作戰(zhàn)任務(wù)中有至關(guān)重要的作用，能夠在緊急作戰(zhàn)情況下，生成快速有效的航線，從而順利完成突防、偵察、搜救等任務(wù)。

關(guān)于飛行區(qū)域內(nèi)的航路規(guī)劃算法，有眾多研究成果，航路規(guī)劃算法大約分為3 類：基于確定性搜索、基于概率型隨機搜索和基于計算規(guī)劃方法［2］?；诖_定性搜索的方法一般化為成本最小化問題，如時間成本最小化或航線里程長短最小化，具體算法有A*算法、動態(tài)規(guī)劃法［3］、RRT 快速擴展隨機樹［4］；基于隨機搜索算法有模擬退火方法［5］、遺傳算法和蟻群算法，三者都屬于全局型的概率搜索算法；基于計算的規(guī)劃方法包括利用電荷之間作用力產(chǎn)生人工勢場法和神經(jīng)網(wǎng)絡(luò)算法［6］等。學者宋雪倩等［7］結(jié)合A*和Dubins路徑的思想，為無人機構(gòu)建由Dubins曲線組成的最短避障路徑，但是A*算法最終最優(yōu)程度取決于啟發(fā)函數(shù)以及加權(quán)因子的選取，從發(fā)表文獻來看，通常是通過試湊的方法來得到較合適的加權(quán)值。學者劉超［8］以航程作為性能指標，將無人機偵察多目標航路規(guī)劃轉(zhuǎn)化為多旅行商問題，基于遺傳算法設(shè)計了有效的染色體編碼和遺傳算子，規(guī)劃出合理有效的航路，但是遺傳算法有一定的局限性：容易過早地收斂以及在進化后期搜索效率較低。學者魏勇等［9］提出了一種基于改進粒子群算法的機器人路徑規(guī)劃方法，將差分方法加入粒子群算法，但差分進化方法變異得到的個體有不在解空間的風險，不適用于飛機航線規(guī)劃。學者曹良秋等［10］在遺傳算法基礎(chǔ)上，設(shè)計了能夠根據(jù)任務(wù)需求為無人機規(guī)劃出飛行航路算法，但該算法設(shè)計基礎(chǔ)是二維平面的規(guī)劃，無法滿足三維飛行區(qū)域內(nèi)的航路規(guī)劃。人工勢場法是通過電荷的相互作用進行規(guī)劃，規(guī)劃實時性好且時間短，適合于飛機的實時航路規(guī)劃，但容易產(chǎn)生局部極小值問題和目標不可達問題［11］。

本文采用蟻群算法對特定飛行區(qū)域內(nèi)的飛行任務(wù)進行航路規(guī)劃，引入信息素動態(tài)更新機制，同時根據(jù)飛機機動性能的影響來調(diào)整航線拐角，通過MATLAB 軟件對算法的航路規(guī)劃結(jié)果進行仿真驗證，試驗結(jié)果表明，可以在航線規(guī)劃時有效躲避威脅源并利用地形隱蔽作用生成航跡。

1 飛機航路規(guī)劃問題描述

航路規(guī)劃問題是一個涉及多專業(yè)的綜合性復(fù)雜研究課題，在飛機飛行過程中，首先需要根據(jù)飛行區(qū)域的地形、地物和威脅信息進行飛行航路規(guī)劃，航路規(guī)劃是在復(fù)雜的戰(zhàn)場環(huán)境下，搜索飛機從起點到終點符合飛機機動性能的最優(yōu)航線，提高飛機任務(wù)完成效率［12］。航路規(guī)劃需要解決以下3 個關(guān)鍵問題［2］：

1.1 地形信息的獲取

地形信息是航路規(guī)劃的基礎(chǔ)，由于試驗條件有限，很難獲得高分辨率的衛(wèi)星遙感數(shù)字地圖，而模擬數(shù)字地圖［13］能夠模擬自然界中的山峰和盆地，因此，在仿真條件下，本算法采用模擬數(shù)字地圖，為航路規(guī)劃提供了方便。

1.2 威脅模型建立

威脅信息由先期偵察獲得，建立在地形數(shù)據(jù)上，威脅能力由威脅中心和威脅半徑確定。威脅模型的復(fù)雜程度確定飛機航路規(guī)劃時選擇威脅回避策略還是威脅突防策略。本算法假設(shè)敵威脅面積有限，故采用威脅回避策略。

1.3 航路規(guī)劃算法的選擇

航路規(guī)劃算法能夠在利用地形信息、威脅信息的基礎(chǔ)上充分發(fā)揮計算機技術(shù)的優(yōu)勢，規(guī)劃出高質(zhì)量的航路。由于飛機的飛行任務(wù)區(qū)域范圍較大，使用基于確定性搜索的方法在大范圍內(nèi)將導(dǎo)致數(shù)據(jù)暴增，優(yōu)化時間過長，其巨大的信息處理量是計算機無法承受的；使用基于隨機搜索的方法是以隨機搜索的方式搜索全部解空間，可以跳出局部極小點去尋找全局最優(yōu)值。因此，本文采用蟻群算法進行航路規(guī)劃。

蟻群算法屬于概率型隨機搜索算法，廣泛應(yīng)用于路徑搜索領(lǐng)域，1992 年由M.Dorigo 首先提出，稱為蟻群系統(tǒng)。傳統(tǒng)蟻群算法就是讓人工螞蟻在隨機搜索的路徑空間中隨機行走，人工螞蟻會選擇信息素濃度較高的位置，作為下一次訪問的路徑點并在經(jīng)過的路徑上留下信息素，信息素的濃度與路徑長短有直接相關(guān)性，經(jīng)過多次迭代后，人工螞蟻逐漸聚集到代表最優(yōu)解的最短路徑上，其他路徑上的信息素逐漸揮發(fā)最終消失，最終螞蟻會在信息素的正反饋作用下集中到最優(yōu)路徑上［14］。

但是傳統(tǒng)蟻群算法在航路搜索過程中信息素計算模式不變，會導(dǎo)致在算法搜索過程中，所有螞蟻過早地聚集到同一條覓食路徑，這樣顯然不利于對最優(yōu)解的進一步搜索，使算法陷入局部最優(yōu)解而停止搜索。針對傳統(tǒng)蟻群算法所存在的問題進行適應(yīng)性改進，提出動態(tài)更新信息素大小機制，提高了全局航路搜索能力。

2 改進蟻群算法設(shè)計

2.1 飛行空間構(gòu)建

飛機避障航路規(guī)劃可以歸結(jié)為在三維空間中航線規(guī)劃的問題［15］，將地形高程數(shù)據(jù)映射到三維空間直角坐標系中，以飛機的作戰(zhàn)任務(wù)區(qū)域建立坐標系，以飛機前進方向為x 軸，左右轉(zhuǎn)彎方向為y 軸，縱向攀爬和俯沖方向為h 軸方向。障礙物通常為敵偵察和火力威脅信息，在威脅建模中，敵雷達偵察用紅色球體表示，威脅范圍為雷達偵察范圍；敵火力威脅用藍色球體表示，威脅范圍為防空武器攻擊范圍。通常情況下，在威脅范圍內(nèi)，與敵威脅距離越大，威脅越弱。如果飛行區(qū)域處于敵方陣地范圍，基本上被敵方防御系統(tǒng)所覆蓋，則需要引入突防概率來判斷飛機穿越規(guī)劃空間后的生存概率。本算法對戰(zhàn)場的想定為規(guī)劃空間處于我方地域，敵威脅面積有限，飛機飛行時速度較快，可以很快繞過威脅區(qū)域，實現(xiàn)障礙回避，飛機航線規(guī)劃空間如圖1所示。

圖1 飛機航線規(guī)劃空間

在二維路徑規(guī)劃方法中，柵格法是常用的劃分規(guī)劃空間的方法，柵格法是將搜索空間平均劃分成大小相等的柵格［16］。柵格大小決定了算法規(guī)劃的精度和效率，柵格過大就會造成路徑規(guī)劃算法搜索范圍減小，從而無法規(guī)劃出最有效路徑，柵格過小會造成算法搜索時間過長。因此，選取適當?shù)拇笮∈呛骄€規(guī)劃算法尋優(yōu)和提高效率的關(guān)鍵。對于三維空間下的航路規(guī)劃算法，同樣能夠使用柵格法來劃分任務(wù)空間，航路規(guī)劃算法采用按照坐標來劃分柵格，以單元坐標作為單元柵格，即分別沿著規(guī)劃空間的x，y，h 軸均勻劃分為n 等份，每一等份代表可訪問的航跡點，柵格位置使用規(guī)劃空間的坐標表示。

2.2 航跡點選擇

在規(guī)劃空間中，x 軸作為前進方向，下一航跡點位于當前航跡點的x+L 方向上，L 為前進步長，步長L 決定了可選航跡點的集合大小，航跡點集合為Allow（x，y，h）={a1，a2，…an}。算法采用可變步長的搜索機制，具體方式為：在尋找下一航跡點時，根據(jù)預(yù)設(shè)的最大步長確定航跡點集合，通過信息素和啟發(fā)值確定的轉(zhuǎn)移概率選擇最優(yōu)航跡點，最優(yōu)航跡點與當前位置的前進距離作為此次移動的步長?？勺儾介L機制增加了航路搜索的靈活性和尋優(yōu)能力，縮短了算法搜索時間，具體如圖2 所示。

通過柵格法將三維規(guī)劃空間劃分成n3等份，每一等份都對應(yīng)所在航跡點的信息素的值，信息素矩陣大小同樣為n3，在航跡點集合Allow 中，通過轉(zhuǎn)移概率確定下次訪問的航跡點，轉(zhuǎn)移概率Ps的公式為：

圖2 可達軌跡點集合

式（1）中，Allow 表示可訪問的航跡點集合，s為柵格s 的信息素值，α 為信息素的重要程度因子，α 越大，表明信息素濃度在航跡點選擇中的作用越大，ηs為柵格s 的啟發(fā)值，β 為啟發(fā)值的重要程度因子，β 越大，表明s 點的啟發(fā)值在航跡點選擇中的作用越大。Ps表明飛機從當前位置到s 點的期望概率。

式（2）為ηs的計算公式，其中A 為可達性因子，用于確定航跡點集合中的航跡點是否可達；O 為障礙物因子，使航跡點能夠躲避敵武器威脅范圍；D 為兩個航跡點之間的距離，與啟發(fā)值呈負相關(guān)，距離越大啟發(fā)值越??；AH 為絕對高度，RH 為相對高度，通過相對高度和絕對高度判斷航跡點與地形之間的關(guān)系，選擇能夠盡可能貼地飛行的航跡點。

2.3 信息素更新

2.3.1 信息素局部更新

信息素的更新與航路規(guī)劃形成一個正反饋關(guān)系，當根據(jù)轉(zhuǎn)移概率計算出下一個航跡點時，必須對該航跡點所處柵格位置的信息素進行局部更新，更新規(guī)則為：

2.3.2 信息素全局更新

當人工螞蟻種群完成一次路徑搜索后，由于信息素濃度的揮發(fā)作用，將規(guī)劃空間中的信息素進行揮發(fā)調(diào)整，調(diào)整方式為=（1-ρ），其中，ρ 為揮發(fā)系數(shù)，然后從每只螞蟻搜索到的路徑path 中選取適應(yīng)度值最高的路徑，增加該路徑上的每一個航跡點信息素濃度，提高下次蟻群迭代選擇該路徑的概率。適應(yīng)度值計算方式為：

length 為航線總長度，Δheight為所有航跡點的相對高度和，控制算法選擇貼地飛行的航路。適應(yīng)度值越小，表明航路越好，對于最優(yōu)路徑信息素增加方式為：

其中，Q 為常數(shù)，表示螞蟻迭代一次后釋放的信息素含量，fitness表示航路的適應(yīng)度值。

2.3.3 信息素的動態(tài)更新

信息素的更新方式確定了搜索航跡的效果，因此，當算法陷入收斂時，應(yīng)當使用一定的手段跳出局部解以尋求更多的可能性，本文采用一種動態(tài)的信息素更新機制，更新過程為，若算法的最優(yōu)解在t 代以內(nèi)不發(fā)生改變時，使用以下公式更新信息素［17］：

2.4 算法工作流程

改進蟻群算法的工作流程為：

算法1 改進蟻群算法Input：三維地圖h（x，y，z），螞蟻個數(shù)pop，迭代次數(shù)k，起點坐標start，終點坐標end O utput：最短航線bestpath 1.foreach i∈k do 2. foreach j∈pop do 3. curPoint=start 4. curPoint寫入path 表5. forcurPointx 小于規(guī)劃空間hx do 6. 可達航跡點集合A llow（x，y，h）={a1，a2，…an}7. foreach point∈A llow do 8. 使用啟發(fā)函數(shù)η 計算轉(zhuǎn)移概率Ps 9. 確定下一個航跡點nextPoint 10. end for 11. ifnextPointx 小于規(guī)劃空間hx then 12. path←nextPoint 13. curPoint=nextPoint 14. 更新nextPoint信息素 s=（1-）images/BZ_74_849_2573_875_2609.png15. else 16. 終點end 寫入path 17. curPoint=end 18. end if 19. end for 20. end for 21. 一次迭代完成，計算fitness，bestfitness 22. if t 代以內(nèi)bestfitness沒有變化then 23. 調(diào)整信息素增加求解可能性24. i=［1-（e min+e-1）］i 25. else 26. 增加最優(yōu)路徑信息素= +Δ 27.end for 28.輸出path 中每次迭代適應(yīng)度值最優(yōu)的路徑

3 仿真驗證及結(jié)果分析

運用MATLAB 2019 對改進蟻群算法進行實現(xiàn)，仿真規(guī)劃空間大小為160 km×160 km，高度為4 km，使用柵格劃分法將空間分為41×41×41 的空間；螞蟻種群pop=20，迭代次數(shù)為k=100，每一個柵格的初始信息素濃度=1，螞蟻種群迭代一次后釋放的信息素含量Q=100，信息素局部衰減系數(shù)為=0.5，全局迭代一次后信息素揮發(fā)系數(shù)為ρ=0.2，信息素重要程度因子取值α=3，航跡點啟發(fā)值β=3，假設(shè)敵威脅范圍為：

表1 障礙信息表

假設(shè)飛機航程滿足的情況下，起點相同、終點不同、迭代次數(shù)相同時，改進后的算法和原算法的對比結(jié)果如表2 所示。

表2 算法結(jié)果比較

圖3 改進算法的規(guī)劃結(jié)果

其中，起點為（1，15，6），終點為（41，35，9）的規(guī)劃結(jié)果如圖3所示，圖中虛線表示傳統(tǒng)蟻群算法的規(guī)劃路線，實線為改進后蟻群算法的規(guī)劃路線。結(jié)果表明，改進后的蟻群算法能夠更好地跟隨地形規(guī)劃航線，在適應(yīng)度和規(guī)劃時間方面都優(yōu)于傳統(tǒng)蟻群算法，航線起伏較小。適應(yīng)度值變化趨勢如圖4所示，圖中結(jié)果表明，傳統(tǒng)蟻群算法的最優(yōu)值在40 代收斂，但求解質(zhì)量較差；改進后的算法能夠不斷尋找更多可行解，避免陷入局部最優(yōu)解而導(dǎo)致過早收斂，最優(yōu)適應(yīng)度變化呈階梯式下降，表明在最優(yōu)航線不發(fā)生變化時，會啟用信息素動態(tài)更新機制來幫助跳出局部最優(yōu)解，求解效果明顯優(yōu)于傳統(tǒng)蟻群算法。

圖4 適應(yīng)度值

綜上所述，改進后的航線規(guī)劃算法能夠在敵威脅范圍有限情況下回避以繞行方式回避障礙物；能夠進行地形跟隨，利用地形優(yōu)勢來達到隱蔽作用；可以在較短時間內(nèi)為飛機規(guī)劃出可用的航路。

4 結(jié)論

本文提出了一種改進蟻群算法，該算法將飛機飛行空間定義為三維搜索空間，在三維搜索空間中規(guī)劃航線，利用柵格法將三維空間均勻劃n3等份，每一份代表一個的航跡點，最終規(guī)劃的航線就是從起點柵格出發(fā)，依次連接相鄰柵格直到終點柵格的最短路徑。針對傳統(tǒng)蟻群算法收斂過早和搜索速度慢的缺點，在傳統(tǒng)算法的思想上增加了信息素動態(tài)更新機制，避免路徑尋找陷入局部極小值，增加了算法的搜索空間以尋求最優(yōu)航線，達到縮短求解時間，提高求解質(zhì)量的效果。

航路規(guī)劃問題是一個綜合性的課題，仍然有許多方面進行深入研究，日后尚需進一步完善的任務(wù)有：

1）設(shè)計滿足生存概率和突防概率的航路規(guī)劃算法，在敵威脅較為密集，飛行區(qū)域被敵防御體系所覆蓋時，能夠使用威脅突防策略規(guī)劃航路，以一定的突防概率穿越飛行空間，提高飛機生存概率；

2）建立更為復(fù)雜的威脅信息模型，偵察威脅需要充分考慮目標偵察概率的能力，而火力威脅需要充分考慮毀傷概率的影響；

3）設(shè)計實時航路規(guī)劃算法，能夠處理動態(tài)威脅信息并進行臨機航路調(diào)整。