摘 要：隨著通信技術(shù)的發(fā)展，未來多無人機(jī)系統(tǒng)將會(huì)朝向集群化、自主化和智能化方向發(fā)展。通過單元間的信息融合和能力互補(bǔ)，多無人機(jī)系統(tǒng)可以打破自身能力壁壘，形成多樣化的任務(wù)能力。任務(wù)規(guī)劃是多無人機(jī)系統(tǒng)協(xié)同應(yīng)用的頂層設(shè)計(jì)，屬于帶約束的組合優(yōu)化問題，是在任務(wù)需求、單元能力和環(huán)境態(tài)勢(shì)的影響下，優(yōu)化求解獲得滿足要求的、優(yōu)化的任務(wù)執(zhí)行方案。從問題表征建模和方案求解評(píng)估兩個(gè)角度梳理現(xiàn)有研究，從場景分析、任務(wù)分配和航跡規(guī)劃3個(gè)方面總結(jié)問題表征建模部分的研究，從求解算法和效能評(píng)估兩個(gè)方面總結(jié)方案求解評(píng)估部分的研究。最后，分析未來無人機(jī)任務(wù)規(guī)劃研究中值得關(guān)注的若干方向。

關(guān)鍵詞： 多無人機(jī)系統(tǒng); 任務(wù)規(guī)劃; 問題表征及建模; 方案求解評(píng)估

中圖分類號(hào)： V 221 文獻(xiàn)標(biāo)志碼： A""" DOI：10.12305/j.issn.1001-506X.2024.10.21

Review of research on multi-UAV collaborative mission planning method

WANG Jianfeng， JIA Gaowei GUO Zheng， HOU Zhongxi

（College of Aerospace Science and Engineering， National University of Defense Technology， Changsha 410073， China）

Abstract： With the development of communication technology， the future development of multi-unmanned aerial vehicle （UAV） system is trending towards clusterization， autonomy， and intelligence. Through information fusion and capability complementation among units， multi-UAV system can break through their inherent technology limitations and form diversified mission capabilities. Mission planning serves as the top-level design for collaborative applications of multi-UAV system. It is a combinatorial optimization problem with constraints， seeking to obtain optimal mission execution plans that satisfy requirements， with the consideration of mission demands， unit capabilities， and environmental situations. This paper summarizes existing research result from two perspectives： problem representation modeling and plan solution evaluation. Specifically， it reviews the research result of problem representation modeling in terms of scenario analysis， task allocation， and trajectory planning， and examines solution evaluation in terms of solving algorithms and performance assessment. Finally， several directions worthy of attention in future research on UAV mission planning are analyzed.

Keywords： multi-unmanned aerial vehicle （UAV） system; mission planning; problem representation and modeling; plan solving and evaluation

0 引 言

無人機(jī)作為智能無人系統(tǒng)中的“集大成者”，具有生存能力高、適應(yīng)性強(qiáng)、使用靈活等特點(diǎn)，被廣泛應(yīng)用在多種任務(wù)場景^［13］。當(dāng)前，大型全能型無人機(jī)（如“死神”無人機(jī)、“全球鷹”無人機(jī)等）系統(tǒng)集成度高且功能強(qiáng)大，但面對(duì)日益復(fù)雜的任務(wù)需求，仍存在任務(wù)效費(fèi)比低、系統(tǒng)容錯(cuò)性差、升級(jí)周期長等缺陷。多無人機(jī)系統(tǒng)旨在將大型平臺(tái)的功能分散到空間分布的大量無人機(jī)，利用網(wǎng)絡(luò)連接將這些功能相對(duì)單一的低成本單元，通過合理調(diào)度，實(shí)現(xiàn)不同單元的動(dòng)態(tài)組合和密切協(xié)作，能夠在兼具經(jīng)濟(jì)性的基礎(chǔ)上達(dá)到甚至超過大型平臺(tái)的能力水平。

多無人機(jī)系統(tǒng)具有單元配置靈活、部署形式多樣、任務(wù)能力全面、系統(tǒng)冗余度高、經(jīng)濟(jì)成本低等優(yōu)勢(shì)，可以極大提升未來戰(zhàn)場的不對(duì)稱優(yōu)勢(shì)，因此各國均積極部署大量研究項(xiàng)目，將多無人機(jī)系統(tǒng)的應(yīng)用擴(kuò)展至多種任務(wù)領(lǐng)域^［1］。各國發(fā)展了以“女武神”“神經(jīng)元”“小精靈”“郊狼”和“灰山鶉”等項(xiàng)目為代表的無人機(jī)項(xiàng)目，部署了以系統(tǒng)集成技術(shù)和試驗(yàn)項(xiàng)目、拒止環(huán)境中協(xié)同作戰(zhàn)項(xiàng)目、分布式作戰(zhàn)管理、蜂群無人機(jī)應(yīng)用等為代表的體系協(xié)同項(xiàng)目^［23］。這些項(xiàng)目從集群協(xié)同模式、分布式指揮架構(gòu)、核心關(guān)鍵技術(shù)和集群應(yīng)用演示等方面進(jìn)行大量探索，推動(dòng)多無人機(jī)系統(tǒng)與現(xiàn)有裝備體系的有效融合，探索多樣化的應(yīng)用模式^［4］。

未來多無人機(jī)系統(tǒng)將繼續(xù)朝向集群化、自主化和智能化的方向發(fā)展^［4］，其應(yīng)用面臨多樣化的挑戰(zhàn)：應(yīng)用環(huán)境更為復(fù)雜，存在不確定且強(qiáng)對(duì)抗性因素的干擾;任務(wù)需求更為多樣，機(jī)間協(xié)同壓力更大;單元類型更加豐富，資源配置與調(diào)度難度更大。因此，需要發(fā)展多無人機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)，高效調(diào)度各單元并融合其任務(wù)能力，合理考慮多類因素干擾以保證任務(wù)執(zhí)行效果，自主調(diào)整任務(wù)指派及協(xié)同關(guān)系以應(yīng)對(duì)環(huán)境變化。任務(wù)方案不合理將無法體現(xiàn)出多無人機(jī)的協(xié)同優(yōu)勢(shì)，甚至出現(xiàn)沖突碰撞危險(xiǎn)。

任務(wù)規(guī)劃是多無人機(jī)系統(tǒng)應(yīng)用的頂層設(shè)計(jì)，是在場景先驗(yàn)信息支撐下，在應(yīng)用環(huán)境、任務(wù)需求和單元能力約束下，充分考慮執(zhí)行過程中的不確定因素，量化當(dāng)前條件下的可行資源配置與完成概率的關(guān)系，建立包含無人機(jī)配置、任務(wù)映射關(guān)系、執(zhí)行時(shí)間表和任務(wù)路徑等在內(nèi)的詳盡任務(wù)執(zhí)行方案，并能夠根據(jù)任務(wù)執(zhí)行的過程變化及時(shí)對(duì)任務(wù)方案進(jìn)行調(diào)整，在正常情況下高效完成各項(xiàng)任務(wù)，并在強(qiáng)對(duì)抗情況下最大限度地執(zhí)行任務(wù)。

多無人機(jī)任務(wù)規(guī)劃屬于任務(wù)指派和資源分配范疇，是一個(gè)帶約束的組合優(yōu)化問題^［56］，可分為模型構(gòu)建和模型求解兩部分。從建模角度考慮，任務(wù)規(guī)劃首先需要將多樣化的場景需求表征為任務(wù)組合，在旅行商問題、車輛路徑問題、廣義指派問題、混合整數(shù)線性規(guī)劃等模型^［79］的基礎(chǔ)上，結(jié)合問題特有的約束條件和不確定因素進(jìn)一步細(xì)化模型，在優(yōu)化目標(biāo)牽引下引導(dǎo)模型求解，獲得滿足需求的任務(wù)方案。從求解角度考慮，根據(jù)機(jī)間信息交互策略的不同，求解算法可分為集中式和分布式兩類^［1011］，需要結(jié)合場景需求進(jìn)行選擇并改進(jìn)，以適應(yīng)不同場景下的任務(wù)規(guī)劃求解需求^［1213］。效能評(píng)估是根據(jù)多方面指標(biāo)對(duì)多無人機(jī)系統(tǒng)進(jìn)行的綜合評(píng)價(jià)，可以發(fā)現(xiàn)系統(tǒng)的薄弱點(diǎn)并進(jìn)行針對(duì)性改進(jìn)。

本文從問題表征建模和方案求解評(píng)估兩個(gè)角度對(duì)當(dāng)前研究進(jìn)行梳理分析。問題表征建模分為場景分析、任務(wù)分配和航跡規(guī)劃3部分，其中場景表征部分分析任務(wù)、無人機(jī)和環(huán)境3類要素;任務(wù)分配部分歸納與構(gòu)建任務(wù)映射關(guān)系相關(guān)的約束條件、不確定因素和優(yōu)化目標(biāo);航跡規(guī)劃分析單機(jī)航跡計(jì)算和多機(jī)協(xié)同策略。從方案求解評(píng)估角度，列舉了常用的集中式和分布式算法及其改進(jìn)要點(diǎn)，然后歸納了多無人機(jī)協(xié)同應(yīng)用的效能評(píng)估流程。最后，結(jié)合前序分析給出未來研究中應(yīng)當(dāng)關(guān)注的部分方向。

1 問題表征與建模

全面、合理的模型構(gòu)建是任務(wù)規(guī)劃問題求解的基礎(chǔ)。多無人機(jī)協(xié)同任務(wù)規(guī)劃的內(nèi)涵十分豐富，包含但不局限于復(fù)雜任務(wù)分解、平臺(tái)載荷配置、任務(wù)目標(biāo)分配、航跡協(xié)同規(guī)劃、多機(jī)編隊(duì)協(xié)同、單元自主控制等^［1415］。其中，復(fù)雜任務(wù)分解與平臺(tái)載荷配置主要體現(xiàn)人在回路中的指揮控制，多機(jī)編隊(duì)協(xié)同與單元自主控制主要體現(xiàn)為平臺(tái)底層控制邏輯。任務(wù)目標(biāo)分配和航跡協(xié)同規(guī)劃承上啟下，是體現(xiàn)協(xié)同優(yōu)勢(shì)的核心部分，從技術(shù)上保障了多樣化任務(wù)能力的構(gòu)成。

如圖1所示，本文從場景分析、任務(wù)分配和航跡規(guī)劃3個(gè)層級(jí)分析任務(wù)規(guī)劃問題。場景分析將抽象化的目標(biāo)需求表征為任務(wù)組合，任務(wù)分配建立任務(wù)與無人機(jī)的映射關(guān)系，航跡規(guī)劃設(shè)計(jì)無人機(jī)的任務(wù)路徑。3個(gè)層級(jí)相互關(guān)聯(lián)，高一層級(jí)對(duì)下一層級(jí)進(jìn)行引導(dǎo)，下一層級(jí)在其范圍內(nèi)靈活調(diào)整并向上反饋，在保證精度的前提下降低問題求解難度。

在本節(jié)中，場景分析從目標(biāo)與任務(wù)、無人機(jī)與載荷和任務(wù)環(huán)境3方面分析影響任務(wù)執(zhí)行的要素。任務(wù)分配從建立合理映射關(guān)系出發(fā)，分析約束條件、不確定因素和優(yōu)化目標(biāo)的處理策略;航跡規(guī)劃從精確評(píng)估路徑成本出發(fā)，分析單機(jī)路徑生成和多機(jī)航跡協(xié)同的相關(guān)研究。

1.1 場景分析

1.1.1 目標(biāo)與任務(wù)要素

實(shí)際存在的物體或區(qū)域，根據(jù)形狀可分為點(diǎn)目標(biāo)、條帶目標(biāo)、規(guī)則面目標(biāo)^［1617］和不規(guī)則面目標(biāo)^［1819］;根據(jù)運(yùn)動(dòng)狀態(tài)可分為靜態(tài)目標(biāo)、規(guī)則移動(dòng)目標(biāo)和不規(guī)則移動(dòng)目標(biāo)^{［17，2021］}。

由單架無人機(jī)在一定時(shí)間內(nèi)對(duì)目標(biāo)實(shí)施的一系列行為，不同場景可以視為不同類型和數(shù)量的任務(wù)組合。常見的任務(wù)類型如下。

（1） 覆蓋搜索：對(duì)大面積未知區(qū)域進(jìn)行持續(xù)性監(jiān)視，確定其內(nèi)部目標(biāo)信息，包含行為式覆蓋（Z型、回型）和非行為式覆蓋^{［8，16，19］}。

（2） 定點(diǎn)偵察：采用不同類型的任務(wù)載荷（光學(xué)、紅外或雷達(dá)等）對(duì)位置概略已知的目標(biāo)進(jìn)行多層次的信息收集^{［17，2223］}。

（3） 目標(biāo)追蹤：對(duì)區(qū)域內(nèi)移動(dòng)目標(biāo)進(jìn)行持續(xù)監(jiān)視，為后續(xù)任務(wù)提供信息支撐^［24］。

（4） 火力打擊：使用多類型武器對(duì)信息已知的目標(biāo)進(jìn)行毀傷^{［22，2526］}，同時(shí)多向打擊可以有效提升打擊成功率^［27］。

（5） 效果評(píng)估：對(duì)完成打擊任務(wù)的目標(biāo)進(jìn)行評(píng)估，判斷是否達(dá)到毀傷要求^{［20，28］}。

（6） 通信中繼：為通信能力有限的無人機(jī)提供通信連接，擴(kuò)展無人機(jī)任務(wù)范圍^［29］。

（7） 物資運(yùn)輸：將充足數(shù)量和指定類型的物資運(yùn)輸?shù)侥繕?biāo)點(diǎn)^［25］。

（8） 電子干擾：實(shí)施電子壓制、降低對(duì)方探測和打擊能力^［30］。

可以根據(jù)任務(wù)需求和無人機(jī)能力調(diào)整任務(wù)設(shè)置。文獻(xiàn)［31］區(qū)分防御高和防御低的目標(biāo)，針對(duì)防御高的目標(biāo)增加打擊任務(wù)數(shù)量，以確保毀傷效果。文獻(xiàn)［32］針對(duì)無人機(jī)潛在斷聯(lián)風(fēng)險(xiǎn)，派遣中繼無人機(jī)執(zhí)行通信中繼任務(wù)，使得無人機(jī)可在基站通信范圍外執(zhí)行觀測任務(wù)。文獻(xiàn)［33］針對(duì)應(yīng)急區(qū)域覆蓋搜索，根據(jù)目標(biāo)位置、區(qū)域大小和無人機(jī)續(xù)航能力調(diào)整任務(wù)設(shè)置，能夠兼顧任務(wù)效果與無人機(jī)負(fù)載。

1.1.2 無人機(jī)與載荷要素

多無人機(jī)系統(tǒng)單元間的差異主要體現(xiàn)在動(dòng)力學(xué)性能和載荷功能兩方面。

動(dòng)力學(xué)性能影響任務(wù)路徑設(shè)置和到達(dá)時(shí)間計(jì)算，在任務(wù)規(guī)劃計(jì)算時(shí)主要考慮速度范圍、轉(zhuǎn)彎半徑、最大爬升角、最大下滑角等限制^［3436］，部分研究進(jìn)一步簡化為二維空間的速度與轉(zhuǎn)彎半徑限制^{［20，27］}。

載荷功能影響任務(wù)指派和效果評(píng)估，此處針對(duì)常用的偵察、打擊和通信載荷進(jìn)行分析。

（1） 偵察載荷：從目標(biāo)發(fā)現(xiàn)角度可簡化為搜索半徑^［18］，或通過視場角與飛行高度計(jì)算掃描范圍^{［17，37］}。針對(duì)目標(biāo)識(shí)別問題，單傳感器偵察需考慮置信概率，多傳感器協(xié)同偵察需要考慮信息融合問題。

（2） 打擊載荷：從目標(biāo)毀傷角度，一般簡化為打擊范圍和毀傷概率指標(biāo)^{［30，38］}。

（3） 通信載荷：一般簡化為通信半徑，即該范圍內(nèi)單元相互連接^［3940］，進(jìn)一步考慮通信拓?fù)浣Y(jié)構(gòu)^{［6，41］}、通信跳數(shù)^［41］、路徑損耗^{［10，42］}、接入單元數(shù)量^［42］等限制。

多無人機(jī)系統(tǒng)可以通過平臺(tái)與載荷的靈活配置，形成多樣化的任務(wù)能力。合理的配置方案可以提升機(jī)間協(xié)同效率，在滿足任務(wù)需求的同時(shí)避免資源浪費(fèi)^［43］，還可提升應(yīng)對(duì)不確定因素干擾的能力。

文獻(xiàn)［38］在協(xié)同對(duì)地打擊場景下，對(duì)比不同數(shù)量、不同隱身能力和飛行速度無人機(jī)的體系貢獻(xiàn)率，顯示無人機(jī)數(shù)量存在飽和、隱身能力中等且速度高的無人機(jī)組合效果更好。文獻(xiàn)［44］在速度和需求不確定的場景中，相較確定問題增加少量執(zhí)行單元，有效提升任務(wù)方案的魯棒性。文獻(xiàn)［30］和文獻(xiàn)［45］利用聚類方法將空間分布的多個(gè)任務(wù)劃分成簇，根據(jù)簇群數(shù)量確定無人機(jī)數(shù)量并進(jìn)行任務(wù)分配，提升大規(guī)模問題的求解效率。文獻(xiàn)［13］分析無人機(jī)配置與任務(wù)分配的關(guān)聯(lián)關(guān)系，設(shè)置基于進(jìn)化算法的雙層求解方法，結(jié)合任務(wù)分配計(jì)算情況調(diào)整無人機(jī)數(shù)量，可以獲得精確的無人機(jī)配置方案。文獻(xiàn)［46］針對(duì)無人機(jī)武器載荷配置問題，利用鄰域搜索算法優(yōu)化武器載荷搭載，在滿足毀傷需求的同時(shí)縮短了任務(wù)執(zhí)行時(shí)間。

1.1.3 任務(wù)環(huán)境要素

任務(wù)環(huán)境中影響任務(wù)執(zhí)行的因素可分為地形障礙類、戰(zhàn)場干擾類和氣候條件類。

（1） 地形障礙類：任務(wù)區(qū)域的障礙會(huì)延長任務(wù)路徑，影響到達(dá)時(shí)間的計(jì)算。計(jì)算時(shí)可以直接導(dǎo)入地形數(shù)據(jù)，或建模為三維半球、圓臺(tái)、圓柱等^{［3435，47］}，或二維圓形、方形等^{［26，4849］}，并可根據(jù)安全裕度適當(dāng)擴(kuò)大障礙范圍^［50］。

（2） 戰(zhàn)場干擾類：對(duì)抗環(huán)境中的地面火力和探測雷達(dá)會(huì)影響任務(wù)路徑設(shè)置和任務(wù)風(fēng)險(xiǎn)評(píng)估^［5051］，可將其視為地形障礙以確保無人機(jī)不通過該區(qū)域^［52］，也可建模為發(fā)現(xiàn)概率^［50］和打擊概率^［47］的分布模型，綜合考慮任務(wù)路徑長度和任務(wù)風(fēng)險(xiǎn)進(jìn)行計(jì)算。

（3） 氣候條件類：氣象因素對(duì)飛行的影響是全局性的，且存在較多不確定性，影響路徑設(shè)置和飛行速度^{［36，53］}。如小型無人機(jī)抗風(fēng)能力弱，需要根據(jù)風(fēng)場方向調(diào)整任務(wù)路徑設(shè)置^［19］。

1.2 任務(wù)分配

任務(wù)分配主要構(gòu)建無人機(jī)與任務(wù)的映射關(guān)系，是任務(wù)規(guī)劃的核心。本節(jié)分析任務(wù)和無人機(jī)相關(guān)約束條件和處理策略，歸納影響任務(wù)執(zhí)行的不確定因素和描述方法，最后列舉多種常用優(yōu)化目標(biāo)。

1.2.1 約束條件分析

模型約束可分為任務(wù)相關(guān)類和無人機(jī)相關(guān)類，具體如下。

（1） 任務(wù)時(shí)序耦合約束：不限制任務(wù)的具體執(zhí)行時(shí)間，而是限制任務(wù)間的相對(duì)執(zhí)行順序，可分為同時(shí)執(zhí)行、前序執(zhí)行、后序執(zhí)行、任務(wù)間執(zhí)行和任務(wù)互斥5類^［5455］，可以使用有向無環(huán)圖進(jìn)行精確描述^［28］。忽視該類約束會(huì)出現(xiàn)“死鎖”問題并產(chǎn)生大量無效解^［56］。可以通過任務(wù)分層計(jì)算^［54］、強(qiáng)連通量消除^［28］、關(guān)聯(lián)任務(wù)打包編碼^{［20，31，56］}等方法進(jìn)行處理。

（2） 任務(wù)時(shí)間窗約束：限制任務(wù)的具體執(zhí)行時(shí)間（最早開始/最晚結(jié)束），根據(jù)違約處理策略可分為硬時(shí)間窗和軟時(shí)間窗兩類。在時(shí)間窗限制下，到達(dá)過早需要“等待”，到達(dá)過晚會(huì)受到懲罰或錯(cuò)失任務(wù)^［55］，其中的“等待”過程降低速度不確定性對(duì)任務(wù)執(zhí)行的干擾^［5758］。

（3） 無人機(jī)數(shù)量約束：參與任務(wù)執(zhí)行的某一類型無人機(jī)數(shù)量不能超過數(shù)量限制，主要出現(xiàn)在無人機(jī)配置可變的場景^［13］中。

（4） 無人機(jī)航程約束：無人機(jī)所攜帶的能源有限，部分場景需要考慮返航需求。一般使用燃料消耗^{［13，59］}、飛行距離^［39］、飛行時(shí)間^{［11，60］}、最大任務(wù)數(shù)量^［61］等指標(biāo)進(jìn)行計(jì)算。

（5） 無人機(jī)能力約束：無人機(jī)必須具有相應(yīng)能力方可執(zhí)行任務(wù)。載荷能力可以使用0～1變量進(jìn)行簡要判斷^［10］，或結(jié)合功能半徑和執(zhí)行概率等參數(shù)進(jìn)行進(jìn)一步建模^［6263］。

（6） 無人機(jī)資源約束：無人機(jī)攜帶資源有限，所擔(dān)負(fù)任務(wù)的資源總量不能超出自身的資源類型和數(shù)量限制^{［23，2526］}。

約束數(shù)量隨問題規(guī)模變大呈非線性增加，大部分約束只涉及單架無人機(jī)或部分任務(wù)，少量約束則涵蓋全部任務(wù)與無人機(jī)，約束之間耦合關(guān)系復(fù)雜。對(duì)此，可以使用懲罰策略^{［56，6465］}、放松策略^{［5556，66］}、構(gòu)造修補(bǔ)策略^{［31，65，67］}等進(jìn)行處理，如下所示。

（1） 懲罰策略：根據(jù)違約情況調(diào)整模型優(yōu)化目標(biāo)值^［65］，將原始約束問題轉(zhuǎn)化為無約束問題進(jìn)行求解，在約束較少的情況下篩選可行解的效率高，但在大規(guī)模約束情況下可能無約束解很少^［56］。

（2） 放松策略：在可接受范圍內(nèi)先放松部分約束，后續(xù)根據(jù)需求進(jìn)一步增加限制。放松約束可能導(dǎo)致解的性能下降，但可以有效提升求解效率，增強(qiáng)解的多樣性^［66］。文獻(xiàn)［56］為避免調(diào)整“死鎖”帶來的巨大時(shí)間成本，設(shè)計(jì)成本近似函數(shù)以替代調(diào)整過程，雖然降低了結(jié)果性能，但大大縮短了求解時(shí)間。文獻(xiàn)［68］針對(duì)時(shí)序耦合場景，構(gòu)造包含少量約束的主問題，然后動(dòng)態(tài)增加對(duì)優(yōu)化目標(biāo)有改進(jìn)的約束條件，有效縮短了多約束問題的計(jì)算時(shí)間。

（3） 構(gòu)造修補(bǔ)策略：根據(jù)約束關(guān)系設(shè)計(jì)多種類型的操作，對(duì)違約解進(jìn)行調(diào)整，能夠確保最終解的可行性，但調(diào)整多類約束的操作復(fù)雜。文獻(xiàn)［31］針對(duì)時(shí)序耦合、動(dòng)力學(xué)和能力等約束，調(diào)整編解碼生成無“死鎖”方案，設(shè)計(jì)無人機(jī)選擇算子以滿足能力約束，以Dubins曲線設(shè)計(jì)任務(wù)路徑并協(xié)調(diào)到達(dá)時(shí)間，通過多次調(diào)整生成可行解。

1.2.2 不確定因素建模

在任務(wù)執(zhí)行過程中，存在多種不確定因素的干擾，可分為任務(wù)相關(guān)類和無人機(jī)相關(guān)類。

（1） 目標(biāo)與任務(wù)：存在位置^{［37，67］}、類型^［69］、數(shù)量^{［56，69］}、資源需求、任務(wù)執(zhí)行時(shí)長^{［44，58］}、時(shí)間窗^{［58，7071］}等不確定因素。

（2） 無人機(jī)與載荷：存在單元故障^［7273］、速度變化^{［65，7475］}、載荷置信度^{［57，65］}等不確定因素。

隨著無人機(jī)規(guī)模的增加和協(xié)同關(guān)系的日益復(fù)雜，不確定因素對(duì)任務(wù)執(zhí)行過程的沖擊逐漸加大，需要進(jìn)行針對(duì)性處理。處理策略可分為預(yù)處理和重規(guī)劃兩類，其中預(yù)處理策略是針對(duì)部分可預(yù)估的因素，在建模時(shí)考慮其影響范圍，通過增加部分成本提升方案的魯棒性。重規(guī)劃策略是針對(duì)部分難以預(yù)估的因素，在不確定因素出現(xiàn)后，對(duì)現(xiàn)有方案進(jìn)行快速調(diào)整，降低對(duì)任務(wù)執(zhí)行過程的干擾，具體如下所示。

（1） 預(yù)處理策略：根據(jù)對(duì)不確定因素的描述策略不同，可分為隨機(jī)規(guī)劃、馬爾可夫方法和魯棒優(yōu)化3類。

隨機(jī)規(guī)劃：適用于已知概率分布的不確定因素，使用期望值、最差值和機(jī)會(huì)約束預(yù)估不確定因素的影響范圍。通過求解期望值可以將不確定問題轉(zhuǎn)化為確定問題，但會(huì)存在實(shí)際值與計(jì)算值偏差較大的情況;最差值是預(yù)估不確定因素的最壞影響，可確保最高的可靠性，但會(huì)過于保守;機(jī)會(huì)約束是確保風(fēng)險(xiǎn)閾值內(nèi)的最差情況滿足要求，可以通過調(diào)整閾值設(shè)置平衡成本與魯棒性。文獻(xiàn)［65］考慮速度不確定性并最小化期望違約成本，提升方案魯棒性但仍存在違約情況;文獻(xiàn)［76］對(duì)比使用期望值和最差值兩種策略的效果，在高度不確定的情況下，后者由于過于保守，方案質(zhì)量較差。文獻(xiàn)［75］考慮多類不確定因素，構(gòu)建模糊機(jī)會(huì)約束規(guī)劃模型，可以根據(jù)風(fēng)險(xiǎn)偏好生成多種可行方案。

馬爾可夫方法：描述智能體與外界環(huán)境相互作用的模型，用于求解不確定環(huán)境下的序列決策過程，將不確定性以概率形式表示為轉(zhuǎn)移矩陣，調(diào)整決策最大化累積報(bào)酬。文獻(xiàn)［74］針對(duì)動(dòng)態(tài)對(duì)抗環(huán)境下的規(guī)劃問題，將不確定因素建模為系統(tǒng)的不可觀測部分，通過強(qiáng)化學(xué)習(xí)獲得當(dāng)前置信度下的最佳動(dòng)作序列;文獻(xiàn)［77］針對(duì)移動(dòng)目標(biāo)追蹤任務(wù)，考慮載荷置信度和目標(biāo)移動(dòng)，構(gòu)建任務(wù)路徑與觀測結(jié)果的轉(zhuǎn)移概率，進(jìn)而求解觀測方案。

魯棒優(yōu)化：通過不確定集描述不確定因素，確保不確定集約束下方案的可行性^{［56，70］}，不需要獲取精確概率分布。常用不確定集包括區(qū)間集、預(yù)算集、因子式集、橢球集、離散集等^［70］。不確定集越精細(xì)，模型復(fù)雜度越高，求解越困難;不確定集越寬泛，方案越保守，經(jīng)濟(jì)性越差。文獻(xiàn)［70］對(duì)比上述不確定集的計(jì)算時(shí)間，其中橢球集、離散集和因子式集計(jì)算成本較高，預(yù)算集和區(qū)間集計(jì)算成本較低?？紤]執(zhí)行時(shí)間和速度的不確定性，文獻(xiàn)［78］使用區(qū)間集求解，設(shè)計(jì)區(qū)間支配占優(yōu)關(guān)系，方案魯棒性強(qiáng)但十分保守;文獻(xiàn)［44］和文獻(xiàn)［58］使用預(yù)算集求解，使用動(dòng)態(tài)規(guī)劃方法表征了部分任務(wù)的延誤影響，通過增加少量成本有效提升了方案魯棒性。

（2） 重規(guī)劃策略：根據(jù)對(duì)現(xiàn)有方案調(diào)整程度的不同，分為完全重置和局部重置兩類。完全重置將重置全部任務(wù)映射關(guān)系，可以實(shí)現(xiàn)最高水平的協(xié)調(diào);局部重置只調(diào)整部分方案，可以快速形成可行方案。圖2所示為局部重疊示意圖。文獻(xiàn)［67］針對(duì)未知環(huán)境下的搜索場景，通過完全重置調(diào)整任務(wù)方案，平衡當(dāng)前目標(biāo)搜索收益和對(duì)新目標(biāo)的覆蓋能力。文獻(xiàn)［10］在新目標(biāo)連續(xù)出現(xiàn)的情況下，對(duì)比完全重置和局部重置的計(jì)算效果，在任務(wù)較多時(shí)完全重置計(jì)算時(shí)間過長，使得整體系統(tǒng)始終處于不穩(wěn)定狀態(tài)。針對(duì)局部重置，如圖2所示，為降低對(duì)原有方案的干擾，研究者提出多種調(diào)整策略：如基于到達(dá)時(shí)間、載荷能力^［64］和資源狀況^［79］選擇無人機(jī)參與調(diào)整;基于任務(wù)收益^［40］和與新任務(wù)時(shí)間窗口重疊情況^［80］調(diào)整任務(wù)映射關(guān)系。

1.2.3 優(yōu)化目標(biāo)設(shè)置

優(yōu)化目標(biāo)函數(shù)是引導(dǎo)任務(wù)規(guī)劃求解的關(guān)鍵條件，常見優(yōu)化目標(biāo)如下。

（1） 任務(wù)完成時(shí)間：通過計(jì)算任務(wù)最大完成時(shí)間評(píng)估任務(wù)執(zhí)行效率^{［65，81］}。

（2） 任務(wù)平均開始時(shí)間：通過計(jì)算任務(wù)開始時(shí)間評(píng)估任務(wù)執(zhí)行效率，常用于評(píng)估時(shí)間敏感任務(wù)^{［11，82］}。

（3） 任務(wù)總時(shí)間：通過計(jì)算整體任務(wù)時(shí)間消耗評(píng)估任務(wù)時(shí)間成本^{［16，83］}。

（4） 任務(wù)路徑長度：通過計(jì)算無人機(jī)的路徑總長度評(píng)估任務(wù)成本^{［18，50］}。

（5） 任務(wù)完成數(shù)量：通過計(jì)算任務(wù)完成數(shù)量評(píng)估時(shí)間/資源有限場景內(nèi)任務(wù)規(guī)劃方法的求解效率^{［82，84］}。

（6） 任務(wù)成本：通過計(jì)算任務(wù)路徑長度、任務(wù)風(fēng)險(xiǎn)值^［23］、平臺(tái)損耗^［76］、燃料消耗^［59］等評(píng)估任務(wù)執(zhí)行的經(jīng)濟(jì)成本。

（7） 任務(wù)收益：通過計(jì)算任務(wù)價(jià)值^{［7，80，85］}、任務(wù)價(jià)值與完成時(shí)間的綜合函數(shù)值^{［64，86］}等評(píng)估任務(wù)執(zhí)行效益。

（8） 無人機(jī)數(shù)量：通過計(jì)算參與任務(wù)的無人機(jī)數(shù)量，評(píng)估無人機(jī)配置不定時(shí)規(guī)劃方法的計(jì)算效率^{［13，87］}。

（9） 不確定成本：通過預(yù)期違規(guī)成本^［88］、路線變更成本^［72］、未知區(qū)域覆蓋指標(biāo)^［67］等計(jì)算不確定因素對(duì)任務(wù)執(zhí)行

過程的影響，進(jìn)而評(píng)估任務(wù)方案的魯棒性。

任務(wù)規(guī)劃可以使用多個(gè)優(yōu)化目標(biāo)篩選任務(wù)方案。針對(duì)多個(gè)優(yōu)化目標(biāo)，可以使用權(quán)重策略、分層優(yōu)化和多目標(biāo)優(yōu)化進(jìn)行處理。

（1） 權(quán)重策略：為優(yōu)化目標(biāo)設(shè)置權(quán)重，將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問題^［16］，多應(yīng)用于量綱相同或歸一化的優(yōu)化目標(biāo)。該方法可以通過設(shè)置權(quán)重簡化求解并區(qū)分不同優(yōu)化目標(biāo)，但不合理的權(quán)重設(shè)置可能會(huì)掩蓋部分優(yōu)化目標(biāo)。

（2） 分層優(yōu)化：在某一優(yōu)化目標(biāo)結(jié)果的基礎(chǔ)上求解其余優(yōu)化目標(biāo)，多用于處理處于不同層級(jí)且相互影響的目標(biāo)，可以有效縮小問題搜索空間，但弱化了優(yōu)化目標(biāo)之間的耦合關(guān)系。文獻(xiàn)［89］針對(duì)速度的不確定性，首先最小化任務(wù)路徑長度，在其結(jié)果上最小化不確定因素帶來的預(yù)期損失。

（3） 多目標(biāo)優(yōu)化：使用Pareto占優(yōu)策略篩選多個(gè)優(yōu)化目標(biāo)均占優(yōu)的折中解，多用于處理優(yōu)化目標(biāo)相互矛盾的情況。解集分布可以為問題分析提供參考^［87］，但是需要對(duì)算法進(jìn)行針對(duì)性改造，且優(yōu)化目標(biāo)過多時(shí)算法選擇壓力下降，非支配解數(shù)量激增，需要調(diào)整篩選機(jī)制^［23］。

1.3 航跡規(guī)劃

航跡規(guī)劃是在任務(wù)分配生成的任務(wù)映射的基礎(chǔ)上生成可行路徑，是評(píng)估任務(wù)方案時(shí)間/路徑成本的核心部分。多機(jī)航跡協(xié)同是在滿足動(dòng)力學(xué)約束和環(huán)境避障的基礎(chǔ)上，進(jìn)一步考慮時(shí)序協(xié)同與機(jī)間避障需求。本節(jié)首先對(duì)比單機(jī)航跡規(guī)劃的多種方法，然后在此基礎(chǔ)上分析多機(jī)時(shí)序協(xié)同與機(jī)間避撞的處理策略。

1.3.1 單機(jī)航跡規(guī)劃方法

根據(jù)空間離散策略的不同，單機(jī)航跡規(guī)劃方法可分為圖搜索類方法、概率類方法和人工勢(shì)場法3類，相關(guān)方法對(duì)比如表1所示。

（1） 圖搜索類方法：將任務(wù)空間離散成連接目標(biāo)和障礙的路徑網(wǎng)絡(luò)，在此基礎(chǔ)上搜索獲得最/較優(yōu)路徑。常用空間離散方法包含可視圖法^［22］、Voronoi圖法^［90］、柵格法^{［17，59］}等;常用搜索方法包含Dijkstra算法^［91］、A*算法^［26］、動(dòng)態(tài)規(guī)劃^［8］算法、元啟發(fā)算法^［92］、強(qiáng)化學(xué)習(xí)^［74］方法等。不同離散方法和搜索方法的組合可以適應(yīng)不同任務(wù)需求：文獻(xiàn)［90］針對(duì)城市內(nèi)未知移動(dòng)目標(biāo)搜索場景，使用Voronoi圖法設(shè)置待選航路點(diǎn)，使用滾動(dòng)時(shí)域預(yù)測方法優(yōu)化路徑，可以兼顧飛行安全和搜索效率。文獻(xiàn)［17］針對(duì)不確定區(qū)域內(nèi)的搜索打擊場景，使用柵格法離散區(qū)域，通過分布式蟻群算法優(yōu)化路徑，可以有效引導(dǎo)無人機(jī)搜索目標(biāo)存在概率高的區(qū)域。

（2） 概率方法：在任務(wù)空間中設(shè)置大量采樣點(diǎn)，使用直/曲線連接起點(diǎn)、部分采樣點(diǎn)與終點(diǎn)，形成任務(wù)路徑，通過優(yōu)化連接采樣點(diǎn)提升路徑質(zhì)量，根據(jù)采樣點(diǎn)設(shè)置策略不同分為概率路標(biāo)圖法和快速隨機(jī)樹法。該類方法不需要對(duì)場景進(jìn)行建模，對(duì)動(dòng)態(tài)或多障礙場景適應(yīng)性很好，能夠快速得到可行路徑，但受采樣點(diǎn)設(shè)置和搜索策略影響，路徑較為曲折。文獻(xiàn)［93］利用快速隨機(jī)樹法處理未知障礙或突發(fā)威脅，能夠快速調(diào)整現(xiàn)有路徑，繞過障礙區(qū)域。

（3） 人工勢(shì)場法：在任務(wù)空間建立虛擬力場，疊加目標(biāo)產(chǎn)生的引力與障礙產(chǎn)生的斥力，生成靠近目標(biāo)且遠(yuǎn)離障礙的路徑。該方法原理簡單，可以引入對(duì)方火力威脅、相鄰無人機(jī)等多類因素，有效提升任務(wù)路徑的安全性。但是該方法在力場函數(shù)設(shè)置不合理時(shí)可能產(chǎn)生無法到達(dá)目標(biāo)、違反避障約束和局部震蕩等問題，對(duì)此發(fā)展了多種改進(jìn)策略，如距離修正、局部擾動(dòng)等^［9495］。

航跡規(guī)劃計(jì)算過程中常使用曲線連接航路點(diǎn)，通過調(diào)整曲率和長度生成多樣化的任務(wù)路徑。常用曲線包含Dubins曲線^{［22，96］}、貝塞爾曲線^［34］、B樣條曲線^［3435］、畢達(dá)哥拉斯曲線^{［85，97］}等，多種航跡曲線的對(duì)比如表2所示。

1.3.2 多機(jī)航跡調(diào)整策略

多機(jī)協(xié)同需要考慮任務(wù)時(shí)序耦合約束帶來的時(shí)序協(xié)同要求和無人機(jī)密集部署帶來的機(jī)間避撞需求。

機(jī)間時(shí)序協(xié)同體現(xiàn)在無人機(jī)的到達(dá)位置和到達(dá)時(shí)序，需要根據(jù)協(xié)同需求設(shè)置航路點(diǎn)，針對(duì)性調(diào)整路徑長度和飛行速度。文獻(xiàn)［22］考慮偵察、打擊和評(píng)估任務(wù)的時(shí)序關(guān)系，使用Dubins曲線設(shè)計(jì)任務(wù)路徑，增加盤旋段以調(diào)整到達(dá)時(shí)間，滿足多類任務(wù)的時(shí)序耦合約束。文獻(xiàn)［85］考慮對(duì)目標(biāo)同時(shí)多向打擊的需求，使用畢達(dá)哥拉斯曲線設(shè)計(jì)任務(wù)路徑，使用粒子群優(yōu)化算法優(yōu)化其路徑長度和曲率參數(shù)，并同步調(diào)整飛行速度，滿足同時(shí)到達(dá)要求，避免了單純控制路徑長度所帶來的大量迭代計(jì)算。文獻(xiàn)［24］考慮無人機(jī)對(duì)地面移動(dòng)目標(biāo)的追蹤，考慮無人機(jī)與目標(biāo)速度差異，基于二者相對(duì)位置、速度比和轉(zhuǎn)彎半徑設(shè)計(jì)追蹤路徑，保持無人機(jī)與目標(biāo)的同步運(yùn)動(dòng)并最小化相對(duì)距離。

機(jī)間避撞需求可以通過生成空間無交叉或時(shí)空四維無交叉的路徑進(jìn)行處理。文獻(xiàn)［91］使用路由網(wǎng)絡(luò)對(duì)區(qū)域進(jìn)行劃分，以避開障礙并防止路徑交叉，使用Dijkstra算法計(jì)算最短任務(wù)路徑，在此基礎(chǔ)上插入航路點(diǎn)延長路徑以滿足時(shí)序協(xié)同需求;文獻(xiàn)［94］研究多無人機(jī)編隊(duì)避障問題，通過Voronoi圖將場景分割為不重疊區(qū)域作為無人機(jī)的運(yùn)動(dòng)區(qū)域，并通過人工勢(shì)場法設(shè)計(jì)控制策略，避免無人機(jī)相互碰撞?？紤]時(shí)空調(diào)整，文獻(xiàn)［14］列舉勢(shì)場法和在線預(yù)測策略，通過構(gòu)造時(shí)空無沖突路徑，可以最大限度地降低沖突風(fēng)險(xiǎn)。文獻(xiàn)［98］針對(duì)密集無人機(jī)集群協(xié)同規(guī)劃問題，設(shè)計(jì)分布式動(dòng)態(tài)優(yōu)先級(jí)解耦策略，降低飛行時(shí)間短的無人機(jī)的優(yōu)先級(jí)以挖掘其路徑調(diào)整潛力，低優(yōu)先級(jí)無人機(jī)單向調(diào)整自身路徑以避免與高優(yōu)先級(jí)無人機(jī)發(fā)生碰撞，從而獲得整體無碰撞路徑。

2 方案求解與評(píng)估

任務(wù)規(guī)劃模型的高效求解是多無人機(jī)協(xié)同應(yīng)用的現(xiàn)實(shí)需求。本節(jié)首先列舉常用的集中式和分布式算法，分析不同算法面向任務(wù)規(guī)劃求解的改進(jìn)策略，然后歸納多無人機(jī)系統(tǒng)的效能評(píng)估流程。

2.1 常用求解算法

集中式方法利用中心節(jié)點(diǎn)收集信息并指派任務(wù)，可以充分協(xié)調(diào)各類資源，能夠獲得最優(yōu)方案，但是其依賴于中心節(jié)點(diǎn)且擴(kuò)展性差，適用于在任務(wù)執(zhí)行前綜合已知信息進(jìn)行調(diào)度^［72］。分布式算法基于去中心化思想設(shè)計(jì)，依賴于機(jī)間信息交互以實(shí)現(xiàn)任務(wù)協(xié)同，避免了單點(diǎn)失效風(fēng)險(xiǎn)且擴(kuò)展性較好，但缺少中心節(jié)點(diǎn)的協(xié)調(diào)會(huì)造成單元間的任務(wù)競爭，算法需要在解決單元沖突和提升協(xié)調(diào)效率之間尋找平衡，適用于在任務(wù)執(zhí)行過程中根據(jù)場景變化快速調(diào)整方案。

2.1.1 集中式方法

集中式方法可分為精確方法和近似方法：精確方法是以較高的時(shí)間成本獲得最優(yōu)解，近似方法是在有限時(shí)間內(nèi)獲得滿意解。圖3展示了集中式方法下的精確方法和近似方法的各類具體算法。

（1） 精確方法

精確方法可以為任務(wù)規(guī)劃問題分析提供準(zhǔn)確參考^［58］，包含動(dòng)態(tài)規(guī)劃和分支方法。

動(dòng)態(tài)規(guī)劃是一種求解多步優(yōu)化問題的全局優(yōu)化方法，任務(wù)規(guī)劃問題需要優(yōu)化無人機(jī)對(duì)多個(gè)任務(wù)的執(zhí)行順序，適用于動(dòng)態(tài)規(guī)劃方法^{［8，99］}。文獻(xiàn)［8］針對(duì)多區(qū)域覆蓋偵察問題，使用動(dòng)態(tài)規(guī)劃方法遞歸求解以獲得多個(gè)區(qū)域的最佳訪問順序及進(jìn)出位置。部分研究使用多步前瞻策略簡化動(dòng)態(tài)規(guī)劃方法：文獻(xiàn)［99］針對(duì)對(duì)抗環(huán)境中多無人機(jī)協(xié)同場景，使用兩步前瞻策略求解無人機(jī)的行動(dòng)方案，能夠以較少時(shí)間獲取與最優(yōu)解相近的結(jié)果。文獻(xiàn)［100］針對(duì)Dubins旅行商問題，每次只考慮部分目標(biāo)間的最短路徑，通過多步求解獲得整體路徑，并可動(dòng)態(tài)調(diào)整前瞻程度以平衡求解效率與方案效果。

分支方法是樹搜索策略的一種，主要包含分支定界法、分支定價(jià)法和分支切割法等。分支定界法在混合整數(shù)線性規(guī)劃模型的求解過程中修剪次優(yōu)解分支，避免大量無用搜索。文獻(xiàn)［68］使用分支定價(jià)法求解時(shí)序耦合問題，利用約束分布稀疏的特點(diǎn)，通過列生成策略將問題分解為多個(gè)小問題進(jìn)行求解并逐步逼近最優(yōu)解，有效縮減了計(jì)算時(shí)間。文獻(xiàn)［70］考慮最壞情況建立魯棒異構(gòu)車輛路徑問題線性規(guī)劃模型，使用分支切割法動(dòng)態(tài)引入約束條件以逼近最優(yōu)解，能夠獲得問題的精確下界，可作為多種啟發(fā)式算法的對(duì)比基準(zhǔn)。分支方法擁有大量改進(jìn)策略，如狀態(tài)空間松弛、啟發(fā)式分支修剪、啟發(fā)式標(biāo)簽策略等^［101102］。

（2） 近似方法

近似方法不追求獲得問題的最優(yōu)解，而是利用啟發(fā)式信息引導(dǎo)搜索以期在多項(xiàng)式時(shí)間內(nèi)獲得滿意解，可分為構(gòu)造啟發(fā)式算法和元啟發(fā)式算法兩類。

構(gòu)造啟發(fā)式算法根據(jù)問題特點(diǎn)設(shè)計(jì)搜索規(guī)則指導(dǎo)求解過程，如最鄰近法、最小成本增加插入法^［103］、時(shí)間增加最少插入法^{［81，103］}等。該類方法形式簡單，沒有復(fù)雜的控制參數(shù)，能夠以較少計(jì)算資源生成可行解，但無法確保解的質(zhì)量，因此多用于初始種群構(gòu)造。

元啟發(fā)式算法基于對(duì)自然界的學(xué)習(xí)，為問題求解提供了一種普遍適用框架，不依賴于對(duì)問題的精確數(shù)學(xué)分析，求解魯棒性強(qiáng)，可分為基于個(gè)體信息的搜索方法和基于群體信息的搜索方法。

個(gè)體信息搜索對(duì)單個(gè)解進(jìn)行逐步改進(jìn)以獲得滿意解，代表算法包含模擬退火^［7］、迭代局部搜索^{［70，104］}、自適應(yīng)變鄰域搜索算法^{［44，103］}等。文獻(xiàn)［104］使用變鄰域搜索算法求解車輛車隊(duì)路徑問題，使用了7種路徑間鄰域結(jié)構(gòu)和5種路徑內(nèi)鄰域結(jié)構(gòu)，如shift（m，n）移動(dòng)、k-opts交換等。文獻(xiàn)［44］設(shè)置基于任務(wù)路徑、任務(wù)負(fù)載和時(shí)間窗的多種鄰域，根據(jù)計(jì)算狀態(tài)評(píng)估不同鄰域的效果，并動(dòng)態(tài)調(diào)整重點(diǎn)搜索方向。個(gè)體搜索方法沒有通用架構(gòu)，需要根據(jù)問題特點(diǎn)針對(duì)性設(shè)置更新操作。

群體信息搜索依賴于當(dāng)前大量解的狀態(tài)引導(dǎo)搜索：如粒子群優(yōu)化算法^［11］、蟻群算法^{［17，92］}、遺傳算法^{［20，87］}、狼群算法^［56］、鴿子群算法^［35］等。文獻(xiàn)［20］和文獻(xiàn)［31］基于改進(jìn)遺傳算法求解任務(wù)規(guī)劃，使用多層目標(biāo)束編碼建立無人機(jī)與任務(wù)的映射關(guān)系，改進(jìn)交叉和變異操作以增強(qiáng)搜索能力。文獻(xiàn)［56］利用狼群算法求解，使用兩段式編碼縮小搜索空間，引入新的換位和擴(kuò)展操作以增強(qiáng)搜索能力。該類方法需要將問題空間合理映射至算法空間，動(dòng)態(tài)調(diào)整控制參數(shù)以平衡全局搜索與精細(xì)調(diào)整^{［44，92］}，恰當(dāng)處理多類約束以平衡求解效率與可行性^［66］，融合不同更新操作以增強(qiáng)搜索能力^{［7，87］}。

2.1.2 分布式方法

分布式算法可分為市場協(xié)商方法、分布式約束優(yōu)化方法和多智能體方法3類：市場協(xié)商方法通過競拍將任務(wù)分配給“收益”最高的單元;分布式約束優(yōu)化方法將任務(wù)列表在單元間傳遞，任務(wù)滿足“選擇閾值”則進(jìn)行分配;多智能體方法賦予各單元信息收集與分析能力，以集群涌現(xiàn)的形式實(shí)現(xiàn)任務(wù)協(xié)同。圖4展示了分布式方法下的市場協(xié)商方法、分布式約束優(yōu)化方法和多智能體方法的各類具體算法。

（1） 市場協(xié)商方法

市場協(xié)商方法根據(jù)“拍賣競標(biāo)中標(biāo)”競拍機(jī)制為單個(gè)任務(wù)^［12］或多個(gè)任務(wù)^［105］選擇合適的執(zhí)行單元。該類方法原理簡單，計(jì)算效率高，但由于協(xié)商需求帶來大量通信交互，在大規(guī)?；蛲ㄐ刨Y源密集場景下效果較差^［10］。其代表性算法包括拍賣算法^［56］、合同網(wǎng)算法^［85］、一致性眾包算法^{［61，105］}、性能評(píng)估算法^{［60，106］}等。

一致性眾包算法^［105］將多個(gè)任務(wù)構(gòu)造成任務(wù)包進(jìn)行分配，并通過沖突消解迭代尋找無矛盾解，較拍賣算法效率更高。性能評(píng)估算法^{［60，106］}在構(gòu)建收益函數(shù)時(shí)考慮前后任務(wù)的正/負(fù)向耦合關(guān)系，增加任務(wù)重要性指標(biāo)、提升整體任務(wù)執(zhí)行效率，降低了算法為快速收斂采用的貪婪策略的“短視”影響。為在不影響算法性能的前提下降低信息交互的需求，各類研究設(shè)計(jì)了大量策略：如設(shè)計(jì)動(dòng)態(tài)通信拓?fù)浣Y(jié)構(gòu)^［107］、調(diào)整雙向無源通信為單向有源通信^［29］、調(diào)整同步通信為異步通信^［107］，設(shè)計(jì)分組策略（預(yù)分組^［86］、地理距離^［82］和任務(wù)偏好^［108］）以非全連接形式降低通信需求。

（2） 分布式約束優(yōu)化方法

分布式約束優(yōu)化方法較市場協(xié)商方法更依賴于單元本地信息進(jìn)行決策，協(xié)調(diào)通信需求低，通過合理設(shè)計(jì)求解過程可以獲得誤差許可內(nèi)的近似解^［109］。其代表性算法有：Swarm-Gap算法、令牌傳遞算法、Max-Sum算法等。

Swarm-Gap算法根據(jù)預(yù)設(shè)閾值選擇任務(wù)，閾值設(shè)計(jì)對(duì)方案性能影響很大，因此多采用動(dòng)態(tài)閾值策略。文獻(xiàn)［110］設(shè)計(jì)分散遺忘的響應(yīng)閾值動(dòng)態(tài)調(diào)整策略，提升動(dòng)態(tài)場景的適應(yīng)性。文獻(xiàn)［111］針對(duì)動(dòng)態(tài)蟻群分工模型設(shè)計(jì)響應(yīng)閾值的調(diào)整策略，能夠有效處理異構(gòu)無人機(jī)和時(shí)序耦合任務(wù)的相關(guān)約束，并滿足快速重規(guī)劃需求。令牌傳遞算法傳遞包含任務(wù)信息的令牌，單元在接收令牌后決定執(zhí)行任務(wù)或?qū)⑷蝿?wù)隨機(jī)傳遞給其余單元。文獻(xiàn)［84］針對(duì)分配環(huán)網(wǎng)、任務(wù)選擇順序和無人機(jī)任務(wù)選擇進(jìn)行改進(jìn)，提升任務(wù)完成數(shù)量并縮減了任務(wù)完成時(shí)間。文獻(xiàn)［9］改進(jìn)算法以避免令牌的重復(fù)創(chuàng)建與無效傳遞，在搜索救援場景中較貪婪算法性能提升明顯。文獻(xiàn)［109］設(shè)計(jì)多層Max-Sum算法，通過分層策略處理任務(wù)間時(shí)序約束，通過時(shí)序網(wǎng)絡(luò)處理任務(wù)時(shí)間窗約束，通過構(gòu)建多單元組合降低任務(wù)執(zhí)行時(shí)間，較拍賣算法提升了任務(wù)完成率并縮減了任務(wù)完成時(shí)間。

（3） 多智能體方法

多智能體方法為單元賦予信息收集、狀態(tài)分析與自主決策的能力，基于預(yù)設(shè)規(guī)則和局部交互，各單元自下而上地形成整體有序的協(xié)同狀態(tài)，具有高度自組織性、靈活性和擴(kuò)展性。其代表性算法為博弈論方法^{［49，53，112113］}和群體智能方法^{［9，17，111］}。

文獻(xiàn)［112］利用分布式博弈論框架求解動(dòng)態(tài)任務(wù)分配問題，基于貪婪策略設(shè)計(jì)協(xié)商過程，考慮任務(wù)成本的變化，能夠確保單元與整體收益一致。部分研究借鑒博弈論中的隱式協(xié)調(diào)策略，文獻(xiàn)［113］在一致性眾包算法中基于對(duì)其余智能體的預(yù)測進(jìn)行出價(jià)，在降低信息交互的同時(shí)提升了求解性能。

群體智能算法側(cè)重對(duì)生物群體機(jī)制的學(xué)習(xí)，如魚群遷徙、狼群捕獵、蟻群搬運(yùn)和蜂群覓食等。如圖5所示，無人機(jī)作為集群個(gè)體搜集環(huán)境信息，按照預(yù)定規(guī)則進(jìn)行交互并更新自身行為，在集群層面實(shí)現(xiàn)復(fù)雜任務(wù)協(xié)同^［14］。文獻(xiàn)［96］參考蟻群覓食機(jī)制，處理搜索打擊移動(dòng)目標(biāo)問題，調(diào)整信息素更新機(jī)制引導(dǎo)搜索，較傳統(tǒng)覆蓋搜索方式效率更高。文獻(xiàn)［115］參考狼群高效分工協(xié)作和復(fù)雜環(huán)境的適應(yīng)性，提出了對(duì)抗環(huán)境下無人機(jī)群協(xié)同決策策略。文獻(xiàn)［39］參考蝗蟲的獨(dú)居和群居狀態(tài)，在搜索與救援場景下，提出兼顧區(qū)域覆蓋搜索和關(guān)鍵區(qū)域聯(lián)合救援需求的調(diào)度策略。當(dāng)前群體智能算法多為生物行為的簡單模仿，多用于較為松散、簡單的“觸發(fā)式”任務(wù)場景。未來在復(fù)雜場景應(yīng)用時(shí)需要進(jìn)一步提煉生物群體的交互規(guī)則，如狼群捕獵時(shí)的分布位置、層級(jí)結(jié)構(gòu)、群組構(gòu)型等，針對(duì)性調(diào)整并豐富無人機(jī)內(nèi)部的協(xié)同策略。

2.2 效能評(píng)估流程

效能評(píng)估是通過對(duì)任務(wù)能力、協(xié)同效率、成本代價(jià)、計(jì)算效率等方面的分析，評(píng)估多無人機(jī)系統(tǒng)的綜合能力。效能評(píng)估流程包含評(píng)估指標(biāo)設(shè)計(jì)、指標(biāo)計(jì)算和權(quán)重設(shè)置3個(gè)部分。

評(píng)估指標(biāo)多采用多層體系設(shè)計(jì)，即將整體指標(biāo)劃分為多個(gè)類別，在每個(gè)類別下設(shè)置多種具體指標(biāo)?？紤]單機(jī)任務(wù)能力，在對(duì)地打擊場景下，文獻(xiàn)［116］從打擊、突防、態(tài)勢(shì)感知和能力范圍等方面建立指標(biāo)體系;文獻(xiàn)［117］使用ADC（availability，dependability，capability）法評(píng)估無人機(jī)效能，在完善能力類指標(biāo)基礎(chǔ)上，增加可靠度類和可用度類指標(biāo)?？紤]多機(jī)協(xié)同效率，文獻(xiàn)［118］針對(duì)觀察－判斷－決策－行動(dòng)（observe orient decide act， OODA）決策鏈，設(shè)置感知、通信、決策、打擊、組隊(duì)等全方面的協(xié)同作戰(zhàn)指標(biāo)體系;本文考慮多機(jī)打擊場景^［119］，基于打擊和協(xié)同情況設(shè)計(jì)效能影響因子，描述不同載荷的影響關(guān)系?？紤]綜合成本代價(jià)，文獻(xiàn)［38］考慮代價(jià)類指標(biāo)，分析不同類型無人機(jī)在對(duì)抗情況下的生存率;文獻(xiàn)［51］考慮成本類指標(biāo)，分析無人機(jī)搭載不同類型光學(xué)載荷、執(zhí)行偵察任務(wù)的經(jīng)濟(jì)成本;文獻(xiàn)［120］在評(píng)估裝備體系貢獻(xiàn)率時(shí)考慮成本因素，面向任務(wù)需求給出有限預(yù)算下的裝備列表?？紤]計(jì)算效率，文獻(xiàn)［121］設(shè)置規(guī)劃計(jì)算時(shí)間、重規(guī)劃響應(yīng)時(shí)間等指標(biāo)。

在指標(biāo)計(jì)算方面，定量指標(biāo)可以結(jié)合任務(wù)數(shù)據(jù)計(jì)算具體數(shù)值，如任務(wù)完成數(shù)量、命中概率、計(jì)算時(shí)間等;定性指標(biāo)沒有明確的表達(dá)式，一般需要在專家系統(tǒng)的支撐下，在預(yù)設(shè)范圍內(nèi)進(jìn)行評(píng)分，如抗干擾能力、協(xié)同感知能力等^{［38，51，119］}。部分研究對(duì)指標(biāo)值進(jìn)行規(guī)范化：文獻(xiàn)［117］將指標(biāo)實(shí)際值與預(yù)設(shè)期望值進(jìn)行對(duì)比;文獻(xiàn)［120］設(shè)計(jì)能力滿足函數(shù)進(jìn)行歸一化，指標(biāo)超出預(yù)定值則保持為1。

在權(quán)重設(shè)置方面，由于各類型指標(biāo)差異較大，可以采用模糊層級(jí)歸納法^［5152］、層次分析法^［117］、證據(jù)推理法^［121］等方法將多種指標(biāo)統(tǒng)一為綜合效能值。但上述方法主觀因素比較大，且不適用于多變的任務(wù)環(huán)境。因此，文獻(xiàn)［122］提出基于靜態(tài)貝葉斯網(wǎng)絡(luò)的評(píng)估方法，降低主觀因素的干擾;文獻(xiàn)［123］提出基于自適應(yīng)粒子群算法的反向傳播神經(jīng)網(wǎng)絡(luò)方法，具有良好的泛化能力，適用于動(dòng)態(tài)任務(wù)場景。

效能評(píng)估可以發(fā)現(xiàn)多無人機(jī)協(xié)同應(yīng)用的薄弱環(huán)節(jié)，為優(yōu)化多無人機(jī)系統(tǒng)的規(guī)模配置提供參考^［119］，指導(dǎo)后續(xù)無人機(jī)和任務(wù)載荷的改進(jìn)設(shè)計(jì)。

3 未來研究要點(diǎn)分析

任務(wù)規(guī)劃技術(shù)的發(fā)展可以推動(dòng)多無人機(jī)系統(tǒng)在多場景中的應(yīng)用，是無人機(jī)自主控制領(lǐng)域的關(guān)鍵問題。當(dāng)前多無人機(jī)協(xié)同任務(wù)規(guī)劃還存在較多挑戰(zhàn)，現(xiàn)梳理部分可行方向。

（1） 量化評(píng)估無人機(jī)配置與完成概率的關(guān)聯(lián)

無人機(jī)的配置影響整體協(xié)同效率，并與最終任務(wù)執(zhí)行效果息息相關(guān)。需要在合理表征無人機(jī)任務(wù)能力、資源數(shù)量、飛行航程和任務(wù)耦合關(guān)系的基礎(chǔ)上，在任務(wù)分配和航跡規(guī)劃計(jì)算方法支撐下，量化評(píng)估當(dāng)前條件下的可行資源配置與完成概率的關(guān)系，建立無人機(jī)配置計(jì)算方法，在避免遍歷無人機(jī)配置組合的前提下，根據(jù)任務(wù)需求調(diào)派合理數(shù)量的無人機(jī)，并根據(jù)場景變化靈活調(diào)整無人機(jī)數(shù)量。

（2） 不確定因素影響下的任務(wù)規(guī)劃建模

不確定因素會(huì)影響任務(wù)方案性能，甚至造成方案失效，需要在計(jì)算任務(wù)方案時(shí)考慮該類因素的影響。不確定因素的合理建模是平衡任務(wù)方案魯棒性和方案成本增加的關(guān)鍵，需要對(duì)比不同建模方法的差異，尋找合理的建模方法和控制參數(shù)，為模型構(gòu)建提供合理參考;同時(shí)考慮多種不確定因素同時(shí)出現(xiàn)時(shí)的建模策略，分析多類型因素的關(guān)聯(lián)性（如時(shí)間窗口的存在可以降低速度不確定性對(duì)任務(wù)方案的沖擊），以較小的成本獲得魯棒性強(qiáng)的任務(wù)方案。

（3） 適用于動(dòng)態(tài)場景高效求解的分布式算法

分布式算法通過單元間的信息交互實(shí)現(xiàn)任務(wù)指派，求解效率高，能夠適應(yīng)動(dòng)態(tài)任務(wù)場景需求。分布式算法需要針對(duì)信息交互機(jī)制、收益評(píng)估函數(shù)、沖突消解機(jī)制和集群協(xié)同規(guī)則等進(jìn)行改進(jìn)。調(diào)整信息交互機(jī)制，減少冗余信息交互，在不影響算法求解性能的同時(shí)降低通信壓力;豐富收益評(píng)估函數(shù)內(nèi)容，在單機(jī)收益基礎(chǔ)上增加對(duì)多機(jī)協(xié)同情況的評(píng)估;調(diào)整沖突消解機(jī)制，兼顧算法探索性能與收斂速度;設(shè)計(jì)協(xié)同規(guī)則，實(shí)現(xiàn)多約束下的集群智能涌現(xiàn)系統(tǒng)的構(gòu)建。

（4） 適用于任務(wù)規(guī)劃求解的強(qiáng)化學(xué)習(xí)方法

強(qiáng)化學(xué)習(xí)算法通過與環(huán)境的交互進(jìn)行學(xué)習(xí)，能夠有效獲取訓(xùn)練過程中的信息，突破“短視”限制獲得整體占優(yōu)的方案，適用于任務(wù)規(guī)劃這種多階段決策問題，在大規(guī)模多約束任務(wù)規(guī)劃問題中應(yīng)用前景廣闊。但任務(wù)規(guī)劃問題場景多樣，存在不同的任務(wù)、無人機(jī)配置和執(zhí)行要求等，需要考慮強(qiáng)化學(xué)習(xí)方法對(duì)環(huán)境的敏感問題，在構(gòu)建訓(xùn)練環(huán)境時(shí)考慮問題的復(fù)雜性，提升算法的泛化能力?？紤]到環(huán)境存在不確定因素干擾，無人機(jī)采取動(dòng)作后獲得的收益不是確定值，因此可以采用值分布強(qiáng)化學(xué)習(xí)算法處理不確定因素的問題，通過訓(xùn)練獲得收益的概率分布，提高方法的魯棒性。

（5） 多無人機(jī)系統(tǒng)任務(wù)規(guī)劃效能評(píng)估方法

效能評(píng)估可以為無人機(jī)配置部署和設(shè)計(jì)升級(jí)提供針對(duì)性的參考。需要面向異構(gòu)多無人機(jī)系統(tǒng)在復(fù)雜環(huán)境下的協(xié)同應(yīng)用，構(gòu)建全面的指標(biāo)體系，考慮任務(wù)能力、協(xié)同效率和動(dòng)態(tài)環(huán)境適應(yīng)性等。在指標(biāo)體系的基礎(chǔ)上，可以使用神經(jīng)網(wǎng)絡(luò)方法，在較少主觀因素的影響下，建立任務(wù)規(guī)劃效能評(píng)估方法。同時(shí)，需要建立參數(shù)敏感性分析方法，發(fā)現(xiàn)限制多無人機(jī)系統(tǒng)的薄弱點(diǎn)，進(jìn)而指導(dǎo)無人機(jī)配置與設(shè)計(jì)改進(jìn)。

4 結(jié) 論

任務(wù)規(guī)劃是多無人機(jī)協(xié)同應(yīng)用的頂層設(shè)計(jì)。本文針對(duì)這一帶約束的組合優(yōu)化問題，從表征建模和求解評(píng)估兩個(gè)角度梳理現(xiàn)有研究。從場景分析、任務(wù)分配和航跡規(guī)劃分析任務(wù)規(guī)劃建模，歸納要素表征、約束條件、不確定因素和航跡協(xié)同等方面的研究，為未來不同場景下的任務(wù)規(guī)劃建模提供參考;總結(jié)任務(wù)規(guī)劃求解中常用的集中式算法和分布式算法的特點(diǎn)及改進(jìn)策略，為后期優(yōu)化方法的選擇與改進(jìn)提供支撐;分析系統(tǒng)效能評(píng)估中指標(biāo)設(shè)計(jì)、數(shù)值計(jì)算和權(quán)重設(shè)置的研究，指導(dǎo)后期無人機(jī)單元配置與設(shè)計(jì)改進(jìn)。最后，總結(jié)未來無人機(jī)任務(wù)規(guī)劃研究的若干發(fā)展方向。本文的研究對(duì)于全面了解多無人機(jī)任務(wù)規(guī)劃研究現(xiàn)狀具有良好的參考意義。

參考文獻(xiàn)

［1］ OTTO R P. Small unmanned aircraft systems （SUAS） flight plan： 2016-2036. Bridging the gap between tactical and strategic［R］. Washington， DC： United States Air Force， 2016.

［2］ 牛軼峰， 沈林成， 李杰， 等. 無人有人機(jī)協(xié)同控制關(guān)鍵問題［J］. 中國科學(xué)： 信息科學(xué)， 2019， 49（5）： 538554.

NIU Y F， SHEN L C， LI J， et al. Key scientific problems in cooperation control of unmanned-manned aircraft systems［J］. Scientia Sinica （Informationis）， 2019， 49（5）： 538554.

［3］ 劉雷， 劉大為， 王曉光， 等. 無人集群與反無人集群發(fā)展現(xiàn)狀分析［J］. 航空學(xué)報(bào)， 202 42（S1）： 526908.

LIU L， LIU D W， WANG X G， et al. Analysis the development status of unmanned clusters and anti-unmanned clusters［J］. Acta Aeronautica et Astronautica Sinica， 202 42（S1）： 526908.

［4］ 王祥科， 劉志宏， 叢一睿， 等. 小型固定翼無人機(jī)集群綜述和未來發(fā)展綜述［J］. 航空學(xué)報(bào)， 2020， 41（4）： 23732.

WANG X K， LIU Z H， CONG Y R， et al. Miniature fixed-wing UAV swarms： review and outlook［J］. Acta Aeronautica et Astronautica Sinica， 2020， 41（4）： 23732.

［5］ ZHANG J， XING J H. Cooperative task assignment of multi-UAV system［J］. Chinese Journal of Aeronautics， 2020， 33（11）： 28252827.

［6］ OH G， KIM Y， AHN J， et al. Market-based task assignment for cooperative timing missions in dynamic environments［J］. Journal of Intelligent amp; Robotic Systems， 2017， 87（1）： 97123.

［7］ LIU H， LI X M， WU G H， et al. An iterative two-phase optimization method based on divide and conquer framework for integrated scheduling of multiple UAVs［J］. IEEE Trans.on Intelligent Transportation Systems， 202 22（9）： 59265938.

［8］ XIE J F， CARRILLO L R G， JIN L. An integrated traveling salesman and coverage path planning problem for unmanned aircraft systems［J］. IEEE Control Systems Letters， 2019， 3（1）： 6772.

［9］ FERREIRA P R， SANTOS F D， BAZZAN A L C， et al. RoboCup rescue as multiagent task allocation among teams： experiments with task interdependencies［J］. Autonomous Agents and Multi-Agent Systems， 2010， 20（3）： 421443.

［10］ BUCKMAN N. Decentralized task allocation for dynamic， time-sensitive tasks［D］. Cambridge： Massachusetts Institute of Technology， 2018.

［11］ GENG N， MENG Q S， GONG D W， et al. How good are distributed allocation algorithms for solving urban search and rescue problems？ A comparative study with centralized algorithms［J］. IEEE Trans.on Automation Science and Engineering， 2019， 16（1）： 478485.

［12］ YAO W R， QI N M， WAN N， et al. An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles［J］. Aerospace Science and Technology， 2019， 86： 455464.

［13］ WANG Y， RU Z Y， WANG K Z， et al. Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing［J］. IEEE Trans.on Cybernetics， 2020， 50（9）： 39843997.

［14］ 賈高偉， 王建峰. 無人機(jī)集群任務(wù)規(guī)劃方法研究綜述［J］. 系統(tǒng)工程與電子技術(shù)， 202 43（1）： 99111.

JIA G W， WANG J F. Research review of UAV swarm mission planning method［J］. Systems Engineering and Electronics， 202 43（1）： 99111.

［15］ LIU Z H， WANG X K， SHEN L C， et al. Mission-oriented miniature fixed-wing UAV swarms： a multilayered and distributed architecture［J］. IEEE Trans.on Systems， Man， and Cybernetics： Systems， 202 52（3）： 15881602.

［16］ WANG Z， LIU L， LONG T， et al. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding［J］. Chinese Journal of Aeronautics， 2017， 31（2）： 339350.

［17］ ZHEN Z Y， ZHU P， XUE Y X， et al. Distributed intelligent self-organized mission planning of multi-UAV for dynamic targets cooperative search-attack［J］. Chinese Journal of Aeronautics， 2019， 32（12）： 27062716.

［18］ CHEN H X， NAN Y， YANG Y. Multi-UAV reconnaissance task assignment for heterogeneous targets based on modified symbiotic organisms search algorithm［J］. Sensors， 2019， 19（3）： 734.

［19］ COOMBES M， FLETCHER T， CHEN W H， et al. Optimal polygon decomposition for UAV survey coverage path planning in wind［J］. Sensors， 2018， 18（7）： 2132.

［20］ YE F， CHEN J， TIAN Y， et al. Cooperative multiple task assignment of heterogeneous UAVs using a modified genetic algorithm with multi-type-gene chromosome encoding strategy［J］. Journal of Intelligent amp; Robotic Systems， 2020， 100（2）： 615627.

［21］ MEYER Y， ISAIAH P， SHIMA T. On Dubins paths to intercept a moving target［J］. Automatica， 2015， 53： 256263.

［22］ WU W N， WANG X G， CUI N G. Fast and coupled solution for cooperative mission planning of multiple heterogeneous unmanned aerial vehicles［J］. Aerospace Science amp; Technology， 2018， 79： 131144.

［23］ WANG J F， JIA G W， LIN J C， et al. Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm［J］. Journal of Central South University， 2020， 27（2）： 432448.

［24］ MENG W， HE Z R， SU R， et al. Decentralized multi-UAV flight autonomy for moving convoys search and track［J］. IEEE Trans.on Control Systems Technology， 2017， 25（4）： 14801487.

［25］ FU X W， FENG P， GAO X G. Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism［J］. IEEE Access， 2019， 7： 4109041100.

［26］ YAN F， ZHU X P， ZHOU Z， et al. Heterogeneous multi-unmanned aerial vehicle task planning： simultaneous attacks on targets using the Pythagorean hodograph curve［J］. Proc.of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering， 2019， 233（13）： 47354749.

［27］ WU W N， CUI N G. A distributed and integrated method for cooperative mission planning of multiple heterogeneous UAVs［J］. Aircraft Engineering and Aerospace Technology， 2018， 90（9）： 14031412.

［28］ DENG Q B， YU J Q， MEI Y S. Deadlock-free consecutive task assignment of multiple heterogeneous unmanned aerial vehicles［J］. Journal of Aircraft， 2014， 51（2）： 596605.

［29］ KIM K S， KIM H Y， CHOI H L. Minimizing communications in decentralized greedy task allocation［J］. Journal of Aerospace Information Systems， 2019， 16（8）： 340345.

［30］ FU X W， FENG P， LI B， et al. A two-layer task assignment algorithm for UAV swarm based on feature weight clustering［J］. International Journal of Aerospace Engineering， 2019， 2019：

3504248.

［31］ XU G T， LONG T， WANG Z， et al. Target-bundled genetic algorithm for multi-unmanned aerial vehicle cooperative task assignment considering precedence constraints［J］. Proc.of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering， 2019， 234（3）： 760773.

［32］ KOPEIKIN A N， PONDA S S， JOHNSON L B， et al. Real-time dynamic planning to maintain network connectivity in a team of unmanned air vehicles［C］∥Proc.of the IEEE Globecom Workshops， 2011： 13031307.

［33］ LIU J L， LIAO X H， YE H P， et al. UAV swarm scheduling method for remote sensing observations during emergency scenarios［J］. Remote Sensing， 202 14（6）： 1406.

［34］ WANG G G， CHU H E， MIRJALILI S. Three-dimensional path planning for UCAV using an improved bat algorithm［J］. Aerospace Science and Technology， 2016， 49： 231238.

［35］ DUAN H B， ZHAO J X， DENG Y M， et al. Dynamic discrete pigeon-inspired optimization for multi-UAV cooperative search-attack mission planning［J］. IEEE Trans.on Aerospace and Electronic Systems， 202 57（1）： 706720.

［36］ YOMCHINDA T， HORN J F， LANGELAAN J W. Modified dubins parameterization for aircraft emergency trajectory planning［J］. Proc.of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering， 2016， 231（2）： 374393.

［37］ MOON S， YANG K， GAN S， et al. Decentralized information-theoretic task assignment for searching and tracking of moving targets［C］∥Proc.of the International Conference on Unmanned Aircraft Systems， 2015： 10311036.

［38］ 劉文金， 裴揚(yáng)， 葛玉雪， 等. 基于ABMS的對(duì)地攻擊型無人機(jī)體系貢獻(xiàn)率評(píng)估［J］. 航空學(xué)報(bào)， 202 43（9）： 225972.

LIU W J， PEI Y， GE Y X， et al. System-of-systems contribution evaluation of ground-attack UCAV based on ABMS［J］. Acta Areonautica et Astronautica Sinica， 202 43（9）： 225972.

［39］ KURDI H A， HOW J P. Bio-inspired algorithm for task allocation in multi-UAV search and rescue missions［C］∥Proc.of the AIAA Guidance， Navigation， and Control Conference， 2016： 22832291.

［40］ BUCKMAN N， HOW J P， CHOI H L. Partial replanning for decentralized dynamic task allocation［C］∥Proc.of the AIAA Scitech Forum， 2019： 11741184.

［41］ MERCKER T， CASBEER D W， MILLET P T， et al. An extension of consensus-based auction algorithms for decentralized， time-constrained task assignment［C］∥Proc.of the American Control Conference， 2010： 63246329.

［42］ KOPEIKIN A N， PONDA S S， JOHNSON L B， et al. Dynamic mission planning for communication control in multiple unmanned aircraft teams［J］. Unmanned Systems， 2013， 1（1）： 4158.

［43］ OTTO A， AGATZ N， CAMPBELL J， et al. Optimization approaches for civil applications of unmanned aerial vehicles （UAVs） or aerial drones： a survey［J］. Networks， 2018， 72（4）： 411458.

［44］ HU C H， LU J， LIU X， et al. Robust vehicle routing problem with hard time windows under demand and travel time uncertainty［J］. Computers amp; Operations Research， 2018， 94： 139153.

［45］ MANDAL S， GAO T， BHATTACHARYA S. Planning for aerial robot teams for wide-area biometric and phenotypic data collection［C］∥Proc.of the IEEE/RSJ International Conference on Intelligent Robots and Systems， 2021： 25862591.

［46］ ZHANG J M， LIU Z， SHI J， et al. Weapon configuration， allocation and route planning with time windows for multiple unmanned combat air vehicles［J］. Journal of Systems Engineering and Electronics， 2018， 29（5）： 953968.

［47］ XU C， XU M， YIN C J. Optimized multi-UAV cooperative path planning under the complex confrontation environment［J］. Computer Communications， 2020， 162： 196203.

［48］ MOON S， OH E， SHIM D H. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments［J］. Journal of Intelligent amp; Robotic Systems， 2013， 70（1）： 303313.

［49］ JANG I， SHIN H S， TSOURDOS A， et al. An integrated decision-making framework of a heterogeneous aerial robotic swarm for cooperative tasks with minimum requirements［J］. Proc.of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering， 2018， 233（6）： 21012118.

［50］ DASDEMIR E， KOKSALAN M， TEZCANER OZTURK D. A flexible reference point-based multi-objective evolutionary algorithm： an application to the UAV route planning problem［J］. Computers amp; Operations Research， 2020， 114（2）： 104811.

［51］ SEETHALER J， STROHAL M， STTZ P. Measuring multi-UAV mission efficiency： concept validation and enhanced metrics［C］∥Proc.of the International Conference on Modeling and Simulation for Autonomous Systems， 2022： 158179.

［52］ SEETHALER J， STROHAL M， STTZ P. Multi-UAV mission efficiency： first results in an agent-based simulation［C］∥Proc.of the International Conference on Modeling and Simulation for Autonomous Systems， 2020： 169188.

［53］ GARCIA E， CASBEER D W. Cooperative task allocation for unmanned vehicles with communication delays and conflict resolution［J］. Journal of Aerospace Information Systems， 2016， 13（2）： 113.

［54］ WHITTEN A K， CHOI H L， JOHNSON L B， et al. Decentralized task allocation with coupled constraints in complex missions［C］∥Proc.of the American Control Conference， 2011： 16421649.

［55］ NUNES E， MANNER M， MITICHE H， et al. A taxonomy for task allocation problems with temporal and ordering constraints［J］. Robotics and Autonomous Systems， 2017， 90： 5570.

［56］ CHEN Y B， YANG D， YU J Q. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm［J］. IEEE Trans.on Aerospace and Electronic Systems， 2018， 54（6）： 28532872.

［57］ VERBEECK C， VANSTEENWEGEN P， AGHEZZAF E H. Solving the stochastic time-dependent orienteering problem with time windows［J］. European Journal of Operational Research， 2016， 255（3）： 699718.

［58］ MUNARI P， MORENO A， VEGA J D L， et al. The robust vehicle routing problem with time windows： compact formulation and branch-price-and-cut method［J］. Transportation Science， 2019， 53（4）： 10431066.

［59］ ZHAI Z Y， ORTEGA J M， MARTINEZ N L， et al. A mission planning approach for precision farming systems based on multi-objective optimization［J］. Sensors， 2018， 18（6）： 1795.

［60］ WHITBROOK A， MENG Q， CHUNG P W H. A novel distributed scheduling algorithm for time-critical multi-agent systems［C］∥Proc.of the IEEE/RSJ International Conference on Intelligent Robots and Systems， 2015： 64516458.

［61］ YE F， CHEN J， SUN Q， et al. Decentralized task allocation for heterogeneous multi-UAV system with task coupling constraints［J］. The Journal of Supercomputing， 202 77（1）： 111132.

［62］ HU X X， LIU Y H， WANG G Q. Optimal search for moving targets with sensing capabilities using multiple UAVs［J］. Journal of Systems Engineering and Electronics， 2017， 28（3）： 526535.

［63］ MILLET T， CASBEER D， MERCKER T， et al. Multi-agent decentralized search of a probability map with communication constraints［C］∥Proc.of the AIAA Guidance， Navigation， and Control Conference， 2010： 8424.

［64］ CHEN J， QING X G， YE F， et al. Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment［J］. The Journal of Supercomputing， 202 78（8）： 17121740.

［65］ JIA Z Y， YU J Q， AI X L， et al. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm［J］. Aerospace Science and Technology， 2018， 76： 112125.

［66］ VIDAL T， CRAINIC T G， GENDREAU M， et al. Time-window relaxations in vehicle routing heuristics［J］. Journal of Heuristics， 2015， 21（3）： 329358.

［67］ EVERS L， BARROS A I， MONSUUR H， et al. Online stochastic UAV mission planning with time windows and time-sensitive targets［J］. European Journal of Operational Research， 2014， 238（1）： 348362.

［68］ CASBEER D， HOLSAPPLE R. Column generation for a UAV assignment problem with precedence constraints［J］. International Journal of Robust and Nonlinear Control， 201 21： 14211433.

［69］ XIONG J， LI J， LI J， et al. Probability-tuned market-based allocations for UAV swarms under unreliable observations［J］. IEEE Trans.on Cybernetics， 2022： 112.

［70］ SUBRAMANYAM A， REPOUSSIS P P， GOUNARIS C E. Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty［J］. Informs Journal on Computing， 2020， 32（3）： 661681.

［71］ ZHANG Y， BALDACCI R， SIM M， et al. Routing optimization with time windows under uncertainty［J］. Mathematical Programming， 2019， 175： 263305.

［72］ DULAI T， WERNER-STARK ， HANGOS K M. Algorithm for directing cooperative vehicles of a vehicle routing problem for improving fault-tolerance［J］. Optimization and Engineering， 2017， 19（2）： 239270.

［73］ PATEL R， RUDNICK-COHEN E， AZARM S H， et al. Robust multi-UAV route planning considering UAV failure［C］∥Proc.of the International Conference on Unmanned Aircraft Systems， 2019： 205212.

［74］ CUI J H， WEI R X， LIU Z C， et al. UAV motion strategies in uncertain dynamic environments： a path planning method based on Q-learning strategy［J］. Applied Sciences， 2018， 8（11）： 2169.

［75］ 張安， 楊咪， 畢文豪， 等. 基于多策略GWO算法的不確定環(huán)境下異構(gòu)多無人機(jī)任務(wù)分配［J］. 航空學(xué)報(bào)， 2023， 44（8）： 327115.

ZHANG A， YANG M， BI W H， et al. Task allocation of heterogeneous multi-UAV in uncertain environment based on multiple strategies GWO［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（8）： 327115.

［76］ WHITBROOK A， MENG Q， CHUNG P W H. Addressing robustness in time-critical， distributed， task allocation algorithms［J］. Applied Intelligence， 2019， 49（1）： 115.

［77］ CAMPBELL T， JOHNSON L， HOW J. Multiagent allocation of Markov decision process tasks［C］∥Proc.of the American Control Conference， 2013： 23562361.

［78］ 孫昱， 姚佩陽， 孫鵬， 等. 基于魯棒多目標(biāo)優(yōu)化的智能體群組協(xié)同任務(wù)規(guī)劃［J］. 控制與決策， 2016， 31（11）： 20452052.

SUN Y， YAO P Y， SUN P， et al. Cooperative task scheduling method for agent group using robust multiobjective optimization approach［J］. Control and Decision， 2016， 31（11）： 20452052.

［79］ YANG M， ZHANG A， BI W H， et al. A resource-constrained distributed task allocation method based on a two-stage coalition formation methodology for multi-UAVs［J］. The Journal of Supercomputing， 202 78（7）： 1002510062.

［80］ YANG M， BI W H， ZHANG A， et al. A distributed task reassignment method in dynamic environment for multi-UAV system［J］. Applied Intelligence， 202 52（2）： 15821601.

［81］ GAO K Z， YANG F J， ZHOU M C， et al. Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm［J］. IEEE Trans.on Cybernetics， 2019， 49（5）： 19441955.

［82］ LIU J M， WANG Q， XU Y J， et al. A novel distributed method for time-critical task allocation problems in multi-UAV system［C］∥Proc.of the IEEE International Conference on Communications， 2021.

［83］ XU G T， LI L， LONG T， et al. Cooperative multiple task assignment considering precedence constraints using multi-chromosome encoded genetic algorithm［C］∥Proc.of the AIAA Guidance， Navigation， and Control Conference， 2018： 33363344.

［84］ SCHWARZROCK J， ZACARIAS I， BAZZAN A L C， et al. Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence［J］. Engineering Applications of Artificial Intelligence， 2018， 6： 1020.

［85］ 嚴(yán)飛， 祝小平， 周洲， 等. 考慮同時(shí)攻擊約束的多異構(gòu)無人機(jī)實(shí)時(shí)任務(wù)分配［J］. 中國科學(xué)： 信息科學(xué)， 2019， 49（5）： 555569.

YAN F， ZHU X P， ZHOU Z， et al. Real-time task allocation for a heterogeneous multi-UAV simultaneous attack［J］. Scientia Sinica （Informationis）， 2019， 49（5）： 555569.

［86］ CHEN J， XIAO K， YOU K， et al. Hierarchical task assignment strategy for heterogeneous multi-UAV system in large-scale search and rescue scenarios［J］. International Journal of Aerospace Engineering， 2021（2）： 19.

［87］ ATENCIA C R， SER J D， CAMACHO D. Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning［J］. Swarm and Evolutionary Computation， 2019， 44： 480495.

［88］ SUBRAMANYAM A. Robust optimization of vehicle routing problems under uncertainty［D］. Pittsburgh： Carnegie Mellon University， 2018.

［89］ SUNDAR K， VENKATACHALAM S， MANYAM S G. Path planning for multiple heterogeneous unmanned vehicles with uncertain service times［C］∥Proc.of the International Conference on Unmanned Aircraft Systems， 2017： 480487.

［90］ WOLEK A， CHENG S， GOSWAMI D， et al. Cooperative mapping and target search over an unknown occupancy graph using mutual information［J］. IEEE Robotics and Automation Letters， 2020， 5（2）： 10711078.

［91］ LUITPOLD B. Coordinated target assignment and UAV path planning with timing constraints［J］. Journal of Intelligent amp; Robotic Systems， 2019， 94（3）： 857869.

［92］ XIA C， LIU Y T， YIN L Y， et al. Cooperative task assignment and track planning for multi-UAV attack mobile targets［J］. Journal of Intelligent amp; Robotic Systems， 2020， 100（3）： 13831400.

［93］ ZHEN Z Y， GAO C， ZHENG F Y， et al. Cooperative path replanning method for multiple unmanned aerial vehicles with obstacle collision avoidance under timing constraints［J］. Proc.of the Institution of Mechanical Engineers， Part G： Journal of Aerospace Engineering， 2015， 229（10）： 18131823.

［94］ HU J W， WANG M， ZHAO C H， et al. Formation control and collision avoidance for multi-UAV systems based on Voronoi partition［J］. Science China Technological Sciences， 2019， 63（1）： 6572.

［95］ FU Z J， MAO Y H， HE D J， et al. Secure multi-UAV collaborative task allocation［J］. IEEE Access， 2019， 7： 3557935587.

［96］ ZHEN Z Y， XING D J， GAO C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-orga-nized algorithm［J］. Aerospace Science and Technology， 2018， 76： 402411.

［97］ YAN F， ZHU X P， ZHOU Z， et al. A hierarchical mission planning method for simultaneous arrival of multi-UAV coalition［J］. Applied Sciences， 2019， 9（10）： 1986.

［98］ 徐廣通， 王祝， 曹嚴(yán)， 等. 動(dòng)態(tài)優(yōu)先級(jí)解耦的無人機(jī)集群軌跡分布式序列凸規(guī)劃［J］. 航空學(xué)報(bào)， 202 43（2）： 415426.

XU G T， WANG Z， CAO Y， et al. Dynamic priority decoupled UAV swarm trajectory planning using distributed sequential convex programming［J］. Acta Aeronautica et Astronautica Sinica， 202 43（2）： 415426.

［99］ ALIGHANBARI M， HOW J P. Cooperative task assignment of unmanned aerial vehicles in adversarial environments［C］∥Proc.of the American Control Conference， 2005： 46614666.

［100］ COHEN I， EPSTEIN C， ISAIAH P， et al. Discretization-based and look-ahead algorithms for the dubins traveling salesperson problem［J］. IEEE Trans.on Automation Science and Engineering， 2017， 14（1）： 383390.

［101］ 黃楠. 復(fù)雜多行程車輛路徑問題的精確算法研究［D］. 武漢： 華中科技大學(xué)， 2021.

HUANG N. A dissertation submitted in partial fulfillment of the requireme［D］. Wuhan： Huazhong University of Science amp; Technology， 2021.

［102］ MARN A. Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem［J］. European Journal of Operational Research， 2015， 245（3）： 680689.

［103］ KOC C， BEKTAS T， JABALI O， et al. A hybrid evolutio-nary algorithm for heterogeneous fleet vehicle routing problems with time windows［J］. Computers amp; Operations Research， 2015， 64： 1127.

［104］ PENNA P H V， SUBRAMANIAN A， OCHI L S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem［J］. Journal of Heuristics， 2013， 19（2）： 201232.

［105］ CHOI H L， BRUNET L， HOW J P. Consensus-based decentralized auctions for robust task allocation［J］. IEEE Trans.on Robotics， 2009， 25（4）： 912926.

［106］ ZHAO W Q， MENG Q G， CHUNG P W H. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario［J］. IEEE Trans.on Cybernetics， 2016， 46（4）： 902915.

［107］ JOHNSON L B， PONDA S S， CHOI H L， et al. Improving the effciency of a decentralized tasking algorithm for UAV teams with asynchronous communications［C］∥Proc.of the AIAA Guidance， Navigation， and Control Conference， 2010： 8421.

［108］ KIM K S， KIM H Y， CHOI H L. A bid-based grouping method for communication-efficient decentralized multi-UAV task allocation［J］. International Journal of Aeronautical and Space Sciences， 2020， 21（1）： 290302.

［109］ SUSLOVA E， FAZLI P. Multi-robot task allocation with time window and ordering constraints［C］∥Proc.of the IEEE/RSJ International Conference on Intelligent Robots and Systems， 2020： 69096916.

［110］ KAZAKOVA V A， WU A S， SUKTHANKAR G R. Respecializing swarms by forgetting reinforced thresholds［J］. Swarm Intelligence， 2020， 14（3）： 171204.

［111］ WU H S， LI H， XIAO R B， et al. Modeling and simulation of dynamic ant colony’s labor division for task allocation of UAV swarm［J］. Physica： A Statistical Mechanics amp; its Applications， 2018， 491（2018）： 127141.

［112］ BAKOLAS E， LEE Y. Decentralized game-theoretic control for dynamic task allocation problems for multi-agent systems［C］∥Proc.of the American Control Conference， 2021： 32283233.

［113］ JOHNSON L B， CHOI H L， HOW J P. Hybrid information and plan consensus in distributed task allocation［C］∥Proc.of the AIAA Guidance， Navigation， and Control Conference， 2013： 34053413.

［114］ NOWAK D J. Exploitation of self-organization in UAV swarms for optimization in combat environments［R］. Wright-Patterson AFB： Air Force Institute of Technology， 2008.

［115］ 段海濱， 張岱峰， 范彥銘， 等. 從狼群智能到無人機(jī)集群協(xié)同決策［J］. 中國科學(xué)： 信息科學(xué)， 2019， 49（1）： 112118.

DUAN H B， ZHANG D F， FAN Y M， et al. From wolf pack intelligence to UAV swarm cooperative decision-making［J］. Scientia Sinica （Informationis） 2019， 49（1）： 112118.

［116］ 屈高敏， 董彥非， 岳源. 對(duì)地攻擊型無人機(jī)作戰(zhàn)效能評(píng)估［J］. 火力與指揮控制， 2016， 41（4）： 145149.

QU G M， DONG Y F， YUE Y. Operational effectiveness evaluation of ground attack UCAV［J］. Fire Control amp; Command Control， 2016， 41（4）： 145149.

［117］ 何勝杰， 郭強(qiáng)， 王興虎， 等. 基于ADC分析法優(yōu)化的無人機(jī)效能評(píng)估方法［J］. 無人系統(tǒng)技術(shù)， 202 5（2）： 106116.

HE S J， GUO Q， WANG X H， et al. UAV performance evaluation method optimized based on ADC analysis method［J］. Unmanned Systems Technology， 202 5（2）： 106116.

［118］ 黃吉傳， 周德云. 無人機(jī)協(xié)同作戰(zhàn)效能評(píng)估指標(biāo)體系設(shè)計(jì)與分析［J］. 西安工業(yè)大學(xué)學(xué)報(bào)， 2020， 40（1）： 3844.

HUANG J C， ZHOU D Y. Design and analysis of an evaluation index system for UAV cooperative combat effectiveness［J］. Journal of Xi’an Technological University， 2020， 40（1）： 3844.

［119］ 李坎. 對(duì)地攻擊型無人機(jī)群協(xié)同作戰(zhàn)效能分析［J］. 指揮控制與仿真， 2017， 39（6）： 6368.

LI K. Effectiveness analysis of cooperative engagement for the ground attack unmanned aerial vehicles［J］. Command Control ＆ Simulation， 2017， 39（6）： 6368.

［120］ 劉鵬， 趙丹玲， 譚躍進(jìn)， 等. 面向多任務(wù)的武器裝備體系貢獻(xiàn)度評(píng)估方法［J］. 系統(tǒng)工程與電子技術(shù)， 2019， 41（8）： 17631770.

LIU P， ZHAO D L， TAN Y J， et al. Multi-task oriented contribution evaluation method of weapon equipment system of systems［J］. Systems Engineering and Electronics， 2019， 41（8）： 17631770.

［121］ 董新. 多功能UUV任務(wù)規(guī)劃與評(píng)估方法研究［D］. 哈爾濱： 哈爾濱工程大學(xué)， 2014.

DONG X. Research on mission planning and evaluation method of multi-function UUV［D］. Harbin： Harbin Engineering University， 2014.

［122］ 繆永飛. 多UAV聯(lián)合搜救任務(wù)規(guī)劃建模及優(yōu)化方法研究［D］. 武漢： 武漢理工大學(xué)， 2017.

MIAO Y F. Research on modeling and optimization of mission planning for multi-UAVs in joint search-and-rescue mission［D］. Wuhan： Wuhan University of Technology， 2017.

［123］ 陳俠， 胡乃寬. 基于APSO-BP神經(jīng)網(wǎng)絡(luò)的無人機(jī)空地作戰(zhàn)效能評(píng)估研究［J］. 飛行力學(xué)， 2018， 36（1）： 8892.

CHEN X， HU N K. Research on effectiveness evaluation of UAV air-to-ground attack based on APSO-BP neural network［J］. Flight Dynamics， 2018， 36（1）： 8892.

作者簡介

王建峰（1995—），男，助理研究員，博士，主要研究方向?yàn)闊o人機(jī)集群任務(wù)規(guī)劃。

賈高偉（1989—），男，副教授，博士，主要研究方向?yàn)橄冗M(jìn)飛行器設(shè)計(jì)、智能集群技術(shù)。

郭 正（1974—），男，教授，博士，主要研究方向?yàn)轱w行器氣動(dòng)設(shè)計(jì)、空氣動(dòng)力學(xué)。

侯中喜（1972—），男，教授，博士，主要研究方向?yàn)轱w行器總體設(shè)計(jì)。