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

 

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

 

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

 

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

 

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

 

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

 

       很多是基于市場(chǎng)機(jī)制的合同網(wǎng)絡(luò)協(xié)議。Smith，R.G.在1980年首次提出將合同網(wǎng)協(xié)議用于分布式問(wèn)題求解。該方法的基本思想是將任務(wù)分配過(guò)程視為一個(gè)市場(chǎng)交易過(guò)程，通過(guò)“拍賣(mài)-競(jìng)標(biāo)-中標(biāo)”（auction-bid-award）這個(gè)市場(chǎng)競(jìng)拍機(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ā)布市場(chǎng)拍賣(mài)合約；其他成員則對(duì)該合約進(jìn)行評(píng)估，如果可行則向拍賣(mài)者回復(fù)自己執(zhí)行該合約的代價(jià)；合約拍賣(mài)者收到競(jìng)標(biāo)者的價(jià)碼后，進(jìn)行評(píng)估，選擇合適的執(zhí)行者，進(jìn)行任務(wù)指派。這樣，一個(gè)基本的市場(chǎng)交易活動(dòng)即大致完成。其原理簡(jiǎn)單直觀，易于實(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ā)展中，越來(lái)越受到關(guān)注，已經(jīng)有大量的方法被提出和應(yīng)用，如協(xié)商一致理論、對(duì)策論、信息素、多智能體系統(tǒng)等等。這類(lèi)方法由于其對(duì)動(dòng)態(tài)不確定性問(wèn)題的適用性發(fā)展迅速，目前正處于火熱的研究中。

 

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

 

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

 

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

 

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

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

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

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

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

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

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

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