基于動(dòng)態(tài)環(huán)境的多無人機(jī)協(xié)同攻擊路徑規(guī)劃

李士波

摘要： 針對(duì)動(dòng)態(tài)環(huán)境下多無人機(jī)協(xié)同攻擊的路徑規(guī)劃，提出將其分解為起飛前規(guī)劃和路徑重規(guī)劃兩個(gè)階段，并將每個(gè)階段分解為路徑生成與路徑協(xié)同兩個(gè)子問題。并提出一種新的路徑協(xié)同方法，即通過附加最小轉(zhuǎn)彎使每架無人機(jī)的飛行路徑大致相等，并通過進(jìn)一步調(diào)整飛行速度使每一架無人機(jī)到達(dá)目標(biāo)的時(shí)間相等。最后經(jīng)仿真證明了該算法能滿足動(dòng)態(tài)環(huán)境下多機(jī)協(xié)同路徑規(guī)劃的要求。

關(guān)鍵詞： 無人機(jī)； 協(xié)同規(guī)劃；航跡重規(guī)劃；實(shí)時(shí)規(guī)劃

中圖分類號(hào)：TP273 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）01-0242-04

Abstract： For route planning of Multi-Unmanned Aerial Vehicles（UAVs） on dynamic environment， A method is presented to divide the whole process in to two stage： Planning before takeoff， Re-planning in flight. Each stage can be concluding two questions， Route Generation and Route Cooperation. A new cooperative route planning method is presented， this method uses minim circle to form the path to let the Route Length nearly equal， Then Adjust each UAVs speed to make them arrive the target simultaneity. Finally the simulation results show the efficiency of the algorithms.

Key words： Unmanned aerial vehicles（UAVs）， Route planning， dynamic environment， real-time planning

現(xiàn)有無人機(jī)航跡規(guī)劃算法一般局限于確定環(huán)境中，即局限在我們對(duì)規(guī)劃區(qū)域內(nèi)的地形、威脅等情況已知或大部分已知的基礎(chǔ)上。這些規(guī)劃算法一般考慮飛行器的任務(wù)要求、安全要求等因素，在地面起飛前離線找到一條最優(yōu)軌跡作為參考航跡[1][2]。在飛行時(shí)，根據(jù)在線獲得的威脅信息，由地面人員發(fā)出指令，或通過一定的航跡算法對(duì)參考航跡進(jìn)行部分修正，使無人機(jī)能夠順利到達(dá)目標(biāo)，完成指定任務(wù)。

在軍事應(yīng)用中無人機(jī)通常需要穿越動(dòng)態(tài)危險(xiǎn)環(huán)境對(duì)目標(biāo)進(jìn)行打擊[3]，無人機(jī)執(zhí)行的任務(wù)通常具有很大的危險(xiǎn)性和復(fù)雜性，因此通常使用多架無人機(jī)共同執(zhí)行任務(wù)，。這就涉及協(xié)同攻擊任務(wù)中的動(dòng)態(tài)環(huán)境路徑規(guī)劃問題，一般以能夠同時(shí)到達(dá)目標(biāo)上空作為規(guī)劃的目標(biāo)[4][5]，以提高攻擊的突然性、有效性。

近年來，多無人機(jī)協(xié)同控制已經(jīng)成為無人機(jī)領(lǐng)域的一個(gè)新的研究熱點(diǎn)，較高程度的無人機(jī)協(xié)同規(guī)劃能力是無人機(jī)在高度危險(xiǎn)的戰(zhàn)場(chǎng)環(huán)境中順利完成任務(wù)所必備的一項(xiàng)技能，而多機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)是多無人機(jī)協(xié)同控制的關(guān)鍵技術(shù)[6]，因此有必要加強(qiáng)對(duì)多機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)的研究。

在多機(jī)協(xié)同攻擊路徑規(guī)劃問題中，主要存在兩大難點(diǎn)：一是多機(jī)路徑規(guī)劃本身固有的復(fù)雜性[7]，即不僅要產(chǎn)生每架無人機(jī)的飛行路徑和飛行速度，而且產(chǎn)生的路徑要滿足各種復(fù)雜約束條件和協(xié)同性要求；二是針對(duì)動(dòng)態(tài)環(huán)境需要產(chǎn)生實(shí)時(shí)路徑，當(dāng)規(guī)劃環(huán)境發(fā)生變化時(shí)，要對(duì)每架飛機(jī)的飛行航路、速度進(jìn)行實(shí)時(shí)修改。

多機(jī)協(xié)同路徑規(guī)劃問題是一個(gè)大系統(tǒng)的非線性最優(yōu)化問題[8]，計(jì)算復(fù)雜，對(duì)信息處理速度要求苛刻[9]。目前該問題還處于理論探索階段，離實(shí)用存在較長(zhǎng)的一段距離。特別是動(dòng)態(tài)環(huán)境下的多機(jī)協(xié)同路徑規(guī)劃，目前還未見相關(guān)的研究和報(bào)道。本文主要研究多機(jī)協(xié)同攻擊路徑規(guī)劃問題，從理論上給出多無人機(jī)協(xié)同攻擊的解決辦法。

1 算法描述

1.1 算法簡(jiǎn)介

在解決多機(jī)協(xié)同攻擊路徑規(guī)劃問題時(shí)，克服以上提出的兩方面難點(diǎn)，提出將其分解為路徑生成與路徑協(xié)同兩個(gè)子問題。首先根據(jù)初始位置和目標(biāo)位置確定每架無人機(jī)的飛行路徑，路徑的計(jì)算可以參照前面介紹的參考路徑規(guī)劃的方法來進(jìn)行，并進(jìn)行多機(jī)間的路徑協(xié)調(diào)。在飛行過程中，由于規(guī)劃環(huán)境的變化，往往需要對(duì)無人機(jī)群內(nèi)的個(gè)別無人機(jī)進(jìn)行航跡的重規(guī)劃，即根據(jù)無人機(jī)的當(dāng)前位置和目標(biāo)位置重新產(chǎn)生一條航路，并進(jìn)行優(yōu)化，使路徑平滑可飛。

在每次路徑重規(guī)劃發(fā)生后，在多架無人機(jī)之間進(jìn)行通訊，由每一架無人機(jī)報(bào)告其當(dāng)前位置以及剩余的飛行路徑的長(zhǎng)度，將這些信息輸入多機(jī)路徑協(xié)調(diào)規(guī)劃模塊得到無人機(jī)群整體協(xié)調(diào)變量，之后每架無人機(jī)根據(jù)協(xié)調(diào)變量對(duì)其路徑進(jìn)行處理，通過附加機(jī)動(dòng)使每架無人機(jī)的飛行路徑大致相等，并通過進(jìn)一步調(diào)整飛行速度使每一架無人機(jī)到達(dá)目標(biāo)的時(shí)間相等。采用這種規(guī)劃策略的優(yōu)點(diǎn)在于單機(jī)路徑生成與路徑協(xié)調(diào)過程彼此獨(dú)立，這使得單機(jī)路徑生成時(shí)只需考慮路徑最短、威脅規(guī)避等因素，不必考慮路徑協(xié)調(diào)因素，避免了在其他協(xié)調(diào)航跡規(guī)劃算法中為了保證協(xié)調(diào)效果而集中生成所有路徑造成的計(jì)算的復(fù)雜性，并能滿足動(dòng)態(tài)環(huán)境下多機(jī)協(xié)同路徑規(guī)劃的實(shí)時(shí)性要求。

圖1給出了協(xié)同攻擊路徑規(guī)劃結(jié)構(gòu)圖。無人機(jī)群在參考路徑產(chǎn)生或在飛行過程中由于戰(zhàn)場(chǎng)環(huán)境變化使某一架或某幾架無人機(jī)飛行軌跡發(fā)生改變后，都按照?qǐng)D1給出的結(jié)構(gòu)對(duì)每架無人機(jī)的飛行路徑和飛行速度進(jìn)行一定的調(diào)整。

1.2 算法總體描述

在多無人機(jī)協(xié)同路徑規(guī)劃中，定義表示第架無人機(jī)的當(dāng)前位置，表示第架無人機(jī)的目標(biāo)位置，表示規(guī)劃區(qū)域內(nèi)所有位置的集合，則有，。

定義表示從到的任意一條可飛路徑，定義為到的所有可飛路徑的集合，則有：。endprint

為了有效地進(jìn)行協(xié)同路徑規(guī)劃，必須在無人機(jī)群當(dāng)中進(jìn)行信息交換與共享，由此本文提出全局協(xié)同變量這個(gè)概念，作為協(xié)同空間的一個(gè)向量，即滿足。若每架無人機(jī)能夠通過地面指揮臺(tái)、衛(wèi)星通信或機(jī)群間通訊等方式及時(shí)獲得協(xié)同變量，并嚴(yán)格按照來確定下一步飛行路徑和飛行速度，則可以保證滿足協(xié)同路徑規(guī)劃的要求。在本文中，取無人機(jī)編隊(duì)到達(dá)時(shí)間t作為協(xié)同變量，以時(shí)間域T作為協(xié)同空間。

協(xié)同空間包含全局協(xié)同變量和局部協(xié)同變量，局部協(xié)同變量用表示。全局協(xié)同變量只有一個(gè)，而局部協(xié)同變量可以存在多個(gè)。定義函數(shù)，表示從可飛路徑集合到協(xié)同空間的一個(gè)映射。針對(duì)第架無人機(jī)從飛行至，根據(jù)給出針對(duì)第架無人機(jī)的局部協(xié)同變量一個(gè)集合如下：

其中，第架無人機(jī)最小局部協(xié)同變量為：

若路徑規(guī)劃算法以及代價(jià)評(píng)估函數(shù)已經(jīng)確定，則可以確定一條可飛路徑。

在確定可飛路徑之后，根據(jù)式（1），針對(duì)第架無人機(jī)的最小局部協(xié)同變量的數(shù)值也唯一確定：

令函數(shù)表示根據(jù)每架無人機(jī)的最小局部協(xié)同變量計(jì)算全局協(xié)同變量的函數(shù)表達(dá)式，則有

一旦得到全局協(xié)同變量，剩下的任務(wù)是根據(jù)對(duì)每架飛機(jī)的航跡和速度進(jìn)行修正，得到每架飛機(jī)修正后的路徑和飛行速度：

1.3 算法具體實(shí)現(xiàn)

在算法實(shí)現(xiàn)中，首先需要為每架無人機(jī)確定一條平滑可飛最短路徑，路徑的長(zhǎng)度即為。得到路徑可以視為由直線和圓弧構(gòu)成，對(duì)路徑離散化得到一系列的航路點(diǎn)，其中為飛行起點(diǎn)，為飛行終點(diǎn)，則整條路徑的長(zhǎng)度可以表示為：

由于在區(qū)間內(nèi)變化，因此對(duì)于一條給定路徑，局部協(xié)同變量的變化范圍為。若路徑唯一確定，則速度與局部協(xié)同變量之間的關(guān)系如圖2所示。

最小局部協(xié)同變量相當(dāng)于取最大值時(shí)的取值。

若存在N架無人機(jī)，全局協(xié)同變量為：

圖3中，給出3架無人機(jī)在已知局部協(xié)同變量時(shí)，全局協(xié)同變量的計(jì)算示意圖。為了使無人機(jī)群能夠同時(shí)到達(dá)，給路徑長(zhǎng)度較短的航線附加一些機(jī)動(dòng)，使所有航線的長(zhǎng)度大致相等；然后通過調(diào)整每架無人機(jī)速度，使其到達(dá)目標(biāo)時(shí)間。

以圖3為例，通過添加最小轉(zhuǎn)彎半徑組成的圓來調(diào)整航跡，簡(jiǎn)化了路徑協(xié)調(diào)的難度和工作量，在具體操作中首先考察全局協(xié)同變量，在與的關(guān)系圖中，自橫坐標(biāo)為的點(diǎn)作垂直橫軸的直線，存在一系列路徑與該直線相交，這說明這些路徑通過調(diào)整飛行速度即可滿足同時(shí)到達(dá)的要求，計(jì)算這些路徑對(duì)應(yīng)的速度。

而對(duì)于不相交的路徑，說明這些路徑的局部協(xié)同變量的最大值依然小于，即以速度大小到達(dá)目標(biāo)時(shí)間仍早于協(xié)調(diào)時(shí)間，需要對(duì)這部分路徑進(jìn)行加長(zhǎng)，計(jì)算與每架無人機(jī)的最大局部協(xié)同變量的偏差量。

以上方法的實(shí)質(zhì)是通過調(diào)整添加最小轉(zhuǎn)彎的個(gè)數(shù)，針對(duì)每一架無人機(jī)形成一系列待選路徑，待選路徑的長(zhǎng)度之間相差，如圖4所示。這些路徑的局部協(xié)調(diào)變量表示為

局部協(xié)調(diào)變量之間存在間隙，即存在無法實(shí)現(xiàn)的協(xié)調(diào)時(shí)間，這種情況發(fā)生一般發(fā)生在，差別不大，而較大時(shí)，對(duì)應(yīng)不等式14、15、16無法全部成立的情況。在圖4中給出了一種無解的情況。

若全局協(xié)同變量無解，為了使有解并保持一個(gè)較小值，本文提出兩種方法來解決這個(gè)問題。第一種方法是調(diào)整轉(zhuǎn)彎的半徑，即加大，使局部協(xié)同變量與存在交點(diǎn)，在此種情況下轉(zhuǎn)彎個(gè)數(shù)為，若速度取為，則轉(zhuǎn)彎半徑計(jì)算公式為：

第二種方法通過改變?nèi)謪f(xié)調(diào)變量來實(shí)現(xiàn)，適當(dāng)加大，并調(diào)整轉(zhuǎn)彎個(gè)數(shù)，使所有路徑的局部協(xié)調(diào)變量均與有交點(diǎn)，獲得后，再計(jì)算各架UAV的速度。

這兩種方法都能使無人機(jī)群到達(dá)目標(biāo)的時(shí)間一致。在具體實(shí)現(xiàn)時(shí)，應(yīng)當(dāng)根據(jù)實(shí)際情況和執(zhí)行任務(wù)的不同，選擇不同的方式。在對(duì)到達(dá)時(shí)間有嚴(yán)格要求的緊急情況下，傾向于使用第一種方式，而在障礙物或威脅密集的復(fù)雜環(huán)境中，為了保證飛行安全，則一般考慮使用第二種方式。

2 仿真及結(jié)論

本節(jié)對(duì)多機(jī)協(xié)同路徑規(guī)劃問題進(jìn)行仿真。若使用3架無人機(jī)去攻擊3個(gè)目標(biāo)，并使無人機(jī)到達(dá)目標(biāo)的時(shí)間相等，無人機(jī)與協(xié)同規(guī)劃問題相關(guān)參數(shù)如表1所示。

設(shè)計(jì)要求對(duì)無人機(jī)進(jìn)行目標(biāo)分配，并考慮對(duì)所有威脅進(jìn)行規(guī)避，生成每架無人機(jī)的路徑如圖5。路徑代價(jià)評(píng)估函數(shù)J取為從起點(diǎn)到終點(diǎn)的實(shí)際路徑長(zhǎng)度，以路徑長(zhǎng)度最短產(chǎn)生每架無人機(jī)飛行的航跡。

首先解決無人機(jī)參考路徑的協(xié)同規(guī)劃問題，即解決靜態(tài)環(huán)境下的多機(jī)協(xié)同路徑規(guī)劃問題。按照（7）式計(jì)算每一條航跡的長(zhǎng)度，UAV1、UAV2和UAV3對(duì)應(yīng)的路徑path1、path2、path3長(zhǎng)度分別為20.39，28.32，16.28。根據(jù)UAV相關(guān)技術(shù)參數(shù)得到與的關(guān)系圖5，根據(jù)圖5可以得到協(xié)調(diào)時(shí)間為5.14，其中UAV1、UAV2路徑長(zhǎng)度不變，速度分別取為3.96，5.5。而UAV3的路徑附加一個(gè)半徑為2.5的圓形轉(zhuǎn)彎，轉(zhuǎn)彎時(shí)可以順時(shí)針或逆時(shí)針轉(zhuǎn)彎，根據(jù)規(guī)劃區(qū)域的威脅分布情況而定，速度取為4.99。規(guī)劃結(jié)果如圖6所示。

針對(duì)動(dòng)態(tài)環(huán)境下的多機(jī)協(xié)同路徑規(guī)劃，若在規(guī)劃過程中遇到突然出現(xiàn)的威脅，則需要對(duì)受到威脅影響的路徑進(jìn)行重規(guī)劃，重規(guī)劃結(jié)果如圖8所示。path2路徑進(jìn)行了重規(guī)劃，重規(guī)劃的路徑長(zhǎng)度為29.8，重新繪制與的關(guān)系如圖7，得到協(xié)調(diào)時(shí)間更改為5.41。此時(shí)UAV2速度取最大值5.5。

考察圖7，可以得出這樣的結(jié)論，即path1、path3的路徑均不需要重新修正，只要調(diào)整UAV1、UAV3的速度即可，通過計(jì)算得到UAV1、UAV3的速度取值為3.76和4.74。

參考文獻(xiàn)：

[1] 唐強(qiáng)，張翔倫，左玲. 無人機(jī)航跡規(guī)劃算法的初步研究[J]. 航空計(jì)算技術(shù)，2003，33（1）：125.

[2] 張同法，于雷，魯藝. 多架無人機(jī)協(xié)同作戰(zhàn)的路徑規(guī)劃[J].火力指揮與控制，2009，34（2）：143.

[3] Rathinam S， Sengupta R. A Safe Flight Algorithm for Unmanned Aerial Vehicles[C]. Proc. of the IEEE Aerospace conference， 2004， 3025-3030.

[4] 霍霄華，陳 巖，朱華勇，等. 多UCAV協(xié)同控制中的任務(wù)分配模型及算法[J].國防科技大學(xué)學(xué)報(bào)，2006，28（3）：885.

[5] Randal W， Timothy W. Coordinated Target Assignment and Interpret for Unmanned air Vehicles[J].IEEE Transaction on Robotics and automation， 2002， 18（6）：911-922.

[6] 張耀中，李寄瑋，胡波，等.基于改進(jìn)ACO算法的多UAV協(xié)同航路規(guī)劃[J].火力指揮與控制，2017（5）：139-145.

[7] A Richards， J Bellingham， M. Tillerson， J. How. Coordination and control of multiple UAVs[A]. AIAA Conf. Guidance， Navigation and Control， Monterey [C]. CA， 2002， AIAA-2002-4288.

[8] Tal Shima， Steven J. Rasmussen， and Andrew G. Sparks. UAV Cooperative Multiple Task Assignments using Genetic Algorithms[A]. 2005 American Control Conference [C]， Portland， OR， USA： 2005，2989.

[9] Tan K， L. Lee Q，Ou K. Heuristic methods for vehicle routing problem with time windows[J]. Artif. Intell. Eng.， 2001， 15（3）：282.endprint