一.協(xié)同任務(wù)規(guī)劃的功能與結(jié)構(gòu)

多無人機協(xié)同任務(wù)規(guī)劃即是根據(jù)一組特定條件的約束，以實現(xiàn)某個準(zhǔn)則函數(shù)的最優(yōu)或次優(yōu)為目標(biāo)，將某項作戰(zhàn)任務(wù)分解成一些子任務(wù)并分配給多無人機系統(tǒng)中的各個無人機分別去完成的過程。 通常多無人機任務(wù)規(guī)劃可以分成兩大部分：上層的任務(wù)分配(Task Assignment or Task Allocation)和下層的路徑規(guī)劃(Path Planning)

任務(wù)分配考慮各種約束條件，以總體任務(wù)有效達成為目標(biāo)，將具體目標(biāo)和行動任務(wù)分配給各機，而各機根據(jù)分配的任務(wù)再進行具體的作戰(zhàn)路徑規(guī)劃。

而路徑規(guī)劃的功能是在滿足如最大線性速度、最大轉(zhuǎn)角速度、操作的安全性、時間和環(huán)境變量等自身或外部限制的前提下在一系列位置之間設(shè)計或生成路徑。同時，多無人機協(xié)同任務(wù)規(guī)劃系統(tǒng)本身又是整個多無人機協(xié)同控制系統(tǒng)的重要組成部分。

二.任務(wù)分配

按照無人機作戰(zhàn)任務(wù)之間的相關(guān)聯(lián)性，可歸類為
1.獨立任務(wù)分配
2.協(xié)同任務(wù)分配
按照無人機作戰(zhàn)任務(wù)所處環(huán)境可分為
1.靜態(tài)任務(wù)分配
2.動態(tài)任務(wù)分配
按照分配方法可分為
1.集中式任務(wù)分配
2.分布式任務(wù)分配
3.分層式分布任務(wù)分配

協(xié)同任務(wù)分配

多無人機協(xié)同任務(wù)分配的目標(biāo)是在考慮各種諸如任務(wù)執(zhí)行順序、時間、無人機自身物理條件等約束條件的前提下，以總體任務(wù)效率最優(yōu)或次優(yōu)為目標(biāo)，離線地或?qū)崟r地將具體目標(biāo)和行動任務(wù)分配給各機。

三.建模

以集中式控制系統(tǒng)為基礎(chǔ)進行任務(wù)分配最常用的模型有
多旅行商問題（multiple traveling salesman problem,MTSP）模型[13]、
車輛路徑問題(Vehicle Routing,VRP)模型[14]、
多機路徑分配模型(mVRP)[19]、
混合整數(shù)線性規(guī)劃問題(Mixed-Integer Linear Programming ,MILP,)模型[15]、
動態(tài)網(wǎng)絡(luò)流優(yōu)化（Dynamic Network Flow Optimization ,DNFO)模型[16]、
多處理器資源分配問題模型(Multiple Processsors Resources Allocation ,CMTMP)模型[17]
除了上述模型外，美國空軍研究實驗室在無人機任務(wù)分配研究中建立了
帶時間窗的不同能力約束車輛路徑問題(CVRPTW,Capacitated Vehicle Routing Problem with Time Windows）

四.方法

1. 集中式任務(wù)分配方法

集中式控制系統(tǒng)就是編隊中的無人機之間的通信、信號的傳輸和控制均由唯一的一個控制中心來進行。
常用的模型有MTSP、VRP、MILP、DNFO、CMTAP。

1.1最優(yōu)化方法

(1)窮舉法，適用于離散且規(guī)模小的情況
(2)整數(shù)規(guī)劃法(Mixed-Integer Linear Programming,MIP)根據(jù)既定的目的和目標(biāo)，通過建立目標(biāo)函數(shù)和約束條件的方法對規(guī)模較小的任務(wù)分配問題進行解決的一種最優(yōu)化方法矩陣作業(yè)法、單純型法、匈牙利法、分支定界法等是比較常用的整數(shù)規(guī)劃方法。
(3)約束規(guī)劃(Constaint Programming CP)方法由變量集和約束集兩者組成，變量集內(nèi)的所有變量都有自己對應(yīng)的值域，且變量的取值也只能從其值域中選取，它是求解組合優(yōu)化問題的一種通用方法。
(4)圖論方法是通過圖示的方法把任務(wù)和接受任務(wù)的成員特征表述出來，同時在任務(wù)和系統(tǒng)成員之間用圖論方法建立匹配，以此設(shè)計出合理可行的任務(wù)分配方案。網(wǎng)絡(luò)流模型和偶圖匹配模型是兩種經(jīng)典的圖論任務(wù)分配模型。

1.2啟發(fā)式算法

在能夠接受的時間范圍內(nèi)求得局部最優(yōu)解或滿意解。
(1)列表規(guī)劃（List Scheduling，LS）方法的步驟是首先建立任務(wù)的優(yōu)先權(quán)函數(shù)，求得任務(wù)的處理次序，然后按照求得的任務(wù)處理次序?qū)⑷蝿?wù)分派給系統(tǒng)成員。最常見的列表規(guī)劃方法有動態(tài)列表規(guī)劃（Dynamic List Scheduling ，DLS）法、多維動態(tài)列表規(guī)劃（Multi-Dimensional Dynamic List Scheduling,MDLS）方法、多優(yōu)先級動態(tài)列表規(guī)劃（Multi-Priority List Dynamic Scheduling ,MPLDS）等。
(2)智能優(yōu)化算法
①進化算法EA 遺傳算法GA 遺傳規(guī)劃Genetic Programming-GP 進化規(guī)劃Evolutionary Programming-GP等
②群智能算法 PSO ACO
③人工免疫、禁忌搜索、模擬退火。

2.分布式任務(wù)分配

分布式控制系統(tǒng)與集中式控制系統(tǒng)不同的是實現(xiàn)信號傳輸?shù)姆绞?，前者無人機還可以在編隊內(nèi)進行通信，具有更好的靈活性。分布式控制系統(tǒng)結(jié)構(gòu)相比集中式控制系統(tǒng)結(jié)構(gòu)來說對無人機的要求更高，需要無人機具備獨立計算、分析與決策等能力。

2.1合同網(wǎng)方法

目前，合同網(wǎng)（ContractNet）是應(yīng)用范圍最廣的一種分布式任務(wù)分配方法，它的核心是為防止產(chǎn)生沖突，對每個問題的求解用通信的方式協(xié)商處理。[25]
合同網(wǎng)方法有發(fā)布者和競標(biāo)者兩個角色，由“招標(biāo)- 投標(biāo)- 中標(biāo)- 確認”4 個交互階段組成。在合同網(wǎng)協(xié)作方法中，系統(tǒng)成員的角色不用提前規(guī)定，任何系統(tǒng)成員可以是管理者，也可以是工作者，區(qū)別只在于成員是發(fā)布任務(wù)通知還是應(yīng)答任務(wù)通知，于是任務(wù)能夠被層次地分解分派。這種方法的缺點是通信量大、作為發(fā)布者的系統(tǒng)成員工作強度大且任務(wù)分解分配沒有有效融合等。

2.2 拍賣方法

拍賣方法是實現(xiàn)資源配置的一種市場機制，指的是買方在清楚了解拍賣規(guī)則的前提下，采用競價的方式?jīng)Q定特定物品的價格，也就是將要拍賣的物品用公開競價的方式轉(zhuǎn)賣給應(yīng)價最高（ 最低）者的一種交易方式。一個拍賣主要由參與方、拍賣品、收益函數(shù)和應(yīng)價策略4 個要素組成，在無人機任務(wù)分配問題中，無人機需要執(zhí)行的任務(wù)可視為拍賣品，無人機的任務(wù)分配方和任務(wù)接受方共同組成參與者，且雙方都有各自對應(yīng)的收益函數(shù)和出價策略。拍賣方法是一種協(xié)商協(xié)議，因其規(guī)則明確且便于操作，近年來受到越來越多學(xué)者們的關(guān)注。拍賣方法用明確的規(guī)則引導(dǎo)買賣雙方進行交互，可操作性非常強，能在較短時間內(nèi)將資源合理分配，得到問題的最優(yōu)解或較優(yōu)解。該方法現(xiàn)已廣泛運用在無人機作戰(zhàn)和傳感器等資源分配問題中。

綜述

文獻[1] 將任務(wù)分配方法歸納為集中式任務(wù)分配、分布式任務(wù)分配、分層次分布式任務(wù)分配三類，并對方法進行了簡單闡述，提出了幾個任務(wù)分配的可能的未來發(fā)展趨勢。

文獻［6］歸納和總結(jié)了多無人機協(xié)同任務(wù)規(guī)劃的國內(nèi)外研究現(xiàn)狀，重點總結(jié)了任務(wù)分配方法的常見模型和算法，對各種算法的優(yōu)缺點進行了討論，得出多智能體的市場機制類算法在空戰(zhàn)中將有廣泛的應(yīng)用價值。

模型

文獻［5］探索了對不同種類的目標(biāo)進行偵察、打擊和評估任務(wù)時異構(gòu)無人機的協(xié)同任務(wù)分配問題。對于偵察與評估任務(wù)中所得到的信息量，運用信息論中熵的變化量對其進行度量，把無人機對不同類型目標(biāo)的打擊能力簡化為對目標(biāo)的毀傷概率，同時把每個任務(wù)之間的關(guān)聯(lián)性考慮在內(nèi)，建立了異構(gòu)多無人機協(xié)同任務(wù)分配模型。

文獻［7］建立了以合同網(wǎng)協(xié)議和多智能體系統(tǒng)理論為基礎(chǔ)的有人機／ 無人機編隊MAS(Multi-agent System MAS)結(jié)構(gòu)和基于投標(biāo)過程的無人機任務(wù)分配模型。

文獻[23]提出了集群組網(wǎng)任務(wù)分配模型和任務(wù)分配求解算法。分析了集群組網(wǎng)的任務(wù)分配問題，并剖析了任務(wù)分配分層遞階結(jié)構(gòu)；借助層次分析思路，建立了集群組網(wǎng)任務(wù)分配模型；結(jié)合群體智能優(yōu)化算法的優(yōu)勢，提出了基于PSO-ICWPA 的集群組網(wǎng)任務(wù)分配算法；

同構(gòu)

1.蟻群

文獻［8］在無人機協(xié)同多任務(wù)分配的研究中，運用了基于分工機制的蟻群算法進行求解，并給出了基于作戰(zhàn)任務(wù)能力評估的問題解構(gòu)造策略和基于作戰(zhàn)任務(wù)代價的狀態(tài)轉(zhuǎn)移規(guī)則，大幅度提升了算法的性能。

2.粒子群

文獻［11］設(shè)計出一種多無人機任務(wù)分配與航跡規(guī)劃相結(jié)合的整體控制架構(gòu)，假設(shè)威脅和障礙區(qū)域為合理的多邊形模型，使用改進的算法求出兩個航跡點之間的最短路徑，將此路徑當(dāng)成任務(wù)分配過程全局目標(biāo)函數(shù)的輸入，然后用粒子群優(yōu)化任務(wù)分配迭代尋優(yōu)。

文獻［10］在基于任務(wù)依賴關(guān)系和ISO–DATA（Iterative Self-organizing Data Analysis Technique）算法相結(jié)合的基礎(chǔ)上設(shè)計了新的任務(wù)分組方法，在保持無人機負載均衡的基礎(chǔ)上，給出了基于資源福利的任務(wù)組級組粗粒度的無人機任務(wù)分配方法，在任務(wù)組內(nèi)提出了結(jié)合粒子群算法的細粒度任務(wù)分配算法。

文獻[21]通過綜合考慮多無人機任務(wù)分配約束條件，以多UCAV 總飛行航程和多UCAV 總飛行時間兩個關(guān)鍵指標(biāo)作為任務(wù)分配方案的評價標(biāo)準(zhǔn)，構(gòu)建多無人機任務(wù)分配模型，采用改進的QPSO 算法進行優(yōu)化求解多無人機任務(wù)分配問題。

文獻[22]，綜合考慮了協(xié)同多任務(wù)分配問題的任務(wù)優(yōu)先級和任務(wù)協(xié)同約束、任務(wù)時間約束，同時針對無人機載彈量有限的實際情況，將無人機的載彈量約束等同于無人機執(zhí)行攻擊任務(wù)的最大次數(shù)限制，建立了協(xié)同多任務(wù)分配模型，在算法引入自組織慣性權(quán)重和加速系數(shù)，增強了算法的全局和局部搜索能力，優(yōu)于遺傳算法的協(xié)同多任務(wù)分配。

GA

文獻[20]針對較為真實的戰(zhàn)場環(huán)境,將避障約束、禁飛區(qū)約束、任務(wù)執(zhí)行時間窗口約束、任務(wù)執(zhí)行次序約束等加入到CMTAP模型中,建立了較為完整的UAV協(xié)同任務(wù)分配模型, 用整數(shù)規(guī)劃法MIP和遺傳算法求解。但忽略了UAV間的避碰約束、UAV的異構(gòu)性、任務(wù)執(zhí)行時間約束等。

文獻[24]針對戰(zhàn)場環(huán)境的多目標(biāo)、多任務(wù)以及無人機能力有限等特點，設(shè)計了一種適應(yīng)于多目標(biāo)、多無人機、多任務(wù)種類的無人機群協(xié)同多任務(wù)分配模型。結(jié)合該模型以及其中的任務(wù)偏序約束、協(xié)同任務(wù)約束、無人機能力約束等約束條件提出了基于任務(wù)序列的遺傳算法染色體編碼方法，和基于同類任務(wù)的遺傳算法交叉、變異算子。該方法利用遺傳算法的全局搜索優(yōu)化解特點，對無人機群的協(xié)同任務(wù)分配進行優(yōu)化.

動態(tài)及不確定環(huán)境下

文獻[12]分析了實際戰(zhàn)場上信息的不確定性，同時指出了在此條件下多無人機面臨的任務(wù)分配問題。將收益毀傷代價指標(biāo)、目標(biāo)價值及航程代價指標(biāo)的不確定信息作為參考依據(jù)，在此基礎(chǔ)上建立了基于區(qū)間信息環(huán)境下多無人機的任務(wù)分配模型，采用隨機概率的多屬性方案排序（Stochastic Multi-criteria Acceptability Analysis,SMAA）方法，得出不確定環(huán)境下多無人機動態(tài)任務(wù)分配求解方法。

文獻[3]建立了多UCAV任務(wù)分配模型，對動態(tài)重分配策略進行研究并做出改進，將周期性重調(diào)度和事件驅(qū)動重調(diào)度進行有機結(jié)合。提出了一種改進的混合重調(diào)度策略．增加了對突發(fā)事件的處理能力，并結(jié)合粒子群算法和細菌覓食算法的優(yōu)缺點。提出了混合細菌覓食算法(PBFO)解決多UCAV的動態(tài)任務(wù)分配問題。

異構(gòu)

文獻［9］以異構(gòu)類型多目標(biāo)多無人機任務(wù)分配問題為原型，設(shè)計了一種基于時間窗的多無人機聯(lián)盟組任務(wù)分配方法，此算法使用沖突消解機制來防止無人機實時任務(wù)分配過程中出現(xiàn)多機資源死鎖，其次通過無人機兩階段任務(wù)聯(lián)盟構(gòu)成算法，組成了任務(wù)聯(lián)盟，使無人機任務(wù)分配的有效性和實時性有了很大的提高。
文獻[18]以多異構(gòu)無人機執(zhí)行SEAD任務(wù)為背景采用圖論的方法完成問題的建模,將無人機本體等效為Dubins Car模型,并對其在相應(yīng)目標(biāo)處執(zhí)行偵查、打擊、評估任務(wù)時的進入角度進行約束,通過Dubins路徑完成對無人機飛行路徑的等效,采用分布式遺傳算法完成對問題的快速求解.

文獻[4]基于文獻[20]的研究成果,將模型適用范圍擴展到了異構(gòu)UAV,但對約束條件的假設(shè)仍然相對理想.

文獻

[1]陳俠,喬艷芝.無人機任務(wù)分配綜述[J].沈陽航空航天大學(xué)學(xué)報,2016,33(6):1-7. DOI:10.3969/j.issn.2095-1248.2016.06.001.
[2]李煒,張偉. 基于粒子群算法的多無人機任務(wù)分配方法[J].控制與決策，2010,25(9):1359 -1364.
[3]楊尚君,王社偉,陶軍, 等.動態(tài)環(huán)境下的多UCAV協(xié)同任務(wù)分配研究[J].電光與控制,2012,19(7):32-36,79. DOI:10.3969/j.issn.1671-637X.2012.07.008.
[4]Wang J, Zhang Y F, Geng L, et al. A heuristicmission planning algorithm for heterogeneous tasks with
heterogeneous UAVs[J]. Unmanned Systems, 2015, 3(3):205-219.
[5]邸斌,周銳,丁全心. 多無人機分布式協(xié)同異構(gòu)任務(wù)分配[J].控制與決策,2013,28(2):274 -278.
[6]朱毅,張濤,程農(nóng),等.多UAV協(xié)同任務(wù)規(guī)劃研究[J]. 系統(tǒng)仿真學(xué)報,2009(20):194 -199.
[7]劉躍峰,張安.有人機/無人機編隊協(xié)同任務(wù)分配方法[J]. 系統(tǒng)工程與電子技術(shù),2010，32(3):584-588.
[8]蘇菲,，陳巖,沈林成.基于蟻群算法的無人機協(xié)同多任務(wù)分配[J]. 航空學(xué)報,2008(29):184-191.
[9]林林,孫其博,王尚廣,等.基于時間窗的多無人機聯(lián)盟任務(wù)分配方法研究[J].電子與信息學(xué)報,2013,35(8):1983-1988.
[10]譚何順,曹雷,彭輝,等. 一種多無人機層次化任務(wù)分配方法[J]. 解放軍理工大學(xué)學(xué)報(自然科學(xué)版),2014,15(1):18 -24.
[11]孫小雷,齊乃明,董程,等. 無人機任務(wù)分配與航跡規(guī)劃協(xié)同控制方法[J]. 火力與指揮控制,2015,37(12):2772 -2776.
[12]陳俠,唐婷.不確定環(huán)境下多無人機動態(tài)任務(wù)分配方法.火力與指揮控制[J].2013,38(1):45 -49.
[13]SECREST. Traveling salesman problem for surveillance mission using particel swarm optimization [Ｄ]. wright-PattersonAFB:Air Force Institute of Technologhy,2003.
[14]O’Rourke K P,Bailey T G,Hill R,et al. Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search[J].Military Operations Research Journal, 2001(6):5 -30.
[15]ALIGHANBARI M.Task assignment algorithms for teams of UAVs in dynamic environments[D].Cambridge:Massachusetts Institute of Technology,2004.
[16]NYGARD K E,CHANDLER P R,PACHTER M.Dynamic network flow optimization modles for air vehicle resourceallocation[C]//Proceedingsofthe 2001 American Control Conference,2001,3:1853-1858.
[17] ALVARO E G .Stability Analysis of Network-based Cooperative Resource Allocation Strategies[D].Columbus:Ohio State University,2003.
[18]吳蔚楠,關(guān)英姿,郭繼峰, 等.基于SEAD任務(wù)特性約束的協(xié)同任務(wù)分配方法[J].控制與策,2017,32(9):1574-1582. DOI:10.13195/j.kzyjc.2016.0858.
[19] Arsie A, Savla K, Frazzoli E. Efficient routing algorithmsfor multiple vehicles with no explicit communications[J].IEEE Trans on Automatic Control, 2009, 54(10):2302-2317.
[20]Geng L, Zhang Y F, Wang J, et al. Cooperative missionplanning with multipleUAVs in realistic environments[J].Unmanned Systems, 2014, 2(1): 73-86.
[21]鄧可,連振江,周德云, 等.基于改進量子粒子群算法的多無人機任務(wù)分配[J].指揮控制與仿真,2018,40(5):32-36. DOI:10.3969/j.issn.1673-3819.2018.05.007.
[22]梁國強,康宇航,邢志川, 等.基于離散粒子群優(yōu)化的無人機協(xié)同多任務(wù)分配[J].計算機仿真,2018,35(2):22-28. DOI:10.3969/j.issn.1006-9348.2018.02.005.
[23]汪汝根,李為民,劉永蘭,劉金松.無人機集群組網(wǎng)任務(wù)分配方法研究[J].系統(tǒng)仿真學(xué)報,2018,30(12):4794-4801+4807.
[24]姚敏,王緒芝,趙敏.無人機群協(xié)同作戰(zhàn)任務(wù)分配方法研究[J].電子科技大學(xué)學(xué)報,2013,(5):723-727. DOI:10.3969/j.issn.1001-0548.2013.05.015.
[25]SM ITH R G.The Contractnet Protocol :High level Communication and Control in a Distributed problem solver [J]. IEEE Transaction and Computers