為繞開這個(gè)計(jì)算難點(diǎn)以減低大型問題的求解難度，Rasmussen，S.J.等人提出了一種樹搜索（tree search）算法對WASM問題進(jìn)行處理，他們將組合優(yōu)化問題以決策樹（decision tree）的形式表達(dá)出來，然后一邊通過最佳優(yōu)先所搜（best-first search）在已搜索的可行解中不斷降低解的上界，一邊又在決策樹上未評估的分支中通過歐氏距離確定解的下界以減少計(jì)算量，在這個(gè)定界的過程中，可行解的上下界范圍不斷縮小。從而避免確定性所搜算法遍歷枚舉（exhaustive enumeration）計(jì)算量過大的缺點(diǎn)，在處理小型問題時(shí)截止確定最優(yōu)解；而大型問題時(shí)則如果在線使用能立即給出一個(gè)相對較好的可行解，如果離線使用則仍能找到問題的最優(yōu)解。因而，該方法具有較好的靈活性。然而，盡管這種改進(jìn)的確定性樹搜索算法能在某些問題中取得好的效果，但其廣泛適用性卻可能經(jīng)不住考驗(yàn)。

 

       啟發(fā)式算法（heuristics）在處理這類大型復(fù)雜的組合優(yōu)化問題時(shí)，由于其啟發(fā)式的隨機(jī)特性，并不企圖窮遍整個(gè)搜索空間，而在計(jì)算時(shí)間和解的最優(yōu)性能之間達(dá)成某種妥協(xié)，從而可以再接受的時(shí)間和計(jì)算代價(jià)內(nèi)獲得較好的次有解。Rasmussen，S.J.等人早在2003年就對啟發(fā)式算法和最優(yōu)算法處理大型問題時(shí)的效果進(jìn)行了比較，結(jié)果表明啟發(fā)式算法具有明顯的優(yōu)勢。因而，這種啟發(fā)式的隨機(jī)特性使得它們在處理大型復(fù)雜問題時(shí)具有天然的優(yōu)勢，今年來已經(jīng)有大量的研究使用了這類算法。

 

       GA作為一種典型的啟發(fā)式算法，被研究人員廣泛的用于多UAV協(xié)同任務(wù)規(guī)劃問題研究中心。Shinma，T.等人把任務(wù)規(guī)劃問題歸納成CMTAP模型之后，將該問題的解編碼成矩陣的形式：以矩陣的列作為染色體的基因（gene），表示將某架UAV指派去對某個(gè)目標(biāo)（target）上執(zhí)行某項(xiàng)任務(wù)（task）；以矩陣為染色體（chromosome），表示CMTAP的一個(gè)可能解。通過對自然選擇的過程的模型，首先構(gòu)建一個(gè)初始化種群，然后通過雜交、變異、選擇等過程，對染色體種群迭代演進(jìn)，最終獲得一個(gè)較好的可行解。盡管該解可能不是最優(yōu)解，但能在可接受的時(shí)間內(nèi)獲得一個(gè)次優(yōu)解，怎么都要比長時(shí)間等待計(jì)算最優(yōu)解的結(jié)果來的好。隨后Karaman，S.等人使用進(jìn)程代數(shù)（process algebra）改進(jìn)了GA的染色體編碼和雜交、變異等遺傳算子，從而進(jìn)一步提高了GA再處理大中小型問題時(shí)的適用性。

 

       PSO作為另一種啟發(fā)式算法，有著與GA不同的演化策略，它模仿鳥群捕食行為，將可能解視作一個(gè)粒子（particle），被賦予一個(gè)速率在解空間中運(yùn)動(dòng)，根據(jù)其自身歷史最佳位置和粒子群（particle swarm）整體的歷史最佳位置，調(diào)整其運(yùn)動(dòng)速率，從而達(dá)到在解空間中尋優(yōu)的目的。這個(gè)算法與GA相比，不需要構(gòu)建大量個(gè)體組成的種群，概念簡單，實(shí)現(xiàn)容易。

 

       集中式控制方法經(jīng)過多年的發(fā)展已經(jīng)較為成熟，其全局特性較好，在處理強(qiáng)復(fù)雜耦合問題時(shí)，可以通觀全局，獲得較好的可行解，具有較大的優(yōu)勢。但其實(shí)時(shí)性、魯棒性和容錯(cuò)性等方面的不足導(dǎo)致了它在動(dòng)態(tài)、不確定性和實(shí)時(shí)性要求較高的應(yīng)用中效果不佳。此時(shí)，需要尋求別的解決方法。

 

       （2）分布式任務(wù)規(guī)劃方法

 

       很多是基于市場機(jī)制的合同網(wǎng)絡(luò)協(xié)議。Smith，R.G.在1980年首次提出將合同網(wǎng)協(xié)議用于分布式問題求解。該方法的基本思想是將任務(wù)分配過程視為一個(gè)市場交易過程，通過“拍賣-競標(biāo)-中標(biāo)”（auction-bid-award）這個(gè)市場競拍機(jī)制實(shí)現(xiàn)分布式系統(tǒng)內(nèi)部工作任務(wù)的指派和調(diào)整。當(dāng)一個(gè)系統(tǒng)成員產(chǎn)生新任務(wù)時(shí)，如發(fā)現(xiàn)新目標(biāo)，可以向系統(tǒng)中其他成員發(fā)布市場拍賣合約；其他成員則對該合約進(jìn)行評估，如果可行則向拍賣者回復(fù)自己執(zhí)行該合約的代價(jià)；合約拍賣者收到競標(biāo)者的價(jià)碼后，進(jìn)行評估，選擇合適的執(zhí)行者，進(jìn)行任務(wù)指派。這樣，一個(gè)基本的市場交易活動(dòng)即大致完成。其原理簡單直觀，易于實(shí)現(xiàn)，且執(zhí)行效率高，已在包括多個(gè)UAV協(xié)同決策與控制在內(nèi)的多個(gè)領(lǐng)域被廣泛研究和應(yīng)用。

       在合同網(wǎng)協(xié)議的基礎(chǔ)上，研究人員進(jìn)一步發(fā)展處更多的分布式方法。由于合同網(wǎng)只給出了協(xié)商的框架和協(xié)議，卻反形式化的模型。有研究人員將一種描述離散事件動(dòng)態(tài)系統(tǒng)的圖形化工具——Petri引入到合同網(wǎng)的建模與分析中，使合同網(wǎng)協(xié)議更加的嚴(yán)格化，從而實(shí)現(xiàn)更好的系統(tǒng)協(xié)商效果。

       分布式方法在近些年的發(fā)展中，越來越受到關(guān)注，已經(jīng)有大量的方法被提出和應(yīng)用，如協(xié)商一致理論、對策論、信息素、多智能體系統(tǒng)等等。這類方法由于其對動(dòng)態(tài)不確定性問題的適用性發(fā)展迅速，目前正處于火熱的研究中。

 

       國內(nèi)研究現(xiàn)狀

 

       今年來國內(nèi)越來越多的研究人員參與到多無人機(jī)協(xié)同規(guī)劃問題的研究中。如葉媛媛④詳細(xì)分析了任務(wù)規(guī)劃問題的理論和特性，以多目標(biāo)優(yōu)化理論為基礎(chǔ)，建立多無人機(jī)協(xié)同任務(wù)規(guī)劃的多目標(biāo)證書規(guī)劃模型，并對其進(jìn)行求解；龍濤⑤提出一種有限中心的分布式控制體系，在合同網(wǎng)協(xié)議基礎(chǔ)上提出多種類型合同和協(xié)商機(jī)制的分布式體系進(jìn)行在線實(shí)時(shí)的任務(wù)重分配；柳林⑥在對分布式多機(jī)器人系統(tǒng)的研究中，總結(jié)了合同網(wǎng)拍賣機(jī)制的理論基礎(chǔ)，基于合同網(wǎng)機(jī)制提出NeA-MRTA和NeA-MRTA算法進(jìn)行簡單任務(wù)動(dòng)態(tài)分布式分配，針對復(fù)雜任務(wù)的動(dòng)態(tài)分布式分配問題，則基于NeA-MRTA提出一種CA-MRTA算法進(jìn)行處理，取得了比較好的效果。

 

       具有里程碑意義的是，2013年，國內(nèi)在多無人機(jī)協(xié)同決策與控制領(lǐng)域處于領(lǐng)先地位的國防科技大學(xué)沈林成教授團(tuán)隊(duì)歸納總結(jié)最新研究成果，出版了一本專著《多無人機(jī)自主協(xié)同控制理論與方法》⑦。這本專著分析總結(jié)了多無人機(jī)系統(tǒng)的理論和技術(shù)發(fā)展脈絡(luò)，對包含多無人機(jī)協(xié)同任務(wù)分配、協(xié)同軌跡規(guī)劃、協(xié)同目標(biāo)狀態(tài)估計(jì)、編隊(duì)協(xié)同控制、多機(jī)協(xié)同自組織等在內(nèi)的多個(gè)協(xié)同控制課題都進(jìn)行了歸納與研究，提出多個(gè)方法解決對應(yīng)的協(xié)同問題，并給出典型應(yīng)用下多機(jī)協(xié)同控制問題的理論分析和方法描述。這本專著對國內(nèi)的研究人員有很高的參考和指導(dǎo)價(jià)值。

 

       注④ ：葉媛媛.多UCAV協(xié)同任務(wù)規(guī)劃方法研究。長沙：國防科學(xué)技術(shù)大學(xué)，2005.

       注⑤ ：龍濤.多UCAV協(xié)同任務(wù)控制中分布式任務(wù)分配與任務(wù)協(xié)調(diào)技術(shù)研究。長沙：國防科學(xué)技術(shù)大學(xué)，2006.

       注⑥ ：柳林.多機(jī)器人系統(tǒng)任務(wù)分配及編隊(duì)控制研究。國防科學(xué)技術(shù)大學(xué)，2006.

       注⑦ ：沈林成，牛鐵峰，朱華勇。多無人機(jī)自主協(xié)同控制理論與方法。北京：國防工業(yè)主板社。2013.

       研究現(xiàn)狀分析。綜合國內(nèi)外文獻(xiàn)，大部分研究對基于多任務(wù)時(shí)序優(yōu)先級約束的多無人機(jī)協(xié)同任務(wù)規(guī)劃問題不夠深入。該問題主要受如下因素影響：

       （1） 多無人機(jī)系統(tǒng)的異構(gòu)性，即機(jī)群由多種具有不同性能的無人機(jī)組成；

       （2） 無人機(jī)機(jī)載資源（如彈藥）的有限性，即無人機(jī)群僅懈怠了有限的資源執(zhí)行任務(wù)；

       （3） 多任務(wù)間的時(shí)序優(yōu)先級約束，如對地面目標(biāo)的確認(rèn)/攻擊/毀傷評估一體化任務(wù)中，必須對目標(biāo)確認(rèn)之后才能發(fā)起攻擊，而毀傷評估則顯然必須在攻擊完成之后才能進(jìn)行，這類時(shí)序約束帶來的問題，如死鎖問題，將會嚴(yán)重影響對多無人機(jī)協(xié)同的協(xié)同控制；