基于蜂群與A*混合算法的三維多無人機協同

王 平 白 昕 解成超

1.天津航天中為數據系統科技有限公司，天津 300301 2.北京科技大學自動化學院，北京 100083

隨著航空技術與人工智能的迅速發展，無人機以其操作靈活，成本低廉等特點，在民用領域及軍用偵查都有廣闊的應用前景。軍事作戰中派遣多無人機協同作戰相比于單無人機能夠在穿透敵方防御系統，探測目標以及執行攻擊任務等方面更具優勢[1]。航跡規劃與多機協作問題成為當下研究熱點。

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

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

1 航跡代價模型

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

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

(1)

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

2 航跡規劃算法

2.1 蜂群算法

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

2.2 A*算法

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

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

(2)

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

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

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

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

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

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

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

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

圖1 混合算法航跡規劃流程圖

3 多機協作

3.1 自適應時間協同

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

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

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

3.2 攻擊角度協同

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

圖2 自適應時間約束流程圖

表1 自適應時間約束條件

圖3 攻擊角度協同

4 仿真結果

4.1 地形仿真

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

(3)

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

圖4 基礎地形圖

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

圖5 融合地形

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

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

圖6 A*算法航跡規劃

圖7 混合算法航跡規劃

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

4.3 基于混合算法的多機協作

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

圖8 多機自適應時間協同仿真結果

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

5 結語

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