無人機(jī)集群任務(wù)分配技術(shù)研究綜述

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

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

0 引 言

隨著無人機(jī)相關(guān)技術(shù)的突破創(chuàng)新和快速發(fā)展,無人機(jī)類型越來越多樣化,任務(wù)領(lǐng)域范圍不斷拓展,已經(jīng)逐步實(shí)現(xiàn)從安全空域下執(zhí)行偵察監(jiān)視等簡單任務(wù)向?qū)箍沼蛳峦环来驌舻葟?fù)雜作戰(zhàn)任務(wù)的跨越式發(fā)展。與此同時(shí),網(wǎng)絡(luò)化、信息化、體系化的戰(zhàn)場環(huán)境呈現(xiàn)出高動(dòng)態(tài)、強(qiáng)對抗、巨復(fù)雜等特點(diǎn),單架無人機(jī)有限的載荷能力很難獨(dú)立執(zhí)行大區(qū)域監(jiān)視、多目標(biāo)攻擊等復(fù)雜任務(wù),因此無人機(jī)的作戰(zhàn)樣式正在朝著集群化和智能化方向發(fā)展,無人機(jī)集群協(xié)同作戰(zhàn)是未來無人機(jī)作戰(zhàn)方式的重要發(fā)展趨勢。

在無人機(jī)集群作戰(zhàn)中,低成本、大規(guī)模的異構(gòu)無人機(jī)平臺搭載不同的載荷,通過自組織協(xié)同形成規(guī)模優(yōu)勢,具有資源配置靈活、戰(zhàn)場適應(yīng)能力強(qiáng)等特點(diǎn),可滿足巨復(fù)雜、高動(dòng)態(tài)、強(qiáng)對抗的戰(zhàn)場環(huán)境下大區(qū)域協(xié)同偵察監(jiān)視、協(xié)同多目標(biāo)飽和攻擊等任務(wù)需求,達(dá)到集群對抗的效果,提高無人機(jī)集群的作戰(zhàn)效能。

無人機(jī)集群作戰(zhàn)帶來的巨大規(guī)模優(yōu)勢和作戰(zhàn)效能引起了以美國為代表的世界各軍事強(qiáng)國對無人機(jī)集群作戰(zhàn)技術(shù)的熱切關(guān)注,其中無人機(jī)集群任務(wù)分配技術(shù)作為無人機(jī)集群作戰(zhàn)的關(guān)鍵技術(shù)之一,是實(shí)現(xiàn)無人機(jī)集群化和智能化的重要技術(shù)支撐,已成為國防工業(yè)部門和各科研機(jī)構(gòu)、研究學(xué)者的研究熱點(diǎn)。

1 無人機(jī)集群任務(wù)分配技術(shù)研究現(xiàn)狀

目前,無人機(jī)集群任務(wù)分配技術(shù)在頂層設(shè)計(jì)、理論研究、項(xiàng)目論證、關(guān)鍵技術(shù)攻關(guān)等方面都取得了一定的進(jìn)展。

1.1 無人機(jī)集群協(xié)同任務(wù)分配理論研究現(xiàn)狀

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

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

1.2 無人機(jī)集群任務(wù)分配問題建模研究現(xiàn)狀

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

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

1.3 無人機(jī)集群任務(wù)預(yù)分配算法研究現(xiàn)狀

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

1.3.1 多無人機(jī)任務(wù)預(yù)分配集中式求解算法研究現(xiàn)狀

集中式求解算法可以分為最優(yōu)化方法和啟發(fā)式方法兩類[17]。

最優(yōu)化方法在問題有解的前提條件下,能夠基于簡化的假設(shè)求解得到問題的最優(yōu)解,代表性算法包括窮舉法、分支定界、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃等。但隨著無人機(jī)數(shù)量的增加,最優(yōu)化方法求解任務(wù)分配問題的難度、計(jì)算時(shí)間都急劇增加,而且無法準(zhǔn)確描述復(fù)雜環(huán)境下的大規(guī)模任務(wù)分配問題,不能模擬出戰(zhàn)場環(huán)境的隨機(jī)性和動(dòng)態(tài)性,因此近年來采用最優(yōu)化方法求解無人機(jī)集群任務(wù)分配問題的研究逐漸減少。

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

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

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

目前,基于遺傳算法和粒子群優(yōu)化算法解決多無人機(jī)任務(wù)預(yù)分配問題依舊是當(dāng)前的研究熱點(diǎn),通過改變具體的編碼方式或?qū)蛹壗Y(jié)構(gòu)來提高自身求解性能,具有大量的研究成果,但大部分算法是針對特定的應(yīng)用背景及約束條件進(jìn)行改進(jìn),無法全面考慮實(shí)際多無人機(jī)集群任務(wù)預(yù)分配問題時(shí)存在的復(fù)雜耦合約束,算法的魯棒性與可擴(kuò)展性較低。

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

1.3.2 多無人機(jī)任務(wù)預(yù)分配分布式求解算法研究現(xiàn)狀

隨著無人機(jī)自主能力的不斷提升和無人機(jī)集群通信組網(wǎng)技術(shù)的快速發(fā)展,具有優(yōu)越的可擴(kuò)展性和魯棒性的分布式求解算法逐漸成為任務(wù)分配算法研究方向的熱點(diǎn)。

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

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

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

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

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

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

上述算法在針對小規(guī)模多無人機(jī)任務(wù)預(yù)分配問題時(shí)可以獲得較好的求解質(zhì)量,并已有許多學(xué)者針對特定約束對算法進(jìn)行擴(kuò)展,但隨著異構(gòu)無人機(jī)類型的逐漸增加,無人機(jī)集群規(guī)模不斷擴(kuò)大,約束條件復(fù)雜耦合,上述算法的求解效率較低,求解質(zhì)量也直線下降。

1.4 無人機(jī)集群任務(wù)重分配算法研究現(xiàn)狀

隨著戰(zhàn)場對抗不斷升級,無人機(jī)集群在任務(wù)執(zhí)行過程中遇到突發(fā)事件時(shí),任務(wù)重分配算法需要通過各無人機(jī)平臺之間的信息交互對戰(zhàn)場態(tài)勢和動(dòng)態(tài)任務(wù)快速做出反應(yīng),在有限時(shí)間內(nèi)完成任務(wù)的重構(gòu)與優(yōu)化,并達(dá)成無沖突的任務(wù)重分配方案[52]。

基于市場機(jī)制的任務(wù)重分配算法具有簡單易實(shí)現(xiàn)、靈活性較好、可擴(kuò)展性強(qiáng)的優(yōu)點(diǎn),因此被廣泛應(yīng)用到無人機(jī)集群任務(wù)重分配,并且結(jié)合具體的無人機(jī)集群任務(wù)重分配場景,對求解性能、約束滿足、沖突消解等方面進(jìn)行擴(kuò)展,提出了眾多改進(jìn)算法。文獻(xiàn)[53]提出了一種基于分布式拍賣算法的博弈理論非協(xié)調(diào)決策框架,并證明其在異步網(wǎng)絡(luò)環(huán)境下求解大規(guī)模無人機(jī)任務(wù)重分配問題時(shí)具有較好的收斂性。文獻(xiàn)[54]中每架無人機(jī)在執(zhí)行任務(wù)時(shí)估計(jì)所有其他無人機(jī)的位置,并在此基礎(chǔ)上用簡單的分布式拍賣方案實(shí)現(xiàn)了無沖突的任務(wù)重分配,得到了較滿意的解。文獻(xiàn)[55]為更好地利用有限資源,采用基于分布式拍賣的方法解決了多機(jī)器人動(dòng)態(tài)任務(wù)重分配問題。文獻(xiàn)[56]討論了一種滿足任務(wù)執(zhí)行時(shí)長約束與機(jī)器人壽命約束的分布式拍賣算法,解決了具有任務(wù)執(zhí)行時(shí)間約束的多機(jī)器人動(dòng)態(tài)任務(wù)重分配問題。為處理戰(zhàn)場環(huán)境中的通信約束,文獻(xiàn)[57]針對有限通信距離的場景,提出了一種基于改進(jìn)市場機(jī)制的分布式任務(wù)重分配算法。文獻(xiàn)[58]在其基礎(chǔ)上針對時(shí)變網(wǎng)絡(luò)拓?fù)涞那闆r進(jìn)行了改進(jìn),提高了任務(wù)重分配算法的實(shí)用性。

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

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

1.5 無人機(jī)集群與其他無人系統(tǒng)聯(lián)合應(yīng)用下任務(wù)分配研究現(xiàn)狀

隨著智能自主技術(shù)、體系作戰(zhàn)的快速發(fā)展,無人機(jī)、無人車、四足機(jī)器人、無人水面艇、無人水下航行器等無人系統(tǒng)逐步成為能改變未來戰(zhàn)爭形態(tài)和作戰(zhàn)樣式的關(guān)鍵性武器裝備。無人系統(tǒng)的聯(lián)合應(yīng)用也向“協(xié)同、群智”的趨勢發(fā)展,已受到廣泛關(guān)注。

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

2 無人機(jī)集群任務(wù)分配技術(shù)面臨的問題

隨著無人機(jī)集群相關(guān)技術(shù)的迅猛發(fā)展,無人機(jī)集群在平臺異構(gòu)性上從單一的同構(gòu)平臺發(fā)展到復(fù)雜多任務(wù)下多異構(gòu)平臺,在成員規(guī)模上從傳統(tǒng)多機(jī)編隊(duì)的數(shù)架無人機(jī)擴(kuò)展到幾十架甚至是成百上千架的無人機(jī)集群。同時(shí),伴隨著無人機(jī)集群作戰(zhàn)樣式的轉(zhuǎn)變,無人機(jī)集群的作戰(zhàn)任務(wù)類型更加復(fù)雜,從僅可執(zhí)行安全空域下偵察監(jiān)視等簡單任務(wù)拓展到執(zhí)行對抗空域下突防打擊等復(fù)雜作戰(zhàn)任務(wù),研究方向由簡單任務(wù)的預(yù)分配技術(shù)轉(zhuǎn)變?yōu)閺?fù)雜多任務(wù)的預(yù)分配和動(dòng)態(tài)環(huán)境下實(shí)時(shí)重分配,大規(guī)模無人機(jī)集群任務(wù)分配技術(shù)在模型建立、算法求解、任務(wù)分配實(shí)時(shí)性等研究方向的一些問題也暴露出來。

2.1 無人機(jī)集群任務(wù)分配建模的架構(gòu)問題

在異構(gòu)無人機(jī)集群任務(wù)分配模型的架構(gòu)設(shè)計(jì)上,許多研究人員只是在經(jīng)典多無人機(jī)協(xié)同任務(wù)分配模型的基礎(chǔ)上面向特定的異構(gòu)無人機(jī)任務(wù)需求與約束條件進(jìn)行改進(jìn),沒有提出無人機(jī)集群任務(wù)分配建模的架構(gòu)理論,沒有依據(jù)多任務(wù)適應(yīng)性綜合考慮真實(shí)戰(zhàn)場環(huán)境中的各種約束及優(yōu)化目標(biāo)。如戰(zhàn)場中的不確定性、平臺異構(gòu)性、通信約束、任務(wù)的時(shí)序約束、資源約束等,只面向某些特定約束條件與應(yīng)用場景下的任務(wù)分配問題,建立模型不能夠面向不同作戰(zhàn)環(huán)境和作戰(zhàn)任務(wù),對無人機(jī)集群任務(wù)分配的規(guī)模擴(kuò)展性不足。

因此,如何立足于動(dòng)態(tài)多變、高度不確定性的真實(shí)戰(zhàn)場環(huán)境,在考慮多種無人機(jī)類型、通信約束、不同任務(wù)需求目標(biāo)、多種約束相互耦合的情況下“向?qū)崙?zhàn)聚焦”,探究更符合真實(shí)戰(zhàn)場的異構(gòu)無人機(jī)集群任務(wù)分配架構(gòu),是大規(guī)模異構(gòu)無人機(jī)集群任務(wù)分配的一個(gè)嚴(yán)峻問題,也是異構(gòu)無人機(jī)集群任務(wù)分配算法能否真正應(yīng)用于實(shí)戰(zhàn)的一大挑戰(zhàn)。

2.2 面向多任務(wù)的無人機(jī)集群任務(wù)預(yù)分配算法最優(yōu)解求解問題

當(dāng)前的大部分無人機(jī)集群任務(wù)預(yù)分配算法求解都是面向中小型規(guī)模的同構(gòu)無人機(jī)集群,無法對大規(guī)模異構(gòu)無人機(jī)集群任務(wù)分配問題的多約束因素進(jìn)行有效解耦,且不能高效處理有優(yōu)先級差別的任務(wù),求解復(fù)雜度隨無人機(jī)集群的規(guī)模呈幾何級數(shù)增長,甚至導(dǎo)致出現(xiàn)無法求解的情況。

隨著無人機(jī)集群任務(wù)預(yù)分配的研究對象從小規(guī)模的同構(gòu)無人機(jī)轉(zhuǎn)向大規(guī)模的異構(gòu)多平臺無人機(jī),研究方向由確定信息下的簡單任務(wù)預(yù)分配轉(zhuǎn)變?yōu)椴煌耆畔⑾碌膹?fù)雜多任務(wù)預(yù)分配,任務(wù)預(yù)分配所涵蓋的范圍和規(guī)模不斷擴(kuò)大,主要表現(xiàn)為:約束條件繁多且耦合程度高,強(qiáng)對抗戰(zhàn)場環(huán)境導(dǎo)致指標(biāo)因素具有強(qiáng)不確定性,機(jī)載傳感器、武器載荷等任務(wù)要素復(fù)雜,任務(wù)預(yù)分配結(jié)果需符合作戰(zhàn)意圖等。這些都對任務(wù)分配算法求解提出了新的挑戰(zhàn)。

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

2.3 有限時(shí)間下面向突發(fā)事件的無人機(jī)集群任務(wù)重分配算法尋優(yōu)問題

與無人機(jī)集群任務(wù)預(yù)分配相比,無人機(jī)集群任務(wù)重分配既要克服戰(zhàn)場態(tài)勢信息的動(dòng)態(tài)性所帶來的負(fù)面影響,又需要在資源和時(shí)間都有限的條件下得到合理可行的分配結(jié)果。

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

因此,面對動(dòng)態(tài)對抗環(huán)境下的突發(fā)事件,如何對沖突任務(wù)進(jìn)行消解與優(yōu)化,以及如何利用高性能的重分配算法在局部最優(yōu)和全局最優(yōu)間進(jìn)行合理有效的折中,以便在有限時(shí)間下獲得無人機(jī)集群任務(wù)重分配的較優(yōu)解,是無人機(jī)集群任務(wù)重分配研究中的關(guān)鍵問題。

2.4 路徑規(guī)劃緊耦合下面向大規(guī)模異構(gòu)無人系統(tǒng)的協(xié)同任務(wù)分配問題

當(dāng)前的大部分任務(wù)分配算法都將任務(wù)分配與路徑規(guī)劃分離,以松耦合的方式先求解任務(wù)分配,再對單平臺進(jìn)行路徑規(guī)劃,忽略實(shí)際路徑對分配任務(wù)執(zhí)行的影響。而多變?nèi)蝿?wù)類型和復(fù)雜動(dòng)態(tài)環(huán)境下大規(guī)模異構(gòu)無人集群協(xié)同任務(wù)分配不僅要在整體宏觀層上進(jìn)行異構(gòu)無人集群內(nèi)各智能體的任務(wù)分配,而且要在個(gè)體動(dòng)力學(xué)層上為每個(gè)智能體設(shè)計(jì)路徑軌跡,實(shí)現(xiàn)路徑規(guī)劃耦合下的任務(wù)分配,使得大規(guī)模異構(gòu)無人集群作戰(zhàn)效能近似最優(yōu)。

與此同時(shí),國內(nèi)外在針對不同應(yīng)用場景下的較小規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)優(yōu)化分配算法已取得較為扎實(shí)的研究成果。然而,面向大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配問題時(shí),隨著規(guī)模的迅速增長和異構(gòu)性的增強(qiáng),已有的方法大多適用性不足;其次,異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配需要依靠集群通信組網(wǎng)獲取信息,時(shí)延、拓?fù)鋾r(shí)變、丟包、誤碼等通信約束大幅增加了大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配的難度。

如何在路徑規(guī)劃緊耦合下考量異構(gòu)耦合涌現(xiàn)效應(yīng),更高效、合理地實(shí)現(xiàn)異構(gòu)無人系統(tǒng)的協(xié)同任務(wù)分配,是未來大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配的關(guān)鍵問題。

3 無人機(jī)集群任務(wù)分配技術(shù)的發(fā)展方向

3.1 基于模型的系統(tǒng)工程的無人機(jī)集群任務(wù)分配的通用化建模理論

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

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

圖1 無人機(jī)集群任務(wù)分配“4W1H”關(guān)系圖Fig.1 “4W1H” relational graph of unmanned aerial vechtle swarm task allocation

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

3.2 不完全信息下面向多任務(wù)的基于生成對抗網(wǎng)絡(luò)的無人機(jī)集群任務(wù)預(yù)分配技術(shù)

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

圖2 基于GANs的無人集群任務(wù)預(yù)分配網(wǎng)絡(luò)框架Fig.2 Task pre-allocation network framework of unmanned aerial vehcile swarm based on GANs

將深度學(xué)習(xí)理論與無人機(jī)集群任務(wù)預(yù)分配技術(shù)交叉融合,并在不完全信息下利用GANs針對不同任務(wù)需求高效地求解面向多任務(wù)的異構(gòu)無人機(jī)集群任務(wù)預(yù)分配的最優(yōu)解將是無人機(jī)集群任務(wù)分配研究中的熱點(diǎn)方向。

3.3 有限時(shí)間下面向突發(fā)事件的基于性能影響算法的無人機(jī)集群任務(wù)重分配技術(shù)

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

有限時(shí)間下基于改進(jìn)性能影響算法的無人機(jī)集群任務(wù)重分配框架如圖3所示。

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

針對無人機(jī)集群任務(wù)重分配應(yīng)對動(dòng)態(tài)對抗環(huán)境下多種突發(fā)事件的實(shí)時(shí)性需求,研究如何對沖突任務(wù)進(jìn)行消解與優(yōu)化,為后續(xù)無人機(jī)集群任務(wù)重分配算法求解降低求解復(fù)雜度;如何基于改進(jìn)性能影響算法在有限時(shí)間下獲得無人機(jī)集群任務(wù)重分配的較優(yōu)解,提高異構(gòu)無人機(jī)集群戰(zhàn)術(shù)靈活性,將成為解決日益復(fù)雜的無人機(jī)集群任務(wù)重分配問題的重要途徑。

3.4 群集智能下大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配技術(shù)

(1) 大規(guī)模異構(gòu)無人系統(tǒng)拓?fù)渚W(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化

拓?fù)渚W(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化是異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配的關(guān)鍵支撐技術(shù)。雖然集中式、分層式、分布式拓?fù)渚W(wǎng)絡(luò)已被提出,但相關(guān)研究未涉及大規(guī)模異構(gòu)無人系統(tǒng),也未與實(shí)際應(yīng)用中“自組織性、異構(gòu)性、對抗性”等特征相結(jié)合。

設(shè)計(jì)合理、高效、穩(wěn)健、可重構(gòu)的協(xié)同控制拓?fù)渚W(wǎng)絡(luò),使得異構(gòu)無人系統(tǒng)可以在復(fù)雜對抗戰(zhàn)場環(huán)境中保持通信鏈路穩(wěn)定,實(shí)時(shí)感知態(tài)勢信息和實(shí)時(shí)評估結(jié)果,并以此為基礎(chǔ)動(dòng)態(tài)調(diào)整任務(wù)分配方案,增強(qiáng)異構(gòu)無人系統(tǒng)在通信受限環(huán)境下的適應(yīng)能力,提升系統(tǒng)的魯棒性。

(2) 精確時(shí)空協(xié)同下路徑規(guī)劃技術(shù)

由于無人平臺異構(gòu),其移動(dòng)速度、機(jī)動(dòng)能力、載荷、可達(dá)區(qū)域等不盡相同,而且任務(wù)存在邏輯、時(shí)序以及時(shí)間窗約束,傳統(tǒng)的任務(wù)分配方法難以滿足現(xiàn)實(shí)需求。

為適應(yīng)大規(guī)模異構(gòu)無人系統(tǒng)任務(wù)分配問題的不斷發(fā)展和變化,任務(wù)分配方法呈現(xiàn)多層次、強(qiáng)耦合的特點(diǎn),各層通過相互耦合在不同的細(xì)節(jié)粒度上進(jìn)行求解,高層主要面向任務(wù)分配共性問題的研究,底層與異構(gòu)無人平臺的性能特點(diǎn)及作戰(zhàn)樣式結(jié)合,強(qiáng)調(diào)多重威脅、多源干擾下的路徑軌跡精確規(guī)劃與控制,對異構(gòu)無人平臺協(xié)同路徑規(guī)劃提出新的要求——精確的時(shí)間協(xié)同與空間沖突消解。其中,精確的時(shí)間協(xié)同是可靠地實(shí)施任務(wù)分配方案的基礎(chǔ),空間沖突消解是大規(guī)模異構(gòu)無人系統(tǒng)安全地執(zhí)行任務(wù)分配方案的重要保障。

(3) 復(fù)雜環(huán)境下基于群集智能的大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配技術(shù)

相比于同構(gòu)無人系統(tǒng)任務(wù)分配,大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配的任務(wù)規(guī)模大、類型多,協(xié)同關(guān)系復(fù)雜并存在組合約束,涌現(xiàn)性復(fù)雜,通信拓?fù)渚W(wǎng)絡(luò)多變,任務(wù)分配呈現(xiàn)出不確定性、隨機(jī)性、涌現(xiàn)性。傳統(tǒng)的任務(wù)分配方法不再適用于大規(guī)模異構(gòu)無人系統(tǒng),因此亟需提出滿足大規(guī)模協(xié)同任務(wù)分配需求的高效求解方法。

基于群集智能的大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配可以表述為:各個(gè)異構(gòu)無人平臺在復(fù)雜環(huán)境下動(dòng)態(tài)感知外界態(tài)勢信息,從而更新個(gè)體知識以適應(yīng)復(fù)雜環(huán)境,再與系統(tǒng)內(nèi)其他異構(gòu)無人平臺交互,完成自適應(yīng)學(xué)習(xí)與進(jìn)化,最終執(zhí)行復(fù)雜有序的群集行為(即協(xié)同任務(wù)分配)。智能涌現(xiàn)在協(xié)同任務(wù)分配上的表征為單異構(gòu)無人平臺、異構(gòu)無人系統(tǒng)和任務(wù)3個(gè)層面,分別對應(yīng)于單異構(gòu)無人平臺對環(huán)境的學(xué)習(xí)、無異構(gòu)無人系統(tǒng)群集智能行為的進(jìn)化以及無人機(jī)集群對復(fù)雜多樣化任務(wù)的分配。

利用深度學(xué)習(xí)構(gòu)建異構(gòu)無人系統(tǒng)分布式學(xué)習(xí)及訓(xùn)練環(huán)境,通過大數(shù)據(jù)挖掘提取協(xié)同任務(wù)分配訓(xùn)練樣本數(shù)據(jù)特征,研究復(fù)雜環(huán)境下基于群集智能的大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配技術(shù),使得大規(guī)模異構(gòu)無人系統(tǒng)具備在線學(xué)習(xí)與自主決策能力,提升復(fù)雜環(huán)境下大規(guī)模異構(gòu)無人系統(tǒng)協(xié)同任務(wù)分配的自主性與靈活性。

4 結(jié) 論

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