改進蟻群算法的無人機突防航路規劃*

歐陽志宏，郭強

(國防科技大學 電子對抗學院，安徽 合肥 230037)

0 引言

現代戰爭中，軍用無人機承擔著情報偵察、戰場監視、伴隨防護等諸多重要任務。無人機航路規劃就是要在充分掌握地形和敵情的前提下，依據具體任務明確飛行約束條件，尋找從初始點到目標點并且滿足某種性能指標最優的運動軌跡。航路規劃的優劣直接決定無人機作戰效能發揮，甚至影響其戰場生存。軍用無人機突防航路規劃一般以生存概率最大為核心目標，目前較為成熟的方法有：最速下降法、動態規劃法、樣條插值法、神經網絡法、啟發式A*搜索法、模擬退火法、電勢理論法、遺傳算法、蟻群算法等[1-8]。

本文充分分析了無人機突防航路規劃面臨的威脅約束和性能約束，提出了改進的蟻群算法用于最優航路生成。算法充分考慮飛行過程中的威脅因素，對蟻群的轉移概率計算進行了修正，提高了航路安全性；再通過在目標點及其周圍增加固有信息素，縮小了蟻群在航路末段的搜索空間，能夠快速收斂獲取最優航路解，提高了規劃的時效性。通過仿真實例驗證了方法的時效性。

1 約束條件分析

無人機突防航路規劃的主要約束條件是威脅約束和性能約束，其中，威脅主要源自火力威脅和地形威脅。飛行航路規劃需要在各影響因素之間進行權衡[9-12]。

(1) 威脅約束

無人機規劃得到的航路既要滿足任務要求，又要盡量減少墜毀概率和被摧毀概率。威脅約束主要來自敵方火力威脅和地形起伏威脅。無人機在飛行過程中，敵方雷達會對飛機形成探測威脅，飛機被發現后會招致地面防空武器的火力打擊威脅。此外，還要考慮地形起伏因素，確保離地高度，躲避危險地形和惡劣天氣等。

將火力威脅和地形威脅均以區域表示，分別為QH和QD，無人機應盡量繞過威脅區域飛行，如圖1所示。

圖1 無人機規避威脅示意圖Fig.1 Schematic diagram of UAV threat avoidance

飛行區域為QF，那么威脅約束可表示為

(QD∪QH)∩QF=?.

(1)

威脅區域邊界的劃定涉及到雷達探測距離計算、雷達探測概率計算、火力覆蓋范圍計算以及命中概率計算等。

(2) 性能約束

無人機飛行性能約束主要包括：飛行速度、飛行高度、航程(燃油)等。

飛行速度約束可表示為

vmin≤vi≤vmax

,

(2)

式中:vi為飛機在航路第i段飛行速度;vmax和vmin分別為飛機的最大和最小航速。

飛行高度約束可表示為

Hmin≤hi≤Hmax

,

(3)

式中:hi為飛機在航路第i段飛行高度;Hmax和Hmin分別為飛機的最大和最小飛行高度。

航程(燃油)約束可表示為

(4)

式中:li為飛機在航路第i段飛行距離；Lmax和Lmin分別為飛機的最大航程和最小飛行距離。

此外還應適當考慮爬升角、轉彎角、降落約束、過載等性能約束。

2 航路規劃方法

突防航路規劃以整體航線規劃得到的航線為參考，依據最新的威脅信息、地形信息等因素，動態地生成最優航跡并沿著最優航跡飛行。整體參考航線的規劃涉及全局的優化，既要避免局部最優又要減少計算量，而航跡的動態優化則應盡可能減少計算量以確保實時性。

蟻群算法是一種模擬螞蟻群體覓食的仿生優化算法，具有分布計算、信息正反饋和啟發式搜索的特征，是國際智能計算領域備受關注的研究熱點和前沿性課題[13-15]。目前，蟻群算法在航路規劃上的應用得到了廣泛研究。本文依據蟻群算法基本思路，提出了改進的航路規劃方法，首先將威脅因素引入轉移概率計算，再將目標點及其周圍點對蟻群的末端誘惑引入信息素更新，使得算法在結果準確性、合理性和收斂速度上均有所提升。算法基本流程如圖2所示。

圖2 改進蟻群算法流程圖Fig.2 Search flow chart of penetration route based on improved ant colony algorithm

航路搜索過程如下：

(1) 初始化

初始化主要針對蟻群和信息素進行。蟻群初始化包括起點和終點、蟻群移動規則、蟻群數量規模m、信息啟發式因子α、期望啟發式因子β等。信息素初始化包括初始信息素Q、揮發程度系數ε和信息素修正權值e等。搜索次數、網格尺寸、威脅點位置等參數同步初始化。

蟻群移動規則為限定螞蟻在柵格地圖中位于節點(i,j)的可搜索范圍為節點(i+1,j+1)、節點(i+1,j)和節點(i+1,j-1)，如圖3所示。

圖3 移動規則示意圖Fig.3 Schematic diagram of movement rule of ant colony

(2) 轉移概率修正

蟻群自起點開始搜索路徑的轉移概率計算公式為

(5)

式中:xs為當前時刻螞蟻所在節點;xe為螞蟻下一時刻要前往的節點，該節點符合移動規則。τ(xs,xe)表示節點xs到節點xe的信息素強度，一般可將其等效于節點xe的信息素強度，無法前往的點或威脅點信息素為0；η(xs,xe)表示節點xs到節點xe的可見性，一般是節點間移動油耗的倒數。

本文綜合考慮威脅因素和轉移油耗，通過加權處理修正轉移可見性計算，表達式為

(6)

式中：wt和wo分別為威脅代價和油耗代價，σt和σo為2類代價的重要度權值。

wt還可根據打擊威脅、偵察威脅、地形威脅等類型作進一步區分，計算方法fd，fz和fx可按具體情況定制，顯然，距離威脅越近fd，fz和fx應越大。wt表達式為

(7)

(3) 引入目標誘惑

以往的蟻群算法蟻群在第1次搜索航路時僅考慮固定威脅，無其他任何先驗信息，航路具有很大的隨機性，導致能夠走到目標點的螞蟻數量很少，從而后續完成全部搜索形成穩定的最優航路所需時間較長。

然而，螞蟻在接近目標點時，可通過多維感官感受到附近存在對其有吸引力的目標，且越接近吸引力越強。也就是說，目標點對螞蟻存在誘惑性，反映在算法中可以對目標點及其臨近點增加信息素在路徑的末端，誘使螞蟻以更大的概率走向目標點。

設全局信息素矩陣為I，則引入目標誘惑后的I*更新為

I*=I+IY

.

(8)

目標誘惑引入的信息素IY是一種固有信息素，不會消逝也不會增加，對每一群搜索螞蟻的吸引力相同。

(4) 啟動搜索，獲取最優解

蟻群按移動規則和沿途信息素強弱開始路徑搜索，根據轉移概率計算方法，從結點(i,j)移動至節點(i+1,j+1)、節點(i+1,j)和節點(i+1,j-1)的概率分別為P1,P2和P3，顯然滿足

P1+P2+P3=1.

(9)

然后，根據計算的轉移概率采取賭輪法隨機選取下一個節點。按此方法進行搜索，直至柵格地圖終點。一次搜索過程，m只螞蟻中，部分螞蟻能夠到達指定目標點，另一部分偏離目標點，而又有部分中途遇到威脅終結生命。

比較每只螞蟻所經過路徑的航路代價，可以得到這次搜索過程中的最優航路，稱之為局部最優航路。將局部最優航路的航路代價與之前的全局最優航路的航路代價作比較，若本次搜索得到的局部最優航路的航路代價小于全局最優航路的航路代價，則將本次局部最優航路作為全局最優航路；否則，全局最優航路不變。

(5) 信息素更新

引入的目標誘惑不屬于信息素更新的范疇，所以信息素更新前應去除目標點及其周圍點增加的信息素。信息素矩陣的第1次更新I1為

I1=I*-IY

.

(10)

然后以固定揮發量、局部最優路徑增量和全局最優路徑增量的方式，更新各單元信息素。設ε為揮發系數，ej,eq和Ij,Iq分別為局部最優路徑和全局最優路徑的信息素修正權值和修正量。信息素矩陣的第2次更新I2為

I2=(1-ε)I1+ejIj+eqIq.

(11)

最后為下一次搜索再次加入固定的目標誘惑信息素。信息素矩陣的第3次更新I3為

I3=I2+IY.

(12)

(6) 形成全局最優航路

重復步驟(3)～(5)，進行多輪次搜索，更新全局最優解。直至完成全部搜索，形成全局最優航路。

3 作戰仿真實例

為驗證本文基于改進蟻群算法的航路規劃方法較以往方法具有更好的準確性和收斂速度，設置仿真場景：蟻群數量規模m為20只螞蟻，揮發程度系數ε為0.5，修正權值ej,eq為1.5和1.8，移動規則為點(i,j)處的螞蟻只能向(i+1,j+1)，(i+1,j)，(i+1,j-1)3個方向移動，信息啟發式因子和期望啟發式因子分別為1.0和1.1，起點A和終點B分別位于(1,9)和(16,9)，在柵格地圖中，設置若干威脅點，不區分威脅類型，轉移可見性系數是常數。某次搜索的3只螞蟻行走情況如圖4所示。

對蟻群執行5輪、10輪、20輪搜索分別進行500次蒙特卡羅仿真，對比以往算法和本文改進蟻群算法的航路搜索結果，搜索成功次數統計數據如表1所示。

針對蟻群執行20輪搜索進行的500次蒙特卡羅仿真，形成最優航路所需搜索輪數統計數據如表2所示。

圖4 蟻群路徑搜索示意圖Fig.4 Schematic diagram of path search of ant colony

算法名稱5輪搜索成功次數10輪搜索成功次數20輪搜索成功次數以往蟻群算法226382480改進蟻群算法321458498

表2 最優航路形成平均搜索輪數對照表

顯然，基于改進蟻群算法的航路規劃方法在搜索成功率和速率上優于以往蟻群航路規劃方法，尤其是在較少的搜索次數上能夠以較大概率快速獲取全局最優航路，在實時性上滿足實戰中突防航路規劃要求。

對無人機飛行路徑中遭遇多種威脅類型進行仿真，與上述不區分威脅類型的情況進行最優航路搜索結果比較。設σt,σo分別為0.6,0.4，過程中存在打擊威脅和地形威脅，fd和fx分別為

(14)

仿真結果如圖5所示。可見，當考慮路徑威脅類型時，最優航路不僅追求最短航程，也能夠主動繞行重點威脅。

圖5 威脅類型對蟻群路徑搜索影響圖Fig.5 Diagram of threat effect to path search

4 結束語

本文針對軍用無人機突防航路規劃問題，提出了基于改進蟻群算法的航路規劃方法，提升了航路搜索的準確性和時效性。航路規劃系統的發展方向是具備面對不確定環境的實時自適應航路規劃能力，單一的規劃方法顯然難以需求，分層、分段、分區域的多種規劃方法的融合，既有大范圍的離線規劃，又有小范圍的在線修正，是下一步的研究重點。

[1] 鄭昌文,嚴平,丁明躍.飛行器航跡規劃研究現狀與趨勢[J].宇航學報,2007,28(6):1441-1446. ZHENG Chang-wen,YAN Ping,DING Ming-yue.Research Status Quo and Development Trend of Aircraft Route Planning[J].Journal of Astronautics,2007,28 (6):1441-1446.

[2] 丁明躍,鄭昌文,周成平,等.無人飛行器航跡規劃[M].北京:電子工業出版社,2009. DING Ming-yue,ZHENG Chang-wen, ZHOU Cheng-ping,et al.UAV Route Planning[M].Beijing:Publishing House of Electronics Industry,2009.

[3] 葉文,朱愛紅,范洪達.低空突防航路規劃算法綜述[J].系統仿真學報,2007,19(10):2357-2361. YE Wen,ZHU Ai-hong,FAN Hong-da.Survey of Route Planning of Low Altitude Penetration[J].Journal of System Simulation,2007,19(10):2357-2361.

[4] 董文洪,易波,栗飛.Memetic算法在無人機偵察航路規劃中的應用[J].彈箭與制導學報,2012,32(1):211-214. DONG Wen-hong,YI Bo,LI Fei.The Application of Memetic Algorithm in UAV Reconnaissance Route Planning[J].Journal of Projectiles,Rockets,Missiles and Guidance,2012,32(1):211-214.

[5] 劉鋼,老松楊,譚東風.基于功能區域的反艦導彈逆向航路規劃[J].系統工程與電子技術,2011,33(4):799-805. LIU Gang,LAO Song-yang,TAN Dong-feng.Reverse Route Planning of Anti-Ship Missile Based on Functional Regions[J].Systems Engineering and Electronics,2011,33(4):799 -805.

[6] 李猛,王道波,柏婷婷,等.采用威脅啟發粒子群算法的無人機航路規劃[J].電光與控制,2011,18(12):1-4. LI Meng,WANG Dao-bo,BAI Ting-ting,et al.Route Planning Based on Particle Swarm Optimization with Threat Heuristic[J].Electronics Optics & Control,2011,18(12):1-4.

[7] 葉文,姜文志,劉博.飛機低空突防航路規劃系統研究[J].電光與控制,2007,14(5):5-8. YE Wen,JIANG Wen-zhi,LIU Bo.Study on Route Planning System in Low-Altitude Penetration[J].Electronics Optics & Control,2007,14(5):5-8.

[8] 王慶江,彭軍,倪保航,等.基于航路點搜索法的軍用飛行器航路規劃[J].電光與控制,2014,40(2):280-288. WANG Qing-jiang,PENG Jun,NI Bao-hang,et al.Route Planning for Military Aircrafts Based on Waypoint Searching Method[J].Computer Engineering,2014,40(2):280-288.

[9] 李子杰,劉湘偉,湯博,等.基于進化算法的雷達對抗偵察無人機航路規劃[J].火力與指揮控制,2013,38(6):51-54. LI Zi-jie,LIU Xiang-wei,TANG Bo,et al.Research on Route Planning of UAV for Radar EW Reconnaissance Based on Evolutionary Algorithm[J].Fire Control & Command Control,2013,38(6):51-54.

[10] 周燕,范鵬.戰術航空偵察航路規劃評價模型[J].電光與控制,2007,14(1):52-54. ZHOU Yan,FAN Peng.Evaluation Model for Tactical Aeronautical Reconnaissance Route Planning[J].Electronics Optics & Control,2007,14(1):52-54.

[11] 汲萬峰,張有志,章堯卿,等.不確定環境中基于概率威脅的航跡規劃研究[J].電光與控制,2013,20(10):56-61. JI Wan-feng,ZHANG You-zhi,ZHANG Yao-qing,et al.Flight Path Planning Based on Threat Probabilistic Distribution Under Uncertain Environment[J].Electronics Optics & Control,2013,20(10):56-61.

[12] 熊丹君,蔡滿意,劉宇坤,等.多約束條件下飛行器航路規劃[J].彈箭與制導學報,2009,29(2):289-292. XIONG Dan-jun,CAI Man-yi,LIU Yu-kun,et al.Air Vehicle Route Planning for Multi-Constraints[J].Journal of Projectiles,Rockets,Missiles and Guidance,2009,29(2):289-292.

[13] 唐上欽,黃長強,胡杰,等.基于威脅等效和改進PSO算法的UCAV實時航路規劃方法[J].系統工程與電子技術,2010,32(8):1706-1710. TANG Shang-qin,HUANG Chang-qiang,HU Jie,et al.UCAV Real-Time Route Planning Method Based on Threat Equivalence and Improved PSO Algorithm[J].Systems Engineering and Electronics,2010,32(8):1706-1710.

[14] 李子杰,劉湘偉,劉暢,等.雷達假目標干擾無人機航路規劃研究[J].現代雷達,2013,35(8):84-88. LI Zi-jie,LIU Xiang-wei,LIU Chang,et al.Research on Route Planning of UAV for Radar False Target Jamming[J].Modern Radar,2013,35(8):84-88.

[15] 葉文,范洪達.基于改進蟻群算法的飛機低空突防航路規劃[J].飛行力學,2004,22(3):35-38. YE Wen,FAN Hong-da.Aircraft Low-Altitude Penetration Route Planning Based on Improved Ant Colony Algorithm[J].Flight Dynamics,2004,22(3):35-38.