面向多無人機協同對地攻擊的雙層任務規劃方法

余 婧, 雍恩米, 陳漢洋, 郝 東, 張顯才

(1. 中國空氣動力研究與發展中心計算空氣動力研究所, 四川 綿陽 621000;2. 中國空氣動力研究與發展中心空天技術研究所, 四川 綿陽 621000)

0 引 言

飛行器任務規劃是隨著航空技術和制導/控制技術的進步及其在軍事上的應用而形成的一個新的研究領域。無人機(unmanned aerial vehicles, UAVs)的任務規劃問題包含任務分配、執行順序規劃以及航跡規劃等。任務分配是指確定哪些任務由哪些UAVs執行;執行順序確定是指在已知任務集合的條件下,確定UAVs執行任務的先后順序;航跡優化即確定UAVs執行任務的具體飛行航跡。任務分配與執行順序規劃都是典型的復雜約束下的組合優化問題,航跡規劃的優化方式則因建模方式的不同而有所差別。一般而言,3個層次的優化問題相互嵌套、相互影響。執行順序規劃需要以任務分配方案為輸入;航跡規劃需要以任務執行順序為輸入;執行任務的航程或飛行時間又進一步影響任務分配方案的決策。為了達到任務規劃的全局最優,需要全盤梳理3個層次的優化關系,提出高效的優化策略。

目前已存在多種UAVs任務規劃的建模方法,包括旅行商模型、車輛路由模型、網絡流模型、混合整數模型等,其中混合整數模型具有較強的可擴展性,車輛路由模型可以更好地處理帶約束問題。針對優化模型,可以選擇很多種搜索算法進行求解。傳統的優化方法有枚舉法、動態規劃法、圖搜索算法等,但隨著問題維數的增加,時間消耗呈指數增長,不利于復雜問題的求解。隨后,智能優化方法因具備易于實現、計算復雜度低等特點,被廣泛應用。目前常用的智能優化算法有遺傳算法(genetic algorithm, GA)、粒子群優化(particle swarm optimization, PSO)算法、模擬退火(simulated-annealing, SA)算法等。在當前研究中,任務分配與執行順序規劃因內在行為的緊耦合性,通常被作為一個整體考慮,因此任務規劃問題大多側重前兩者的優化,而忽略航跡的影響。在優化算法方面,SA算法因在理論上有完備的證明,可以達到全局極小值,而備受研究者的青睞。在任務規劃問題中,SA算法已有很多成功應用,但其亦存在一個致命的缺點,即容易陷入局部最優,因此研究者也一直在嘗試諸多改進方法。

本文綜合考慮任務規劃中任務分配、執行順序規劃以及航跡規劃3個層面的優化需求和相互間影響,從優化框架出發,設計了雙層互耦的任務規劃求解策略,而后將優化模型求解分為上層任務分配和下層任務序列優化,并對每一層的優化方法和優化步驟進行了詳細設計;在任務分配問題中,基于SA算法,提出了可跳出局部最優的SA-撒點(SA-shooting, SAS)算法,并詳細探討了算法參數的設計原則。最后，通過仿真分析,驗證了所提出的規劃框架和優化算法的有效性。

1 任務描述

假設有無人攻擊機架和待打擊目標個,UAVs起飛后需要飛行至待打擊目標位置進行對地攻擊。一架UAV最多攜帶的武器數量為,即一架UAV最多攻擊個目標，且一個目標只能被一架UAV攻擊。任務分配的目的是優化出哪些UAVs需要打擊哪些目標，以及實施打擊的具體作戰順序、飛行路徑,最大化對地攻擊效益。圖1給出了多UAV協同對地打擊的示意圖。

圖1 多UAV協同對地打擊示意圖Fig.1 Sketch map for multi-cooperative UAV air-to-ground attack

2 多UAVs協同對地攻擊任務分配建模

本文的UAVs對地攻擊任務分配問題,可用四元組〈,,,〉來描述:

表示戰場環境態勢,包含了戰場威脅分布、天氣情況、地形等戰場信息。為了方便討論,本文將所有環境態勢分為兩部分,一部分為禁飛區,即由于雷達威脅、惡劣天氣、不利地形所導致的UAV不可駛入的區域;另一部分即為UAV可以機動的區域。

即UAV狀態,已知UAV集合={UAV,UAV,…,UAV},其中UAV={loc,},表示第架UAV的初始位置和所攜帶的武器數量,為UAV數量。

為待攻擊目標集合={tar,tar,…,tar},為目標數量,且≤。

表示任務分配中的約束,包括任務時長約束、匹配約束、數量約束等,將在建模中詳細討論。

任務規劃的本質是一個優化問題,包含設計變量、任務約束和評價指標3個關鍵因素。下面將對本文研究問題的關鍵要素進行分析和建模。

2.1 設計變量

(1)

2.2 評價指標

(1) 毀傷效果

假設UAV對tar的殺傷概率為 ,則整個攻擊任務的毀傷效果為

(2)

(2) 損傷程度

假設UAV對tar進行打擊,生存概率為 ,則該UAV被擊毀的概率為 =1- ,整個攻擊任務的損耗可表示為

(3)

(3) 航程代價

UAV到達目標的航程越短,完成任務的時間代價就越小,航程代價需要在任務序列確定后,經過航跡規劃給出,因此該評價指標僅在航跡規劃時使用。令表示第架UAV的飛行距離,則整個任務的航路代價可表示為

(4)

2.3 任務約束

在整個任務分配過程中,需要考慮以下任務約束:

:任務時長約束,UAV最長航行距離不得超過其航程限制。

:任務分配約束,每一架UAV都必須分配一個任務,每一個任務僅由一架UAV執行。

:禁飛區約束,UAV在航行過程中,不可經過禁飛區域。

:任務數量約束,第架UAV最多攜帶個武器。

:飛行姿態角約束,UAV進行機動時,有最大偏航角。

2.4 任務規劃模型

綜上,本文所研究的UAVs任務分配問題,可表示為如下優化模型:

(5)

式中:和分別表示毀傷效果與損傷程度指標的權重系數,反映了二者的重要程度;可稱為任務效益指標;為航路指標;至描述了需要滿足的約束。

3 模型求解

3.1 求解框架

求解上述模型,理論上需要嵌套的兩層規劃去完成(見圖2)。上層規劃用于進行任務分配,即確定哪些UAVs執行哪些任務,主要滿足優化指標;下層規劃用于解決任務順序和航路規劃問題,即在已知UAVs需要打擊的目標集合的前提下,優化出最優的任務序列和對應的飛行航路,主要關心優化指標。為了達到全局最優,上層規劃和下層規劃往往是相互聯系和相互影響的,且在一定程度上,上層和下層的優化指標是相互矛盾的。當任務收益達到最大,可能航路代價并非最優;當選取了航路代價最優,則需要犧牲一些任務收益指標。

圖2 雙層任務規劃框架Fig.2 Bi-level mission planning framework

本文認為,整個任務分配的效益指標遠比航路指標重要。為提高規劃效率,本文根據問題特點,對問題進行了簡化,即上層規劃僅考慮效益指標,下層規劃僅考慮航路指標,規劃策略如圖3所示。

圖3 雙層任務規劃策略Fig.3 Strategy for Bi-level mission planning

在下層航路優化中,根據已知的任務目標集合進行任務序列窮搜,而后采用已有蟻群算法,進行點對點航路規劃,選取航路最優的任務序列為最終的任務執行方案,并給出對應的航路信息。

3.2 基于SAS的任務分配

任務分配為上層優化,任務分配的目的是優化出每一架UAV需要執行的具體任務的集合,而對具體的執行順序和飛行航路不關心。任務分配模型,可以從公式中分解得出:

find= ,=1,2,…,;=1,2,…,

(6)

max=-

(7)

(8)

(9)

(10)

(11)

式(6)表示任務分配的決策變量,式(7)表示任務效益指標,式(8)表示每個目標只能被分配給一架UAV,式(9)表示每架UAV都必須被分配目標,式(10)表示UAV具有多目標攻擊能力,最大攻擊數取決于自身攜帶的武器數量,式(11)表示所有目標都必須被分配給UAVs。

任務分配是一個典型的組合優化問題,SA算法是其求解方法之一。SA算法是一種通用的隨機搜索算法,是對局部搜索算法的擴展。與一般局部搜索算法不同,SA以一定的概率選擇鄰域中目標值相對較小的狀態,是一種理論上的全局最優算法。在實際應用中,SA算法易于陷入局部最優,因此需要根據具體問題進行有針對性的改進,以跳出局部最優。

本文主要用SA算法進行任務分配優化,并在基本算法基礎上拓展撒點算子,以跳出局部最優,下面對其關鍵步驟進行介紹。

(1) 編碼設計

如果直接以決策變量編碼,則是一個×維的矩陣,比較浪費空間,且不利于尋優搜索。為了便于鄰域搜索,本文的編碼設計為1×維的向量,為待打擊目標的數量。假如向量中第個元素的值為,則表示 =1。假如求解的規劃問題有5個任務,則一個狀態編碼如圖4所示。

圖4 狀態編碼示例Fig.4 Example for encoding

圖4中的編碼表示,任務1分配給UAV,任務2分配給UAV,任務3分配給UAV,任務4分配給UAV,任務5分配給UAV。

(2) 鄰域搜索

算法的編碼為整數編碼,且編碼需要滿足模型中的各種約束。在領域搜索的過程中,采取概率賦值的方式。具體方法如下(見圖5)。

圖5 鄰域搜索示例Fig.5 Neighborhood searching

隨機選取編碼中的個位置;

依次將個位置上的值,隨機賦予一個不同的值,賦值范圍為1～。

(3) 撒點算子設計

SA算法的缺點是易于陷入局部最優,因此在迭代的過程中,本文引入撒點算子,其基本原理是,在整個搜索空間隨機選取若干候選編碼,通過目標函數值計算,選取最優編碼為鄰域編碼。在傳統的SA算法中,僅根據當前編碼選取一個鄰域解作為候選點,不僅搜索空間有限,而且候選點數量很少。加入撒點算法后,首先鄰域搜索范圍擴展到了整個尋優空間,不局限于鄰域,即跳出了鄰域局部空間的束縛,其次撒點操作一次性并行地搜索多個候選點,有利于提高搜索效率,盡快找到更優的候選點。通過隨機撒點,可以盡快跳出局部最優,提高傳統算法的全局尋優能力。具體步驟如下:

判斷優化過程是否滿足無條件轉移,如果滿足,繼續下一步;

隨機生成pop個編碼(pop稱為撒點算子規模);

對編碼進行目標函數值計算,選取目標值最優的編碼為鄰域編碼,并賦值給當前編碼。

(4) 算法流程

SAS算法的具體流程如圖6所示。

圖6 SAS算法流程Fig.6 Flowchart for SAS

(5) 算法復雜度分析

與傳統的SA算法相比，本文所改進的SAS算法，主要是在鄰域搜索結束后，多了一個撒點算子操作，撒點操作過程中，需要進行目標函數值計算，且計算過程是并行的。假設計算一次目標函數的計算代價為，時間代價為，記傳統SA算法的計算代價為SA ()，時間代價為SA ()，則可推知，從時間上看，本文改進的SAS算法的時間代價為SA ()+iter·，即每一次迭代僅比傳統算法多了一個時間單位的代價。這是由于，盡管撒點算子過程中進行了多次目標函數值計算，但計算過程是并行的，總時間消耗僅多出一次目標函數值的計算時間。從計算復雜度上看，改進算法的計算代價為SA ()+iter·pop·，比傳統算法略高，且復雜度與撒點算子規模有關。

3.3 任務序列優化

當每個UAV的攻擊任務集合已知,則可進行下層優化,即任務序列優化。任務序列優化的目的是規劃出UAVs執行任務的順序以及對應的航路。下層優化的模型,可表述為

(12)

min=

(13)

s.t.∩∩

(14)

本文采用已有的蟻群算法進行航路規劃,蟻群算法在此不再贅述。下層優化的具體步驟如下:

針對第架UAV,根據已知的任務集合,窮搜可能的排序組合;

針對每一組任務序列組合,調用已有的蟻群算法,進行航路規劃,并記錄最優航路代價;

選取所有排序組合中航路代價最優的組合,作為最優任務序列輸出,并同時輸出飛行航跡。

4 仿真分析

本文的仿真不考慮UAV間的通信與在線協同問題，戰場環境威脅均簡化為數學模型，且假設UAV飛行為勻速飛行，不考慮飛行高度等因素。

4.1 任務分配仿真

(1) 算例配置

假設UAVs數量=6,任務目標數量=10,每架UAV攜帶的最大武器數量為=4(=1,2,…,),UAVs的毀傷概率和生存概率隨機給出,具體數值如表1和表2所示。定義==05。SA算法的參數值由表3給出。

表1 毀傷概率Table 1 Destructive probability

表2 生存概率Table 2 Survival probability

表3 SA算法參數設置Table 3 Parameter configuration for SA algorithm

(2) 優化參數影響分析

假設撒點算子規模始終為50,改變鄰域搜索過程中元素位置搜索數目,連續運行5次優化程序,其優化結果如表4所示。

表4 鄰域搜索參數對優化結果的影響Table 4 Optimization results with different neighborhood searching parameters

從表4可以看出,不論參數設置為1還是10,算法的搜索結果都相對穩定,總體上趨于較好的優化結果,且優化結果的方差不大。從表4還可看出,鄰域搜索的位置數目并不是越多越好,當搜索數目為1和3時,都能夠得到最優解4.025,當搜索數目變大時,雖然也能得到較好的優化結果,但不容易得到相對最優的結果。這是由于隨著搜索數目的增大,鄰域搜索空間也增大,在有限的搜索次數內,并不能保證搜到鄰域的最優值。從表4可以推斷出,當編碼有10個值時,鄰域搜索位置數目設置在3比較合適。

根據表4結果,將鄰域搜索位置數目設為3,改變撒點算子規模,連續運行5次優化程序,優化結果如表5所示。

表5 撒點算子規模對優化結果的影響Table 5 Optimization results with different shooting populations

撒點算子的設計,是為了解決SA算法容易陷入局部最優的問題。從表5可以看出,隨著撒點算子規模的增加,算法的尋優效果越來越好。這是由于撒點算子規模越大,搜索的空間越大,則跳出局部最優的概率越大。

圖7和圖8給出了表4和表5優化中最優結果的收斂過程。

圖7 鄰域搜索參數變化的收斂過程Fig.7 Convergence process with different neighborhood searching parameters

圖8 撒點算子規模變化的收斂過程Fig.8 Convergence process with different shooting populations

(3) 算法對比分析

圖9給出了本文的SA算法與傳統SA算法以及PSO算法的收斂對比。從圖9可以看出,本文提出的SAS算法收斂效果最好,傳統SA算法次之,傳統PSO算法最差。PSO算法更善于處理連續優化問題,傳統編碼對組合優化問題的適應性不強,且迭代次數較少,導致其優化效果較差。SAS算法由于設計了跳出局部最優的撒點算子操作,優化效果優于傳統SA算法。

圖9 不同優化算法的收斂過程對比Fig.9 Convergence process for different algorithms

(4) 優化結果與分析

從表4和表5中選取最優的一組優化結果,其任務分配情況如表6所示。

表6 最優分配結果Table 6 Optimal results for assignment

從表6中可以看出,優化的結果均滿足公式約束。任務大多趨于分配給UAV,這是由于在隨機給出的毀傷概率和生存概率中,UAV的數值都比較好。UAV的概率數值都較差,如果沒有任務數量約束,整個任務分配偏于將任務分配給其他UAVs,而非UAV。

4.2 任務序列優化仿真

本節根據表6的任務分配結果,進行任務序列優化。

(1) 算例配置

在任務序列規劃中,涉及到航跡的規劃,需要給出飛行環境。本算例中,飛行環境主要考慮無人機、目標的位置、飛行區域以及涉及到的環境、雷達和導彈威脅。任務目標的地理位置如表7所示,各威脅的編號、類型與坐標如表8所示。整個任務的執行區域限制在[0, 0] km到[60, 60] km范圍內。為了進行航跡規劃,需要對飛行區域進行地圖數字化,本文采用柵格法進行地圖建模,柵格離散化間隔為2 km。無人機初始位置為[2, 2] km。

表7 任務目標坐標Table 7 Coordinates for targets

表8 威脅分布Table 8 Distribution for threats

(2) 任務序列枚舉

從表6可知每架無人機的目標任務集合。第3.3節已給出了任務序列規劃的具體方法,首先需要對任務集合中的所有序列組合進行枚舉。如表9所示,UAV～UAV都只有一個目標任務,因此可能的任務序列組合只有一種。UAV有24種可能的組合方法,而UAV有2種。每一種可能的任務序列組合都將采用蟻群算法對其進行航跡規劃,記錄航程,其中航程最短的組合將最終被定為UAV需要執行的任務序列方案和飛行航跡方案。

表9 任務序列枚舉Table 9 Enumeration results for mission sequences

由于UAV～UAV只有一個任務目標,采用航跡規劃算法進行點對點航跡規劃即可,具體優化結果如圖10所示。UAV有兩個任務需要執行,可能的任務序列為[2, 7]和[7, 2]。當任務序列為[2, 7]時,最優飛行航跡如圖11所示,航程為68.08 km。當任務序列為[7, 2]時,最優飛行航跡如圖12所示,航程為87.94 km。因此,UAV的最佳任務序列為[2, 7]。UAV有24種可能的序列組合,經過優化,其最優任務序列為[1, 9, 3, 8],飛行航跡如圖13所示,航程為149.05 km。

圖10 UAV1～UAV4飛行航跡Fig.10 Trajectories for UAV1～UAV4

圖11 UAV6執行任務序列[2, 7]的飛行航跡Fig.11 Trajectory for UAV6 attacking targets [2, 7]

圖12 UAV6執行任務序列[7, 2]的飛行航跡Fig.12 Trajectory for UAV6 attacking targets [7, 2]

圖13 UAV5飛行航跡Fig.13 Trajectory for UAV5

5 結束語

UAVs的任務規劃包含任務分配、執行順序確定以及航跡優化等。為了達到任務規劃的全局最優,需要全盤梳理任務的各個方面,提出高效的優化策略。本文綜合考慮任務規劃過程中任務分配、執行順序確定以及航跡優化等方面的需求和相互間影響,首先從優化框架出發,設計了雙層互耦的任務規劃求解策略,而后將任務規劃模型分為上層任務分配和下層任務序列優化,并對每一層的優化方法和優化步驟進行了詳細設計;在任務分配問題中,基于SA算法,提出了可跳出局部最優的SAS算法,并詳細探討了算法參數的設計原則。通過仿真分析可知:① 本文提出的雙層規劃策略,可有效梳理3個層次的優化關系,利于優化求解。但需要注意的是,雙層規劃策略的應用以任務收益優先為前提,當航程等指標優先級較高時,需要對規劃策略進行進一步改進。② 本文提出的SAS算法可以跳出局部最優,有效進行任務分配優化。在算法參數設置過程中,鄰域搜索時的可變位置數目并不是越多越好,一般設置在編碼總數的1/3左右;而撒點算子規模的設置則是越大越好,規模越大,搜索的空間越大,則跳出局部最優的概率越大。

在進一步研究中，將更多考慮實際應用場景，考慮UAV間的協同、通信、復雜電磁環境、飛行高度等問題。