基于蜂群與A*混合算法的三維多無人機(jī)協(xié)同

王 平 白 昕 解成超

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

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

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

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

1 航跡代價(jià)模型

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

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

(1)

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

2 航跡規(guī)劃算法

2.1 蜂群算法

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

2.2 A*算法

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

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

(2)

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

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

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

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

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

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

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

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

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

3 多機(jī)協(xié)作

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

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

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

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

3.2 攻擊角度協(xié)同

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

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

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

圖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)點(diǎn)，z1(x,y)為基礎(chǔ)地形高度，z2(x,y)為威脅模型等效山峰高度，n為山峰個(gè)數(shù)，zi為第i個(gè)山峰的最高高度，x0i和y0i第i個(gè)山峰最高點(diǎn)處的坐標(biāo)。xsi和ysi為威脅山峰坡度參數(shù)。

圖4 基礎(chǔ)地形圖

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

圖5 融合地形

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

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

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

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

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

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

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

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

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

5 結(jié)語

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