飛行控制與仿真   2023-04-11 14:08 發(fā)表于廣東

點(diǎn)擊上方藍(lán)字關(guān)注我們微信公眾號(hào)！

    國(guó)內(nèi)的無(wú)人機(jī)集群在編隊(duì)表演方面已經(jīng)演繹的淋漓盡致，但是在作業(yè)與軍事上還是鮮有研究，而國(guó)外特別是美國(guó)直奔戰(zhàn)場(chǎng)而去，并形成了理論。

無(wú)人機(jī)技術(shù)正處于大力發(fā)展階段，單架無(wú)人機(jī)的系統(tǒng)集成度越來(lái)越高，功能也越來(lái)越強(qiáng)大。然而，面對(duì)日益復(fù)雜的應(yīng)用環(huán)境和多樣化的需求，無(wú)人機(jī)受其自身軟硬件條件的限制，仍有某些局限性：對(duì)單架無(wú)人機(jī)而言，其自身的燃料、重量和尺寸起著重要的限制作用，無(wú)法形成持續(xù)有力的打擊力度；受機(jī)載傳感器以及通信設(shè)備的限制，單架無(wú)人機(jī)也無(wú)法實(shí)現(xiàn)對(duì)任務(wù)區(qū)域的多維度、大范圍覆蓋；在執(zhí)行高風(fēng)險(xiǎn)任務(wù)時(shí)，單架無(wú)人機(jī)可能因?yàn)槭艿焦艋蜃陨砉收隙?，從而?dǎo)致任務(wù)系統(tǒng)容錯(cuò)性不足等等。對(duì)小型無(wú)人機(jī)尤其如此。

為彌補(bǔ)單架無(wú)人機(jī)的局限性，美國(guó)空軍科學(xué)顧問(wèn)委員會(huì)指出，無(wú)人機(jī)應(yīng)當(dāng)以集群的方式協(xié)同工作，而不是單獨(dú)行動(dòng)。在未來(lái)很多應(yīng)用場(chǎng)景中，無(wú)人機(jī)將體現(xiàn)出多機(jī)西戎工作的特點(diǎn)。即由多架相同或不同型號(hào)的UAV組成多無(wú)人機(jī)系統(tǒng)，協(xié)同作業(yè)，共同完成任務(wù)。無(wú)人機(jī)群，由多種型號(hào)的有人或無(wú)人機(jī)組成的混合集群，甚至無(wú)人機(jī)與其他有人或無(wú)人作戰(zhàn)機(jī)器如無(wú)人戰(zhàn)斗車輛組成的混合異構(gòu)群組，必然是未來(lái)戰(zhàn)爭(zhēng)無(wú)人作戰(zhàn)機(jī)器的主要作戰(zhàn)形式。這樣，既能最大地發(fā)揮無(wú)人機(jī)的優(yōu)勢(shì)，又能避免由于單架無(wú)人機(jī)執(zhí)行任務(wù)效果不佳或失敗造成的不良后果，提高任務(wù)執(zhí)行效率，拓展新的任務(wù)執(zhí)行方式，從而達(dá)到提高系統(tǒng)可靠性、改善任務(wù)執(zhí)行效果的目的。

多UAV協(xié)同工作的優(yōu)勢(shì)主要來(lái)源于信息融合和資源互補(bǔ)兩個(gè)方面。在多機(jī)并行執(zhí)行任務(wù)的過(guò)程中，每架無(wú)人機(jī)收集到的信息都是其各自位置上的局部信息，無(wú)人機(jī)群眾所有成員的信息又組合成一個(gè)信息模型，提供給鞠策系統(tǒng)進(jìn)行多機(jī)系統(tǒng)內(nèi)的任務(wù)分工和調(diào)度，以提高任務(wù)的執(zhí)行效率；且當(dāng)某個(gè)成員失效時(shí)，能及時(shí)更新系統(tǒng)信息，動(dòng)態(tài)調(diào)整系統(tǒng)成員間的執(zhí)行效果，從而提高系統(tǒng)的可靠性和容錯(cuò)性；受單機(jī)能力和任務(wù)要求的限制，需要多架無(wú)人機(jī)共同完成某項(xiàng)任務(wù)，或者多機(jī)相互配合，以滿足任務(wù)的時(shí)間、空間與指標(biāo)優(yōu)化等要求，達(dá)到資源和功能互補(bǔ)的效果，如對(duì)同一個(gè)目標(biāo)依序執(zhí)行確認(rèn)、攻擊和毀傷評(píng)估任務(wù)，對(duì)同一個(gè)執(zhí)行同時(shí)性的多角度跟蹤任務(wù)等。

要指派多架UAV協(xié)同執(zhí)行一項(xiàng)任務(wù)，提高任務(wù)的效能，就離不開(kāi)合理高效的協(xié)同控制手段，必須對(duì)多機(jī)系統(tǒng)進(jìn)行合理的協(xié)同任務(wù)規(guī)劃。它是對(duì)多無(wú)人機(jī)UAV協(xié)同執(zhí)行任務(wù)進(jìn)行研究的核心，設(shè)計(jì)控制理論、運(yùn)籌學(xué)、決策理論、圖論、信息論、系統(tǒng)論、計(jì)算機(jī)科學(xué)、榮恭智能、通信理論等多個(gè)學(xué)科領(lǐng)域。

在實(shí)際任務(wù)的執(zhí)行中、受UAV、任務(wù)要求和環(huán)境因素等的影響與制約，對(duì)多UAV進(jìn)行協(xié)同控制是一個(gè)極其復(fù)雜、極具挑戰(zhàn)性的過(guò)程，其復(fù)雜性主要體現(xiàn)在：

（1）任務(wù)環(huán)境的復(fù)雜性：復(fù)雜的對(duì)抗性的動(dòng)態(tài)環(huán)境，可能包含著多種既有的和突發(fā)的威脅、障礙、極端天氣等，而且UAV與系統(tǒng)可能無(wú)法獲知或無(wú)法及時(shí)獲知環(huán)境的全局信息及其變化；

（2）多無(wú)人機(jī)系統(tǒng)成員間的差異：UAV數(shù)量以及不同UAV間的運(yùn)動(dòng)學(xué)動(dòng)力學(xué)特性、功能差異、信息收集與處理和通信能力的差異，而且無(wú)人機(jī)可能在任務(wù)執(zhí)行過(guò)程中失效等；

（3）任務(wù)需求的復(fù)雜性：不同的任務(wù)具有不同的要求，其在作戰(zhàn)目標(biāo)、時(shí)序約束、時(shí)間感性約束、任務(wù)間耦合約束、任務(wù)指標(biāo)等各個(gè)方面均可能存在著差異，而且作戰(zhàn)目標(biāo)還可能存在著不確定性，如移動(dòng)目標(biāo)、目標(biāo)參數(shù)不確定等問(wèn)題；

（4）計(jì)算復(fù)雜性：在進(jìn)行協(xié)同任務(wù)規(guī)劃問(wèn)題研究時(shí)，不可避免的會(huì)碰到一個(gè)NP難題，即隨著問(wèn)題規(guī)模的線性增長(zhǎng)，如無(wú)人機(jī)數(shù)量、目標(biāo)數(shù)量等，問(wèn)題的解空間呈指數(shù)級(jí)的爆炸式擴(kuò)張，當(dāng)問(wèn)題規(guī)模增大時(shí)，從這個(gè)龐大的解空間中找到最優(yōu)解需要耗費(fèi)大量的計(jì)算，非常困難。當(dāng)任務(wù)的實(shí)時(shí)性要求較高時(shí)，這個(gè)矛盾會(huì)更突出，甚至?xí)苯右阅氵x哪個(gè)協(xié)同任務(wù)的執(zhí)行效果；

（5）通信約束的復(fù)雜性：任務(wù)環(huán)境的復(fù)雜多變就必然會(huì)對(duì)UAV機(jī)群的通信網(wǎng)絡(luò)造成影響，如通信拓?fù)浣Y(jié)構(gòu)變化、寬帶受限、通信干擾、通信延時(shí)等，甚至可能會(huì)出現(xiàn)虛假通信等問(wèn)題，在考慮到UAV本身的通信設(shè)備性能限制，如通信距離和寬帶等，以及某些任務(wù)可能會(huì)要求通信盡可能的少，這極大的增加了多機(jī)協(xié)同問(wèn)題的復(fù)雜程度。

在上述復(fù)雜性的共同作用下，多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃問(wèn)題就變成了一個(gè)極其復(fù)雜的問(wèn)題，對(duì)該問(wèn)題進(jìn)行建模與求解的難度也大大增加。作為無(wú)人機(jī)技術(shù)發(fā)展的一個(gè)重要趨勢(shì)，多UAV協(xié)同控制方面的研究方向收到了美國(guó)軍方的極大重視，已經(jīng)被美國(guó)空軍研究局列為六大基礎(chǔ)研究課題①之一，也成為學(xué)術(shù)界的研究熱點(diǎn)之一。

注① ：美國(guó)空軍研究局六大基礎(chǔ)研究課題：1）靈感來(lái)自生物的概念；2）協(xié)同控制；3）等離子體動(dòng)力學(xué)；4）太空微型科學(xué)；5）量子計(jì)算；6）用于可支付得起的新型系統(tǒng)的材料工程學(xué)。

國(guó)外研究現(xiàn)狀

為探索多無(wú)人機(jī)協(xié)同工作的理論與實(shí)現(xiàn)機(jī)理，國(guó)外已經(jīng)開(kāi)展了大量相關(guān)的研究項(xiàng)目。其中具有代表性的是美國(guó)國(guó)防部高級(jí)研究計(jì)劃局（DARPA）牽頭的自治編隊(duì)混合主動(dòng)控制項(xiàng)目（Mixed InitiativeControl of Automata-teams，MICA②）、廣域搜索彈藥項(xiàng)目（Wide Area Search Munitions，WASM）和歐洲信息社會(huì)技術(shù)計(jì)劃（Information Society Technologies，IST）資助的異構(gòu)無(wú)人能及群實(shí)時(shí)協(xié)同與控制項(xiàng)目（Real-time Coordination and Control of Multiple Heterogeneous UAVs，COMETS③）等。

注② ：ＭＩＣＡ 項(xiàng)目的目標(biāo)是，在減少操作員人為干預(yù)的前提下提升無(wú)人機(jī)的自主與協(xié)同控制能力，涉及的研究?jī)?nèi)容包括無(wú)人機(jī)自主協(xié)同作戰(zhàn)的分層控制結(jié)構(gòu)、多無(wú)人機(jī)自主編隊(duì)控制方法和無(wú)人機(jī)協(xié)同作戰(zhàn)的建模與仿真技術(shù)等，參與研究的機(jī)構(gòu)包括加州大學(xué)伯克利分校、麻省理工學(xué)院（ＭＩＴ ） 以及霍尼韋爾公司（Ｈｏｎｅｙｗｅｌｌ）等。

注③ ：歐洲COMETS項(xiàng)目是一個(gè)多國(guó)合作的民用研究項(xiàng)目，其研究對(duì)象是一個(gè)由包括無(wú)人直升機(jī)和無(wú)人飛艇在內(nèi)的多平臺(tái)異構(gòu)無(wú)人機(jī)群組成的協(xié)同探測(cè)與監(jiān)視系統(tǒng)，研究目標(biāo)是為該異構(gòu)多UAV設(shè)計(jì)和實(shí)現(xiàn)分布式實(shí)時(shí)控制系統(tǒng)，集成分布式感知與實(shí)時(shí)圖像處理等技術(shù)，并在森林火災(zāi)監(jiān)視任務(wù)中對(duì)系統(tǒng)的關(guān)鍵技術(shù)進(jìn)行演示驗(yàn)證。該項(xiàng)目的相關(guān)結(jié)果已經(jīng)陳列在其官方網(wǎng)站上http://www.comets-uavs.org/），最終成果也已經(jīng)集中出版。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為繞開(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-firstsearch）在已搜索的可行解中不斷降低解的上界，一邊又在決策樹(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）在處理這類大型復(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)有大量的研究使用了這類算法。

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ù)（processalgebra）改進(jìn)了GA的染色體編碼和雜交、變異等遺傳算子，從而進(jìn)一步提高了GA在處理大中小型問(wèn)題時(shí)的適用性。

PSO作為另一種啟發(fā)式算法，有著與GA不同的演化策略，它模仿鳥(niǎo)群捕食行為，將可能解視作一個(gè)粒子（particle），被賦予一個(gè)速率在解空間中運(yùn)動(dòng)，根據(jù)其自身歷史最佳位置和粒子群（particleswarm）整體的歷史最佳位置，調(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ò)“拍賣-競(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)拍賣合約；其他成員則對(duì)該合約進(jìn)行評(píng)估，如果可行則向拍賣者回復(fù)自己執(zhí)行該合約的代價(jià)；合約拍賣者收到競(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)等等。這類方法由于其對(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ǔ)上提出多種類型合同和協(xié)商機(jī)制的分布式體系進(jìn)行在線實(shí)時(shí)的任務(wù)重分配；柳林⑥在對(duì)分布式多機(jī)器人系統(tǒng)的研究中，總結(jié)了合同網(wǎng)拍賣機(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é)最新研究成果，出版了一本專著《多無(wú)人機(jī)自主協(xié)同控制理論與方法》⑦。這本專著分析總結(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)題的理論分析和方法描述。這本專著對(duì)國(guó)內(nèi)的研究人員有很高的參考和指導(dǎo)價(jià)值。

國(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)行，這類時(shí)序約束帶來(lái)的問(wèn)題，如死鎖問(wèn)題，將會(huì)嚴(yán)重影響對(duì)多無(wú)人機(jī)協(xié)同的協(xié)同控制；

（4） 對(duì)多無(wú)人機(jī)系統(tǒng)內(nèi)部成員間的工作負(fù)荷強(qiáng)度關(guān)注 不足，由于協(xié)同任務(wù)執(zhí)行過(guò)程中，可能有的系統(tǒng)成員工作強(qiáng)度大，有的則顯得過(guò)于“清閑”，這時(shí)如果存在一種機(jī)制能使得系統(tǒng)成員間的工作強(qiáng)度相對(duì)的均衡化，那么系統(tǒng)效能將得到一定程度的提升。

注：本文章轉(zhuǎn)載自其它媒體，轉(zhuǎn)載目的在于傳遞更多信息，如有侵權(quán)可聯(lián)系我們進(jìn)行刪除。