三維多無人機系統協同任務規劃關鍵問題綜述

趙明　李濤　蘇小紅　趙玲玲　張彥航

摘 要：隨著無人機技術的迅猛發展，人們對無人機技術的需求越來越廣泛，已從單機簡單任務向多機協同執行多個復雜任務、且自主協調、無人干預、群體合作的方向發展。而多無人機系統的協同任務規劃技術，是無人機自主導航飛行和無人機之間自主協調配合共同完成任務的關鍵。這一任務規劃決定了無人機各類資源的協調和執行目標的合理分配，無人機協調可飛飛行航跡的規劃，以及在飛行過程中，取代人為干預，實時協調化解多機飛行時可能產生的各種沖突和問題。因此，對多無人機系統協同任務規劃的關鍵問題，如目標分配、航跡規劃、在線重規劃等深入研究，是提高多機系統執行任務能力的重要環節。近年來，該領域的研究日益廣泛，但還存在諸多問題需要解決，尤其迫切需要研究在三維戰場環境下的多機協同任務規劃方法。

關鍵詞：多無人機系統；任務規劃；三維戰場；多機協同

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-2163（2015）06-

Abstract： With the rapid development of UAV technology， peoples demand for the UAV is becoming more and more extensive. The trend of UAV research has been developed from a single UAV and simple task to the multiple UAVs performing complex tasks with autonomous coordination， no intervention， and group cooperation. The cooperative task planning of multi-UAV system is not only the key to the autonomous navigation of UAVs， but also the focus on coordination and cooperation with the UAVs to complete tasks. It determines the optimal tasks of UAV and the reasonable allocation of resources， the path planning of UAVs cooperative flight， and replacing human intervention to resolve various conflicts and problems in real time. So， the key issues of cooperative task planning for UAVs， such as target assignment， path planning， and on-line re-planning， are all important parts of improving the ability of UAVs system. In spite of the wide range of research in this field recently， there are still many problems need to be solved. In particular， it is urgent to research on multi-UAVs cooperative task planning methods in three dimensional battlefield environments.

Keywords： Multi-UAVs System； Task Planning； target assignment； Path Planning； Re-planning.

0引 言

與有飛行員駕駛的載人飛行器相比，無人機（Unmanned Aerial Vehicle， UAV）具有眾多明顯以及潛在的特點優勢，如自主飛行的無人機在燃油充足的情況下不需要休息，可以組織更長時間的空中巡航。無人機不需要提供飛行員必須的生命支持系統，這不僅減少了飛行成本，還為部署傳感器和其他設備提供了更多空間[1]。此外，無人機不必考慮機載人員的生理限制，因此可以支持超越極限的更靈活的自由度完成各種復雜飛行任務，并可探索人類無法接近的危險區域[2]。現代戰爭中，無人機的廣泛使用，極大程度上降低了人員傷亡的代價，提高了作戰系統平臺的安全性和自適應性。因此“無人化”勢將逐漸改變現代戰爭的面貌，成為未來信息化戰爭的新方向。在民用和科研領域，無人機的作用也日益凸顯，成為輔助人類探索自然、增進社會安全、參與救災搶險等重大任務必不可少的技術支撐[3]。

近年來隨著無人技術的廣泛推廣，無人系統在各領域獲得普遍關注，除了無人飛行器系統（Unmanned Aircraft System， UAS）被概念化以外，無人地面系統（Unmanned Ground System， UGS）和無人海洋系統（Unmanned Maritime System， UMS）也相繼成為矚目熱點。可以預期的是，無人技術發展的未來趨勢，必然是陸地、天空、海洋以及外太空多種無人系統一體化的綜合應用[2]。無人系統技術的全面推廣，將以更為縱深立體的方式影響未來高新科技格局。圖1顯示了UAS預期的自主級別發展規劃[4]，從其中可以看出，分布式控制、群協同和在線重規劃等自主需求都作為預期的目標要加以研究實現，而完全群體自主的UAVs系統則是未來發展的最終目標。

在空間立體化復雜戰場態勢下，參與作戰的飛行器種類不斷增加，性能迅速提高，形成了技術密集、結構復雜的特征。因此單架無人機有限的飛行能力和載彈負荷將很難獨自完成復雜戰場態勢中的信息收集、區域監視、多目標攻擊等顯示高端任務。而多無人機協同作戰則可以處理各種復雜的問題，提高任務完成的效率和成功率，具有比單機更靈活、執行任務時間更短、信息傳遞更迅速等優點。同時，多無人機系統中部分無人機的毀傷和失效也不致影響完成任務的最終效果[5]。因此多機系統已經逐漸取代單機，成為執行各種復雜任務的開放目標指向中的重點關鍵技術。

但是，多機協同作戰增加了問題求解的規模，問題的復雜程度隨無人機和任務數量的增加呈幾何級數增長。在協同過程中，不但要處理無人機自身的約束條件，更要考慮相互協同的約束；此外，還要避免多機間沖突導致的系統退化、共享資源競爭等關鍵問題的影響。在控制方面，傳統的基于中央控制的方法越來越難行，尤其是多架次無人機協同作戰，需要更多的通信帶寬、更完備的信息共享和更高的自主決策能力支持；多無人機系統面臨著復雜的挑戰。因此，近年來多無人機協同任務規劃系統成為無人機研究領域的新熱點，贏得了來自多方的重視和關注。

多無人機協同任務規劃系統從功能和實施階段上，可以分為協同目標分配、協同航跡規劃和協同任務執行三個部分。其中多機協同目標分配 （Multi-UAVs Cooperative Multi-Targets Assignment， MUCMTA）是基于一定的環境知識和任務需求，為多機系統中的每架UAV分配一個或一組有序目標，以便在完成最大可能數量任務的同時保證執行目標總代價最小和總效益最大的問題，該問題是一個多模型、多約束、計算難度大、復雜度呈幾何級數增長的最優化NP難題；多機協同航跡規劃（Multi-UAVs Cooperative Path Planning）是在給定已知、部分已知或未知信息的環境中，規劃出從起始點到達目標點，可以繞過威脅區和障礙物、安全可靠無碰撞，且同時滿足各種約束條件和協同關系的多條可行飛行航跡，該問題是一個多目標優化問題；在任務執行階段，環境的動態改變可能導致全局規劃結果的部分失效，因此需要對環境的改變做出響應，對失效的航跡段進行在線協同重規劃（Online Cooperative Path Planning），以保證任務執行過程中UAVs飛行的安全可靠、且高效。

1國內外研究現狀及分析

1.1無人機和無人機任務規劃系統概況

近年來，無人機的研究和應用在多數發達國家呈幾何級數急增，這些國家投入了大量的人力和財力組織研發，涌現出一批性能優良的新型無人機系統[6]，如Global Hawk、WASP 3、Raven、Scan Eagle、MQ-18、RQ-4 Blk、X47-B 和 RQ-170、以及我國自主產權的“翼龍（GJ-1）”，“海鷹（WJ-600）”等。隨著無人機性能不斷深入發展，針對無人機系統性的研究也日趨普遍具體。近年來，國際民用航空組織（ICAO）、美國聯邦航空管理局（FAA）、美國國防部（DoD）、歐洲航空安全局（EASA）一致通過如下決議：采用Unmanned Aircraft System（UAS）取代即將過時的術語“UAV”[2]，將系統性的研究提到了新的高度。

針對UAS概念的提出和發展，在任務需求復雜度不斷提高的情況下，多機協同任務規劃系統的研究也日益廣泛，并逐漸成為未來無人機應用的主要研究方向。例如，美國國防部建立了無人機聯合開發局（JPO），致力于從大尺度多機系統轉型為研發小型、低空、低成本、一次性的多無人機群系統。2013年，美國國防部在無人系統未來25年發展規劃中，提出聯合地面、空中和海上的多種無人機協同工作將成為未來無人機發展的挑戰[2]。此外，歐盟很早就進行了異構多無人機實時協同和控制（COMETS）項目的研究。近年來，多機系統不斷向著群體人工智能和分布式網絡控制技術方向發展，例如，歐盟聯合開發的Neuron作戰無人機單元陣列項目、美國海軍研究所的LOCUST項目（低代價無人機群集）都是利用群智能的典范。

我國無人機領域的研究起步比較晚，90年代以來，西北工業大學、北京航天航空大學和南京航天航空大學、清華大學、華中理工大學、哈爾濱工業大學等高校率先成立了無人機和無人機任務規劃系統的專門研究機構，并已研發出幾十個型號的無人機和多種無人機仿真平臺。2000年以來，中航工業集團、航天科工集團、航天科技集團下屬的一些院所也開始了軍事或民用無人機的研制，雖然這些研發距離大批量生成和產業化發展還有一定的距離，但國內無人機市場化趨勢已成為現實必然[7]。與此同時，與無人機體系緊密配套的無人機任務規劃系統的研究，也已從初期研究的單平臺航跡規劃問題發展到包括異構多平臺、多任務的規劃問題。目前主要有國防科技大學多UAV任務協調技術的研究[8]，北京航空航天大學基于DTC的無人機任務規劃研究[9]，華中科技大學的協同航跡規劃研究[10]等，均獲得了豐碩的研究成果。此外，尤其值得一提的是，2015年紀念抗戰70周年閱兵式上，我國首次以無人機受閱方隊的形式，向全世界展示了最新型的偵察打擊一體無人機，從而說明我國無人機在軍事領域已經進入了嶄新的高度和飛速發展時期。

多無人機系統任務規劃由協同目標分配、航跡規劃和任務執行三個部分組成。下面詳細介紹相關方面常用的技術手段和研究方法。

1.2多機協同的目標分配方法

解決多機協同目標分配問題，常采用集中式或分布式目標分配系統。具體地，集中式系統可以統一控制，但是擴展性較差；分布式系統計算靈活，但是對通信要求較高。目前常用的方法有：數學規劃法、協商法和智能算法等。針對這幾類常用方法，給出如下的論述與分析。

2.2.1 基于數學規劃法的協同目標分配

數學規劃（Mathematical Programming）法是集中式解決分配問題的經典方法，如匈牙利算法[11]在處理分配問題時具有較好的效果，但該方法要求已知所有信息、其容錯能力也較差，針對模型不一致的多機多目標分配的普適性則欠佳；此外，目標分配問題是一個典型的整數規劃問題，可利用整數規劃的方法進行求解。Jonathan P.How等人基于混合整數線性規劃（MILP）研究實現的協同任務分配[12]。此類方法簡單靈活，求解速度較快，但是對復雜問題的抽象過于簡單，環境表示不清晰，僅適合簡單環境的問題求解；動態規劃（Dynamic Programming）也是求解協同目標分配問題常用的一種數學規劃方法[13]，該方法把多過程轉化為一系列單階段問題，雖然結構簡單，但卻過度簡化了無人機之間的關系，從而降低了結果的可信度。

1.2.2 基于協商法的協同目標分配

分布式目標分配系統計算靈活，可以將協同和分配問題分布到各個節點上進行高速處理，適合解決大規模的目標分配問題。目前最常見的是基于合同網的協商方法，合同網將目標分配看作一個市場交易過程，通過“招標-投標-中標”的拍賣機制，實現任務的委派遷移[14]。UAV將執行任務過程中自己無法處理的任務對外拍賣，由其他UAV進行投標，系統通過協商將任務遷移給能夠以最低代價執行的UAV。基于合同網的方法原理簡單、易于實現，效率較高。但是對協同和約束的處理能力較差，在追求整體最優的目標下，通常會與個體利益沖突。尤其忽略了三維真實環境的動態特征，致使其實現效果受到影響。

1.2.3基于智能算法的協同目標分配

利用人工智能的方法處理目標分配問題，具有靈活、自適應、啟發性、易于實現和計算復雜度低等優點，靈活的編碼結構尤其適合三維問題的建模和求解。常見的方法有：進化規劃、粒子群算法和蟻群算法等。

多目標遺傳規劃方法將原有的單目標優化進行了擴展，通過在協同目標分配中對多個相互沖突的目標實施優化，向適應度最優的個體方向實行搜索，可以有效收斂到最優的目標分配結果[15]。但是遺傳規劃存在迭代周期長、容易陷入局部最優解的不足，因此陸續出現了更多改進方法，如采用差分進化算法[16]、免疫進化算法[17]等。

粒子群算法是一種并行群進化技術，粒子在演化學習過程中，不但受整體社會精英的影響，還將受到其近鄰關系的影響，因此粒子飛行的方向是社會和個體經驗的集合，該算法反映了群體智能決策特有的簡單和高效性[18]。與進化算法相比，粒子群算法摒棄了交叉和變異操作，具有比遺傳算法更好的效率。但該算法的精細搜索能力不強，尤其是處理離散問題時易陷入局部最優，全局搜索能力差。

蟻群算法是一種利用隱式通信而獲得信息共享，在未知環境中搜索目標和解的智能自組織方法。該方法通過傳遞信息素共享環境信息，引導搜索向信息密度高的方向遞次進化[19]。該算法通過無智能或簡單智能的聚集協同表現出全局智能行為特性，具有計算簡單、魯棒性好的優點。但是蟻群系統收斂速度很慢，易于出現停滯現象。

1.3多機協同的航跡規劃方法

多機協同航跡規劃是多機任務規劃系統中的另一主要問題。已有研究方法有：從單機航跡規劃方法發展來的多機規劃方法；適合群體計算的群智能算法；以及基于路徑優化的規劃方法等。在此，對各類研究方法可分別作如下具體詳述。

1.3.1 從單航跡規劃發展來的多航跡規劃

啟發式A*算法是一種靜態路網中求解最短路徑卓具成效的啟發式方法。A*算法和稀疏A*（SAS）算法[20]用來解決二維和三維環境下的單航跡規劃問題，可以很好地處理各種復雜的約束條件。A*算法存在的問題是：對環境信息的依賴程度高，計算量大，并行能力差，因此不適合大規模三維多機協同航跡規劃。

常用的概率圖算法包括通視圖法、輪廓圖法、隨機路線圖法和Voronoi圖法等[10]。其中的Voronoi圖是由一組連接兩鄰點直線的垂直平分線組成的連續多邊形網格圖，可將環境中的威脅源和障礙物作為Voronoi圖的特征元素，并通過對空間進行分解，就可以表示空間中距離威脅最遠的通路。Voronoi圖具有數量級低、構造時間快、距離威脅和障礙最遠，因而航路最安全等優點[21]。但是由于三維空間沒有確定的特征元素選擇方法，因此很難構建其三維空間的相應表示，且最短路徑也不一定就存在于其中。

人工勢場是一種仿效作用力形成空間力場的規劃方法，具體是將物體的運動看成是排斥力和吸引力相互作用下的結果，其中吸引力不斷將運動物體拉向目標點，而排斥力則努力使運動物體遠離威脅和障礙。算法原理是通過計算勢函數對運動物體進行導航，其規劃結果是沿勢函數下降最快的方向搜索而得的航跡[22]。人工勢場法的優點是規劃速度快、躲避障礙和威脅的能力強等。缺點是存在靜止點。

1.3.2 基于群智能的多航跡協同規劃

與任務分配階段相似，群智能算法也同樣適合求解多機協同規劃問題。這種算法具有規劃速度快、并行性好、易于協同、可以收斂到全局最優等優點。其缺點則在于沒有明確的基因表示定義、求得的最優解不唯一，且存在沖突和違背約束等問題。

當前，大量的航跡規劃研究都圍繞著改進的進化算法來實現展開，如平行進化算法[23]、量子遺傳算法[24]等，這些方法證明了利用物種進化機制和并行尋優方法，可以較快搜索到解空間的最優位置。此外，人們更進一步地認識到，進化算法還特別適合處理三維空間中的規劃問題，因此，該方法在實際航跡規劃問題的求解上將有著獨特優勢。Roberge等則引領性地將平行進化算法與粒子群算法進行了比較[25]，強調了兩者的區別和各自的優點，并將其混合方法應用于實際的航跡協同規劃。此外，還有利用免疫應答、神經元網絡[26]等多種智能航跡規劃的方法。由此可見，基于群體智能和仿生學的航跡協同規劃算法，必將在無人機發展的歷程中收獲更多優質豐富的科研成果。

1.3.3 基于路徑優化的多機協同航跡規劃

無人機特殊的飛行機動特性，要求規劃時必須考慮結果的可飛性，因此規劃時還需要對航跡段進行平滑，以獲得一條平滑可飛的飛行航線。常用的曲線平滑方法有二次樣條曲線、B樣條曲線、Bezier曲線等。Jung D采用B樣條控制點作為遺傳基因，通過遺傳算法優化B樣條曲線，規劃平滑可飛的飛行航跡[27]。該方法的缺點是分離了無人機性能和規劃之間的具體聯系。Antonlos則指出將規劃和平滑分開的不合理性，并提出直接利用曲線對UAV的航跡進行規劃的方法，基于無人機飛行最大轉角條件下，利用Dubins曲線進行多機協同的航跡規劃[28]。該方法的缺點是規劃的曲線不是最優航跡，且多航跡協同規劃時，優化規則也過于簡單。