基于改進A*算法的多無人機協同戰術規劃

張哲， 吳劍,2， 代冀陽， 李品偉

(1.南昌航空大學 信息工程學院, 江西 南昌 330063; 2.北京航空航天大學 可靠性與系統工程學院, 北京 100191)

0 引言

現代空中作戰往往需要以多無人機聯合作戰的方式進行，而采用分層遞階結構的思想來分解問題，是解決多無人機自主協同控制和決策復雜性的有效手段[1]。

戰術飛行任務管理系統是先進戰機智能化的集中體現。為了合理地對多機作戰方式進行安排、實現多機戰斗力的倍增，需要對戰術飛行任務管理系統進行深入分析。目前大多數研究僅停留在宏觀角度進行探討，如Sutton等[2]提出的多無人機協同控制分層遞階結構，將系統分為3個決策層和1個控制層。文獻[3-6]提出集中式系統執行層次結構，任務執行效能不高。這些研究只給出了任務飛行管理系統的某種分層遞階結構。文獻[7-11]研究了分布式多機協同層次化關系，將4個層次進行細分，提高了任務的執行效能，進一步優化了各執行層次間的控制結構。文獻[12-14]重點討論了系統任務層和導航層的層次化關系，并將它們作為系統底層，簡單地細分為任務分配和航路規劃兩個方面分別進行研究。

本文提出一種基于改進A*算法的復雜環境下多無人機編隊協同戰術規劃方法，結合分層思想和多機協同控制系統優化流程，以編隊成員時間代價和碰撞代價為協同變量，建立多無人機編隊協同飛行控制的數學模型，提出作戰效能的評估方法；在求解協同作戰航路時，針對目前A*算法的不足，提出一種多層變步長搜索策略的改進A*算法，以提高航路搜索效率，保證解的最優性；研究了任務分配方法和資源協調方法，分別利用改進A*算法和傳統A*算法進行編隊協同作戰的對比仿真實驗。仿真結果驗證了所提改進算法和戰術規劃方法的有效性。

1 作戰規劃

1.1 多無人機編隊協同戰術規劃系統流程

從戰術規劃內容方面，可將多無人機協同戰術規劃系統分為作戰目標確定、態勢分析、任務規劃、航路規劃和彈藥規劃等內容，該部分可以歸納為決策層和協調層2個層次。進一步分析整個戰術規劃系統的實現步驟，可以得到多無人機編隊協同控制優化系統的流程如圖1所示。

圖1 多無人機編隊協同控制優化系統的流程Fig.1 Process of formation collaborative control optimization system for UAVs

1.2 離線規劃

1.2.1 戰役層規劃

戰役層的規劃由地面站或編隊內的長機完成。具體包括：1)制定戰役目標，并設置主次戰役任務的重要等級分別為ring0和ring1；2)獲取戰場全局態勢；3)啟動編隊戰術規劃；4)監督編隊整體戰術規劃的結果，內容為編隊飛機任務規劃和編隊彈藥規劃的總體結果；5)依據戰場態勢，確定戰場的不確定戰役目標；6)當所有戰役目標都有解決方案且作戰飛機載荷都已加載完成時，戰役層的規劃結束。

戰役層規劃中的基本要素為任務、平臺和決策者，三者之間的關系可用如下3個矩陣表示。

1)決策者- 平臺控制矩陣md：

(1)

2)平臺- 任務匹配矩陣mp：

(2)

3)任務- 決策者分配矩陣mt：

(3)

由于時間測度是戰役層規劃結果的關鍵性能指標，用于衡量規劃的時間效率，因此給出相關數學分析如下：

1)任務完成時間fc. 主要確定第i個任務Ti的開始時間fs和任務處理時間fp，從而得到在戰役層每個執行平臺上所有任務的完成時間為

(4)

式中：T為子任務構成的集合，T={T1,T2,…，Ti,…，TM}。

2)任務間平均轉移時間ft. 該指標是指戰役層上各個任務不同發生位置之間轉移所用時間的均值。則任務間的平均轉移時間為

(5)

1.2.2 戰術層規劃

戰術層規劃由戰役規劃啟動，采用全自動方式進行。規劃內容分為以下決策層尋優和協調層尋優兩步。決策層尋優表現為作戰目標的增補與泛化過程，依據圖1中的結構關系可以進一步抽象為圖2所示的流程。圖2中：①表示由戰役目標出發，依據戰場態勢的變化，經迭代循環后增補一些必要對象為新的作戰目標，形成戰術目標集；②表示依據戰場態勢，對潛在的不確定性事件進行評估。

圖2 作戰目標的迭代優化Fig.2 Iterative optimization of operational objectives

(6)

協調層總體分為任務規劃和航路規劃兩個層次，目標在于實現作戰資源的協調和優化。以平臺利用測度來反映協調層尋優結果，它體現了平臺作為直接參與行動的物理資源，包括其資源和時間上性能的好壞。下面給出相關數學描述。

1)平臺資源利用率U. 平臺的資源利用率是任務規劃中平臺資源使用情況評價指標。對于?Pj，其資源利用率為

(7)

2)平臺時間利用率N. 該指標反映了平臺執行任務時間占整個任務執行時間段的平均比例。對于?Pj，其時間利用率為

(8)

1.2.3 離線規劃的步驟

步驟1針對主要戰術目標的解決方案。依據工事的堅固程度，確定需要使用的彈藥資源數量；依據飛機的性能(每次發射多少發彈)，確定打擊威脅所需要的總飛機數量；依據威脅的特點，確定提供攻擊波次所需要的無人機數量。

步驟2補充掩護任務的解決方案。依據戰場態勢信息，確定擔任掩護任務所需要的彈藥和飛機數量。

步驟3補充附加戰術目標的解決方案。依據戰場態勢信息，確定潛在的戰場威脅，評估可能新增的作戰任務。然后，為可能新增的作戰任務確定需要額外攜帶的彈藥和增派的飛機數量。

步驟4對編隊內的彈藥進行協調。對于不同飛機，采用交換彈藥的方法，避免出現某架飛機過多的重要任務，均衡各架飛機的彈藥載荷。

1.3 在線規劃

當編隊處于執行任務中時，需要對編隊及編隊中各架飛機進行作戰行為的監督，并適時做出適度的調整[15-16]。

1.3.1 戰役層規劃

對于戰役層，戰場態勢信息、彈藥信息和編隊無人機信息通常都集中于地面站或編隊中的長機，因此，戰役層在線規劃的具體步驟如下：

步驟1依據各種傳感器的實時信息，對戰場的全局態勢進行增補。

步驟2對于突然發生的戰場重大態勢變化，適時增補或刪減戰役目標，并設置相應的任務等級。

步驟3啟動編隊內的在線規劃。

1.3.2 戰術層規劃

對于戰術層，當編隊協同作戰過程中任務、彈藥資源或戰場環境信息發生改變時，需要進行戰術層的在線規劃，具體步驟如下：

步驟1針對新增戰術目標本身的打擊方案。依據戰役目標的對象尋找相應的彈藥，再由彈藥尋找載機。在各個任務級別比當前任務級別低的載機中，尋找打擊代價最小的載機執行戰術任務。

步驟2采取新增戰術目標打擊方案替代此前的戰術任務，進行任務重分配。

步驟3為新增戰術目標打擊方案的掩護行動尋找解決方案。

步驟4采取新增掩護行動任務方案替代的此前戰術任務，進行任務重分配。

2 多無人機協同作戰數學模型

2.1 單架無人機的運動學模型

忽略空氣阻力的影響，采用如下質點模型：

(9)

根據無人機飛行包線的約束，建立以下約束條件：

(10)

式中：φmin、φmax分別為航向角的最小值與最大值；γmin、γmax分別為爬升角的最小值與最大值；Hmin為最低飛行高度。

2.2 編隊無人機間的相對運動關系

不考慮天氣等干擾因素對編隊飛行控制的影響，對無人機編隊飛行過程進行研究[17]，建立編隊中無人機間相對運動模型為

(11)

2.3 協同代價分析

2.3.1 威脅代價

在無人機編隊飛行過程中，戰場環境中的威脅通常為組網雷達系統。對于雷達威脅，無人機在空間中某一位置的雷達探測概率與當前姿態角和自身與雷達位置的相對距離有關。若組網雷達系統中有多部雷達，則當無人機處在雷達探測范圍內時會受到雷達多次掃描，累計多次掃描的瞬時探測概率便可得到雷達對目標的發現概率。因此，組網雷達系統對無人機的聯合探測概率為

(12)

式中:P為組網雷達探測概率；Q表示系統中雷達的數量；PI表示第I部雷達的探測概率。

2.3.2 協同代價分析

在多無人機編隊協同作戰中，不僅要考慮無人機受到的威脅代價，還需要考慮多架無人機編隊成員之間的時間協同代價以及防碰撞約束條件[18-19]，才能在實現戰術規劃的目標下保證編隊成員間的安全。因此，需要從無人機的時間協同代價與碰撞代價的目標函數兩方面進行分析。

對于編隊成員間的時間協同代價，建立目標函數為

(13)

式中:Jt為時間協同代價的目標函數；ta為第a架無人機到達指定位置的實際時間；K為無人機的數量；tac為第a架無人機到達指定位置的指令時間。

對于編隊成員間的碰撞代價，建立目標函數為

(14)

編隊成員間的具體約束條件為

(15)

式中：Rmin、Rmax分別為兩架無人機之間相對距離的最小值與最大值；xd，min、xd，max分別為氣流坐標系下x軸方向上相對距離的最小值與最大值；yd，min、yd，max分別為氣流坐標系下y軸方向上相對距離的最小值與最大值；zd，min、zd，max分別為氣流坐標系下z軸方向上相對距離的最小值與最大值；φe，min、φe，max分別為航向角差值的最小值與最大值。

因此，綜合考慮無人機的時間協同代價與碰撞代價兩方面，采用線性加權指標作為綜合編隊目標函數，結合實際戰場態勢確定權重系數取值，可以得到綜合目標函數表達式為

(16)

式中：tr為編隊到達時間；ω1、ω2、ω3、ω4為函數的權重系數，分別表示時間最短、威脅最小、指令誤差最小和等效碰撞次數最少。

2.4 作戰效能分析

2.4.1 攻擊收益

在編隊協同作戰規劃過程中，為了保證編隊成員的攻擊收益最大化，需要在任務分配基礎上根據無人機所攜帶的彈藥資源評估目標打擊效果。通過分析攻擊收益，可以保障充分利用武器彈藥載荷，最大化地實現摧毀目標價值。假設每架無人機均攜帶一定數量的彈藥資源，進行如下分析：

1)無人機所攜帶的彈藥資源種類。假設第a架無人機攜帶的資源向量為Ra={R1,R2,…,RL}。例如Ra={2,0,1}表示第a架無人機裝載了第1類和第3類彈藥資源的數量分別為2個和1個，沒有裝載第2類彈藥資源。

(17)

式中：ATi為任務完成的表征系數，對于某個任務Ti，當前彈藥資源的總量大于執行任務所需的彈藥量，則所有目標成功被擊毀時ATi=1，任務完成，反之ATi=0，任務失敗。

3)作戰規劃總攻擊收益。由上述分析可以得到編隊協同作戰規劃過程中的總攻擊收益為

(18)

式中：Vi為第i架無人機的攻擊收益。

2.4.2 無人機的毀傷代價

當無人機編隊協同飛行時，假設第a架無人機執行任務Ti后的生存概率為Pai,則Pai=1-P. 對于編隊中的無人機，執行任務時造成的毀傷代價為

(19)

3 A*算法及改進方案

在進行任務和資源的合理分配后，需要為無人機編隊設計規劃作戰時的航路，這時需要利用一些路徑規劃算法解決問題。A*算法作為一種啟發式搜索算法，廣泛應用于各類智能體的路徑規劃問題中。

3.1 算法描述

在標準A*算法的航路搜索過程中，通過設定合適的啟發函數，全面估計待搜索區域可擴展搜索點的代價值，比較各點不同代價值的大小，兼顧考慮航跡點搜索的運算時間與距離代價，找出一條最優的航路。在A*算法中，通常利用對OPEN表和CLOSE表的操作實現航跡點的存儲和更新。算法的尋優運算可以表示為

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

(20)

式中：f(n)為起點到終點的路徑代價估值，n為航跡點序號；g(n)為起點到當前航跡點的實際路徑代價值；h(n)為當前航跡點到終點的最優路徑代價估值。

然而，當A*算法在大規模作戰環境中進行航路尋優時，由于航路點搜索數量龐大，傳統A*算法的時間代價會隨著搜索節點的增加呈現超線性增長，已經無法滿足無人機協同作戰過程中的實時性要求。因此，有必要對A*算法進行改進，盡可能減少搜索節點的數量，提高航路搜索效率，同時保證解的較優性。

3.2 改進方案

首先，為了提高算法的搜索精度，使待搜索區域的代價更為精確[20-21]，在傳統A*算法的(19)式中引入一個加權因子λ，其中λ>1，此時有f(n)的表達式：

f(n)=g(n)+λ·h(n).

(21)

這意味著增大了未知路徑代價在總路徑代價的占比，即增加了A*算法的搜索深度，防止算法陷入局部搜索的死區中，保證最優解的質量。

然后，為了減少搜索節點的數量規模，通過對A*算法中的OPEN表和CLOSE表的操作，對算法搜索的擴展方式進行改進。

3.2.1 單步擴展的搜索方式

在實際作戰航路規劃中，對于A*算法需要考慮的要點包括：1)結合飛機方程等物理特性，體現多約束條件下的可飛航路擴展，滿足最短直飛距離和最小轉彎半徑等限制；2)合理的單步擴展，以合理地處理好解的最優與迭代收斂速度之間以及搜索區域廣度和分辨精度之間的矛盾[22]；3)實時規劃條件下還需要考慮戰場下的威脅源限制。

當存在最短直飛距離和最小轉彎半徑限制時，可以設置A*方法的每步擴展為扇形輻射狀擴展，即從當前點E出發，在以最大擴展角αmax的水平扇面內有n+1個擴展點，當擴展范圍內存在某個威脅時，無人機從E至H的最優路徑如圖3所示。圖3中，H點為目標點，F為最佳擴展點，G為威脅與目標點在水平方向上的切點。

圖3 單步擴展Fig.3 Single step expansion

3.2.2 多層變步長擴展的搜索方式

在單步擴展時，若作戰地圖離散化后的柵格距離很小，則可能造成所得到的航路會部分穿過威脅區域，航路質量不能得到保證。為了解決這一問題，將三維擴展搜索區域劃分為具有一定高度的W個扇形平面，在單步擴展方式基礎上設計一種多層變步長的搜索策略，如圖4所示。圖4中，B2q+1,q表示扇形區域中航跡點所在的位置，q表示弧長分段的數量。

圖4 多層變步長搜索方式Fig.4 Multi-layer variable step size search method

由圖3和圖4可見，當網格間距很小時，最優擴展點F與其鄰近擴展點十分接近。若扇面離散化的過程中F未被選中，則可以用其相鄰擴展點來很好地逼近F.

在改進A*算法的搜索過程中，第c步的航跡點坐標與第c+1步的航跡點坐標計算公式如下：

(22)

式中：(xc,yc,zc)、(xc+1,yc+1,zc+1)分別為算法搜索第c步和第c+1步的航跡點坐標；αc,n和Lc,n分別為擴展搜索線段之間的夾角與對應的弧長；Lh為扇面的弧長；α0和L0分別為初始搜索角度和對應的弧長。

4 實驗仿真分析

假設編隊可以調度4架先進無人戰斗機(UCAV)，每架無人機可以攜帶2發彈藥，戰場態勢如圖5所示。計算機配置為Intel(R) Core i5-4210M @2.60 GHz，采用Windows10操作系統和MATLAB R2017a軟件進行仿真實驗。

圖5 戰場態勢Fig.5 Battlefield situation

4.1 任務分配

在任務分配的逐次迭代過程中，載機信息和彈藥資源的參數變化分別如表1和表2所示。表1和表2中標記出了每次迭代改變了的內容。

下面對表1和表2的結果進行具體分析。第1次迭代：對主要戰術目標給出解決方案，表現為UCAV 1和UCAV 2各掛載1發1類彈；第2次迭代：對主要戰術目標的掩護行動給出解決方案，表現為UCAV 2和UCAV 3各掛載1發3類彈；第3次迭代：對潛在的可能戰術目標及其掩護行動給出解決方案，表現為UCAV 1掛載1發3類彈，UCAV 2掛載1發2類彈，UCAV 3 掛載2發3類彈，UCAV 4掛載1發2類彈和1發3類彈；第4次迭代：對編隊載機的彈藥進行協調，避免同類彈過于集中，表現為UCAV 3和UCAV 4各掛載1發2類彈、UCAV 1掛載的1類彈變為2類彈；第5次迭代：對同一類彈的任務進行調整，避免掛載同一類彈的某架載機任務壓力過于集中，表現為UCAV 2和UCAV 3之間的彈藥資源進行了交換。

表1 每次迭代中載機信息的變化

表2 每次迭代中彈藥信息的變化

因此，經過5次迭代后，載機和彈藥依據任務需求合理地進行了分配。

4.2 作戰航路規劃

當戰斗打響、觸發雷達開機時，導致編隊飛行途中遭遇雷達威脅。分別采用改進A*算法和傳統A*算法進行對比仿真實驗，其中：加權因子λ=1.5，最大扇形擴展角度αmax=60°，初始擴展搜索角α0=5°，q=16，W=20，初始步長為2. 計算得到4架無人機協同作戰航路如圖6和圖7所示，作戰效能如表3所示，編隊無人機的作戰資源變化情況如表4和表5所示。

圖6 航路規劃結果(改進A*算法)Fig.6 Path planning results (improved A* algorithm)

圖7 航路規劃結果(傳統A*算法)Fig.7 Path planning results (conventional A* algorithm)

表3 作戰效能分析

由于對高射炮的打擊行動屬于ring0級的掩護任務和ring1級的戰術任務，在編隊協同打擊過程中需要對高射炮的任務進行重分配，重分配結果如表6和表7所示。

由表3可知，在4架無人機協同打擊敵方雷達、高射炮和指揮所目標的過程中，利用改進A*算法求解得到的航路在計算耗時和航路代價方面均優于傳統A*算法所求解得到的結果，提高了航路搜索的效率，驗證了改進A*算法在三維空間下多機協同作戰規劃問題中的有效性。在作戰效能方面，編隊無人機之間能夠較好地實現協同作戰，任務完成精度均在90%以上，完成質量較高。對目標的總攻擊收益在80%以上，毀傷代價相對較低，平臺資源利用率也基本保持在60%以上，整個編隊協同作戰過程中資源分配合理，能夠有效地摧毀目標。

圖8所示為改進A*算法尋優能力分析。由圖8可知，尋優能力可以具體表現為航路的總代價、擴展搜索的航跡點總數和航路的折點數，體現了航路的最優性、算法的搜索效率和飛行性能約束。分別對比λ的3種取值對結果的影響，λ=1時實際上為傳統A*算法，λ>1時為改進A*算法，λ=1.5時改進A*算法得到的航路達到最優，與傳統A*算法相比，進一步表明了改進A*算法具有較好的尋優能力。

表4 無人機協同作戰過程中的載機信息

表5 無人機協同作戰過程中的彈藥信息

表6 重分配過程中的載機信息

5 結論

本文提出了一種基于改進A*算法的多無人機協同戰術規劃方法，用于實現高效地任務分配、資源調度，提高系統整體的作戰效能。得出以下主要結論：

1)與傳統A*算法相比，改進A*算法在對作戰航路求解時具有更好的尋優能力，結合單步擴展方式和多層變步長搜索策略，提高了航跡點的搜索效率，航路總代價減小了21.57%，搜索航跡點總數減少了46.35%，航路的折點數減少了81.81%.

2)基于戰場態勢，使用戰役層和戰術層的作戰目標迭代優化方法能夠實現4架無人機之間任務和資源的合理分配與調度，保障各個作戰任務能夠順利執行。

3)編隊無人機能夠較好地完成協同打擊雷達、高射炮和指揮所的作戰任務，獲得了較高的攻擊收益，從而實現了作戰效能的最大化。與傳統A*算法相比，驗證了本文方法的有效性。

未來戰場環境將存在各種不確定的威脅，本文方法對于動態威脅的適用性有限，如何在有移動目標威脅的復雜環境下實現多無人機協同作戰，是今后的主要研究方向。