多無人機多目標協同近距任務分配研究*

張 哲，吳 劍，何 誠

(南昌航空大學信息工程學院， 南昌 330063)

0 引言

在復雜的戰場環境中，當單架無人機常常難以完成指定的任務時，需要多架無人機進行協同任務分配以保證無人機的作戰效能和作戰自主性[1]。當無人機同時面對雷達威脅源和大量近距的目標群時，如何快速準確地進行協同任務分配更是當前的一大難題[2-4]。

針對多無人機協同任務分配問題，諸多文獻提出了一系列的模型及算法。在模型方面，如運籌學中的多旅行商(MTSP)模型[5-6]和混合整數線性規劃(MILP)模型[7-8]等。然而，MTSP模型并未討論任務的異構性，忽略了任務與不同時間節點的關系。MILP模型僅適用于范圍小、任務目標數量少的任務分配問題。在算法方面，文獻[9]提出了一種周期性快速搜索的遺傳算法來解決任務分配問題，但是該算法僅僅驗證了在目標數量少、范圍小的環境下有較快的收斂速度，而當目標范圍和數量較大時，并不能體現該算法的優越性。文獻[10-13]研究了一系列智能優化算法及其改進方法等，如蟻群算法、模擬退火算法和量子粒子群算法等，這些算法在求解過程中仍存在陷入局部最優、計算時間較長、解空間規模大和收斂速度較慢等局限性。

文中建立了基于混合粒子群算法的多機協同任務分層分配模型。將任務分解為3層，即多目標群之間任務分配、各群內目標搜索路線分配和無人機載荷約束下的路線優化，從而將多目標規劃問題轉化為單目標規劃。利用混合粒子群算法(GA-PSO)去求解模型，該算法摒棄了傳統粒子群算法中的通過跟蹤極值來更新粒子位置，而是引入了遺傳算法中的交叉變異操作來搜索最優解。

1 分層任務分配模型

1.1 問題描述

多無人機多目標近距協同任務分配問題的實質是多約束條件的多目標優化與決策問題。針對這類問題，考慮無人機執行任務時的飛行總時間、個體載荷、自身協同約束和環境威脅約束[14]等進行建模分析。

假設有7個無人機基地，各基地均配備若干數量的FY-1型無人機，主要完成目標偵察和作戰攻擊。根據任務要求，無人機需完成偵察和打擊的目標群為A01～A10，每個目標群包含多個地面目標，周圍均配有雷達站。無人機基地的相關信息如表1。

表1 無人機基地的相關信息

1.2 多目標群間任務分配模型

1.2.1 目標函數

1)飛行總路程

設一個賦權無向完全圖G=(C,X,D),目標群集合、邊集合分別為C={c1,c2,…,cn}和X={Xij|i,j=0,1,2,…,n},Xij為目標群Ci到目標群Cj的邊,表示該條飛行線路是否應該執行。距離集合D={dij|i,j=1,2,…,n}表示目標群Ci到目標群Cj的距離。

給定m架無人機，無人機從任一基地bi出發。首先飛向目標群Ci，沿一條路徑偵察并且從目標群Cj(Ci≠Cj)離開。每架無人機都至少到達一個目標群，任意目標群都需要被無人機偵察且僅被偵察一次。求m條路徑，使得m架無人機的飛行總路程L1最小。在討論雷達對無人機協同飛行的影響時，可以將問題抽象為二維平面的路線規劃問題，使得無人機在敵方雷達探測范圍內的飛行路徑最短。由于多架無人機從不同的基地起飛，且每架無人機到達第一個目標群和離開最后一個目標群都會增加滯留在雷達探測區內的路程2R(R為雷達探測半徑)。

令Si={cin,c2,…,cout}為第i架無人機飛行路線，其中cin和cout為第i架無人機偵查路線的起點和終點。求總路線S={s1,s2,…,sm}，使得:

(1)

2)攻擊目標收益

攻擊目標收益是指多無人機在協同完成任務時對目標造成的毀傷價值。它可定義為目標價值和毀傷概率的函數。該函數指向了無人機協同任務攻擊時的作戰效能最大化。記第i架無人機攻擊目標群Cj所帶來的效益為P，則

P=Vtj·P(Ai)

(2)

式中：Vtj為目標群Cj的價值，P(Ai)為第i架無人機對目標群Cj的擊毀概率。即：

minL2=1-Vtj·P(Ai)

(3)

3)完成任務所需時間

完成任務所需時間定義為:

t=maxti

(4)

式中：ti為第i架無人機完成規劃任務所花費的時間，考慮各無人機間任務分配和載荷資源的合理性，給出時間代價函數L3，則

(5)

4)執行任務時造成的威脅

當無人機協同飛行時，假設第i架無人機經過目標群Cj后的生存概率為P(Bi),則P(Bi)=1-P(Kj)。對任一無人機來說，執行n個任務時造成的威脅代價L4符合：

(6)

式中：Vui為第i架無人機的價值；P(Kj)為目標群Cj擊毀無人機的概率。

1.2.2 任務分配模型

通過建模分析,可以得到第一層任務規劃，即多目標群任務規劃模型為：

minf=ω1·L1+ω2·L2+ω3·L3+ω4·L4

(7)

約束條件為：

(8)

式中：ω1,ω2,ω3,ω4為各目標函數所占的權重；dis( )表示無人機從目標群飛回基地的距離；M為無人機最大航程；s為燃料安全系數；xij∈{0,1}為決策變量，xij=1表示第i架無人機對第j個目標群執行任務；N表示目標群數量；Oi為第i架無人機的任務載荷。約束條件使得無人機至少偵察一個目標群，并且所有目標群有且僅有一次被無人機偵察。因此各無人機之間軌跡無重合。

1.3 各群內目標搜索路線分配

在確定了無人機對多目標群的任務路線后，對單個目標群內部進行路線規劃，即第二層任務規劃。對于單個目標群內的多個目標點，使得無人機遍歷所有目標點，且每個目標點只被偵察一次。具體路線分配策略如下：

Step1:分別規劃所有目標群內的路線，并確定出入口。

Step2:計算在第一層規劃獲得的路線中相鄰的兩個目標群質心距離。

Step3:相鄰兩個目標群的出入口有4個，計算4個出入口在兩質心連線上的投影。

Step4:選擇兩質心連線上投影距離最短的兩個出入口作為兩個目標群之間的路線。

1.4 載荷約束下的路線優化

確定了無人機在各目標群內的路線順序后，針對無人機分別加載的S-1型和S-2型載荷進行路線優化。具體如圖1和圖2。

圖1 加載S-1型載荷航跡示意圖

圖2 加載S-2型載荷航跡示意圖

兩圖中虛線為目標點間規劃的結果，實線為根據兩種不同載荷限制而規劃的無人機航跡。對于加載S-1型載荷：無人機從基地飛向目標1過程中，直接到達目標1所在圓的切點，然后依次飛向目標2、3對應的切點直至偵察任務完成后飛回基地。對于加載S-2型載荷：無人機從基地直接到達與目標1所在圓的交點，完成對目標1的攻擊后，飛往目標2，直接到達目標2所在圓的交點，直至最終飛回基地。線段a和線段b分別為無人機根據最短線飛向目標1和目標2的路徑。線段c是無人機完成對目標1攻擊任務后飛向目標2的路徑。

2 混合粒子群算法

2.1 算法改進方案

多機協同的任務分層分配模型的求解實質上可以看成是對MTSP問題的求解。由于MTSP問題屬于NP難題[15]，若運用精確的求解方法，其計算量會隨著網格數量的增大呈指數性增長。因此通常采用一些啟發式優化算法來進行求解。

由于傳統粒子群算法是通過追隨個體極值和種群極值完成尋優，雖然操作簡單，且能夠快速收斂，但是隨著迭代次數的不斷增加，在種群收斂集中的同時，各粒子也越來越相似，出現粒子貧化現象，導致陷入局部最優解中無法跳出。對于標準的遺傳算法來說，在求解MTSP問題時通過交叉變異，雖然能夠保證解的多樣性，但可行解的數目為(n+m-1)!，耗時巨大且全局搜索能力不強。因此，為了提高算法的執行效率，增大收斂于全局最優解的可能性，保證解空間的多樣性，采用GA-PSO算法來實現模型求解。

2.2 算法實現

2.2.1 個體編碼

粒子個體編碼采用整數編碼的方式，染色體長度為n+m-1,其中染色體前n位為隨機的整數呈亂序排列，按大小排序后即為無人機偵察各目標點的順序。后(m-1)位為斷點位置的標號，斷點用來表示目標在不同無人機之間的分配。

2.2.2 種群初始化

將種群分為多個組，每個組的個體數量為10，組的數量根據模型需要設置為15個。每組內的個體之間相互交叉無障礙，交叉和變異概率pc為0.9，pi為0.01，即組中個體有很小的幾率逃逸到另一個組中。

2.2.3 適應度計算及選擇策略

適應度函數為各目標函數，取適應度函數最高(目標函數最小)的個體為父代。為了加速收斂，直接刪除該群中其他的個體。

2.2.4 交叉操作和變異操作

采用多種遺傳方式[16-18]來生成子代，具體規則如下：1)對換染色體前半段的任意兩個數;2)對換染色體前半段的兩個數段，即同時將多個數進行對換;3)對染色體前半段的數進行左移操作;4)隨機更新染色體后半段;5)同時進行Step1和Step4;6)同時進行Step2和Step4;7)同時進行Step3和Step4;8)染色體不變。

利用上述8種規則產生新個體，得到的新個體采用了保留優秀個體策略，只有當新粒子適應度值優于舊粒子時才更新粒子。

2.2.5 算法終止規則

將最大迭代次數作為終止條件，設置最大迭代次數為200。

2.2.6 算法流程圖

圖3 混合粒子群算法流程圖

3 仿真分析

3.1 分層任務分配仿真

為了驗證模型和算法的合理性和高效性，在Windows 10操作系統上，PC機配置為Intel(R) Core i5-4210M @2.60 GHz，基于MatlabR2017a環境下完成仿真實驗。各基地配置一定數量的FY-1型無人機，機上加載的S-1、S-2兩種載荷用于對目標群完成偵察和攻擊任務。設定無人機速度為200 km/h，高度為1 500 m，最大飛行時間為10 h，無人機每次只能加載一種載荷。目標群數量N=10，目標點個數n=68,各目標函數的權重ω={0.276,0.182,0.235,0.307}，根據混合粒子群算法的流程，計算得到了第一層、第二層和第三層任務分配如圖4、圖5、圖6。

圖4 各目標群之間任務規劃

圖5 群內目標點間任務規劃

圖6 載荷約束下的路線優化

3.2 全局任務分配仿真

基于全局優化的思想，將所有目標點統一規劃，不考慮目標的聚散情況，直接求出各目標點之間的任務分配路線如圖7。

圖7 全局任務分配的路線

3.3 任務分配模型和算法對比

混合粒子群算法和標準粒子群算法對比如圖8。分層任務分配的調度方案見表2，全局任務分配調度方案見表3，兩種任務分配差異見表4。

圖8 適應度變化

表2 多機協同分層任務分配方案

表3 多機協同全局任務分配方案

表4 兩種任務分配模型對比

4 結論

研究了多目標多無人機近距的協同任務分配問題。在模型上，考慮了雷達威脅和密集目標群對無人機協同任務分配的影響，建立了任務分層分配模型，給出了3層的設計方案，即各目標群之間任務分配、各目標群內的目標進行了路線分配和在載荷約束條件下的路線優化；在算法上，針對傳統遺傳算法和粒子群算法存在的局限性，提出了一種混合粒子群算法(GA-PSO)來求解任務分配模型。仿真結果表明：1)分層任務分配模型與全局任務分配模型相比，任務分配的效率更高，任務分配花費時間為全局分配的90.1%，計算耗時為全局分配的15.1%。2)分層分配模型適用于解決范圍大、目標數量多和威脅源覆蓋廣的任務分配問題中，不再僅限于前人研究的范圍小和目標數量少的情況。3)提出的混合粒子群算法比傳統的粒子群算法更具優越性，加快了解的收斂速度，引入了遺傳算法中的交叉變異操作，搜索最優解的能力更強。4)提出的模型和改進算法很好地解決了多機協同任務分配問題。上述研究對于無人機在復雜戰場環境中迅速作出反應和戰略調整具有現實意義。