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

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

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

0 引言

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

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

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

1 飛機(jī)航路規(guī)劃問(wèn)題描述

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

1.1 地形信息的獲取

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

1.2 威脅模型建立

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

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

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

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

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

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

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

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

圖1 飛機(jī)航線(xiàn)規(guī)劃空間

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

2.2 航跡點(diǎn)選擇

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

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

圖2 可達(dá)軌跡點(diǎn)集合

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

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

2.3 信息素更新

2.3.1 信息素局部更新

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

2.3.2 信息素全局更新

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

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

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

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

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

2.4 算法工作流程

改進(jìn)蟻群算法的工作流程為：

算法1 改進(jìn)蟻群算法Input：三維地圖h（x，y，z），螞蟻個(gè)數(shù)pop，迭代次數(shù)k，起點(diǎn)坐標(biāo)start，終點(diǎn)坐標(biāo)end O utput：最短航線(xiàn)bestpath 1.foreach i∈k do 2. foreach j∈pop do 3. curPoint=start 4. curPoint寫(xiě)入path 表5. forcurPointx 小于規(guī)劃空間hx do 6. 可達(dá)航跡點(diǎn)集合A llow（x，y，h）={a1，a2，…an}7. foreach point∈A llow do 8. 使用啟發(fā)函數(shù)η 計(jì)算轉(zhuǎn)移概率Ps 9. 確定下一個(gè)航跡點(diǎn)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. 終點(diǎn)end 寫(xiě)入path 17. curPoint=end 18. end if 19. end for 20. end for 21. 一次迭代完成，計(jì)算fitness，bestfitness 22. if t 代以?xún)?nèi)bestfitness沒(méi)有變化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 仿真驗(yàn)證及結(jié)果分析

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

表1 障礙信息表

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

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

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

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

圖4 適應(yīng)度值

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

4 結(jié)論

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

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

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

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

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