李士波

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

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

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

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

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

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

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

1 算法描述

1.1 算法簡介

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

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

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

1.2 算法總體描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 仿真及結(jié)論

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

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

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

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

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

參考文獻：

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

[2] 張同法，于雷，魯藝. 多架無人機協(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é)報，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] 張耀中，李寄瑋，胡波，等.基于改進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