多架無(wú)人機(jī)協(xié)同航跡規(guī)劃研究綜述

供稿|侯捷，李博威，念誠(chéng)，周浩，趙越飛 / HOU Jie, LI Bo-wei, NIAN Cheng, ZHOU Hao, ZHAO Yue-fei

內(nèi)容導(dǎo)讀

多架無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)已經(jīng)成為未來(lái)無(wú)人機(jī)發(fā)展的重要趨勢(shì)，多無(wú)人機(jī)協(xié)同航跡規(guī)劃是保障多無(wú)人機(jī)協(xié)同完成任務(wù)的重要手段之一。文章系統(tǒng)梳理了多無(wú)人機(jī)協(xié)同航跡規(guī)劃研究現(xiàn)狀，歸納現(xiàn)有多無(wú)人機(jī)協(xié)同航跡規(guī)劃方法，從搭建航跡規(guī)劃仿真地圖、明確多機(jī)協(xié)同評(píng)價(jià)指標(biāo)和選擇規(guī)劃算法三個(gè)方面闡述多無(wú)人機(jī)協(xié)同航跡規(guī)劃實(shí)現(xiàn)方法，最后對(duì)協(xié)同航跡規(guī)劃技術(shù)的發(fā)展進(jìn)行了展望：提高無(wú)人機(jī)群的自主性、協(xié)同性和規(guī)劃算法性能是多無(wú)人機(jī)協(xié)同航跡規(guī)劃的發(fā)展趨勢(shì)，最終有望實(shí)現(xiàn)無(wú)人機(jī)群在任何情況下都能夠快速自主規(guī)劃最優(yōu)航跡并同時(shí)保持多無(wú)人機(jī)空間和時(shí)間上的協(xié)同。研究高精度的無(wú)人機(jī)航跡規(guī)劃仿真地圖、合理的多機(jī)協(xié)同結(jié)構(gòu)對(duì)提高多無(wú)人機(jī)協(xié)同航跡規(guī)劃技術(shù)也具有較大的實(shí)踐意義。

無(wú)人駕駛飛機(jī)簡(jiǎn)稱“無(wú)人機(jī)”，英文名稱為“Unmanned Aerial Vehicle”(簡(jiǎn)稱“UAV”)。美國(guó)航空航天學(xué)會(huì)(The American Institute of Aeronautics and Astronautics，簡(jiǎn)稱AIAA)對(duì)無(wú)人機(jī)定義為：一種設(shè)計(jì)或改裝過(guò)的，不搭載飛行員，依靠飛行控制器進(jìn)行控制，或者在沒(méi)有飛行控制器參與的前提下，依靠機(jī)載自動(dòng)飛行駕駛系統(tǒng)進(jìn)行控制的飛行器。

隨著飛行器技術(shù)的不斷成熟，飛行任務(wù)的難度、危險(xiǎn)度和強(qiáng)度不斷加大，對(duì)飛行員綜合素質(zhì)的要求越來(lái)越高，任務(wù)的完成也越來(lái)越困難。解決這一問(wèn)題的一種有效途徑就是采用無(wú)人機(jī)航跡規(guī)劃技術(shù)[1]。無(wú)人機(jī)航跡規(guī)劃就是在滿足無(wú)人機(jī)各種約束條件的情況下，為無(wú)人機(jī)規(guī)劃一條從起點(diǎn)到終點(diǎn)的飛行軌跡，使其綜合飛行代價(jià)最小。多架無(wú)人機(jī)協(xié)同航跡規(guī)劃是在滿足無(wú)人機(jī)航跡規(guī)劃定義的基礎(chǔ)上，規(guī)劃出滿足多機(jī)協(xié)同關(guān)系的多條飛行軌跡，并使整個(gè)飛行系統(tǒng)代價(jià)最小。

研究背景

隨著信息技術(shù)的發(fā)展，現(xiàn)代戰(zhàn)爭(zhēng)也趨于高技術(shù)化、信息化，多角度全方位的特點(diǎn)逐漸凸顯。在這種情況下，無(wú)人機(jī)由于其靈活、輕便、隱蔽性強(qiáng)等特點(diǎn)在戰(zhàn)爭(zhēng)中發(fā)揮出越來(lái)越大的作用[2]。隨著社會(huì)的發(fā)展，具有得天獨(dú)厚優(yōu)勢(shì)的無(wú)人機(jī)也逐漸走進(jìn)人民的日常生活中，并得到民眾的迅速認(rèn)可。

賦予無(wú)人機(jī)的任務(wù)一般是多重且復(fù)雜的[3]，在實(shí)際應(yīng)用中，單架無(wú)人機(jī)很多時(shí)候無(wú)法滿足任務(wù)要求。單架無(wú)人機(jī)體積小，工作能力有限，工作范圍也受限制。同時(shí)單架無(wú)人機(jī)執(zhí)行任務(wù)還涉及很多其他方面的問(wèn)題[4，5]，主要有：

(1) 單架無(wú)人機(jī)如果在執(zhí)行任務(wù)的過(guò)程中出現(xiàn)了設(shè)備損壞、能源不足等問(wèn)題，則必須返航，不能完成任務(wù)。如果在戰(zhàn)爭(zhēng)中，由于戰(zhàn)場(chǎng)的多變性很有可能會(huì)造成不可估量的損失；

(2) 單架無(wú)人機(jī)在執(zhí)行觀測(cè)偵查任務(wù)時(shí)，工作空間小、視角范圍小，極可能錯(cuò)失一些重要的目標(biāo)點(diǎn)，錯(cuò)失區(qū)域內(nèi)的重要信息；

(3) 單架無(wú)人機(jī)在物流運(yùn)輸中的載重量是一個(gè)很大的限制。

為了解決單架無(wú)人機(jī)在執(zhí)行任務(wù)中可能出現(xiàn)的以上問(wèn)題，提高無(wú)人機(jī)的工作效率，拓寬使用范圍，同時(shí)應(yīng)未來(lái)信息化戰(zhàn)爭(zhēng)的需要，比如很多作戰(zhàn)任務(wù)需要多架無(wú)人機(jī)相互配合、相互協(xié)作才能完成。所以近年來(lái)，人們開(kāi)始研究多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)。多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)時(shí)可以在任務(wù)分配時(shí)進(jìn)行冗余配置，從而提高任務(wù)的完成概率，當(dāng)在執(zhí)行任務(wù)的過(guò)程中有部分無(wú)人機(jī)突發(fā)情況無(wú)法繼續(xù)任務(wù)，還有部分無(wú)人機(jī)可以繼續(xù)執(zhí)行任務(wù)。此外，通過(guò)任務(wù)分配，有效利用多無(wú)人機(jī)數(shù)量?jī)?yōu)勢(shì)可以大大縮短任務(wù)完成時(shí)間，從而提高執(zhí)行任務(wù)的效率。另外，多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)還可以對(duì)目標(biāo)進(jìn)行協(xié)同定位和協(xié)同干擾等，從而增強(qiáng)執(zhí)行任務(wù)的能力。因此，多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)已成為未來(lái)無(wú)人機(jī)發(fā)展的必然趨勢(shì)。

多無(wú)人機(jī)協(xié)同航跡規(guī)劃是多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)中關(guān)鍵的組成部分。多無(wú)人機(jī)協(xié)同航跡規(guī)劃不是將多架無(wú)人機(jī)單獨(dú)規(guī)劃出的航跡簡(jiǎn)單地疊加在一起，在協(xié)同航跡規(guī)劃的過(guò)程涉及眾多因素，問(wèn)題非常復(fù)雜，主要體現(xiàn)在[6]：(1) 規(guī)劃空間是三維立體空間，需要考慮地形、雷達(dá)、火炮等眾多威脅，規(guī)劃環(huán)境復(fù)雜，可變因素較多；(2) 存在較多約束條件，其中包括無(wú)人機(jī)機(jī)動(dòng)約束，空間協(xié)同性、時(shí)間協(xié)同性約束，航跡安全性約束等；(3) 對(duì)無(wú)人機(jī)航跡的動(dòng)態(tài)調(diào)整性能要求較高，需要隨規(guī)劃環(huán)境的變化而快速變化，及時(shí)地對(duì)航跡進(jìn)行調(diào)整。

從本質(zhì)上來(lái)講，多無(wú)人機(jī)協(xié)同航跡規(guī)劃是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，在滿足單架無(wú)人機(jī)航跡可飛性要求的同時(shí)也要滿足多無(wú)人機(jī)航跡間的協(xié)同性要求。多機(jī)協(xié)同航跡規(guī)劃除了需要考慮對(duì)各種威脅障礙的規(guī)避以外，還需要協(xié)調(diào)處理各無(wú)人機(jī)航跡間的關(guān)系。多無(wú)人機(jī)協(xié)同航跡規(guī)劃優(yōu)化生成的多無(wú)人機(jī)航跡是要使整個(gè)多機(jī)系統(tǒng)的性能指標(biāo)達(dá)到最優(yōu)或者較優(yōu)，但是這些航跡對(duì)系統(tǒng)內(nèi)分別對(duì)應(yīng)的單架無(wú)人機(jī)來(lái)說(shuō)不一定是最優(yōu)的[7]。

經(jīng)過(guò)多無(wú)人機(jī)協(xié)同航跡規(guī)劃，無(wú)人機(jī)在執(zhí)行任務(wù)的過(guò)程中應(yīng)當(dāng)是能夠安全自主飛行并且通過(guò)相互協(xié)作和信息共享促進(jìn)每架無(wú)人機(jī)的效能發(fā)揮，最終達(dá)到提高完成任務(wù)成功率的目的。在當(dāng)前階段，如美國(guó)、俄羅斯等軍事強(qiáng)國(guó)都對(duì)多無(wú)人機(jī)協(xié)同航跡規(guī)劃研究投入了大量的精力，以期提升其軍事實(shí)力。

研究現(xiàn)狀

航跡規(guī)劃算法是航跡規(guī)劃的核心，種類眾多，根據(jù)不同的分類規(guī)則對(duì)航跡規(guī)劃算法有不同的區(qū)分方式。目前多無(wú)人機(jī)協(xié)同航跡規(guī)劃常用的研究方法根據(jù)其基本思想大致可以分為三類：(1) 基于純數(shù)學(xué)優(yōu)化的規(guī)劃方法，如動(dòng)態(tài)規(guī)劃法、窮舉法、混合整數(shù)線性規(guī)劃法等，該類算法通過(guò)對(duì)模型控制量和輸出量的調(diào)整，使代價(jià)函數(shù)最小從而得到最優(yōu)路徑。這種算法的運(yùn)算能力和問(wèn)題的規(guī)模息息相關(guān)，當(dāng)遇到大規(guī)模問(wèn)題的時(shí)候容易出現(xiàn)計(jì)算時(shí)間暴增的情況。(2) 基于圖論的規(guī)劃方法，如通試圖法、Voronoi圖法[8]、隨機(jī)樹(shù)法[9]等，該類算法的基本思想是將規(guī)劃空間按約束、威脅等條件處理成一個(gè)通路圖，然后在通路圖上獲取最優(yōu)航跡。具有代表性的Voronoi圖就是根據(jù)地圖中的威脅和障礙，將空間劃分為多個(gè)共邊多邊形，這些共邊多邊形相互連接就形成了通路圖。在這個(gè)通路圖上只需從起點(diǎn)開(kāi)始經(jīng)過(guò)多邊形的共邊到下一個(gè)多邊形頂點(diǎn)，再經(jīng)過(guò)共邊一直到終點(diǎn)為止就能得到一條安全可飛的航跡。利用Voronoi圖法進(jìn)行無(wú)人機(jī)航跡規(guī)劃具有構(gòu)造時(shí)間快、航跡絕對(duì)安全等優(yōu)點(diǎn)，但是在三維空間中應(yīng)用于多無(wú)人機(jī)航跡規(guī)劃，如何對(duì)空間進(jìn)行劃分及體現(xiàn)多機(jī)協(xié)同性還值得探究。(3) 基于啟發(fā)信息的傳統(tǒng)人工智能優(yōu)化算法，如A*算法、Dijkstra算法等。該類算法的基本思想是通過(guò)啟發(fā)信息對(duì)下一步節(jié)點(diǎn)的位置進(jìn)行估算，從而不斷搜尋空間中的最優(yōu)航跡。具有代表性的A*算法及其改進(jìn)算法稀疏A*算法可以很好地對(duì)無(wú)人機(jī)航跡規(guī)劃環(huán)境中的復(fù)雜約束條件進(jìn)行處理，但是也因?yàn)檫@個(gè)特點(diǎn)導(dǎo)致其對(duì)環(huán)境信息高度依賴，當(dāng)環(huán)境復(fù)雜時(shí)計(jì)算量大，并行性差。(4) 基于生物種群進(jìn)化的群智能算法，如遺傳算法[10]、蟻群算法[11]、粒子群算法[12]等，該類算法的基本思想均借鑒于人類智能、生物的群體性行為或自然現(xiàn)象規(guī)律，從而在多條無(wú)人機(jī)航跡中迭代優(yōu)化出最符合評(píng)價(jià)指標(biāo)的最優(yōu)航跡。具有代表性的遺傳算法是模仿自然界生物進(jìn)化機(jī)制，根據(jù)確定的編碼方式、適應(yīng)度函數(shù)，通過(guò)選擇、交叉、變異等操作，在由多條無(wú)人機(jī)航跡組成的初始種群中迭代優(yōu)化出最優(yōu)航跡。群智能優(yōu)化算法適合求解如多無(wú)人機(jī)協(xié)同航跡規(guī)劃這類多目標(biāo)優(yōu)化問(wèn)題，具有并行性、協(xié)同性好，可以收斂到全局最優(yōu)等優(yōu)點(diǎn)，但是存在沒(méi)有明確的優(yōu)化指標(biāo)、最優(yōu)解不惟一等問(wèn)題。

在這四個(gè)方面，國(guó)內(nèi)外的學(xué)者均做了大量的研究，其中群智能算法是目前研究最廣泛的方法。表1對(duì)一些常見(jiàn)的航跡規(guī)劃算法進(jìn)行了羅列并簡(jiǎn)單比較。

實(shí)現(xiàn)方法

無(wú)論是何種類型的無(wú)人機(jī)，針對(duì)多機(jī)協(xié)同航跡規(guī)劃問(wèn)題，都包含搭建航跡規(guī)劃仿真地圖、明確協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)和選擇航跡規(guī)劃算法三個(gè)共同步驟。

搭建航跡規(guī)劃仿真地圖

在無(wú)人機(jī)航跡規(guī)劃前需要掌握一定的無(wú)人機(jī)航跡規(guī)劃環(huán)境信息，包括地形、威脅等。根據(jù)無(wú)人機(jī)任務(wù)的不同，無(wú)人機(jī)的飛行區(qū)域可能是山地、草原也有可能是盆地丘陵等。不同的地形會(huì)對(duì)無(wú)人機(jī)飛行造成很大的威脅，但是與此同時(shí)在某些軍事行動(dòng)中，地形卻能夠起到阻礙雷達(dá)探測(cè)，為無(wú)人機(jī)制造躲避探測(cè)的條件。因此在無(wú)人機(jī)航跡規(guī)劃中精準(zhǔn)描述地形十分重要。對(duì)地形圖采用不同的數(shù)字化處理方式可以得到不同的信息產(chǎn)品，比較常見(jiàn)的有數(shù)字正射影像圖(DOM，Digital Orthophoto Map)、數(shù)字線劃地圖(DLG，Digital Line Graphic)、數(shù)字地面模型(DTM，Digital Terrain Model)、數(shù)字高程模型(DEM，Digital Elevation Model)和數(shù)字柵格地圖(DRG，Digital Raster Graphic)等。其中DEM是我國(guó)基礎(chǔ)地理信息系統(tǒng)賴以分析的核心數(shù)據(jù)系統(tǒng)，其數(shù)據(jù)具有較高的精度和較強(qiáng)的可加工性，在航跡規(guī)劃中被較多采用。

在航跡規(guī)劃中首要考慮的因素就是航跡的隱蔽性，因此有效、準(zhǔn)確地對(duì)威脅進(jìn)行描述是對(duì)無(wú)人機(jī)進(jìn)行成功航跡規(guī)劃的關(guān)鍵。在考慮地形的基礎(chǔ)上，無(wú)人機(jī)飛行過(guò)程中還需要對(duì)氣候威脅、禁飛區(qū)及人為敵對(duì)威脅等進(jìn)行考慮，人為敵對(duì)威脅又包括雷達(dá)、火炮、地空導(dǎo)彈等。其中雷達(dá)是當(dāng)前最重要的探測(cè)設(shè)備，不但種類繁多而且發(fā)現(xiàn)目標(biāo)的能力與周?chē)沫h(huán)境息息相關(guān)，在搭建航跡規(guī)劃仿真地圖中是首要考慮的威脅因素。在雷達(dá)探測(cè)發(fā)現(xiàn)目標(biāo)后，地空導(dǎo)彈作為一種高效擊毀無(wú)人機(jī)的武器，經(jīng)常搭配雷達(dá)一同考慮。此外，氣候、禁飛區(qū)以及其他各類威脅在無(wú)人機(jī)執(zhí)行不同的任務(wù)時(shí)分別針對(duì)任務(wù)類型在搭建航跡規(guī)劃仿真地圖時(shí)加以考慮。

明確協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)

明確多機(jī)協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)需要考慮三個(gè)方面的內(nèi)容：解析無(wú)人機(jī)約束條件、確定多機(jī)協(xié)同關(guān)系和設(shè)計(jì)協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)。

首先對(duì)無(wú)人機(jī)的機(jī)動(dòng)約束條件進(jìn)行解析。在無(wú)人機(jī)航跡規(guī)劃中一般將無(wú)人機(jī)簡(jiǎn)化為質(zhì)點(diǎn)，不考慮無(wú)人機(jī)的質(zhì)量和大小，但是在確定最終無(wú)人機(jī)航跡時(shí)需要考慮無(wú)人機(jī)的物理限制，如最大爬升角/俯沖角、最小轉(zhuǎn)彎半徑等，否則無(wú)人機(jī)將無(wú)法跟蹤生成的航跡飛行[13]。無(wú)人機(jī)最小轉(zhuǎn)彎半徑與無(wú)人機(jī)最大滾轉(zhuǎn)角有關(guān)，體現(xiàn)了無(wú)人機(jī)的過(guò)載約束能力。最大爬升角/俯沖角則是無(wú)人機(jī)從當(dāng)前航跡點(diǎn)移動(dòng)到下一航跡點(diǎn)過(guò)程中垂直方向上的角度限制，小于或等于最大爬升角/俯沖角才能滿足無(wú)人機(jī)的機(jī)動(dòng)約束。

其次確定多機(jī)協(xié)同關(guān)系。多機(jī)協(xié)同航跡規(guī)劃除了需要考慮躲避威脅障礙，還需要對(duì)多無(wú)人機(jī)間的協(xié)同關(guān)系，包括空間和時(shí)間協(xié)同關(guān)系進(jìn)行考慮?？臻g協(xié)同關(guān)系是多機(jī)協(xié)同關(guān)系在空域上的體現(xiàn)，是在空間位置上對(duì)每架無(wú)人機(jī)的限制，體現(xiàn)在兩個(gè)方面：一是各無(wú)人機(jī)間的距離要小于一個(gè)最遠(yuǎn)協(xié)同距離來(lái)保證各無(wú)人機(jī)之間能互相配合、掩護(hù)；二是各無(wú)人機(jī)之間的距離應(yīng)大于一個(gè)安全距離來(lái)防止發(fā)生碰撞。時(shí)間協(xié)同關(guān)系是多機(jī)協(xié)同關(guān)系在時(shí)域上的體現(xiàn)，是對(duì)多機(jī)完成任務(wù)到達(dá)目標(biāo)點(diǎn)時(shí)間的限制，其中包含兩方面的內(nèi)容：一是過(guò)程中的時(shí)間協(xié)同；二是完成任務(wù)所用時(shí)間的協(xié)同。

最后設(shè)計(jì)協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)。多機(jī)協(xié)同航跡規(guī)劃問(wèn)題的本質(zhì)是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，為了在優(yōu)化的過(guò)程中達(dá)到多機(jī)協(xié)同的目的，就需要表征多機(jī)航跡協(xié)同性的評(píng)價(jià)指標(biāo)，由此指標(biāo)設(shè)計(jì)的函數(shù)將在優(yōu)化過(guò)程中作為判斷條件，判斷出更符合多機(jī)協(xié)同性要求的航跡。多機(jī)協(xié)同關(guān)系主要分為空間協(xié)同關(guān)系和時(shí)間協(xié)同關(guān)系，這兩種關(guān)系在協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)設(shè)計(jì)時(shí)分別對(duì)應(yīng)于空間協(xié)同性和時(shí)間協(xié)同性。

選擇航跡規(guī)劃算法

對(duì)多無(wú)人機(jī)協(xié)同航跡規(guī)劃問(wèn)題進(jìn)行分解，搭建航跡規(guī)劃仿真地圖和明確協(xié)同航跡規(guī)劃評(píng)價(jià)指標(biāo)后，就需要在眾多規(guī)劃算法中選擇適當(dāng)?shù)乃惴ㄟM(jìn)行求解。為提高規(guī)劃算法性能，可以將多種計(jì)算方法相結(jié)合，包括混合算法、離線預(yù)規(guī)劃與在線重規(guī)劃相結(jié)合等等。

工作展望

隨著人們對(duì)無(wú)人機(jī)航跡規(guī)劃研究的深入，無(wú)人機(jī)航跡規(guī)劃技術(shù)日趨完善，出現(xiàn)了大量的研究方法和成果。但是，隨著無(wú)人機(jī)任務(wù)的不斷復(fù)雜化、多重化以及多無(wú)人機(jī)體系的構(gòu)建，對(duì)該技術(shù)的研究提出了更高的要求。為了適應(yīng)復(fù)雜的規(guī)劃環(huán)境，進(jìn)一步貼合現(xiàn)實(shí)需求，未來(lái)多無(wú)人機(jī)協(xié)同航跡規(guī)劃技術(shù)的發(fā)展將趨于提高無(wú)人機(jī)群的自主性、協(xié)同性和規(guī)劃算法性能，其具體體現(xiàn)在無(wú)人機(jī)群在任何情況下都能夠快速自主規(guī)劃最優(yōu)航跡并同時(shí)保持多無(wú)人機(jī)空間和時(shí)間上的協(xié)同。其中在提高規(guī)劃算法性能方面的發(fā)展趨勢(shì)是將多種方法相結(jié)合，包括混合算法、離線預(yù)規(guī)劃與在線重規(guī)劃相結(jié)合等等。此外，研究高精度的無(wú)人機(jī)航跡規(guī)劃仿真地圖、合理的多機(jī)協(xié)同結(jié)構(gòu)對(duì)提高多無(wú)人機(jī)協(xié)同航跡規(guī)劃技術(shù)也具有較大的實(shí)踐意義。