無人機集群任務分配技術研究綜述

畢文豪, 張夢琦, 高 飛, 楊 咪, 張 安

(1. 西北工業大學航空學院, 陜西 西安 710072; 2. 山東交通學院航空學院, 山東 濟南 250357)

0 引 言

隨著無人機相關技術的突破創新和快速發展,無人機類型越來越多樣化,任務領域范圍不斷拓展,已經逐步實現從安全空域下執行偵察監視等簡單任務向對抗空域下突防打擊等復雜作戰任務的跨越式發展。與此同時,網絡化、信息化、體系化的戰場環境呈現出高動態、強對抗、巨復雜等特點,單架無人機有限的載荷能力很難獨立執行大區域監視、多目標攻擊等復雜任務,因此無人機的作戰樣式正在朝著集群化和智能化方向發展,無人機集群協同作戰是未來無人機作戰方式的重要發展趨勢。

在無人機集群作戰中,低成本、大規模的異構無人機平臺搭載不同的載荷,通過自組織協同形成規模優勢,具有資源配置靈活、戰場適應能力強等特點,可滿足巨復雜、高動態、強對抗的戰場環境下大區域協同偵察監視、協同多目標飽和攻擊等任務需求,達到集群對抗的效果,提高無人機集群的作戰效能。

無人機集群作戰帶來的巨大規模優勢和作戰效能引起了以美國為代表的世界各軍事強國對無人機集群作戰技術的熱切關注,其中無人機集群任務分配技術作為無人機集群作戰的關鍵技術之一,是實現無人機集群化和智能化的重要技術支撐,已成為國防工業部門和各科研機構、研究學者的研究熱點。

1 無人機集群任務分配技術研究現狀

目前,無人機集群任務分配技術在頂層設計、理論研究、項目論證、關鍵技術攻關等方面都取得了一定的進展。

1.1 無人機集群協同任務分配理論研究現狀

美國國防高級研究計劃局、海軍研究辦公室、麻省理工學院、賓夕法尼亞大學“格拉斯帕”實驗室和諾斯羅普·格魯門公司等研究單位在多無人機任務分配技術的研究方向上開展了大量的研究和論證工作,取得了很多理論成果,并且啟動了多個無人機集群項目。2016年5月,美國空軍發布的小型無人機系統發展路線圖——《2016-2036年小型無人機系統飛行規劃》[1]指出:為確保戰爭的制勝能力與強軍事對抗環境下的非對稱優勢,應重點研究更具成本效益和作戰威力的集群式無人機作戰樣式。同時,詳細闡述了“無人機蜂群”的概念,并計劃在2036年建成橫跨航空、太空、網空三大作戰領域的無人機集群作戰系統。2018年8月,美國國防部發布的《無人系統綜合路線圖2017-2042》[2]指出了19項近、遠期需要重點發展的面向軍事作戰需求、能大幅提升無人機集群作戰效能的關鍵技術,包括開放式體系架構、機器學習、人工智能等。美國海軍研究生院[3-4]提出了一種面向無人集群作戰體系設計的一體化框架,該框架針對未來無人機集群作戰的去中心化、自組網、扁平化結構等特點,構建了無人機集群“使命-戰術-行動-算法-數據”五層任務框架,并以無人機集群執行情報、監視、偵察和空戰任務為例分析了無人機集群在每層中的具體任務,給出了具體的軍事概念模型。

2017年7月發布的《新一代人工智能發展規劃》中多次提及“群體感知、協同與演化”“群體集成智能”“自主無人系統”等概念,同時明確指出應將人工智能與無人機集群緊密融合,借助人工智能重點突破無人系統相關核心技術,實現無人機集群相關技術的跨越式發展[5]。文獻[6]針對無人飛行器集群訪問、打擊、察打一體化等多樣化任務類型的特點和需求,結合無人機集群任務資源調度問題的約束條件與收益函數,分析論述了無人機集群任務調度技術進展和常用的智能優化算法。文獻[7]介紹了無人機集群的研究動機和研究方法,分析了無人機集群的蜂群作戰、忠誠僚機、組隊協作、狼群作戰等典型作戰模式,并提出了面向復雜作戰任務的調度與管理技術、分布式協同控制技術等亟需解決的共性關鍵技術。文獻[8]首先從任務分配和航跡規劃兩方面對多無人機任務規劃技術方法、新的技術難點進行了全面的總結,然后結合群集智能分析了無人機集群任務規劃技術的若干發展方向。文獻[9]強調協作任務分配是多無人機自主控制的關鍵技術,分析了多無人機協同任務分配在表征場景和獲得高質量解決方案方面的重要性和難點,提出了無人機群中的協作任務分配發展方向。文獻[10]通過分析復雜環境下無人集群任務場景及能力需求,論述了復雜環境下無人集群OODA(observation, orentation, decision, action)任務面臨的挑戰,梳理了無人集群自組織任務規劃、無人集群協同控制等關鍵技術及發展方向。

1.2 無人機集群任務分配問題建模研究現狀

國內外研究人員一般利用經典的組合優化問題模型來描述無人機集群協同作戰任務分配問題。經典模型主要有:旅行商問題(traveling salesman problem, TSP)模型[11]、網絡流優化(network flow optimization, NFO)模型[12]、車輛路由問題(vehicle routing problem, VRP)模型[13]、協同多任務分配問題(cooperative multi-tasks assignment problem, CMTAP)模型[14]、混合整數線性規劃(mixed integer linear programming, MILP)模型[15]、基于馬爾可夫決策過程(Markov decision process, MDP)模型[16]等。

TSP和VRP模型主要用于求解單一任務的分配問題,而對多任務情況適用性較差;NFO模型較早運用于彈藥較少的廣域搜索彈藥任務分配問題上;MILP模型描述簡潔,很容易表示涉及到數值的全局約束,將任務規劃問題描述為一個組合優化問題,實用性較強,但計算成本會隨問題規模增大而呈指數型增長;而基于NFO和MILP模型提出的CMTAP模型考慮多無人機編隊完成探測識別、打擊、毀傷評估等一系列時序任務,通過優化完成任務的總時間或者飛行的總距離來實現任務分配,更適用于復雜任務分配問題建模,但可擴展性低;在考慮系統存在不確定因素和多智能體協同系統時,可分別通過部分可觀測的MDP(partially observable MDP, POMDP)及多智能體的MDP(multi-agent MDP, MMDP)對協同任務分配問題進行建模,但上述模型均存在通用性較差的缺點。

1.3 無人機集群任務預分配算法研究現狀

任務預分配是指在無人機執行作戰任務之前,任務規劃平臺通過雷達探測或衛星探測等手段提前獲得戰場中目標點的位置與任務類型等信息,依據任務預分配算法計算得到各無人機的任務分配決策信息。針對無人機集群任務預分配問題的特點,要求任務預分配算法能夠全面考慮無人機自身約束、環境約束、任務約束等,根據不完全戰場信息得到無沖突的完備解與最優解,以最大化執行任務所獲得的收益。由于任務預分配算法靜態結構的特點,求解相對簡單,因此得到了大量研究成果,主要分為集中式求解算法和分布式求解算法兩種。

1.3.1 多無人機任務預分配集中式求解算法研究現狀

集中式求解算法可以分為最優化方法和啟發式方法兩類[17]。

最優化方法在問題有解的前提條件下,能夠基于簡化的假設求解得到問題的最優解,代表性算法包括窮舉法、分支定界、整數規劃、動態規劃等。但隨著無人機數量的增加,最優化方法求解任務分配問題的難度、計算時間都急劇增加,而且無法準確描述復雜環境下的大規模任務分配問題,不能模擬出戰場環境的隨機性和動態性,因此近年來采用最優化方法求解無人機集群任務分配問題的研究逐漸減少。

而啟發式方法面對多無人機任務分配非確定性多項式(nondeterministic polynomially, NP)難問題時,并不盲目地尋求最優解,而是通過權衡求解質量和求解時間,在可接受的計算時間內求得近似最優解、次優解或滿意解,因此其具有計算復雜度低、性能優越、易于實現等特點,被廣泛地應用到任務預分配問題。典型的啟發式算法有:遺傳算法、禁忌搜索算法、粒子群優化算法、模擬退火算法等。

遺傳算法由于使用多點并行搜索,不易陷入全局最優,且能夠以編碼的方式工作而不對參數本身操作,因此得到了大量研究成果。文獻[15]通過添加一個混洗列表來修改交叉運算符,同時引入兩個新的運算符,提高了遺傳算法求解多無人機集群任務預分配問題時的求解質量。文獻[18]為解決多無人機偵察多類型目標時的任務預分配問題,討論了一種基于對位的雙染色體編碼遺傳算法,引入基于對位的學習和多重變異算子對遺傳算法進行改進,得到了較好的求解質量。文獻[19]通過建立執行任務的收益、執行任務的時間以及任務負載因素下的任務分配整體效能模型,提出了基于分布估計思想的量子遺傳算法,實現了多基地情形下無人機任務初始分配和突發威脅下動態分配。文獻[20]提出了一種基于改進遺傳算法的元啟發式算法,解決了具有復雜無人機運動學約束、資源約束與時間約束的多無人機任務預分配問題。針對多無人機執行具有時序約束的任務預分配問題時可能出現的死鎖問題,文獻[21]對遺傳算法進行了改進,首先通過考慮目標標識符和任務優先級約束生成無死鎖個體,并設計特定的交叉和變異算法保證了后代個體的可行性。文獻[22]為有效求解時間窗約束下異構多無人機協同打擊敵雷達陣地的任務分配問題,提出了一種融合并行計算的多層編碼遺傳算法,有效提高了求解效率。

粒子群優化算法簡單易實現,參數少,并且求解速度較快,在多無人機任務分配領域得到了廣泛的應用。文獻[23]針對執行攻擊任務的多無人機協同任務預分配問題,通過位置飽和策略構造粒子的搜索空間,提出了基于自適應慣性權重的改進粒子群優化算法。文獻[24]開發了具有維度級與個體級兩個任務分配模塊的雙級任務分配粒子群變體結構,以平衡探索和開發搜索過程,具有更高的搜索精度,在求解多無人機任務預分配問題時表現出了優異的性能。文獻[25]考慮無人機任務預分配問題中的通信和任務性能因素,采用粒子群優化算法在無人機數量有限的情況下得到了滿意的預分配解。文獻[26]通過建立不同類型的救援模型,提出了基于遺傳學習策略的自適應粒子群算法,實現大規模救援場景下多無人機協同救援任務分配。文獻[27]針對異構多無人機協同觀測偵察、火力打擊、毀傷評估任務分配問題,建立了復雜約束條件下的CMTAP模型,提出了基于拐點的多目標粒子群協同任務分配算法。

目前,基于遺傳算法和粒子群優化算法解決多無人機任務預分配問題依舊是當前的研究熱點,通過改變具體的編碼方式或層級結構來提高自身求解性能,具有大量的研究成果,但大部分算法是針對特定的應用背景及約束條件進行改進,無法全面考慮實際多無人機集群任務預分配問題時存在的復雜耦合約束,算法的魯棒性與可擴展性較低。

除上述典型算法的應用擴展外,為滿足任務預分配問題的最優性、不確定性等約束,一些新的算法也被引入到任務分配問題中。如文獻[28]針對多無人機對地面目標進行察打時任務時長、時敏目標的不確定性問題,提出了基于多策略優化的灰狼算法。文獻[29]面向復雜場景下的任務分配和覆蓋搜索問題,提出了融合改進匈牙利算法和Theta*算法的仿生狼群無人機群任務分配方法。文獻[30]提出了一種基于蟻群系統的啟發式算法,以最小化任務的時間消耗為導向,在協同搜索任務中尋求近似最優解。

1.3.2 多無人機任務預分配分布式求解算法研究現狀

隨著無人機自主能力的不斷提升和無人機集群通信組網技術的快速發展,具有優越的可擴展性和魯棒性的分布式求解算法逐漸成為任務分配算法研究方向的熱點。

分布式求解算法可以進一步分為自頂向下和自下而上兩類。其中,自頂向下的分布式求解方法利用分層遞階求解的思路,將復雜任務協同分配問題逐層分解為若干個更簡單的子任務分配問題,各無人機通過協商與合作實現問題求解。其代表性方法包括:分布式MDP(decentralized MDP, Dec-MDP)方法、基于市場機制的方法、動態分布式約束優化問題(dynamic distributed constraint optimization problem, DDCOP)方法等。與之相反,自下而上的分布式求解方法通過研究無人機個體的局部感知和動態反應,設計基于反應和行為的協同優化策略,實現多無人機整體自組織任務分配。其中,典型算法有基于群智能的自組織算法(self-organized algorithm, SOA)、閾值響應法、蟻群優化(ant colony optimization, ACO)算法等。

作為典型的自頂向下分布式求解算法,基于市場機制的方法通過激勵機制來鼓勵各無人機參與任務分配買賣過程,能在較短時間得到任務問題的滿意解。文獻[31]針對異構多無人機協同打擊不同類型目標的協同任務分配問題,提出了基于分布式通信拓撲的拍賣算法,實現了異構多無人機協同任務預分配問題的快速求解。文獻[32]考慮異構無人機能力、類型分組等約束,在對偶分解任務分配問題的基礎上,提出了融合最大一致性算法的分布式拍賣算法,得到了較高的求解質量。文獻[33]首先將任務分解成不相交的子任務組,然后利用分布式拍賣分配算法使每個機器人通過逐步迭代最大化自己的目標函數,從而解決具有任務約束條件的多機器人任務預分配問題。文獻[34]在分布式拍賣算法的基礎上設計了廣播、應用、審查與提供報表、任務分配四個階段,解決了帶有時序約束的無人機集群任務預分配問題。文獻[35]在機器人壽命約束的條件下,針對任務持續時間相同與不同兩種約束情況,對分布式拍賣的任務分配算法進行擴展,使得多機器人任務預分配解的質量最優。文獻[36]基于一致性包算法(consensus-based bundle algorithm, CBBA)按優先級將目標任務歸入不同層級,只將分配過高階段任務的目標添加至相應的任務包和序列中,保證了無人機任務預分配問題的時序約束。針對多無人機作戰環境中存在的參數不確定性,文獻[37]提出用高斯回歸過程模型對任務回報值進行預測,然后采用CBBA進行任務分配,有效解決了不確定環境下的協同無人機任務預分配問題。文獻[38]針對偵察型和攻擊型異構無人機多智能體系統協同任務分配問題,考慮無人機載荷資源、子任務時序關系等耦合約束,通過改進CBBA的沖突消解規則,提出了基于改進沖突消解的一致性聯盟算法,同時保證了求解質量和求解速度,但是未考慮到動態不確定環境約束下的應用。

自下而上的分布式求解算法中,群智能算法能夠基于每個同構個體的行動決定總體趨勢,具有天然的分布性特點,對問題規模的變化不敏感,因此在協同任務預分配問題上也得到了廣泛研究。文獻[39]采用分布式搜索攻擊任務自組織算法(search attack self organized algorithm, SAMSOA)將多無人機分布式搜索任務預分配全局優化問題分解為可以利用蟻群優化算法快速求解的局部優化問題,然后通過無人機之間的信息交換得到全局最優解。文獻[40]針對多無人機協同搜索攻擊任務預分配問題,提出一種基于改進分布式蟻群優化算法的智能自組織算法,具有較高的求解質量。文獻[41]針對集群機器人任務預分配中通信負載較小、任務復雜耦合的問題,通過合理選取閾值和激勵值,提出了具有較高求解質量的閾值響應法。文獻[42]提出了基于閾值的分布式多無人機任務預分配方法,分別在充分利用無人機資源、選擇更合適的任務和負載平衡3個方面進行了擴展,具有較高的任務預分配求解質量。文獻[43]考慮環境中的自然不確定性,提出了概率決策機制下基于響應閾值模型的分布式方法,有效實現了異構機器人在有限資源下的任務預分配。文獻[44]針對無人機集群任務分配過程中的連續性和動態性,將灰狼交互機制和合作捕食行為映射到無人機集群任務分配,提出了仿灰狼合作捕食行為任務分配算法。

集中式算法和分布式算法對比分析如表1所示。

表1 集中式算法和分布式算法對比分析Table 1 Comparative analysis of centralized algorithm and distributed algorithm

除上述典型算法的應用擴展外,為滿足任務預分配問題的最優性要求和復雜約束條件,一些新的算法也被引入到任務分配問題中。如文獻[45]針對多種復雜約束,引入自適應搜索策略、重置Harmonic平均距離循環策略和全局最優引導鄰域搜索策略等策略改進多目標自適應快速人工蜂群算法,并通過定義自主決策準則引導多目標任務分配的方案選取。文獻[46]面向異構多無人機執行防空壓制任務中的任務分配問題,通過圖論建立了基于路徑約束的協同任務分配模型,并采用分布式遺傳算法進行求解,具有較好的求解速度。文獻[47]給出了一種基于交叉熵(cross entropy, CE)的任務預分配方法,解決了具有資源類型約束與任務類型約束的多類型無人機任務預分配問題。文獻[48]針對環境不確定性條件下異構無人機的任務分配問題,通過優先經驗回放和神經網絡近似,提出了基于強化Q學習的快速任務分配算法。文獻[49]通過設計多無人機智能體高回報獲取、利益分配、聯盟穩定性保證和搜索加速的歷史任務機制,提出了一種用于多無人機協同任務分配的穩定性量子粒子群優化算法。文獻[50]針對無人機在災難應急處置中執行的搜索、緊急醫療運送、救援運送和通信中繼4種任務分配問題,提出了一種近似兩階段方法。文獻[51]將納什均衡的概念應用于任務分配問題,使用貪婪策略搜索有效的納什均衡解,提出了具有預算約束的任務分配問題的博弈算法。

上述算法在針對小規模多無人機任務預分配問題時可以獲得較好的求解質量,并已有許多學者針對特定約束對算法進行擴展,但隨著異構無人機類型的逐漸增加,無人機集群規模不斷擴大,約束條件復雜耦合,上述算法的求解效率較低,求解質量也直線下降。

1.4 無人機集群任務重分配算法研究現狀

隨著戰場對抗不斷升級,無人機集群在任務執行過程中遇到突發事件時,任務重分配算法需要通過各無人機平臺之間的信息交互對戰場態勢和動態任務快速做出反應,在有限時間內完成任務的重構與優化,并達成無沖突的任務重分配方案[52]。

基于市場機制的任務重分配算法具有簡單易實現、靈活性較好、可擴展性強的優點,因此被廣泛應用到無人機集群任務重分配,并且結合具體的無人機集群任務重分配場景,對求解性能、約束滿足、沖突消解等方面進行擴展,提出了眾多改進算法。文獻[53]提出了一種基于分布式拍賣算法的博弈理論非協調決策框架,并證明其在異步網絡環境下求解大規模無人機任務重分配問題時具有較好的收斂性。文獻[54]中每架無人機在執行任務時估計所有其他無人機的位置,并在此基礎上用簡單的分布式拍賣方案實現了無沖突的任務重分配,得到了較滿意的解。文獻[55]為更好地利用有限資源,采用基于分布式拍賣的方法解決了多機器人動態任務重分配問題。文獻[56]討論了一種滿足任務執行時長約束與機器人壽命約束的分布式拍賣算法,解決了具有任務執行時間約束的多機器人動態任務重分配問題。為處理戰場環境中的通信約束,文獻[57]針對有限通信距離的場景,提出了一種基于改進市場機制的分布式任務重分配算法。文獻[58]在其基礎上針對時變網絡拓撲的情況進行了改進,提高了任務重分配算法的實用性。

上述基于市場機制的分布式任務重分配算法都面向于多個無人機協同執行任務的情況,適用規模較小,在求解大規模無人機集群協同作戰時求解性能不足,因此有學者延續市場機制的思想,提出了聯盟組任務重分配算法。文獻[59]針對突發任務的實時分配問題,提出了基于時間窗的兩階段任務聯盟組任務重分配算法,提升了大規模無人機集群任務重分配的實時性。文獻[60]針對大規模無人機集群通信鏈路部分可靠下的任務重分配問題,提出了不確定條件下部分信息可靠的無人機任務重分配一致協調算法,使算法收斂于確定性的目標函數。文獻[61]為同時將多個任務均衡地分給各異構無人機團隊,提出基于市場機制的多緊耦合多無人機任務聯盟重分配算法,得到較好的求解質量。文獻[62]將CBBA擴展以處理具有附加需求和任務依賴性的多無人機復雜動態任務重分配問題,并通過新的數據結構降低了各無人機之間的通信成本,使算法收斂到一個無沖突的可行解。文獻[63]利用貝葉斯理論定量化描述任務空間的不確定量,并采用CBBA算法實現不確定環境下多無人機的協同多任務快速重分配。文獻[64]提出了改進的CBBA,并建立了基于一致性協調理論的沖突消解規則,利用在線協同策略在有限時間內得到多異構無人機任務重分配問題的較優解。

除了經典的基于市場機制的分布式任務分配算法之外,相關學者也針對動態環境中任務重分配問題的特點提出了許多新的算法,并證明有較好的求解效率與求解質量。如文獻[65]設計了新的動態環境激勵、響應閾值和轉移概率,提出了具有對動態環境實時響應能力的動態蟻群分工模型,有效提高了多無人機任務重分配問題的求解效率。文獻[66]討論了一種改進雙組分狼群搜索算法與經典內點法結合的在線分層規劃方法,解決了具有參數與時間敏感的不確定性的多無人機任務重分配問題。文獻[67]提出了基于令牌協議的群體智能策略與廣義分配方法,能夠隨著無人機數量的變化和新目標的出現實時完成動態任務重分配。文獻[68]針對多智能體協同圍捕問題,建立了追逃微分博弈模型,采用自適應動態規劃方法,為各個智能體規劃圍捕目標及運動軌跡。文獻[69]提出了一種基于資源福利的分布式任務分配方案,通過使無人機編隊平衡資源消耗,以保留更多可用無人機來平穩地響應動態事件,提高多無人機對動態事件的響應能力。文獻[70]為最大化提升無人機編隊對多個時敏目標的作戰效能,提出了時敏目標時間窗口約束下的多無人機動態任務重分配算法。文獻[71]針對平臺失效和新增任務兩種突發事件下的任務重分配問題,考慮任務完成精度、任務順序等約束條件,提出了基于可執行任務序列和貪婪策略的任務重分配算法。文獻[72]提出了分布式深度壓縮算法和分布式快速壓縮算法兩種多無人機在線任務分配算法,較好地解決了具有時間窗口約束的異構多無人機任務重分配問題。文獻[73]設計了通信延遲、丟包等約束下帶比較閾值的沖突任務預測與消解機制,提出了基于改進分布式轉運指派算法的多無人機任務重分配方法。文獻[74]采用了一種基于免疫多智能體網絡框架的分布式免疫多無人機任務重分配算法,得到了較好的求解速度。文獻[75]在隨機、動態環境下,將任務分配問題表述為動態匹配問題,并提出了一種基于多等待列表的任務分配(multiple-waitlist based task assignment, MWTA)算法來尋找時間變化環境下的穩定匹配,證明了MWTA可以實現包含策略保護、效率和無嫉妒性的動態穩定性。文獻[76]針對異構無人機集群執行區域察打任務過程發現新目標時的局部任務重分配問題,利用信息一致性算法設計了通信約束下異構多無人機聯盟構建方法,提出了基于改進分布式合同網的多無人機任務重分配方法。文獻[77]針對無人機輔助物聯網中的動態任務分配,通過基于多種群的遺傳算法以及結合動態規劃和改進的K-means聚類的混合算法來解決聯合任務分配和無人機軌跡優化問題。文獻[78]針對無人機多智能體系統攻擊任務場景中突發故障情況下的任務重分配問題,考慮任務時效性和同步性等約束,提出了基于勢博弈理論的任務重分配算法。

1.5 無人機集群與其他無人系統聯合應用下任務分配研究現狀

隨著智能自主技術、體系作戰的快速發展,無人機、無人車、四足機器人、無人水面艇、無人水下航行器等無人系統逐步成為能改變未來戰爭形態和作戰樣式的關鍵性武器裝備。無人系統的聯合應用也向“協同、群智”的趨勢發展,已受到廣泛關注。

解放軍報2019年10月發表《加速推進軍事智能化》文章,將智能集群作戰協同技術列為智能化戰爭的基石;“智領群蜂”國際無人蜂群技術大賽力求通過無人機、無人車聯合協同,驗證空中快速避障集結、協同搜索任務等群集智能多任務分配策略。文獻[79]提出了基于異構強弱、規模大小的異構無人系統分類依據,介紹了異構無人系統協同的內涵和作戰想定,論述了異構無人系統協同作戰中涉及的協同架構、協同任務規劃等關鍵技術。文獻[80]面向由無人車和無人機組成的空地異構無人系統協同執行巡邏任務,提出了融合遺傳算法的改進蟻群優化算法。文獻[81]針對多無人機與無人車協同進行多目標、大區域范圍的察打一體化任務分配問題,利用密度最大值聚類方法進行子任務區域劃分,提出了基于混合遺傳算法和粒子群優化算法的空地異構無人系統協同任務分配方法。文獻[82]針對最后一英里配送中無人機與地面車輛聯合作業任務分配問題,以最小化包括運輸成本和等待懲罰在內的總運營成本為目標,提出了基于MILP和貪婪隨機自適應搜索的聯合配送任務分配算法。文獻[83]面向多無人機與運輸車聯合進行“最后一公里”的貨物配送任務分配問題,提出了區塊鏈式拍賣算法。文獻[84]以“多無人機-無人水面艇”聯合進行海洋大數據收集為背景,提出了基于K-means聚類算法的分組任務分配方法。文獻[85]針對多無人機-多無人車協同任務分配問題,建立了單任務智能體-多智能體任務下的雙層任務分配模型,提出了基于圖神經網絡架構和MILP的多機器人靜態任務分配方法。

2 無人機集群任務分配技術面臨的問題

隨著無人機集群相關技術的迅猛發展,無人機集群在平臺異構性上從單一的同構平臺發展到復雜多任務下多異構平臺,在成員規模上從傳統多機編隊的數架無人機擴展到幾十架甚至是成百上千架的無人機集群。同時,伴隨著無人機集群作戰樣式的轉變,無人機集群的作戰任務類型更加復雜,從僅可執行安全空域下偵察監視等簡單任務拓展到執行對抗空域下突防打擊等復雜作戰任務,研究方向由簡單任務的預分配技術轉變為復雜多任務的預分配和動態環境下實時重分配,大規模無人機集群任務分配技術在模型建立、算法求解、任務分配實時性等研究方向的一些問題也暴露出來。

2.1 無人機集群任務分配建模的架構問題

在異構無人機集群任務分配模型的架構設計上,許多研究人員只是在經典多無人機協同任務分配模型的基礎上面向特定的異構無人機任務需求與約束條件進行改進,沒有提出無人機集群任務分配建模的架構理論,沒有依據多任務適應性綜合考慮真實戰場環境中的各種約束及優化目標。如戰場中的不確定性、平臺異構性、通信約束、任務的時序約束、資源約束等,只面向某些特定約束條件與應用場景下的任務分配問題,建立模型不能夠面向不同作戰環境和作戰任務,對無人機集群任務分配的規模擴展性不足。

因此,如何立足于動態多變、高度不確定性的真實戰場環境,在考慮多種無人機類型、通信約束、不同任務需求目標、多種約束相互耦合的情況下“向實戰聚焦”,探究更符合真實戰場的異構無人機集群任務分配架構,是大規模異構無人機集群任務分配的一個嚴峻問題,也是異構無人機集群任務分配算法能否真正應用于實戰的一大挑戰。

2.2 面向多任務的無人機集群任務預分配算法最優解求解問題

當前的大部分無人機集群任務預分配算法求解都是面向中小型規模的同構無人機集群,無法對大規模異構無人機集群任務分配問題的多約束因素進行有效解耦,且不能高效處理有優先級差別的任務,求解復雜度隨無人機集群的規模呈幾何級數增長,甚至導致出現無法求解的情況。

隨著無人機集群任務預分配的研究對象從小規模的同構無人機轉向大規模的異構多平臺無人機,研究方向由確定信息下的簡單任務預分配轉變為不完全信息下的復雜多任務預分配,任務預分配所涵蓋的范圍和規模不斷擴大,主要表現為:約束條件繁多且耦合程度高,強對抗戰場環境導致指標因素具有強不確定性,機載傳感器、武器載荷等任務要素復雜,任務預分配結果需符合作戰意圖等。這些都對任務分配算法求解提出了新的挑戰。

因此,如何對集群任務中的時間、資源、空間約束信息進行有效的表示和推理;為最大化提升異構無人機集群的作戰效能,如何盡可能求解得到異構無人機集群任務預分配的最優解等都是需要深入考慮的問題。

2.3 有限時間下面向突發事件的無人機集群任務重分配算法尋優問題

與無人機集群任務預分配相比,無人機集群任務重分配既要克服戰場態勢信息的動態性所帶來的負面影響,又需要在資源和時間都有限的條件下得到合理可行的分配結果。

目前,大多數無人機集群任務重分配只是將突發事件作為任務重分配問題的一種約束,不能合理區分不同突發事件對原有任務分配方案帶來的不同影響,對突發事件的處理能力較低;而且隨著問題復雜度的增加,求解效率直線下降,算法的收斂速度不能滿足動態環境下的實時性要求。在實際作戰中,由于任務環境的不確定性、情報信息的誤差,以及高度對抗環境中不斷變化的戰場態勢,要求異構無人機集群任務重分配方法能夠面向突發事件克服信息的動態性和不確定性,在有限時間下快速給出較優解。

因此,面對動態對抗環境下的突發事件,如何對沖突任務進行消解與優化,以及如何利用高性能的重分配算法在局部最優和全局最優間進行合理有效的折中,以便在有限時間下獲得無人機集群任務重分配的較優解,是無人機集群任務重分配研究中的關鍵問題。

2.4 路徑規劃緊耦合下面向大規模異構無人系統的協同任務分配問題

當前的大部分任務分配算法都將任務分配與路徑規劃分離,以松耦合的方式先求解任務分配,再對單平臺進行路徑規劃,忽略實際路徑對分配任務執行的影響。而多變任務類型和復雜動態環境下大規模異構無人集群協同任務分配不僅要在整體宏觀層上進行異構無人集群內各智能體的任務分配,而且要在個體動力學層上為每個智能體設計路徑軌跡,實現路徑規劃耦合下的任務分配,使得大規模異構無人集群作戰效能近似最優。

與此同時,國內外在針對不同應用場景下的較小規模異構無人系統協同任務優化分配算法已取得較為扎實的研究成果。然而,面向大規模異構無人系統協同任務分配問題時,隨著規模的迅速增長和異構性的增強,已有的方法大多適用性不足;其次,異構無人系統協同任務分配需要依靠集群通信組網獲取信息,時延、拓撲時變、丟包、誤碼等通信約束大幅增加了大規模異構無人系統協同任務分配的難度。

如何在路徑規劃緊耦合下考量異構耦合涌現效應,更高效、合理地實現異構無人系統的協同任務分配,是未來大規模異構無人系統協同任務分配的關鍵問題。

3 無人機集群任務分配技術的發展方向

3.1 基于模型的系統工程的無人機集群任務分配的通用化建模理論

近年來,基于模型的系統工程在復雜系統和航空航天領域各個領域的興起[86-87],通過對模型的系統工程中元模型的研究可大大降低系統建模的復雜度,為復雜系統的建模提供一個公共和一致的標準。文獻[88]為解決C4ISR(command,control,communication,computer,intelligence,surveillance,reconnaissance)系統中對武器裝備體系認知的不確定性問題,提出統一采用元模型對環境、能力、用戶、作戰、資源、管理和公共7類數據進行描述,實現C4ISR系統的互聯互通互操作性。文獻[89]針對C4ISR系統中抽象層次高的能力需求建模復雜問題,構建了面向C4ISR系統建模的能力元模型,有力地支持了后續應用層模型的構建與開發。文獻[90]為評估指揮與控制體系結構對動態變化環境的適應能力及完成任務的能力,建立了包含資源元模型、任務元模型和控制元模型的體系任務分解模型,為后續指揮與控制體系結構評估模型的構建提供了建?；A和標準。

無人機集群任務分配的數學描述模型可概括性地表述為:異構無人機平臺(Who)在特定位置(Where)上,為完成某種集群任務而按照一定的約束條件/作戰規則(Why)執行自身分配到的任務(How)并產生與消耗作戰資源(What),即無人機集群任務分配“4W1H”關系,如圖1所示。

圖1 無人機集群任務分配“4W1H”關系圖Fig.1 “4W1H” relational graph of unmanned aerial vechtle swarm task allocation

因此,在建模理論方向,迫切需要分析動態多變、高度不確定性的戰場環境下無人機集群作戰的使命任務、作戰樣式和作戰流程,綜合考慮平臺異構性、通信約束、任務的時序約束、資源約束等約束條件,研究利用基于模型的系統工程方法建立不確定環境下無人機集群任務分配的單任務、任務需求、約束條件、能力和無人機平臺等元模型,構建面向復雜多任務的、具有通用性和可擴展性的無人機集群任務分配建模理論。

3.2 不完全信息下面向多任務的基于生成對抗網絡的無人機集群任務預分配技術

近幾年來人工智能和深度學習理論迅速發展,引起各個領域的廣泛關注[91-94],其在軍事領域應用的研究如火如荼。尤其是深度學習中的生成對抗網絡(generative adversarial networks, GANs),作為一種深度學習網絡結構由Goodfellow提出后,滿足了許多領域的研究和應用需求[95-97]。在網絡結構方面,GANs采用的神經網絡結構不限制生成數據的維度,大幅拓展了生成模型生成數據樣本的能力范圍;在建模能力方面,GANs能夠逼近任意函數,應用范圍廣泛。GANs以其在處理復雜數據信息時的優越性,能為求解具有復雜約束關系的異構無人機集群任務預分配最優解的提供新的研究思路和解決途徑?；贕ANs的無人集群任務預分配網絡框架如圖2所示。

圖2 基于GANs的無人集群任務預分配網絡框架Fig.2 Task pre-allocation network framework of unmanned aerial vehcile swarm based on GANs

將深度學習理論與無人機集群任務預分配技術交叉融合,并在不完全信息下利用GANs針對不同任務需求高效地求解面向多任務的異構無人機集群任務預分配的最優解將是無人機集群任務分配研究中的熱點方向。

3.3 有限時間下面向突發事件的基于性能影響算法的無人機集群任務重分配技術

啟發式的性能影響算法在2016年被首次提出[98],該算法是一種源于CBBA的完全分布式啟發式算法,其使用性能影響的新概念對任務包進行評分和組織,在可進行局部通信的無人機上并行迭代運行任務包含階段、協商一致和任務刪除階段兩個部分來系統地交換任務,使用特定的度量標準來度量所有任務,逐步構建和更新這些代理的任務。性能影響算法結構具有較高的可擴展性和魯棒性,其采用的并行局部通信方式適合于未來高動態對抗、高通信約束的戰場環境,已被證明其在求解具有時敏的任務動態重分配問題時具有較好的表現,而且目前對基本性能影響算法的改進也已經取得了較多的成果。文獻[99]針對基本性能影響算法中可能存在的局部最優和不能處理突發任務的缺點,首先對算法進行了擴展,使其允許實時動態在線重規劃,然后通過引入一個額外的soft-max操作來提高算法的探索性,并在文獻[100]中提出利用性能影響Max Ass算法為未分配任務創造可行的時間段,實現任務分配數量的最大化。文獻[101]為滿足在線重規劃時嚴格的時間窗約束和最大資源利用率的約束,在基本性能影響算法的基礎上提出一種任務交換分配算法,為未分配的任務創建可行空間。文獻[102]對任務納入和沖突解決的標準進行了修改,以總效益最大化而不是最終分配方案的平均等待時間最小化作為全局目標,提出了帶有關鍵任務的擴展性能影響算法(extended performance impact algorithm for critical tasks, EPIAC),并設計了一個新的任務列表調整階段以分配關鍵任務。文獻[103]針對分布式多無人機在動態環境中的任務重分配問題,建立了根據動態事件的類型確定處理策略的分布式框架,設計了子團隊形成機制和部分釋放機制,并基于此提出了部分重分配算法,能夠以較少的數據交換和運行時間獲得無沖突的任務重分配方案。

有限時間下基于改進性能影響算法的無人機集群任務重分配框架如圖3所示。

圖3 有限時間下基于改進性能影響算法的無人機 集群任務重分配框架Fig.3 Task reallocation framework of unmanned aerial vechile swarm based on improved performance impact algorithm in limited time

針對無人機集群任務重分配應對動態對抗環境下多種突發事件的實時性需求,研究如何對沖突任務進行消解與優化,為后續無人機集群任務重分配算法求解降低求解復雜度;如何基于改進性能影響算法在有限時間下獲得無人機集群任務重分配的較優解,提高異構無人機集群戰術靈活性,將成為解決日益復雜的無人機集群任務重分配問題的重要途徑。

3.4 群集智能下大規模異構無人系統協同任務分配技術

(1) 大規模異構無人系統拓撲網絡設計與優化

拓撲網絡設計與優化是異構無人系統協同任務分配的關鍵支撐技術。雖然集中式、分層式、分布式拓撲網絡已被提出,但相關研究未涉及大規模異構無人系統,也未與實際應用中“自組織性、異構性、對抗性”等特征相結合。

設計合理、高效、穩健、可重構的協同控制拓撲網絡,使得異構無人系統可以在復雜對抗戰場環境中保持通信鏈路穩定,實時感知態勢信息和實時評估結果,并以此為基礎動態調整任務分配方案,增強異構無人系統在通信受限環境下的適應能力,提升系統的魯棒性。

(2) 精確時空協同下路徑規劃技術

由于無人平臺異構,其移動速度、機動能力、載荷、可達區域等不盡相同,而且任務存在邏輯、時序以及時間窗約束,傳統的任務分配方法難以滿足現實需求。

為適應大規模異構無人系統任務分配問題的不斷發展和變化,任務分配方法呈現多層次、強耦合的特點,各層通過相互耦合在不同的細節粒度上進行求解,高層主要面向任務分配共性問題的研究,底層與異構無人平臺的性能特點及作戰樣式結合,強調多重威脅、多源干擾下的路徑軌跡精確規劃與控制,對異構無人平臺協同路徑規劃提出新的要求——精確的時間協同與空間沖突消解。其中,精確的時間協同是可靠地實施任務分配方案的基礎,空間沖突消解是大規模異構無人系統安全地執行任務分配方案的重要保障。

(3) 復雜環境下基于群集智能的大規模異構無人系統協同任務分配技術

相比于同構無人系統任務分配,大規模異構無人系統協同任務分配的任務規模大、類型多,協同關系復雜并存在組合約束,涌現性復雜,通信拓撲網絡多變,任務分配呈現出不確定性、隨機性、涌現性。傳統的任務分配方法不再適用于大規模異構無人系統,因此亟需提出滿足大規模協同任務分配需求的高效求解方法。

基于群集智能的大規模異構無人系統協同任務分配可以表述為:各個異構無人平臺在復雜環境下動態感知外界態勢信息,從而更新個體知識以適應復雜環境,再與系統內其他異構無人平臺交互,完成自適應學習與進化,最終執行復雜有序的群集行為(即協同任務分配)。智能涌現在協同任務分配上的表征為單異構無人平臺、異構無人系統和任務3個層面,分別對應于單異構無人平臺對環境的學習、無異構無人系統群集智能行為的進化以及無人機集群對復雜多樣化任務的分配。

利用深度學習構建異構無人系統分布式學習及訓練環境,通過大數據挖掘提取協同任務分配訓練樣本數據特征,研究復雜環境下基于群集智能的大規模異構無人系統協同任務分配技術,使得大規模異構無人系統具備在線學習與自主決策能力,提升復雜環境下大規模異構無人系統協同任務分配的自主性與靈活性。

4 結 論

本文從無人機集群作戰理論、無人機集群任務分配問題建模、無人機集群任務與分配算法和無人機集群任務重分配算法、異構無人系統聯合應用下任務分配等方面對相關研究現狀進行了總結,指出了無人機集群任務分配技術目前面臨的無人機集群任務分配元模型的通用化建模理論、不完全信息下面向多任務的無人機集群任務預分配最優解求解、有限時間下面向突發事件的無人機集群任務重分配尋優、路徑規劃緊耦合下面向大規模異構無人系統的協同任務分配等關鍵問題。在此基礎上,突破傳統方法的不足和局限,探索無人機集群任務分配新理論和新技術發展方向,為增強無人機集群任務分配對不確定戰場環境的適應性、提升無人機集群的任務預分配和重分配的求解質量和求解速度提供新的研究思路和解決途徑,促進無人機集群任務分配技術由目前的先進“跟跑者”逐漸邁向國際領先水平的“領跑者”,具有重要的社會和國防意義。