王 平 白 昕 解成超

1.天津航天中為數(shù)據(jù)系統(tǒng)科技有限公司，天津 300301 2.北京科技大學(xué)自動化學(xué)院，北京 100083

隨著航空技術(shù)與人工智能的迅速發(fā)展，無人機以其操作靈活，成本低廉等特點，在民用領(lǐng)域及軍用偵查都有廣闊的應(yīng)用前景。軍事作戰(zhàn)中派遣多無人機協(xié)同作戰(zhàn)相比于單無人機能夠在穿透敵方防御系統(tǒng)，探測目標(biāo)以及執(zhí)行攻擊任務(wù)等方面更具優(yōu)勢[1]。航跡規(guī)劃與多機協(xié)作問題成為當(dāng)下研究熱點。

無人機自主航跡規(guī)劃[2]中算法是核心部分。經(jīng)典算法有混合整數(shù)線性規(guī)劃(MILP)[3]、A*算法、分布式算法等。其中A*算法的研究與應(yīng)用較多[4-6]，它是一種經(jīng)典的啟發(fā)式搜索算法，運行較快，能夠快速求解并得到最短路徑，但相比其他算法，躲避威脅效果不理想，航跡代價較大；智能算法有遺傳算法(GA)[7-8]、粒子群算法(PSO)、蜂群算法(ABC)等。其中ABC算法模擬蜜蜂覓食，全局尋優(yōu)和局部尋優(yōu)能力較好，迭代尋優(yōu)后能夠得到較理想的路徑且避障能力強。文獻[9]研究了三維環(huán)境下應(yīng)用蜂群算法的無人機航跡規(guī)劃，但該算法需要一定的蜂群數(shù)量和迭代次數(shù)才能生成多航跡點可靠路徑，路徑航跡點不能過多以免計算過于復(fù)雜，航跡點過少，航跡又不夠明確。鑒于單一算法的局限性，對算法改進或是將2種算法結(jié)合成為主要的解決方案。文獻[10]引入了協(xié)方差對蜂群算法改進，文獻[11]提出ABC與RRT結(jié)合方法的移動機器人路徑規(guī)劃。本文擬采用基于蜂群與A*的混合算法進行三維航跡規(guī)劃，利用蜂群全局尋優(yōu)和局部尋優(yōu)優(yōu)勢進行初始規(guī)劃，通過減少種群數(shù)量與迭代次數(shù)簡化計算，生成具有指向性的少量初始航跡點，再利用A*算法能夠快速規(guī)劃和獲得最短路徑的特點規(guī)劃初始航跡點間的路徑多機協(xié)同也是無人機熱門研究之一，目前學(xué)者們對多機協(xié)同的研究有多機協(xié)同攻擊[1,5,12-13]、多機編隊控制[14]、多機協(xié)同信息采集[15]和多機任務(wù)分配[16]等。多機協(xié)同攻擊中時間協(xié)同是主要任務(wù)之一，考慮到增加作戰(zhàn)打擊的有效性和提高威力等，大多數(shù)時間協(xié)同都著重同時到達，但在不滿足同時到達的時間協(xié)同下，時序到達能起到相似的打擊效果，另外在偵查評估時，時序到達還能減少暴露于敵方防空設(shè)施的幾率。文獻[12-13]介紹了多機同時到達和不滿足同時到達、按固定時間間隔時序到達的航跡規(guī)劃。文獻[17]提出了基于Lagucrrc圖和閉環(huán)速度控制的路徑規(guī)劃，實現(xiàn)了多機按固定時間間隔時序到達。但是固定時間間隔時序到達協(xié)同較困難，本文考慮對多機到達的時間差迭代判斷，自適應(yīng)地確定時序到達的時間，最大概率地讓多機能時序到達，提高多機的攻擊效果。另外現(xiàn)有多機協(xié)同攻擊很少考慮到達攻擊角度，文獻[5,13]研究表明滿足攻擊角度約束的多機協(xié)同攻擊，打擊效率更高。

基于以上，本文余下內(nèi)容如下：第1節(jié)介紹航跡代價模型；第2節(jié)研究了蜂群算法、A*算法、基于蜂群與A*的混合算法的航跡規(guī)劃流程；第3節(jié)介紹了基于時間迭代的多機自適應(yīng)時間協(xié)同；第4節(jié)為仿真結(jié)果與討論；第5節(jié)為研究總結(jié)。

1 航跡代價模型

無人機航跡規(guī)劃中航跡代價是航跡評判標(biāo)準(zhǔn)。本文采用二維規(guī)劃航跡點還原高度信息至最小威脅曲面的三維航跡規(guī)劃方法[18-19]，航跡代價如式(1)。

J=(1-β)(Jfule+Jhight/2)+βJthreat

(1)

式中，β為威脅代價系數(shù)，1-β為油耗高度代價系數(shù)，0≤β≤1；Jfule為油耗代價，在二維和三維航跡規(guī)劃中與航跡長度成正比；Jhight為高度代價，二維航跡規(guī)劃中為0，在三維航跡規(guī)劃中與最小威脅曲面上相鄰路徑點間高度差相關(guān)；Jthreat為威脅代價，將威脅山峰中心點作為威脅點，威脅范圍為圓域，單點威脅代價為威脅點與航跡點距離四次方的倒數(shù)。當(dāng)航跡段在威脅圓域內(nèi)，航跡威脅代價為單點威脅代價沿航跡段的積分和[20]；當(dāng)航跡段在威脅圓域外，航跡段威脅代價為0。為了簡化計算，本文采用航跡段的10等分奇數(shù)點，即航跡點間的1/10、3/10、5/10、7/10和9/10處的威脅代價和代替該段航跡積分過程。二維與三維的威脅代價數(shù)值相同。

2 航跡規(guī)劃算法

2.1 蜂群算法

蜂群算法[9-11,21-22]是一種仿生智能算法。它將蜜蜂分為雇傭蜂、跟隨蜂和探索蜂。雇傭蜂的任務(wù)是尋找蜜源并將尋找到的蜜源信息通過“八字舞”分享給跟隨蜂，跟隨蜂則依照“輪盤賭”選擇合適的蜜源采蜜，另外采蜜過程中多次無法更新更優(yōu)蜜源時需要拋棄原有蜜源跳出局部最優(yōu)，此時探索蜂負(fù)責(zé)尋找新蜜源代替原有蜜源重新進行搜索。蜂群算法的尋優(yōu)能力好，能夠跳出局部最優(yōu)的循環(huán)，蜜蜂的種群數(shù)量在一定范圍內(nèi)數(shù)值越大，迭代次數(shù)越多，得到的路徑點越優(yōu)。但是蜂群算法尋優(yōu)能力的提升是以種群數(shù)量和迭代次數(shù)的增加為代價的。當(dāng)航跡點較多時計算復(fù)雜度與計算時間成倍增長，另外蜂群算法局部搜索能力弱，收斂慢。

2.2 A*算法

A*算法[4-6]是一種經(jīng)典啟發(fā)式搜索算法，它的航跡代價公式如式(2)。

f(n)=g(n)+h(n)

(2)

n為當(dāng)前路徑點，f(n)為路徑代價，g(n)為當(dāng)前點到起點的代價，h(n)為當(dāng)前點到終點的代價，取為兩點之間的長度。

A*算法將以當(dāng)前路徑點為中心的九宮格點中代價最小的點作為下一路徑點進行迭代尋找，得到最終路徑。由于簡單的路徑代價選擇，A*算法運行搜索速度快，但也導(dǎo)致了算法的尋優(yōu)能力不足。

2.3 基于蜂群與A*混合算法航跡規(guī)劃

混合算法的航跡規(guī)劃流程如圖1所示。首先預(yù)設(shè)較少航跡點個數(shù)，利用較少種群數(shù)量的蜂群算法迭代較少次得到初始航跡，航跡點間再通過A*算法細(xì)化得到更多航跡點以便明確航跡，步驟如下：

1)將實際環(huán)境與威脅模型結(jié)合描述為融合地形，并對融合地形平滑處理與曲率限制以滿足無人機爬坡俯沖角、轉(zhuǎn)彎角和離地高度，生成最小威脅曲面。將融合地形信息投影到二維平面作為航跡規(guī)劃的基礎(chǔ)。通過三維投影到二維，再還原高度信息，得到最小威脅曲面上的航跡，這種方法能夠降低直接在三維空間進行搜索的空間復(fù)雜度和計算量[18,23]。

2)蜂群算法尋優(yōu)初始航跡點：為保障運算速度，預(yù)設(shè)較少航跡點數(shù)量(算法對比仿真部分為10個，多機協(xié)同仿真部分為5個)。為保證路徑的優(yōu)異并排除異常搜索情況，運行得到多次最優(yōu)航跡，并選取其中三維航跡代價最小的結(jié)果作為初始航跡。

3)A*算法優(yōu)化航跡：選取初始航跡中相鄰航跡點分別作為起點和終點，利用A*算法進行二次規(guī)劃得到初始航跡點間路徑點。

4)將優(yōu)化航跡還原高度信息，投影至最小威脅曲面，得到三維路徑點，連接后確定三維航跡。

圖1 混合算法航跡規(guī)劃流程圖

3 多機協(xié)作

3.1 自適應(yīng)時間協(xié)同

本文以3架無人機為例,設(shè)混合算法得到的各機航跡長度為Li，i=1,2,3，無人機飛行速度范圍v∈[100m/s,150m/s]，則每架無人機的飛行時間范圍為Ti∈[Li/150,Li/100]，i=1,2,3。

考慮攻擊到達角度，三機依照混合算法航跡規(guī)劃，根據(jù)Li與v獲得Ti。當(dāng)Ti存在交集時為同時到達；當(dāng)Ti無交集時，對到達時間差Δt迭代，選擇最小Δt使三機時序到達；若無Δt滿足條件則認(rèn)為無法協(xié)同，需要重新進行航跡規(guī)劃。最后根據(jù)各機到達時間計算各機的速度。自適應(yīng)時間協(xié)同流程圖如圖2所示。Δt的迭代條件及時間協(xié)同狀態(tài)與示意圖如表1所示。

以上步驟能實現(xiàn)多機自適應(yīng)時間協(xié)同，通過Δt的迭代可以使無人機以小Δt快速到達，一方面減小暴露于敵方防空設(shè)施的風(fēng)險，另一方面相比于固定Δt的時序到達，迭代過程加大了無人機滿足時序到達的可能性。本文要求Δt∈[0s,600s]，在實際應(yīng)用中可以根據(jù)需要自行設(shè)定Δt的范圍。

3.2 攻擊角度協(xié)同

滿足到達攻擊角度的多機協(xié)同攻擊效率更高[5,13]。以三機為例，要求攻擊角度為90°、 225°和315°。在以終點為中心的九宮格點中，選擇滿足攻擊角度的臨時點作為航跡終點前的目標(biāo)點，如圖3所示。先計算無人機1與各臨時點的距離，并將最近臨時點分給無人機1，再計算無人機2與剩余臨時點的距離，并將最近臨時點分給無人機2，最后剩余的臨時點分給無人機3。各機根據(jù)起點與臨時點規(guī)劃路徑，再從臨時點直接飛往終點，實現(xiàn)攻擊角度的協(xié)同。

圖2 自適應(yīng)時間約束流程圖

表1 自適應(yīng)時間約束條件

圖3 攻擊角度協(xié)同

4 仿真結(jié)果

4.1 地形仿真

地圖地形數(shù)據(jù)是從地理空間數(shù)據(jù)云(http://www.gscloud.cn/)選取大興安嶺區(qū)域，應(yīng)用Global Mapper軟件截取約12.6km×12.6km區(qū)域并將地形數(shù)據(jù)轉(zhuǎn)換為grd格式以便Matlab讀取。設(shè)置間隔30m采樣平滑得到基礎(chǔ)地形圖如圖4。設(shè)置威脅模型為等效山峰，基礎(chǔ)地形與威脅模型的融合如式(3)。

(3)

式中，z0是地形基準(zhǔn)高度，x，y為水平面坐標(biāo)點，z1(x,y)為基礎(chǔ)地形高度，z2(x,y)為威脅模型等效山峰高度，n為山峰個數(shù)，zi為第i個山峰的最高高度，x0i和y0i第i個山峰最高點處的坐標(biāo)。xsi和ysi為威脅山峰坡度參數(shù)。

圖4 基礎(chǔ)地形圖

參數(shù)：z0=6，n=3。3個威脅模型中心點的x，y坐標(biāo)為[50,100;200,400;350,100]，對應(yīng)最高點z值為[400;450;530]，3個威脅模型坡度參數(shù)設(shè)為[200,130;200,170;110,160]。融合地形如圖5。

圖5 融合地形

4.2 混合算法與A*算法比較

圖6和7為單無人機分別應(yīng)用A*算法和基于蜂群與A*的混合算法進行航跡規(guī)劃的仿真圖，無人機起點平面坐標(biāo)(10,12.6)，終點平面坐標(biāo)(400,370)，最大爬升角60°，曲率0.1。

圖6 A*算法航跡規(guī)劃

圖7 混合算法航跡規(guī)劃

從仿真結(jié)果的平面圖航跡可知，混合算法的航跡比A*算法的航跡稍有一些曲折，與航跡總長度對應(yīng)的油耗高度代價為194，比A*算法的153稍大，但相差不明顯，這是因為航跡長度受點間平面距離和點間縱向高度的影響，其中混合算法的點間平面距離稍大，但縱向高度與A*算法近似并占很大部分的航跡總代價值。但與航跡避障效果相對應(yīng)的威脅代價由A*算法的315減小到混合算法的94，顯示了混合算法航跡規(guī)劃較強的避障能力。

4.3 基于混合算法的多機協(xié)作

蜂群種群數(shù)量50，預(yù)設(shè)路徑點5個，迭代60次，無人機參數(shù)參考本文第3節(jié)多機協(xié)作部分。X0i表示3架無人機的起點坐標(biāo)，Y0表示3架無人機的終點坐標(biāo)，多機協(xié)同仿真如圖8所示。

圖8 多機自適應(yīng)時間協(xié)同仿真結(jié)果

圖8(a)顯示三機同時到達情況，運行結(jié)果為Ti存在交集，交集為[7363.9s,9950.2s]，Δt為0s，選擇7363.9s作為三機同時到達終點的時間，各機速度分別為137.04m/s，135.12m/s和150m/s。插入右上角的終點附近,局部圖顯示三機能夠以固定攻擊角度到達終點；圖8(b)顯示三機時序到達情況，運行結(jié)果為Ti無交集，Δt為393.3s，三機時序到達時間為8059.6s，8452.9s和8846.2s，各機速度分別為100.0014m/s，120.2346m/s和150m/s；插入右上角的終點附近,局部圖顯示時序到達，3架無人機沿長虛線軌跡飛行,直到第1架無人機到達終點，隨后2架無人機沿實線軌跡飛行，經(jīng)過Δt的時間,第2架無人機到達終點，最后一架無人機沿短虛線軌跡,再經(jīng)過Δt的時間到達終點，三機完成時序到達。

5 結(jié)語

提出了一種基于蜂群與A*的混合算法進行三維航跡規(guī)劃，其中蜂群部分采用較少的種群數(shù)量，迭代次數(shù)和預(yù)設(shè)路徑點數(shù)目，減小了計算復(fù)雜度，運行時間較短。經(jīng)過與A*算法的仿真對比，混合算法減小了航跡威脅代價，能夠得到較好的航跡。在多機協(xié)同方面，建議了一種自適應(yīng)時間協(xié)同方法，對時序到達時間差迭代以增加時序到達的可能性；應(yīng)用任務(wù)分配實現(xiàn)了柵格化固定攻擊角度的時間協(xié)同，這些措施都能增加多機協(xié)同打擊效力。