改進(jìn)蟻群算法的無(wú)人機(jī)突防航路規(guī)劃*

歐陽(yáng)志宏，郭強(qiáng)

(國(guó)防科技大學(xué) 電子對(duì)抗學(xué)院，安徽 合肥 230037)

0 引言

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

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

1 約束條件分析

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

(1) 威脅約束

無(wú)人機(jī)規(guī)劃得到的航路既要滿足任務(wù)要求，又要盡量減少墜毀概率和被摧毀概率。威脅約束主要來(lái)自敵方火力威脅和地形起伏威脅。無(wú)人機(jī)在飛行過(guò)程中，敵方雷達(dá)會(huì)對(duì)飛機(jī)形成探測(cè)威脅，飛機(jī)被發(fā)現(xiàn)后會(huì)招致地面防空武器的火力打擊威脅。此外，還要考慮地形起伏因素，確保離地高度，躲避危險(xiǎn)地形和惡劣天氣等。

將火力威脅和地形威脅均以區(qū)域表示，分別為QH和QD，無(wú)人機(jī)應(yīng)盡量繞過(guò)威脅區(qū)域飛行，如圖1所示。

圖1 無(wú)人機(jī)規(guī)避威脅示意圖Fig.1 Schematic diagram of UAV threat avoidance

飛行區(qū)域?yàn)镼F，那么威脅約束可表示為

(QD∪QH)∩QF=?.

(1)

威脅區(qū)域邊界的劃定涉及到雷達(dá)探測(cè)距離計(jì)算、雷達(dá)探測(cè)概率計(jì)算、火力覆蓋范圍計(jì)算以及命中概率計(jì)算等。

(2) 性能約束

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

飛行速度約束可表示為

vmin≤vi≤vmax

,

(2)

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

飛行高度約束可表示為

Hmin≤hi≤Hmax

,

(3)

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

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

(4)

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

此外還應(yīng)適當(dāng)考慮爬升角、轉(zhuǎn)彎角、降落約束、過(guò)載等性能約束。

2 航路規(guī)劃方法

突防航路規(guī)劃以整體航線規(guī)劃得到的航線為參考，依據(jù)最新的威脅信息、地形信息等因素，動(dòng)態(tài)地生成最優(yōu)航跡并沿著最優(yōu)航跡飛行。整體參考航線的規(guī)劃涉及全局的優(yōu)化，既要避免局部最優(yōu)又要減少計(jì)算量，而航跡的動(dòng)態(tài)優(yōu)化則應(yīng)盡可能減少計(jì)算量以確保實(shí)時(shí)性。

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

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

航路搜索過(guò)程如下：

(1) 初始化

初始化主要針對(duì)蟻群和信息素進(jìn)行。蟻群初始化包括起點(diǎn)和終點(diǎn)、蟻群移動(dòng)規(guī)則、蟻群數(shù)量規(guī)模m、信息啟發(fā)式因子α、期望啟發(fā)式因子β等。信息素初始化包括初始信息素Q、揮發(fā)程度系數(shù)ε和信息素修正權(quán)值e等。搜索次數(shù)、網(wǎng)格尺寸、威脅點(diǎn)位置等參數(shù)同步初始化。

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

圖3 移動(dòng)規(guī)則示意圖Fig.3 Schematic diagram of movement rule of ant colony

(2) 轉(zhuǎn)移概率修正

蟻群自起點(diǎn)開(kāi)始搜索路徑的轉(zhuǎn)移概率計(jì)算公式為

(5)

式中:xs為當(dāng)前時(shí)刻螞蟻所在節(jié)點(diǎn);xe為螞蟻下一時(shí)刻要前往的節(jié)點(diǎn)，該節(jié)點(diǎn)符合移動(dòng)規(guī)則。τ(xs,xe)表示節(jié)點(diǎn)xs到節(jié)點(diǎn)xe的信息素強(qiáng)度，一般可將其等效于節(jié)點(diǎn)xe的信息素強(qiáng)度，無(wú)法前往的點(diǎn)或威脅點(diǎn)信息素為0；η(xs,xe)表示節(jié)點(diǎn)xs到節(jié)點(diǎn)xe的可見(jiàn)性，一般是節(jié)點(diǎn)間移動(dòng)油耗的倒數(shù)。

本文綜合考慮威脅因素和轉(zhuǎn)移油耗，通過(guò)加權(quán)處理修正轉(zhuǎn)移可見(jiàn)性計(jì)算，表達(dá)式為

(6)

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

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

(7)

(3) 引入目標(biāo)誘惑

以往的蟻群算法蟻群在第1次搜索航路時(shí)僅考慮固定威脅，無(wú)其他任何先驗(yàn)信息，航路具有很大的隨機(jī)性，導(dǎo)致能夠走到目標(biāo)點(diǎn)的螞蟻數(shù)量很少，從而后續(xù)完成全部搜索形成穩(wěn)定的最優(yōu)航路所需時(shí)間較長(zhǎng)。

然而，螞蟻在接近目標(biāo)點(diǎn)時(shí)，可通過(guò)多維感官感受到附近存在對(duì)其有吸引力的目標(biāo)，且越接近吸引力越強(qiáng)。也就是說(shuō)，目標(biāo)點(diǎn)對(duì)螞蟻存在誘惑性，反映在算法中可以對(duì)目標(biāo)點(diǎn)及其臨近點(diǎn)增加信息素在路徑的末端，誘使螞蟻以更大的概率走向目標(biāo)點(diǎn)。

設(shè)全局信息素矩陣為I，則引入目標(biāo)誘惑后的I*更新為

I*=I+IY

.

(8)

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

(4) 啟動(dòng)搜索，獲取最優(yōu)解

蟻群按移動(dòng)規(guī)則和沿途信息素強(qiáng)弱開(kāi)始路徑搜索，根據(jù)轉(zhuǎn)移概率計(jì)算方法，從結(jié)點(diǎn)(i,j)移動(dòng)至節(jié)點(diǎn)(i+1,j+1)、節(jié)點(diǎn)(i+1,j)和節(jié)點(diǎn)(i+1,j-1)的概率分別為P1,P2和P3，顯然滿足

P1+P2+P3=1.

(9)

然后，根據(jù)計(jì)算的轉(zhuǎn)移概率采取賭輪法隨機(jī)選取下一個(gè)節(jié)點(diǎn)。按此方法進(jìn)行搜索，直至柵格地圖終點(diǎn)。一次搜索過(guò)程，m只螞蟻中，部分螞蟻能夠到達(dá)指定目標(biāo)點(diǎn)，另一部分偏離目標(biāo)點(diǎn)，而又有部分中途遇到威脅終結(jié)生命。

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

(5) 信息素更新

引入的目標(biāo)誘惑不屬于信息素更新的范疇，所以信息素更新前應(yīng)去除目標(biāo)點(diǎn)及其周圍點(diǎn)增加的信息素。信息素矩陣的第1次更新I1為

I1=I*-IY

.

(10)

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

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

(11)

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

I3=I2+IY.

(12)

(6) 形成全局最優(yōu)航路

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

3 作戰(zhàn)仿真實(shí)例

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

對(duì)蟻群執(zhí)行5輪、10輪、20輪搜索分別進(jìn)行500次蒙特卡羅仿真，對(duì)比以往算法和本文改進(jìn)蟻群算法的航路搜索結(jié)果，搜索成功次數(shù)統(tǒng)計(jì)數(shù)據(jù)如表1所示。

針對(duì)蟻群執(zhí)行20輪搜索進(jìn)行的500次蒙特卡羅仿真，形成最優(yōu)航路所需搜索輪數(shù)統(tǒng)計(jì)數(shù)據(jù)如表2所示。

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

算法名稱5輪搜索成功次數(shù)10輪搜索成功次數(shù)20輪搜索成功次數(shù)以往蟻群算法226382480改進(jìn)蟻群算法321458498

表2 最優(yōu)航路形成平均搜索輪數(shù)對(duì)照表

顯然，基于改進(jìn)蟻群算法的航路規(guī)劃方法在搜索成功率和速率上優(yōu)于以往蟻群航路規(guī)劃方法，尤其是在較少的搜索次數(shù)上能夠以較大概率快速獲取全局最優(yōu)航路，在實(shí)時(shí)性上滿足實(shí)戰(zhàn)中突防航路規(guī)劃要求。

對(duì)無(wú)人機(jī)飛行路徑中遭遇多種威脅類型進(jìn)行仿真，與上述不區(qū)分威脅類型的情況進(jìn)行最優(yōu)航路搜索結(jié)果比較。設(shè)σt,σo分別為0.6,0.4，過(guò)程中存在打擊威脅和地形威脅，fd和fx分別為

(14)

仿真結(jié)果如圖5所示?？梢?jiàn)，當(dāng)考慮路徑威脅類型時(shí)，最優(yōu)航路不僅追求最短航程，也能夠主動(dòng)繞行重點(diǎn)威脅。

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

4 結(jié)束語(yǔ)

本文針對(duì)軍用無(wú)人機(jī)突防航路規(guī)劃問(wèn)題，提出了基于改進(jìn)蟻群算法的航路規(guī)劃方法，提升了航路搜索的準(zhǔn)確性和時(shí)效性。航路規(guī)劃系統(tǒng)的發(fā)展方向是具備面對(duì)不確定環(huán)境的實(shí)時(shí)自適應(yīng)航路規(guī)劃能力，單一的規(guī)劃方法顯然難以需求，分層、分段、分區(qū)域的多種規(guī)劃方法的融合，既有大范圍的離線規(guī)劃，又有小范圍的在線修正，是下一步的研究重點(diǎn)。

[1] 鄭昌文,嚴(yán)平,丁明躍.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢(shì)[J].宇航學(xué)報(bào),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] 丁明躍,鄭昌文,周成平,等.無(wú)人飛行器航跡規(guī)劃[M].北京:電子工業(yè)出版社,2009. DING Ming-yue,ZHENG Chang-wen, ZHOU Cheng-ping,et al.UAV Route Planning[M].Beijing:Publishing House of Electronics Industry,2009.

[3] 葉文,朱愛(ài)紅,范洪達(dá).低空突防航路規(guī)劃算法綜述[J].系統(tǒng)仿真學(xué)報(bào),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算法在無(wú)人機(jī)偵察航路規(guī)劃中的應(yīng)用[J].彈箭與制導(dǎo)學(xué)報(bào),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] 劉鋼,老松楊,譚東風(fēng).基于功能區(qū)域的反艦導(dǎo)彈逆向航路規(guī)劃[J].系統(tǒng)工程與電子技術(shù),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] 李猛,王道波,柏婷婷,等.采用威脅啟發(fā)粒子群算法的無(wú)人機(jī)航路規(guī)劃[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ī)低空突防航路規(guī)劃系統(tǒng)研究[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] 王慶江,彭軍,倪保航,等.基于航路點(diǎn)搜索法的軍用飛行器航路規(guī)劃[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] 李子杰,劉湘?zhèn)?湯博,等.基于進(jìn)化算法的雷達(dá)對(duì)抗偵察無(wú)人機(jī)航路規(guī)劃[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] 周燕,范鵬.戰(zhàn)術(shù)航空偵察航路規(guī)劃評(píng)價(jià)模型[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] 汲萬(wàn)峰,張有志,章堯卿,等.不確定環(huán)境中基于概率威脅的航跡規(guī)劃研究[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] 熊丹君,蔡滿意,劉宇坤,等.多約束條件下飛行器航路規(guī)劃[J].彈箭與制導(dǎo)學(xué)報(bào),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] 唐上欽,黃長(zhǎng)強(qiáng),胡杰,等.基于威脅等效和改進(jìn)PSO算法的UCAV實(shí)時(shí)航路規(guī)劃方法[J].系統(tǒng)工程與電子技術(shù),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] 李子杰,劉湘?zhèn)?劉暢,等.雷達(dá)假目標(biāo)干擾無(wú)人機(jī)航路規(guī)劃研究[J].現(xiàn)代雷達(dá),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] 葉文,范洪達(dá).基于改進(jìn)蟻群算法的飛機(jī)低空突防航路規(guī)劃[J].飛行力學(xué),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.