通信約束下UAV集群協同攔截任務分配算法

摘 要：針對多無人機協同攔截多機動目標的任務分配問題，同時考慮到真實戰場環境中存在的通信約束以及探測范圍約束條件，本文提出了分步一致性拍賣算法（SCBAA）。首先，對真實戰場環境中存在的通信約束以及探測范圍約束等問題進行了描述分析，構建了多無人機協同攔截任務分配模型，設計了綜合效能函數以及相應約束條件。其次，為解決多無人機協同打擊單一目標的不平衡任務分配以及沖突消解問題，將原任務分配過程分為主要任務分配以及次要任務分配兩部分，通過多次拍賣以及沖突消解實現多無人機對單一目標的任務分配。仿真結果表明，該算法可有效解決通信約束條件下的分布式多無人機協同攔截問題，并適應動態環境中任務分配對實時性的要求。

關鍵詞：通信約束； 分布式任務分配； 拍賣算法； 實時重分配算法； 無人機集群； 群目標協同攔截

中圖分類號：V279 文獻標識碼：A DOI：10.19452/j.issn1007-5453.2024.04.003

基金項目： 航空科學基金 （20185853040）

隨著戰場信息化和體系化能力的提升，現代戰爭呈現出智能化、多樣化、高動態、強對抗等特點[1]，作戰模式逐漸由單一攻防對抗擴展到集群間的協同對抗和博弈[2]。其中，無人機集群（UAV Swarm）由于其具有的低成本、高效率、無人員傷亡、操作方便簡單、適用范圍廣、生存能力強等特點[3]，在現代戰爭中得到了大量應用。目前無人機種類豐富多樣，包括察打一體無人機、自殺式無人機以及小型旋翼無人機等；同時，無人機執行的任務也從傳統的偵察監視、目標引導等輔助角色，擴展到精確打擊、電子干擾、中繼通信等多元化作戰領域[4]，任務類型不斷豐富。然而在真實戰場環境中，無人機集群協同作戰往往面臨著通信受限、目標機動性高、強對抗等諸多挑戰[1]。如何在復雜戰場環境中，實現高效任務分配[5]成為當前無人機集群研究的熱點問題。

任務分配根據是否存在中心節點，可分為集中式任務分配和分布式任務分配兩種。其中，集中式任務分配[6-8]依靠中心節點生成任務分配方案，并向集群系統內各節點分發分配結果[9]。然而，由于存在NP-hard問題，當攻防雙方的規模增加時，集中式任務分配的尋優復雜度會急劇增大[2]。此外，由于存在中心節點，導致系統抗毀性不足[9]。

分布式任務分配往往通過集群內個體之間的通信交互、協商等手段解決沖突，以實現群體集體利益最大化[10]。由于不依賴掌握全局信息的中心節點，因此分布式任務分配成為當前任務分配研究熱點。Choi等[11]首先將拍賣算法和一致性算法相結合，提出了一致性拍賣算法（CBAA）以及一致性包算法（CBBA），保證至少存在50%的最優性；呂曄等[12]針對異構無人機執行多類型任務時具有的時序約束問題，提出了一種多輪次分布式拍賣算法，可實現異步計算和異步通信，具有較好的求解效率和準確性。曹嚴等[13] 針對多無人機協同任務分配的時序約束問題，提出了基于非死鎖合同網協議的分布式時序任務分配方法，可從理論上避免任務死鎖。上述文獻均假設無人機本身可與集群內的其他所有無人機進行信息交互，并可實時感知任務區域內所有目標的信息。然而，在真實作戰環境中，無人機的通信距離有限，無法實現全局通信。同時，由于通信頻率和帶寬的限制[14]，無人機無法與相鄰無人機建立持續通信。此外，由于戰場環境高度對抗，很難在執行任務過程中實時感知全局目標信息[15]。為解決上述問題，本文在原CBAA的基礎上提出了分步一致性拍賣算法（SCBAA），可實現在通信約束和探測范圍約束條件下的多無人機的局部自主任務分配。本文主要提出了分步一致性拍賣算法SCBAA，解決了通信約束以及探測約束條件下多無人機對單一目標的不平衡任務分配問題；同時，本文提出了基于交互次數的出價閾值變更機制，保證了在動態環境中仍可獲得穩定的任務分配結果，增強了任務分配算法的魯棒性。

1 問題描述及建模

1.1 問題描述

實際戰場環境中，無人機由于探測距離有限，只能獲得部分目標信息，此外，由于通信限制，同時考慮到目標信息的實時有效性，無人機無法將感知到的目標信息傳遞給集群內其他所有無人機。因此，在任務分配初期，無人機只能獲得目標群的大致位置信息，無法獲知目標群數量以及目標具體機動信息。當目標進入無人機探測范圍時，無人機才可以獲取目標具體信息，并將其傳輸給通信范圍內的相鄰無人機。

為了使信息在無人機之間可控的范圍內傳播并保證目標信息的實時有效性，本文將通信約束轉化為信息傳輸的跳數（hop）約束[15]。每個目標信息的傳輸均存在最大跳數，跳數隨著每次信息傳輸而減少，當跳數為零時，目標信息將無法被轉發。可知，在信息傳輸跳數約束下，可接收目標信息的無人機組成局部通信網絡Q，目標只能在該局部網絡中進行分配優化（見圖1）。

1.2 綜合效能函數構建

針對具有高動態的多目標任務分配問題，需要根據戰場環境進行實時的攻擊效能和攔截概率評估。本文綜合考慮攻擊優勢函數[2]和攔截效能函數[16]，提出了綜合效能函數構建方法。

（1） 攻擊優勢效能函數構建

攻擊優勢效能函數是基于當前相對運動信息，對制導難易程度的評價準則。本文中攻擊優勢函數主要包括視線角速率優勢函數、相對距離優勢函數以及速度優勢函數。

重復上述過程，直到所有無人機完成任務拍賣，本輪SCBAA任務拍賣環節結束。

2.2 SCBAA沖突消解環節

SCBAA第二階段為沖突消解環節，通過引入“主要任務出價創建時間T”，將原沖突消解過程分為主要任務沖突消解和次要任務沖突消解兩部分。

SCBAA首先進行主要任務沖突消解，主要任務沖突消解遵循CBBA沖突消解規則，即更新、重置和離開。完成主要任務沖突消解后，進入次要任務沖突消解過程。次要任務沖突消解只有在交互雙方關于主要獲勝者Z以及主要獲勝出價創建時間T達成一致時才會進行，此時雙方對于次要任務的出價才有意義。次要任務沖突消解規則同樣遵循CBBA的沖突消解規則。

SCBAA沖突消解流程如下：（1）通信連接判斷。若gim= 1，無人機i和無人機m可進行直接的信息交互，轉至步驟（2），否則轉至步驟（7）。（2）交互信息發送。無人機i將信息Zi、Yi、Ci、Ti、zi、yi、ci發送給無人機m，轉至步驟（3）。（3）主要獲勝者一致性判斷。對于無人機i，無人機m共同可感知目標k，若Zik= Zmk，轉至步驟（4），否則轉至步驟（5）。（4）主要獲勝出價時間一致性判斷。若Tik= Tmk，則轉至步驟（6），否則轉至步驟（5）。（5）主要任務沖突消解。依照CBBA沖突消解規則進行，次要沖突消解結果依照主要沖突消解結果進行變更，轉至步驟（6）。（6）次要任務沖突消解。主要任務獲勝信息不變，次要任務沖突消解依照CBBA沖突消解規則進行，轉至步驟（7）。（7）無人機i和m沖突消解完成，無人機i進入下一無人機任務沖突消解。

重復上述環節，直到所有無人機完成任務沖突消解，本輪SCBAA沖突消解環節結束。

3 仿真試驗與分析

本節以8架無人機攔截6艘水面機動無人艇的作戰場景來驗證本文提出的SCBAA算法的有效性，并對仿真結果進行分析。

3.1 仿真初始條件

假設有8架己方攔截無人機和6艘敵方機動無人艇。在感知目標信息之前，無人機平飛，感知目標信息后，采用比例導引。本文無人機性能參數如下：探測范圍DetR= 5km，通信距離ComR= 2km。本文算法參數如下：N0= 2， α= 0.6， φ1= 0.38， β=1.5， φ2= 2， k1= 0.45， k2= 0.25， k3= 0.3， γ1= 0.6， γ2= 0.4， ω= 0.2， ξ= 0.1。現給出無人機和目標初始運動信息（見表1、表2）。

3.2 仿真結果及分析

基于上述初始條件對本文所提出的算法進行仿真驗證，得到仿真結果，并對仿真結果進行分析。

由仿真結果可知，在2.486s時，UAV1首先探測到目標1，任務分配開始。圖 2描述了無人機和目標的運動軌跡，其中 □ 代表無人機，○ 代表目標，即無人艇，由圖2可知，所有無人機均實現了對指定目標的打擊。

圖3描述了無人機群在整個任務分配過程中的總收益變化。由圖3可知，在任務分配初期，隨著無人機對目標的不斷探測感知，總收益呈不斷上升趨勢，過程中出現振蕩現象，53次交互后總收益開始穩定。

圖4、圖5描述了任務分配過程中無人機自身主要任務和次要任務的變更情況。結合圖3～圖5可知，在任務分配初始階段，無人機群任務分配結果變更頻繁，無法穩定。尤其在次要任務分配方面，如圖5所示，UAV1、UAV4、UAV5和UAV8頻繁出現次要任務丟失后重新拍賣的情況，這是由于在任務分配初期，交互次數較少，出價更新閾值較低，導致主要獲勝任務出價頻繁更新，同時該階段由于不斷探測感知到新目標，主要獲勝任務結果變更頻繁無法穩定。主要任務變更以及出價更新共同導致了目標剩余價值不斷更新，次要任務被動進行更新，任務分配結果無法穩定，同時也導致圖4中無人機集群總收益出現振蕩現象。

隨著無人機群對目標的探測感知不斷完善、交互次數不斷增加、出價變更閾值不斷提高，當任務分配進入后期，出價變更閾值達到一定值時，無人機出價不再發生變化，任務分配結果以及總收益達到穩定。由圖3～圖5可知，經過100輪交互后，無人機群任務分配結果不再發生變化，總收益穩定，保證了無人機最終可命中各自目標。

4 結論

本文針對真實戰場環境中存在的高動態、通信約束和探測范圍約束等實際問題，提出了分步一致性拍賣算法。首先，將任務分配分為主要任務分配和次要任務分配，實現了多無人機對單目標的任務分配以及沖突消解。之后，引入了基于交互輪數的出價閾值變更機制，以確保即使在動態環境中也能獲得穩定的任務分配結果。通過仿真試驗證明了該算法的有效性。

分步一致性拍賣算法仍然面臨次要任務分配過程收斂速度慢、任務分配過程中結果不穩定等問題。后續將進一步研究如何提高任務分配的收斂速度，并提高在動態環境中任務分配結果的魯棒性。

參考文獻

[1]魏明英，崔正達，李運遷.多彈協同攔截綜述與展望[J].航空學報， 2020， 41（S1）： 29-36.Wei Mingying， Cui Zhengda， Li Yunqian. Review and future development of multi-missile coordinated interception[J]. Acta Aeronautica et Astronautica Sinica， 2020， 41（S1）： 29-36. （in Chinese）

[2]朱建文，趙長見，李小平，等.基于強化學習的集群多目標分配與智能決策方法[J].兵工學報， 2021， 42（9）： 2040-2048. Zhu Jianwen， Zhao Changjian， Li Xiaoping， et al. Multi-target assignment and intelligent decision based on reinforcement learning[J]. Acta Armamentarii， 2021， 42（9）： 2040-2048. （in Chinese）

[3]高璕，張磊，胡高歌，等.基于平面約束人工勢場無人機航跡規劃算法[J].航空科學技術， 2023， 34（8）：68-76. Gao Xun， Zhang Lei， Hu Gaoge， et al. UAV path planning method based on plane-constrained artificial potential field [J]. Aeronautical Science Technology， 2023， 34（8）： 68-76. （in Chinese）

[4]金源，許吉斌，展勇忠，等.無人機蜂群作戰及反制策略研究[J].戰術導彈技術，2023（3）：149-157. Jin Yuan， Xu Jibin， Zhan Yongzhong， et al. Research on UAV swarm combat and countermeasure strategy[J]. Tactical Missile Technology， 2023（3）：149-157. （in Chinese）

[5]畢文豪，張夢琦，高飛，等.無人機集群任務分配技術研究綜述[J].系統工程與電子技術，2024（3）：158-170. Bi Wenhao， Zhang Mengqi， Gao Fei， et al. Review on UAV swarm task allocation technology[J]. Systems Engineering and Electronics，2024（3）：158-170.（in Chinese）

[6]Deng Guochen， Li Meng， Wang Yan， et al， Multi-UGV cooperative task allocation base on ant colony optimization[C]. 2022 IEEE 10th Joint International Information Technology and Artificial Intelligence Conference （ITAIC）， 2022.

[7]馬也，范文慧，常天慶.基于智能算法的無人集群防御作戰方案優化方法[J].兵工學報， 2022， 43（6）：1415-1425. Ma Ye， Fan Wenhui， Chang Tianqing. Optimization method of unmanned swarm defensive combat scheme based on intelligent algorithm[J]. Acta Armamentarii， 2022， 43（6）： 1415-1425. （in Chinese）

[8]胡月，丁萌，姜欣言，等.一種面向有人/無人直升機協同打擊的地面目標任務分配方法[J]. 航空科學技術， 2019， 30（10）： 64-69. Hu Yue， Ding Meng， Jiang Xinyan， et al. Ground target assignment of manned/unmanned helicopters for coordinated attack[J]. Aeronautical Science Technology， 2019， 30（10）： 64-69. （in Chinese）

[9]曹嚴，龍騰，孫景亮，等. 信息重傳與丟包補償的多無人機分布式任務分配方法[J]. 兵工學報， 2023， 44（9）： 2697-2708. Cao Yan， Long Teng， Sun Jingliang， et al. Distributed task allo‐cation algorithm for multiple unmanned aerial vehicle based on information retransmission and package loss compensation[J]. Acta Armamentarii， 2023， 44（9）： 2697-2708. （in Chinese）

[10]翟政，何明，徐鵬，等.基于市場機制的無人集群任務分配研究綜述[J].計算機應用研究， 2023， 40（7）：1921-1928. Zhai Zheng， He Ming， Xu Peng， et al. Research review of task allocation for unmanned swarm based on market mechanism[J]. Application Research of Computers，2023，40（7）：1921-1928.（in Chinese）

[11]Choi H L， Brunet L， Jonathan P H. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Transactions on Robotics， 2009，25（4）：912-926.

[12]呂曄， 周銳， 李興， 等 . 基于多輪次分布式拍賣的異構多任務分配算法[J/OL].北京航空航天大學學報. Doi： 10.13700/j.bh. 1001-5965.2023.0156. Lyu Ye， Zhou Rui， Li Xing， et al. Multi-task assignment algorithm based on multi-round distributed auction[J/OL]. Journal of Beijing University of Aeronautics and Astronautics. Doi： 10.13700/j.bh.1001-5965.2023.0156.（in Chinese）

[13]曹嚴，龍騰，孫景亮，等.非死鎖合同網協議驅動的多機分布式時序任務分配[J].宇航學報， 2022， 43（5）：675-684. Cao Yan， Long Teng， Sun Jingliang， et al. Multi UAV distribut‐ed task allocation with precedence constraints driven by dead‐lock free contract net protocol[J]. Journal of Astronautics， 2022， 43（5）： 675-684. （in Chinese）

[14]唐蘇妍，朱一凡，李群，等.多Agent系統任務分配方法綜述[J].系統工程與電子技術， 2010， 32（10）：2155-2161. Tang Suyan， Zhu Yifan， Li Qun， et al. Survey of task allocation in multi agent systems[J]. Journal of Systems Engineering and Electronics， 2010， 32（10）： 2155-2161. （in Chinese）

[15]陳璞，嚴飛，劉釗，等.通信約束下異構多無人機任務分配方法[J].航空學報， 2021， 42（8）：313-326. Chen Pu， Yan Fei， Liu Zhao， et al. Communication-constrained task allocation of heterogeneous UAVs[J]. Acta Aeronautica et Astronautica Sinica， 2021， 42（8）： 313-326. （in Chinese）

[16]皇甫逸倫，凡永華，李辰璐，等. 基于綜合攔截效能的集群導彈目標分配方法[C].第37屆中國自動化學會青年學術年會（YAC2022），2022. Huangfu Yilun， Fan Yonghua， Li Chenlu， et al. Missile-target assignment based on comprehensive interception effectiveness[C]. 37th Youth Academic Conference of the Chinese Automation Society （YAC2022）， 2022. （in Chinese）

Multi-target Assignment Methods for UAV Swarm under Communication Constraints

Lu Xiaodong1， Wang Yiming1， Wang Wei2

1. Northwestern Polytechnical University， Xi’an 710072， China

2. National Key Laboratory of Science and Technology on Aircraft Control， AVIC Flight Automatic Control Research Institute， Xi’an 710065， China

Abstract： Considering the constraints of communication range and detection scope in the UAV swarm， this paper proposed the Stepwise Consensus-Based Auction Algorithm （SCBAA） to address the problem of multi-UAV cooperative interception of maneuvering targets. Firstly， the issues caused by the limited communication and detection range between the UAVs in the real battlefield environment are described and analyzed. Then， a localized task assignment model considering the communication constraints is proposed with a comprehensive utility function along with multi-task assignment constraints. Furthermore， to resolve the assignment conflicts of multi-UAVs targeting multi-target， the task assignment processes are divided into the primary and secondary stages， which could achieve the conflict-free assignment by applying a new consensus interaction variable that called the primary task bid creation with time variable. Finally， the mathematical simulation results demonstrated that the proposed algorithm can achieved tasking and coordinated strikes against multiple maneuvering targets even with the constraints of communication and detection range.

Key Words： communication constraints； distributed task assignment； auction algorithm； real-time reallocation algorithm； UAV swarm； multi target cooperative interception