基于CBBA 的多域作戰無人系統任務規劃方法研究*

劉奇輝，劉海穎，2，黃魁華，程光權

（1.南京航空航天大學航天學院，南京 211106；2.南京應用數學中心，南京 211135；3.國防科技大學系統工程學院，長沙 410073）

0 引言

隨著戰爭形態的演變，現代戰爭的作戰活動逐漸由單域向多域、由平面向立體、由實空間向虛空間拓展，涉及陸、海、空、天、網的多域戰已成為作戰理論的研究熱點［1-2］。

現代戰爭從機械化向信息化、無人化轉變，以無人作戰單元為核心的無人系統作戰受到世界各國研究，并已在納卡沖突、俄烏沖突等戰場上得到應用［3］。合理的任務規劃是提高無人系統作戰能效的關鍵，無人系統的任務規劃主要指根據系統內的無人單元屬性與作戰任務需求進行協調分配，主要包括任務分配和路徑規劃兩部分［4］。

任務分配主要包括集中式和分布式兩種求解方法［5］。區別于集中式依賴于控制中心對作戰行動進行任務分配，分布式中的各作戰單元根據其局部態勢感知，通過通信和協商自主完成任務分配［6］。分布式方法具有很強的魯棒性和容錯性，適合解決對時效性、動態性要求較高的任務分配問題［7］。另一方面，分布式方法對作戰單元的信息化、智能化程度要求較高，促使分布式作戰體系邁上新的臺階。主流分布式方法主要有基于合同網的市場拍賣方法、分布式馬爾可夫決策方法、分散模型預測控制方法等［8-10］。其中拍賣算法面向任務的動態執行和自主求解，在求解過程中考慮了無人系統之間的通信和協商，契合分布式多域作戰自組織、自決策、靈巧化的發展要求［11］。

在拍賣算法中，無人系統分別對每項任務投標，出價最高的無人系統獲得該任務的執行權及任務獎勵?；谑袌雠馁u機制，CHOI H L 等提出了一致性束算法（consensus-based bundle algorithm，CBBA）［12］，該算法在任務包構建和一致性沖突消解兩個階段間不斷迭代得到無沖突的任務分配結果。CBBA 是一種多項式時間算法，可以很好地隨著無人系統規模和任務數量而擴展，具有比其他拍賣算法更好的收斂性，可以給出可行的無沖突任務分配解決方案［13］。

在多域作戰任務中，需要考慮由敵方防空武器、警戒雷達的使用和地形障礙等因素產生的威脅區，要對無人系統行動路徑進行規劃，避開因上述因素產生的障礙區或禁飛區。CBBA 算法在計算無人系統執行任務的到達時間和距離代價時，直接采用任務之間的歐式距離，而在任務分配結束后再進行路徑規劃，將使得任務分配結果可能不再可行。

針對多域作戰任務中無人系統分布式任務規劃問題，本文對CBBA 算法進行了擴展。首先，考慮任務時間約束、路徑威脅約束，建立多域作戰環境下的任務分配模型以及得分評價體系；其次，基于CBBA 對異構無人系統的分布式任務分配過程進行研究；將路徑規劃耦合到任務分配過程中，即在無人系統每次選取新任務時，采用粒子群算法結合三次Bezier 曲線對無人系統執行路徑進行預規劃，以規劃后的可行路徑計算實際任務得分，在得到任務分配結果時同步得到路徑規劃結果；最后以仿真實驗的方式驗證該方法的可行性。

1 多域作戰任務規劃問題描述

本文考慮到海、陸、空3 個作戰域的作戰任務，包括地面搜救（serach/rescue，SR）、空中偵察打擊（reconnaissance/attack，RA）、海上反潛（antisubmarine，AS）3 種任務，分別由無人車（unmanned vehicle，UV）、無人機（unmanned aerial vehicle，UAV）、無人潛艇（unmanned submarine，US）3 種無人系統執行。定義多域作戰任務參數如下。

作戰區域范圍：

定義Y 軸代表海岸線，X＜0 部分為陸地，X＞0部分為海洋，Z 軸代表海拔高度，Xmin、Xmax、Ymin、Ymax、Zmin、Zmax分別代表作戰區域三維最大、最小范圍，單位km。

設定有Nu個無人系統：

設定有Nt個作戰任務：

設定有N0個威脅區：

要使所有任務均得到執行，則須滿足：

多域作戰任務中無人系統任務分配的目標是在給定Nu個無人系統和Nt個任務的情況下，找到無人系統與任務之間可行的、無沖突的任務分配解并最大化得分函數。無沖突的任務分配是指每個任務最多只分配給一個無人系統，每個無人系統最多只能被分配個任務，避免出現多個無人系統重復執行同一任務的情況。多域作戰無人系統分布式任務分配模型為

滿足以下約束：

式中，xi=｛0，1｝為決策變量，xij=1表示任務Tj被分配給無人系統Ai，pi為無人系統Ai所要執行的有序任務序列。cij（xi，pi）為無人系統Ai沿序列pi執行任務Tj的得分函數。

多域作戰任務中無人系統任務分配的目標是Nu個無人系統與No個威脅區在保持足夠的安全距離條件下，最短化路徑，使得無人系統能更早地到達任務區以執行更多的任務。

2 基于擴展CBBA 算法的問題求解

通過擴展CBBA 算法求解多域作戰無人系統分布式任務規劃問題。CBBA 算法主要在兩個階段之間循環迭代，即任務包構建和一致性沖突消解。在任務包構建階段采用拍賣方法完成無人系統對任務的投標，為每個無人系統構建一個任務包bi；在沖突消解階段通過相鄰無人系統之間的兩兩通信協商消解任務分配沖突。

2.1 任務包構建

在任務包構建階段，無人系統之間異步競標任務，cij為無人系統Ai對任務Tj的出價，也即執行此任務的得分，可由得分函數計算。每個無人系統持續添加任務直到其總得分不再增高。在CBBA 中，每個無人系統將產生如下信息列表，如表1 所示。

表1 CBBA 任務包構建Table1 Construction of CBBA mission packag

1）任務包列表bi：存儲無人系統Ai的所有任務并按任務添加順序排列；

2）執行路徑列表pi：存儲無人系統Ai將要執行的任務序列，按執行先后順序排列。

3）中標無人系統列表zi：zij=k 表示無人系統Ai認為任務Tj被分配給無人系統Ak；

4）中標價格列表yi：各元素與zi相對應，存儲中標無人系統對任務Tj的出價；

5）時間列表si，sij∈si表示無人系統Ai從其他無人系統獲得信息的最新時間。

將任務Tj添加到bi中的得分為：

在任務包構建階段，所有無人系統均獨立添加任務，因此，可能出現多個無人系統將相同的任務添加到自己的任務列表中，即產生任務分配沖突，因此要對任務分配結果進行沖突消解。

2.2 一致性沖突消解

在沖突消解階段，無人系統通過通信協商對任務分配結果達成共識。如果一個無人系統在通信時發現有其他無人系統對自己任務列表中的某一任務有更高出價，那該無人系統要放棄此任務，并釋放在此任務之后添加的所有任務。通信協商時無人系統Ai可以對任務Ti執行以下3 種可能的操作。

具體操作規則如表2 所示，前兩列表示發送方Ak和接收方Ai認為給定任務Tj的當前中標無人系統，第3 列為接受方應該采取的操作。

表2 沖突消解操作規則Table 2 Operating rules for conflict resolution

表3 作戰無人系統信息表Table 3 Information table for operational unmanned systems

表4 作戰任務信息表Table 4 Information table for operational mission

表5 威脅區信息表Table 5 Information table for threat zone

沖突消解階段還需要更新時間列表si，無人系統之間每傳遞一次信息，都需對時間列表作如下更新：

式中，τ 是信息接收時間；g 為對稱鄰接矩陣，代表無人系統之間的通信網絡關系，gik=1 表示在時間τ 時無人系統Ai和Ak間存在鏈接，可以通信。

通過沖突消解，所有無人系統的中標信息將達成一致。之后無人系統繼續添加任務，在任務包構建和沖突消解兩個階段間循環，直到所有無人系統任務包達到穩定并不再有沖突，即得到最終的無人系統任務分配結果。

2.3 路徑規劃

對于存在威脅區的作戰環境，在任務分配后進行路徑規劃，得到的航程與歐式距離之間可能存在較大差異，本文將基于3 次Bezier 曲線的路徑規劃耦合到任務分配中，以提高任務分配結果的可靠性。在實際作戰環境中，路徑規劃問題是一個多約束條件下的優化問題，既要保證路徑長度盡可能小且與威脅區保持安全距離，又要符合無人系統動力學與運動學約束。Bezier 曲線是一種有效的曲線曲面構造方法，特點在于其“皮筋效應”，通過調整控制點以改變Bezier 曲線的形狀［14］。Bezier 曲線的應用可以使路徑的曲率更加平滑和連續，與無人系統的動力特性相符。

2.3.1 Bezier 曲線

Bezier 曲線是利用控制點圍成的特征多邊形來定義曲線，改變特征點位置即可改變曲線的形狀。給定n+1 個控制點，可以定義n 次多項式曲線。Bezeir 曲線各點參數方程如下：

式中，Pi為第i 個頂點的坐標值，Bi，n（t）是n 次Bernsetein 基函數。

根據定義，可推導出Bezier 曲線的一階和二階導數如下：

空間曲線的曲率可表示為：

其中，P（t）=［x（t），y（t），z（t）］。

當t 在區間（0，1）上變動時，就生成了Bezier 曲線。Bezier 曲線的起點和終點與特征多邊形的起點和終點重合，即分別為路徑規劃的起點和終點；中間點為待調參數點，本文采用的是3 次Bezier 曲線，由粒子群算法對兩個控制點進行尋優。

2.3.2 PSO 算法

粒子群算法（particle swarm optimization，PSO）是一種模擬鳥群飛行行為的仿生智能優化算法，對此行為的模擬可以實現虛擬鳥群在解空間內的最優解搜索［15］。

PSO 算法中，每個粒子的位置代表待優化問題的一個候選解，粒子以一定的速度飛行從而不斷更新位置，即改變候選解的取值以實現對待優化問題的求解。粒子i 的運動受到兩個極值的影響，一個為粒子i 的個體極值Pbest，是其在迭代過程中所經歷的最優位置；另一個是全局極值Gbest，是整個種群在迭代過程中所找到最優位置。粒子i 的速度和位置更新公式如下：

式中，wmin為最小權重，wmax為最大權重，Tmax為算法的最大迭代次數，Tcurrent為當前迭代次數。

2.3.3 適應度函數

在有禁行區的情況下，無人系統路徑規劃主要考慮路徑長度、安全距離、路徑平滑性。定義路徑長度適應度函數如下：

式中，Lmin是路徑起始點之間的直線距離，L 是規劃后的路徑弧長。定義安全距離適應度函數如下：

式中，dmin為路徑與禁行區邊界之間的最小距離，Dk為安全距離。定義路徑曲率適應度函數如下：

式中，kmax為路徑曲率最大值，K 為給定路徑曲率上限?？偟倪m應度函數定義為：

式中，a1、a2、a3為權值系數，表示路徑長度、安全距離、曲率在路徑規劃中所占的比重。

2.4 得分函數設計

在設計得分函數時，既要滿足邊際增益遞減，又要考慮時間折扣以符合真實環境。綜合考慮多域作戰對任務執行的及時性、任務遠近程度、無人系統路徑損耗等因素，設計得分函數如下：

式中，Rj0為任務Tj的靜態獎勵值；Lij為無人系統Ai的當前位置與任務Tj之間的路徑弧長，為PSO 路徑規劃的最優值。tij為無人系統Ai沿路徑pi執行任務Tj的時間；tji 為無人系統Ai直接前往任務Tj所需的時間；λ1、λ2為任務Tj的時間折扣率，均小于1，分別決定著任務執行時間、任務距離遠近對得分的影響，可以由指揮人員或專家評估系統，根據對作戰任務執行的不同側重點確定其取值；wj（tij）表示tij是否滿足任務Tj時間窗口的二元變量，表示如下：

可以得到擴展CBBA 任務規劃的流程如圖1 所示。

圖1 擴展CBBA 算法流程圖Fig.1 The extended CBBA algorithm flow

3 仿真實驗與分析

本文以考慮威脅區的海陸空三維作戰環境為例，無人系統分別執行對應域的靜態作戰目標，暫不考慮目標機動性和環境因素對無人系統速度的影響，假設無人系統均為勻速運動。在200×200×20 km的三維空間區域內存在15 個任務和10 個圓形威脅區，其中，包括5 個搜救型任務，5 個察打型任務，5 個反潛型任務。要求作戰無人系統不能進入禁行區內部或上方空域，并保持一定的安全距離。投入6 個無人系統參與作戰，包括兩輛無人車，兩架無人機，兩艘無人潛艇，要求無人系統與禁行區保持2 km 的安全距離。在進行路徑規劃時，設置粒子群參數為：種群規模N=50，學習因子c1=c2=2，wmin=0.1，wmax=0.9，Tmax=150，權值系數a1=1，a2=1，a3=1，曲率上限K=0.01。所有無人系統均能通信，作戰任務及作戰無人系統信息如下。

此外，作戰目標靜態收益均為100，察打型任務時間折扣因子λ1、λ2分別為0.2、0.03，任務耗時10 min；搜救型任務λ1、λ2分別為0.2、0.05，任務耗時20 min；反潛型任務λ1、λ2分別為0.2、0.05，任務耗時10 min。

在CBBA 算法進行任務分配時，無人系統對任務的選擇依賴于粒子群算法的路徑規劃結果，每一次競標都要進行一輪路徑規劃。而對于靜態作戰目標，各任務之間的最優路徑是固定的，因此，無人系統可提前對同類型任務按開始時間順序進行兩兩路徑預規劃，之后在選擇任務時調用預規劃的結果，以減小計算時間。兩個任務間存在有效執行路徑的條件如圖2 所示。

圖2 預規劃路徑Fig.2 The pre-planned path

其中，Δt 為無人系統沿規劃路徑由任務Ti到達任務Tj所需時間，按上式條件進行路徑規劃，得到路徑預規劃結果如下：

可以看出，基于PSO 算法優化的3 次Bezier 曲線路徑規劃有效地為無人系統避開了威脅區，部分路徑與威脅區安全邊界相切，可以保證路徑的平滑性并減小路徑長度。在獲得任務執行路徑網絡之后，采用擴展CBBA 算法進行多無人系統任務分配，經過4 輪通信與任務選擇后，收斂得到如圖3、圖4 所示任務規劃解。

圖3 無人系統三維時空圖Fig.3 Three-dimensional space-time diagram of unmanned systems

圖4 擴展CBBA 任務規劃解Fig.4 Information table for operational mission

由圖3 可知，所有任務均在時間窗口內得到執行，無人系統路徑均未超出作戰邊界。由圖4 可以看出，15 個作戰任務均被執行，總得分761.2 分，每個任務只被1 個無人系統執行，每個無人系統任務數量未超出能力上限，且執行路徑與威脅區均保持足夠的安全距離。整個算法過程可由無人系統獨立執行，不需要控制中心參與，實現多域作戰分布式任務規劃。

4 結論

針對多域作戰任務場景下的異構無人系統分布式任務規劃問題，提出一種擴展CBBA 算法對其進行求解。建立考慮任務時間約束、路徑威脅約束條件下的任務分配模型及評價體系；采用CBBA 算法求解異構無人系統的分布式任務分配問題，得到無沖突的任務分配方案；將基于3 次Bezier 曲線的路徑規劃耦合到任務分配過程中，在得到任務分配結果時同步得到路徑規劃結果；仿真實驗表明，提出的方法可以在有效避開戰場威脅區的同時，為無人系統規劃出無沖突的任務分配方案，能夠適應多域作戰中無人系統的分布式任務規劃要求。