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

 

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

 

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

 

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

 

       集中式控制方法經過多年的發展已經較為成熟，其全局特性較好，在處理強復雜耦合問題時，可以通觀全局，獲得較好的可行解，具有較大的優勢。但其實時性、魯棒性和容錯性等方面的不足導致了它在動態、不確定性和實時性要求較高的應用中效果不佳。此時，需要尋求別的解決方法。

 

       （2）分布式任務規劃方法

 

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

       在合同網協議的基礎上，研究人員進一步發展處更多的分布式方法。由于合同網只給出了協商的框架和協議，卻反形式化的模型。有研究人員將一種描述離散事件動態系統的圖形化工具——Petri引入到合同網的建模與分析中，使合同網協議更加的嚴格化，從而實現更好的系統協商效果。

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

 

       國內研究現狀

 

       今年來國內越來越多的研究人員參與到多無人機協同規劃問題的研究中。如葉媛媛④詳細分析了任務規劃問題的理論和特性，以多目標優化理論為基礎，建立多無人機協同任務規劃的多目標證書規劃模型，并對其進行求解；龍濤⑤提出一種有限中心的分布式控制體系，在合同網協議基礎上提出多種類型合同和協商機制的分布式體系進行在線實時的任務重分配；柳林⑥在對分布式多機器人系統的研究中，總結了合同網拍賣機制的理論基礎，基于合同網機制提出NeA-MRTA和NeA-MRTA算法進行簡單任務動態分布式分配，針對復雜任務的動態分布式分配問題，則基于NeA-MRTA提出一種CA-MRTA算法進行處理，取得了比較好的效果。

 

       具有里程碑意義的是，2013年，國內在多無人機協同決策與控制領域處于領先地位的國防科技大學沈林成教授團隊歸納總結最新研究成果，出版了一本專著《多無人機自主協同控制理論與方法》⑦。這本專著分析總結了多無人機系統的理論和技術發展脈絡，對包含多無人機協同任務分配、協同軌跡規劃、協同目標狀態估計、編隊協同控制、多機協同自組織等在內的多個協同控制課題都進行了歸納與研究，提出多個方法解決對應的協同問題，并給出典型應用下多機協同控制問題的理論分析和方法描述。這本專著對國內的研究人員有很高的參考和指導價值。

 

       注④ ：葉媛媛.多UCAV協同任務規劃方法研究。長沙：國防科學技術大學，2005.

       注⑤ ：龍濤.多UCAV協同任務控制中分布式任務分配與任務協調技術研究。長沙：國防科學技術大學，2006.

       注⑥ ：柳林.多機器人系統任務分配及編隊控制研究。國防科學技術大學，2006.

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

       研究現狀分析。綜合國內外文獻，大部分研究對基于多任務時序優先級約束的多無人機協同任務規劃問題不夠深入。該問題主要受如下因素影響：

       （1） 多無人機系統的異構性，即機群由多種具有不同性能的無人機組成；

       （2） 無人機機載資源（如彈藥）的有限性，即無人機群僅懈怠了有限的資源執行任務；

       （3） 多任務間的時序優先級約束，如對地面目標的確認/攻擊/毀傷評估一體化任務中，必須對目標確認之后才能發起攻擊，而毀傷評估則顯然必須在攻擊完成之后才能進行，這類時序約束帶來的問題，如死鎖問題，將會嚴重影響對多無人機協同的協同控制；