MICA項目對多UAV協(xié)同作戰(zhàn)的多項關(guān)鍵技術(shù)進(jìn)行研究，其研究目標(biāo)是探索新的監(jiān)視和控制手段（即自主協(xié)同控制方法）以使人能更好地參與到戰(zhàn)場管理過程中，實現(xiàn)相對較少的操作人員對大規(guī)模無人作戰(zhàn)平臺編隊的控制。其研究課題包括協(xié)同任務(wù)分配、無人機(jī)路徑規(guī)劃、多機(jī)協(xié)同跟蹤、編隊控制等多個方面，參與團(tuán)隊主要來自麻省理工學(xué)院、加州伯克利大學(xué)等。WASM項目則多以UAV廣域搜索與打擊任務(wù)為背景，采用分層控制與優(yōu)化的手段對多機(jī)協(xié)同控制進(jìn)行研究，并在研究過程中建立一個MultiUAV協(xié)同控制仿真平臺。

       從這些研究項目可以看出，多無人機(jī)系統(tǒng)控制涉及軟硬件機(jī)器整合等多個方面，其中一個核心課題就是多無人機(jī)協(xié)同任務(wù)規(guī)劃問題，它直接決定在各個UAV個體間進(jìn)行工作任務(wù)分配和如何執(zhí)行，以在多種復(fù)雜因素影響下最大化系統(tǒng)效率。目前國內(nèi)外已經(jīng)有大量多個UAV協(xié)同任務(wù)規(guī)劃問題為主題的學(xué)術(shù)論文。

       在任何對多無人機(jī)協(xié)同任務(wù)規(guī)劃的研究中，首先必須明確其研究的任務(wù)背景是什么，再根據(jù)該任務(wù)背景要求進(jìn)行進(jìn)一步的分解和細(xì)化，形成無人機(jī)可以完成的工作，進(jìn)而根據(jù)任務(wù)指標(biāo)并考慮某些因素進(jìn)行問題建模與求解。協(xié)同任務(wù)規(guī)劃問題以多UAV系統(tǒng)總體性能最大化或代價最小化為指標(biāo)，其一般形式為將若干工作指派給多個UAV執(zhí)行。因為現(xiàn)實中存在著極其多樣化的任務(wù)背景以及復(fù)雜的影響因素，目前存在的任務(wù)規(guī)劃方法無不是針對特定的任務(wù)背景進(jìn)行研究。

 

       由于多無人機(jī)協(xié)同任務(wù)規(guī)劃問題的復(fù)雜性，一般采用分層控制（Hierarchical control）的方式將其分解成為決策層、協(xié)調(diào)層、執(zhí)行層等若干個子問題，再對這些子問題進(jìn)行求解，從而降低解決這個復(fù)雜問題的難度。如Boskovic，J.D.等人提出將任務(wù)規(guī)劃問題分解成決策層（decision making layer）、路徑規(guī)劃層（path planning layer）、軌跡生成層（trajectory generation layer）、內(nèi)環(huán)控制層(inner-loop control layer)等4個層次，其中：決策層負(fù)責(zé)多UAV系統(tǒng)頂層的任務(wù)決策、避障、沖突消解、任務(wù)分配和指標(biāo)評估等；路徑負(fù)責(zé)任務(wù)執(zhí)行中的運(yùn)動規(guī)劃，生成航路點，以引導(dǎo)UAV規(guī)避威脅、障礙等；軌跡層則負(fù)責(zé)根據(jù)UAV的狀態(tài)、輸入和初始條件等，為UAV生成通過航路點的可飛路徑；控制層則保證UAV準(zhǔn)確的沿著生成的軌跡飛行，并進(jìn)行一定的冗余管理以降低干擾等因素的影響。Tsourdos，A.等人則從UAV協(xié)同路徑規(guī)劃的角度講任務(wù)規(guī)劃的層次結(jié)構(gòu)分為機(jī)群協(xié)同任務(wù)規(guī)劃與分配層、機(jī)群協(xié)同路徑規(guī)劃層、單機(jī)控制層等三個層次。這些研究表明，這類分層控制的思路可以很好的梳理和降低多UAV協(xié)同決策與控制中的復(fù)雜性，是解決該問題的有效手段。

 

       有了分層控制的思路之后，需要對多機(jī)系統(tǒng)任務(wù)規(guī)劃問題進(jìn)行建模與求解。從數(shù)學(xué)角度（運(yùn)籌學(xué)，Operationgs research）看，該問題屬于一類復(fù)雜的組合優(yōu)化問題，需要對多UAV集群內(nèi)各個成員進(jìn)行任務(wù)指派和資源分配。對該優(yōu)化問題進(jìn)行建模與求解的方法有很多種，大致可以分為集中式和分布式兩類，兩者各有千秋。從發(fā)展的時間早晚來說，集中式的發(fā)展要早于分布式，但由于分布式相對而言在動態(tài)、不確定的場景下和實時性要求等方面的適用性更廣泛，對它的研究熱情有大漲之勢。

 

       （1）集中式任務(wù)規(guī)劃方法（Centrilized control）

特點是在系統(tǒng)中存在著一個中心節(jié)點，由這個中心節(jié)點完成整個系統(tǒng)的任務(wù)指派和調(diào)度、協(xié)調(diào)等工作，無人機(jī)僅充當(dāng)任務(wù)執(zhí)行者的角色。在集中式的處理過程中，問題建模和求解這兩個方面有著較為清晰的界限。

 

       將多UAV協(xié)同任務(wù)規(guī)劃問題抽象成組合優(yōu)化問題的形式，需要借助圖論（graph theory），把問題參與者，包括無人機(jī)和任務(wù)對象（如地面目標(biāo)）等，抽象成圖（graph）的節(jié)點（vertex），而一個UAV以某種狀態(tài)對一個對象執(zhí)行任務(wù)的過程則抽象成圖的邊（edge），再引入二元決策變量，把這個復(fù)雜的規(guī)劃問題刻畫成一個有向圖（directed graph）的形式。實際上不管集中式還是分布式方法都存在著這樣一個問題抽象的過程。

 

       然后，可以采用現(xiàn)有的方法對該問題進(jìn)行建模，并使用某種合適的搜索算法（search algorithm）對這個有向圖搜索以確定最優(yōu)解。

 

       現(xiàn)在已經(jīng)存在多種集中式任務(wù)規(guī)劃建模方法，包括多旅行商問題（Multiple Travelling Salesman problem，mTSP）、車輛路由問題（Vehicle Routing Problem，VRP）、網(wǎng)絡(luò)流（Network Flow Optimization，NFO）模型、混合整數(shù)線性規(guī)劃（Mixed-Integer Linear Programming，MILP）等。前兩種模型一般用于處理單一任務(wù)的多UAV協(xié)同，如協(xié)同搜索任務(wù)等，在建模過程中可以考慮問題的時間相關(guān)約束，如時間窗約束等。在處理多任務(wù)時，如確認(rèn)/攻擊/毀傷評估一體化任務(wù)，設(shè)定為只對目標(biāo)位置訪問一次的mTSP和VRP模型則變得不太好用。此時，NFO和MILP模型相對更適用些。

 

       NFO模型在早期對廣域搜索彈藥（WASM）問題的研究中使用較多。該方法以無人機(jī)為網(wǎng)絡(luò)中的供貨商，需要執(zhí)行的任務(wù)（可能是對地面目標(biāo)的確認(rèn)、打擊、毀傷評估等任務(wù)）為物流，而把對無人機(jī)執(zhí)行某項任務(wù)的指派決策當(dāng)做雪球，無人機(jī)對應(yīng)決策的執(zhí)行代價或收益則作為貨物在網(wǎng)絡(luò)中流動的成本，基于圖論建立網(wǎng)絡(luò)流模型。優(yōu)化目標(biāo)則是網(wǎng)絡(luò)流量總代價最小。

 

       MILP模型應(yīng)該是目前使用較廣泛的集中式任務(wù)規(guī)劃方法，在WASM、SEAD（Suppression of Enemy Air Defense，敵方防控火力壓制）等問題中均能建立較合適的模型。該方法屬于網(wǎng)絡(luò)流模型的自然拓展，其在建模過程中引入了兩種類型的決策變量：二元決策變量和連續(xù)決策變量。這兩類變量的使用，讓MILP方法能處理更管飯的任務(wù)規(guī)劃與調(diào)度問題，可以考慮更復(fù)雜的約束，如時間、資源等，本質(zhì)上講就是使任務(wù)規(guī)劃模型與一般意義上的組合優(yōu)化問題更接近了。

 

       在NFO和MILP模型的基礎(chǔ)上，Shima，T.等人總結(jié)并建立了被稱為“協(xié)同多任務(wù)分配問題”（Cooperative Multiple Task Assignment Problem，CMTAP）的組合優(yōu)化模型。CMTAP模型采用圖論描述方法，以多UAV系統(tǒng)對多個地面目標(biāo)協(xié)同執(zhí)行受時序優(yōu)先級的約束的確認(rèn)（classify）、攻擊（attack）和毀傷評估（verify）等三種任務(wù)為任務(wù)場景，考慮了時間、資源、可飛路徑馮多想約束。該模型能較好的描述多UAV協(xié)同任務(wù)規(guī)劃問題，基于它稍作改動即可適用于廣泛的應(yīng)用場景。

 

       理論上講，在建立任務(wù)規(guī)劃模型后，可以選擇很多種搜索算法進(jìn)行求解，如廣度優(yōu)先搜索（breadth-first search）、深度優(yōu)先搜索（depth-first search）、Dijktra算法、Bellman-Ford算法等確定性的圖搜索算法，分支定界（branch and bound）、動態(tài)規(guī)劃（dynamic programming）等優(yōu)化算法，以及遺傳算法（genetic algorithm，GA）、粒子群優(yōu)化算法（particle swarm optimization，PSO）、禁忌搜索（tabu search）、模擬退火（Simulated Annealing）等啟發(fā)模式隨機(jī)搜索算法。

 

       采用前兩類算法的好處是可以保證能夠找到問題的最優(yōu)解，而且由于已經(jīng)存在大量成熟的商業(yè)軟件如CPLEX等，可以直接使用它們而大大減少研究人員的工作量。在處理簡化問題時，它們因窮遍整個解空間而能獲得問題的最優(yōu)解，但隨著問題規(guī)模的增長，解空間的尺寸也指數(shù)級膨脹，遍歷所搜的計算量迅速增大，要窮遍整個解空間可能變得不顯示。這就是多UAV協(xié)同任務(wù)規(guī)劃問題的NP-hard特性。