無人機蜂群作戰任務規劃研究現狀與展望*

孫 彧，潘宣宏*，戴定成，楊 杰，解學昊

(1.海軍指揮學院,南京 210000;2.解放軍31102部隊,南京 210000)

0 引言

無人機具有低成本、無傷亡、操作簡便、靈活可靠等作戰優勢［1-4］，在近來的局部沖突和戰爭中大放異彩，因此，各國都加大了對其相關概念技術的研究力度。而無人機蜂群［2］作為一種新型作戰樣式，主要以大量中小微型無人機為基礎單元，根據作戰任務搭載對應載荷，通過云計算、大數據、人工智能算法等關鍵技術形成自主協同的集群［5-6］，在任務規劃指令的引導下遂行偵察預警、電子干擾、火力打擊等任務［7-8］。

無人機蜂群作戰任務規劃，是組織實施無人機蜂群作戰的核心，對其作戰能力的發揮至關重要［9-10］。無人機蜂群作戰任務規劃通常分為任務分配和航跡規劃兩個核心部分。無人機蜂群任務分配（task assignment）是在滿足環境和任務條件的基礎上為無人機蜂群分配一個或一種有序的任務序列，使任務完成最大化和己方損失最小化［1，11-12］；無人機蜂群航跡規劃（path planning）則是一個多約束的組合優化問題，其根據任務需求、戰場環境、威脅源等約束條件，為蜂群規劃出一條最優或次優的安全航跡，以保證作戰任務的完成［7，13-16］。

本文按照分類方式、分配模型、典型方法的思路，對比分析了無人機蜂群任務分配方法；按照規劃流程、約束條件、規劃算法的思路，闡述了無人機蜂群航跡規劃方法；展望了無人機蜂群任務規劃的關鍵問題和未來發展趨勢。

1 無人機蜂群作戰任務規劃概念及流程

1.1 無人機蜂群作戰任務規劃基本概念

作戰任務規劃是在綜合作戰環境、作戰企圖、任務需求、作戰資源、作戰規則等約束條件情況下，為實現作戰目的，運用科學規劃方法對整個作戰行動進行設計的過程［17-20］。無人機蜂群作戰任務規劃是以無人機為基礎單元，以不同任務載荷為集群劃分［21-23］，囊括任務分配、航跡規劃、仿真推演等多步流程的作戰概念，與傳統無人機作戰任務規劃相比，其更強調蜂群行動協同的優化和群體智能的涌現［5-6，24-25］，是無人機蜂群作戰的核心環節。

1.2 無人機蜂群作戰任務規劃流程

由于無人機蜂群作戰無飛行人員直接參與，蜂群按照遠程指令完成作戰任務，且作戰任務規劃中各要素互相耦合，約束條件復雜多變。因此，對規劃過程的細致性和準確度要求更高。典型的無人機蜂群作戰任務規劃流程為：1）輸入上級作戰行動構想，包括戰場態勢、作戰任務、行動設想等；2）根據約束條件進行任務預先分配和航跡規劃；3）如果戰場態勢發生變化，則臨機調整任務分配計劃；4）對任務規劃結果進行仿真推演，如果未達到預期作戰目標，則調整行動構想，迭代規劃過程；5）如果達到預期作戰目標，則輸出規劃結果，并以指令的方式引導無人機蜂群完成作戰任務。無人機蜂群實際作戰行動中涉及更為復雜的觀察—調整—決定—行動（observe-orient-decide-act，OODA）指揮控制流程［17，26-27］，不在本文作戰任務規劃的研討范圍之內。

本文的方法介紹涵蓋臨機任務預先分配、任務分配和航跡規劃等各任務規劃環節，但分類方式有所不同。

2 無人機蜂群任務分配及典型方法

無人機蜂群任務分配是其任務規劃流程的第一步，任務分配是指在給定無人機蜂群種類和數量的前提下，基于戰場環境和任務需求，充分考慮無人機各項性能指標，研究如何將合適的任務在合適的時間或合適的地點分配給合適的蜂群，進而形成對應的任務∕目標點序列，最終實現最優作戰效能和最小己方代價［1，9，11，13］。不同無人機蜂群通過高效的任務分配可完成綜合作戰行動。

2.1 任務分配模型

建立任務分配模型是構建任務分配方法的先決條件。根據無人機蜂群所執行作戰任務的不同，可以將任務分配模型劃分為單任務模型和多任務模型兩大類。單任務分配模型是指無人機蜂群共同執行單一任務的分配模型，主要有多旅行商模型（multiple travelling salesman problem，MTSP）［28-30］和車輛路徑模型（vehicle routing problem，VRP）［31-33］；多任務分配模型是指多個蜂群協同執行多項任務的分配模型，主要包括動態網絡流模型（dynamic network flow，DNF）［34-37］、多維多選擇背包模型（multidimensional choice knapsack problem，MCKP）［38-41］、混合整數線性規劃模型（mixed-integer linear programming，MLP）［42-44］、合作多任務分配模型（cooperative multiple task allocation problem，CMTAP）［45-47］等。各分配模型主要特點如下頁表1所示。

表1 典型任務分配模型及特點Table 1 Typical task allocation model and characteristics

2.2 任務分配方法

任務分配方法在現有分配模型的基礎上通過運行計算實現任務分配。根據已有文獻資料，無人機蜂群任務分配方法有多種分類方式，按任務規劃架構可以分為集中式［48-51］和分布式［52-54］；按分配時機可以分為預先式［55-58］和臨機式［59-61］；按任務特性可以分為動態［62-65］和靜態［66-69］；按目標數量可以分為單目標［70-73］和多目標［74-78］。任務分配方法的分類方式如表2所示。

表2 任務分配方法Table 2 Task allocation method

2.3 典型任務分配方法

任務分配方法按照共性特點包含數學歸納類、啟發類、智能優化類、協商機制類等多種類型方法。

2.3.1 數學規劃類方法

數學規劃類（mathematical programming）［79-80］方法主要通過構建目標函數和約束條件解決單目標靜態預先任務分配問題，該類方法簡單易行，但隨著問題維度和約束的顯著增加，方法會因計算量過大而難以產生最優解。比較典型的有窮舉法（exhaustive method，EM）［81-83］、匈牙利算法（hungarian algorithm，HA）［84-85］、分支定界法（branch and bound，BB）［47，86-87］、動 態 規 劃 法（dynamic programming，DP）［88-89］等。

窮舉法是一種常見的適應函數尋優算法，其原理是枚舉解空間中的所有可能解，通過比對找到最優解。窮舉法原理簡單，易于實現，理論上一定可找到最優解，但面對復雜性較高的問題時，運算量巨大。該方法通常用于求解簡單任務分配問題。

匈牙利算法是早期任務分配研究的經典方法，核心是構造并求解分配代價矩陣以實現目標分配，實質是一種指派問題求解算法。該算法實現簡單，但容錯能力較差，只適合求解單任務分配問題。

分支定界法是一種求解整數規劃問題的廣度優先算法，其將任務解空間切分為較小的子集，隨后計算每個子集目標上下界，并通過不斷篩選迭代找到可行解。分支定界法在約束條件較少的情況下能夠快速形成最優解，但矩陣計算量過大，對于硬件要求相對較高。

動態規劃法將多階段任務分配問題分解為多個單階段子問題，并利用各階段的對應關系分別求解。該方法通過分段式求解降低問題難度，可有效適用多目標分配場景，但其過度簡化了分配模型，降低了分配結果可信度。

2.3.2 啟發類方法

啟發求解最初是應對NP-hard 類問題而提出的概念，即如找不到一個問題實例的最優解決方案，則通過啟發式求解方式得到滿足基本約束條件的次優解［90］。該類方法計算速度快，兼容性強，但計算量大，對初始數據要求高，一般難以得到理論上的最優解。常見的啟發類方法包括遺傳算法（genetic algorithm，GA）［47，91］、進 化 算 法（evolutionary algorithm，EA）［47，91］、禁忌搜索法（tabu search，TS）［92-93］等。

遺傳算法模擬達爾文進化論中的自然選擇和遺傳機制，利用遺傳算子完成交叉變異過程，通過對解空間進行搜索迭代演化出近似最優解。該方法不受搜索空間限制，具有較強的并行能力，但容易陷入局部最優解。提出一種自適應的遺傳算法用于無人機蜂群協同問題求解，較好克服了其局部最優問題；通過算法混合的方式，提升了標準遺傳算法的搜索能力，增加了分配精確度；分別從異構蜂群和三維環境為切入點，對分配模型和遺傳算法種群進行改進，取得了良好的任務分配效果。

進化算法是一種以進化論為基礎，模仿自然界遺傳機制進行自適應∕自組織的全局搜索方法，其搜索流程主要包括選擇、重組、變異3 個環節，經過多次迭代遺傳后，算法選擇適應度最強的個體作為最優解。進化算法與遺傳算法原理相似，優點為不受搜索空間限制，并行能力較強，在任務分配領域應用較普遍。缺點為易陷入局部最優。目前與其他方法結合是比較常見的改進方法，如文獻［47，91，94-95］等。

禁忌搜索法讓仿真實體從隨機的可行解出發，按照探索方向不斷移動，最終選擇目標函數變化最大的作為最優分配解，另外算法在探索過程中使用禁忌表規范可能的移動方向，防止盲目迭代造成死循環。相比其他方法，禁忌搜索法探索能力較強、收斂速度較快，分配效率高。

2.3.3 智能優化類方法

智能優化類方法本質是模擬動物種群自交互行為，通過在分配空間內進行順次迭代找到近似最優解。其特點是計算復雜度低，針對特定問題的自適應能力強，具有全局優化性和智能性，因此，逐漸成為大規模動態多目標任務分配的主流方法。當然，該類方法缺乏顯式的數學基礎和理論分析，有效的任務分配評價指標較少，分配結果的可信度存疑。典型算法包括蟻群優化算法（ant colony optimization，ACO）［96-98］、粒子群優化算法（particle swarm optimization，PSO）［99-101］等。

蟻群優化算法模仿螞蟻找食過程的仿生學原理，即將任務分配搜索問題等效為螞蟻找食過程，通過分泌信息素引導搜索源朝路徑最短的方向移動，從而得出最優解。該方法適用于建模困難的任務分配問題，具有較強的可擴展性和泛化搜索能力，但求解速度比較慢，易陷入局部最優。

粒子群優化算法是一種模擬鳥群飛行行為的仿生學智能優化類算法，其通過模仿粒子為尋求歷史最優位置而演化聚合的進程來選擇解空間，最后利用適應度函數實時評估得到最優解，實現最優搜索。該方法簡單高效，易于求解建模困難問題，但分配精細度不高，全局搜索能力差。其中，文獻［101］將任務分配變量離散化以適應粒子群求解框架，并考慮距離、角度、時間等因素構造相對成熟的分配函數，實現了高效的任務分配；針對粒子群算法分配精細度差的缺點，文獻［102］提出了一種基于變鄰域搜索的局部收斂策略，并同步設計了重分配方法，實現了異構蜂群的精確任務分配；文獻［100］則聚焦提升全局搜索能力進行算法改進，強化了較高數量無人機蜂群的任務分配能力。

2.3.4 協商機制類方法

該類方法主要通過設預設分布式協商競價的框架，并使用無人機蜂群自身收益代價模型和數據通信實現任務指派與交換，適合高動態多目標實時分配問題。協商機制類方法簡單直觀，可操作性較強，分配效率較高，但也存在個體利益與整體最優互相沖突，進而影響分配效果。其典型方法有合同網算法（contract net algorithm，CNA）［103-104］等。

合同網算法將任務分配看成市場交易的買賣過程，通過“招標—投標—中標”（auction-bidaward）的市場競拍機制模擬分配過程，每個蜂群單機將自身無法處理的任務對外拍賣，由其他單機投標購買，最終以整體最低代價完成最優任務分配。近來，對合同網算法的改進方法層出不窮，如文獻［105］通過在原始方法中增加原則性約束條件，實現了復雜條件下的動態任務分配；文獻［103］則在標準方法的基礎上，設置了相應的拍賣機制，解決了突發情況下任務再分配問題；文獻［106-107］也針對相應場景對合同網算法進行了改進。當前該方法絕大多數研究主要面向不完全信息條件下多目標動態分配問題。類似的改進的方法也有許多，如文獻［108-110］等。

典型任務分配方法及特點如表3所示?？傮w而言，無人機蜂群作戰任務分配從原始的單任務、小空間、集中式，逐漸向異構型、協同化、多任務方向發展，多種類型方法結合成為主要求解模式。

表3 典型任務分配方法及特點Table 3 Typical task allocation methods and characteristics

3 無人機蜂群航跡規劃及典型方法

無人機蜂群航跡規劃主要在任務分配的基礎上，綜合考慮蜂群平臺、任務區域、威脅源、打擊目標、協同關系等諸多約束條件，規劃出從出發點到打擊目標點之間的最優飛行航跡，使得己方損失最小化和任務完成最大化［13-16，111-112］。

3.1 航跡規劃流程

無人機蜂群航跡規劃流程有以下步驟：1）輸入任務分配指令；2）設置約束條件，包括蜂群平臺自身約束、任務條件約束、戰場環境約束等；3）確定目標函數，主要依據偵察識別、干擾佯動、集群打擊等具體任務分配指令確定；4）選取相應規劃方法生成最優航跡；5）通過仿真推演驗證規劃航跡的有效性。

3.2 航跡規劃約束條件

無人機蜂群航跡規劃約束條件大致可分為蜂群平臺自身約束、任務條件約束、戰場環境約束三大類。其中，平臺自身約束包含飛行高度、飛行速度、轉彎能力、最小航跡長度、最大航程等無人機性能指標；任務條件約束包括戰場威脅、任務載荷、協同關系等作戰任務要素；戰場環境約束則包括作戰時間、戰場空間、地形地貌等外部條件。約束條件如下頁表4所示。

表4 無人機蜂群航跡規劃約束條件Table 4 Constraints for UAV swarm trajectory planning

3.3 典型航跡規劃方法

無人機蜂群航跡規劃典型算法主要可分為基于圖搜索、基于采樣、基于智能三大類。

3.3.1 基于圖論的航跡規劃方法

基于圖論的航跡規劃方法將無人機蜂群的所有可能航跡點轉化為狀態空間圖，通過初始狀態到目標狀態路徑構成可行航跡［113］。典型方法有單元分解法（cell decomposition，CD）［114］、柵格法（grid method，GM）［115］、路標圖法（roadmap method，RM）［116］等。

單元分解法將作戰環境切分為若干多邊形區域，在區域內聯通出發點到目標點形成代價最小的航跡路徑。該方法航跡規劃的質量取決于多邊形區域的細分程度。

柵格法將作戰空間分割為多個柵格網格，并通過啟發式搜索的方式在柵格中尋找最優航跡。對該方法而言，柵格網格顆粒度的大小往往決定算法的精細程度和內存消耗?，F實場景中很少單獨使用柵格法進行航跡規劃，比較常見的是先用柵格劃分規劃區域，再利用其他算法搜索求解最優航跡。

路標圖法本質上是對作戰環境進行采樣，綜合目標威脅因素和航跡規劃空間構建多種類型的路標圖，之后通過搜索得到最優或次優航跡。該方法根據圖形樣式可細分為Voronoi 圖［117-118］、概率路標圖（probabilistic roadmap，PR）［119］、可 視 圖（visible roadmap，VR）［120］等多個子類。Voronoi 圖將環境中相鄰兩個目標點的中垂線連接成多邊形網圖，特征與元素表征威脅區域，通過權值搜索得到最優航跡；隨機路標圖將規劃目標隨機采樣生成路標網絡，進而把航跡規劃問題轉化為圖搜索問題；可視圖規定相鄰點和威脅區頂點連線為“可視”，并順次連接“可視”點得到航跡規劃結果。路標圖法構造簡單、數量級低，可規劃出安全性較高的航跡，但規劃顆粒度較大，且可選航跡有限。

3.3.2 基于搜索的航跡規劃方法

基于搜索的航跡規劃方法對航跡規劃空間進行搜索評估，進而確定到目標位置的最優航跡點集，最終實現航跡規劃。該類方法航跡搜索距離短，因此，規劃效率較高。典型的有A*算法（A* algorithm）［121-122］、模擬退火算法（simulated annealing algorithm，SAA）［123-125］、人工勢場法（artifical potential field，APF）［123-125］、快速隨機搜索樹法（rapidly-exploring random tree，RRT）［126］等。

A*算法是一種啟發式方法，其通過計算當前點到目標點的實際代價函數值不斷擴展搜索選擇，最終得出最優航跡，該方法通常用于求解二維或三維環境下蜂群協同規劃問題。其搜索航跡短、效率高；同時，由于計算量較大、規劃時間較長，算法很難應對大空間復雜航跡規劃。其改進點包括多機協同性、環境適應度、規劃精度、規劃效率等方面。

模擬退火算法是一種基于迭代策略的隨機搜索方法，其特點是利用概率的突變性找出目標函數中的最優解，該方法可以有效避免局部最優，魯棒性較高，但需要復雜的作戰環境量化過程。

人工勢場法將戰場環境中的目標點和威脅區分別定義為對無人機機體產生引力和斥力的實體，并建立對應的勢能函數，無人機蜂群通過引力和斥力的疊加合力控制自身運動，并根據約束條件和勢能函數進行航跡規劃。該類方法無需復雜的搜索優化，計算量較小、實時性強，但易陷入局部最小值，且勢能函數需要根據特定場景定制。

快速隨機搜索樹法的基本原理是先隨機采樣產生多個節點，再利用節點在任務空間中構建隨機樹，該方法能夠在復雜規劃環境中快速找到最優航跡，但易陷入局部最優。其主要應用于考慮平臺自身約束的航跡規劃問題。

3.3.3 基于智能的航跡規劃方法

基于智能的航跡規劃方法可分為傳統智能和人工智能兩大類。傳統智能類算法包括粒子群優化算法［127-128］、蟻群優化算法［129-131］、人工蜂群算法［132］及其多種改進型，該類方法將與上述智能優化類任務分配方法相同的搜索原理應用于航跡規劃場景。

近年來，利用以深度強化學習（deep reinforcement learning，DRL）［133］為代表的人工智能類方法進行航跡規劃成為較為火熱的研究方向。該類方法主要基于馬爾科夫決策過程（Markov decision process）［134］，利用狀態轉移對區域進行探索和預測，并使用回報函數訓練最優航跡，具有極強的實效性和實時性，非常適合處理復雜未知作戰空間的航跡規劃問題。比較典型的有Q-learning［135-136］、分層強化學習（hierarchical reinforcement learning，HRL）［137-139］、DQN［140-141］、DDPG［142］、MADDPG［143-144］等。

Q-learning 是一種早期經典強化學習方法，其利用Q 表存儲回報值，通過在預定空間內不斷試錯訓練出最優航跡，該方法常用于無人機航跡規劃及避障類場景。其缺點為只適合解決離散空間規劃問題，難以滿足現實作戰環境的規劃需要。

分層強化學習方法將復雜的規劃問題分段為多個簡單子問題并依次求解，從一定程度上緩解了強化學習算法難以收斂的問題，但還是無法徹底解決連續動作選擇的難題。

DQN 將深度神經網絡（deep neural network，DNN）引入經典強化學習算法，使用值函數近似器預估動作，能夠較好地模擬連續動作空間航跡規劃。該方法的改進型較多，如文獻［140-141］等。

DDPG 主要解決兩個方面的問題，1）使用策略梯度模型仿真連續動作空間中的動作策略和算法輸入狀態，通過訓練直接輸出最優動作，并由連續時間點的動作組合成最優航跡；2）引入Actor-Critic機制，由Critic 網絡監督Actor 網絡選取最優動作。DDPG 真正意義上實現了連續動作空間的航跡規劃，但算法無法體現蜂群間的協同行為，且一旦無人機數量上升極易導致維度災難而難以收斂。

MADDPG 可以被看作DDPG 算法在解決多智能體環境中競爭合作問題的改進型方法，其核心思想可用集中訓練分散執行（centralized training and decentralized execution，CTDE）概括，即使用集中式的神經網絡進行統一訓練，按照蜂群的組成結構分布式執行，從而可有效提升蜂群間的自主協同規劃能力。該方法適合多種類異構型蜂群協同航跡規劃，但也存在訓練量較大，對硬件需求較高的不足。

典型無人機蜂群航跡規劃方法對比如下頁表5所示?？梢钥闯?，基于圖論的方法僅適合二維簡單模型的航跡規劃，對復雜作戰環境的集群規劃顯得無能為力；基于搜索的航跡規劃方法雖然搜索效率高，易得出最優解，但算法模型過于復雜，無法適應復雜的作戰場景和規劃要素；基于智能的航跡規劃方法對于以智能體為基礎單元，以無模型訓練算法為具體執行對象，較為適合應用于無人機蜂群的編組和協同任務模式，能夠以較為簡單的模型構建實現蜂群作戰靈活編組、群智涌現、動態規劃等特性，是無人機蜂群航跡規劃較為理想的求解方式和發展方向，具有極高的研究意義和價值。

表5 典型無人機蜂群航跡規劃方法對比Table 5 Comparison of typical UAV swarm route planning methods

4 無人機蜂群作戰任務規劃關鍵問題及發展方向

由前所述，研究人員在無人機蜂群作戰任務規劃領域取得了較為豐碩的成果，各類模型方法層出不窮，軍事場景的應用也可圈可點，但目前仍有較多關鍵問題亟待解決。本文分別從場景構設、規劃模型、規劃要素、推演評估、規劃模式等5方面，總結了無人機蜂群作戰任務規劃的關鍵問題，并針對各問題方面對該領域的未來發展方向進行展望。

4.1 場景構設方面

場景構設方面的問題主要表現為：1）現有規劃方法和仿真環境主要集中在二維空間問題的求解上，對于作戰空間、戰場環境、約束條件等復雜性要求更高的三維空間，其規劃完成度和置信度都不夠理想；2）為了降低規劃復雜度，現有場景考慮的條件較為簡單，大都只包括蜂群實體、任務類型、威脅條件、打擊目標等有限要素，雖然簡化了問題求解過程，但仿真真實度、全局度較低。

因此場景構設方面的發展方向主要包括：1）三維仿真場景逐漸成為主流，未來無人機蜂群作戰任務規劃場景構設重點在于研究和完善三維空間下的任務規劃求解方法，以增加仿真規劃的置信度；2）仿真場景要素更加細致全面，未來無人機蜂群作戰任務規劃將融入信息條件、體系支撐、地形氣候等多類復雜要素，在強大算力和智能化方法的加持下，不斷提升任務規劃的真實度。

4.2 規劃模型方面

任務規劃模型方面的問題主要包括：1）現有規劃模型和求解方法較為繁多，但不同模型只針對特定場景，很難形成通用的求解范式，這就導致規劃模型的適應性和魯棒性較弱；2）模型參數較為簡化，對于多參數模型的研究不足，導致現有模型很難應對多蜂群多任務復雜規劃場景。

未來無人機蜂群作戰任務規劃模型將逐漸向多任務、多場景、綜合化的方向發展。即在通盤考慮多種參數指標綜合影響的基礎上，建立符合實際的標準化任務規劃模型，以增加規劃的普適性和魯棒性。

4.3 規劃模式方面

當前無人機蜂群作戰任務規劃自主化水平較低，可以預見隨著規劃方法與模型的不斷迭代演進，智能自主的任務規劃模式必將是未來發展方向。同時也應當看見，戰爭作為一種人與技術的結合體，指揮人員必須擁有最高決策權。因此，在不斷建設智能任務規劃體系的同時，也應當深入研究如何更好地將指揮人員的經驗智慧與機器智能相結合，形成“人在回路”的規劃模式，以贏得未來戰爭的主動權。無人機蜂群作戰任務規劃關鍵問題及發展方向對應關系如表6所示。

表6 無人機蜂群作戰任務規劃關鍵問題及發展方向對應關系Table 6 Key issues and corresponding development directions for UAV swarm combat mission planning

5 結論

無人機蜂群作戰樣式是未來智能化、無人化聯合作戰的重要組成部分，任務規劃作為無人機蜂群執行各類作戰行動的基礎技術，在整個蜂群系統中將發揮舉足輕重的作用。本文通過對任務規劃流程，以及其中兩個重點問題（任務分配、航跡規劃）的模型及方法的介紹，深度分析了無人機蜂群作戰任務規化的現狀以及未來發展方向，以期在未來聯合作戰中贏得戰場主動。