復雜環境下多目標多無人機協同任務規劃

張 哲，吳 劍,2，何 誠，穆忠偉

(1.南昌航空大學，南昌 330063；2.洪都航空工業集團650所，南昌 330024)

在復雜戰場環境中，多無人機協同任務規劃已成為提高無人機作戰自主性和作戰效能的關鍵技術[1]。尤其是在復雜戰爭環境下，面對威脅源和大量搜索目標群時，如何快速準確地協同任務規劃是當前的一大難題[2-5]。

針對多目標多無人機協同任務規劃問題，目前主要研究的模型有多車輛路徑(MVRP)[6-7]、多維多選擇背包[8]、多旅行商(MTSP)[9-10],混合整數線性規劃(MILP)[11-12]和動態網絡流優化(DNFO)[13]等。MVRP模型更多地描述任務分配中有關時間的約束，而未充分考慮無人機的動力學特性。MMKP和MTSP模型并未討論任務的異構性。MILP和DNFO模型僅適用于范圍小、目標數量少和環境威脅源單一的任務規劃問題。Mahesh等[14]提出的將多機協同問題抽象為多個相互獨立的TSP問題，優化指標為最短路線長度，然后利用模擬退火算法去進行解決，該方法雖然降低了問題的復雜程度，但是忽略了協同的本質。

本文在上述研究的基礎上，針對復雜環境中雷達站和無人機載荷約束之間的任務均衡性，在充分了解地形情況和敵方目標信息的情況下，建立了多目標多無人機協同任務規劃模型。將多目標規劃問題轉化為單目標規劃，并且運用主客觀賦權法計算各指標的權重。探討了利用改進遺傳算法去求解模型，加快了收斂速度，提高了任務規劃效率。最后根據任務載荷的約束，對規劃路線進行了優化，給出了多機協同的任務規劃方案。

1 多無人機協同任務規劃模型

某作戰部隊配有7個無人機基地，分別記為P01～P07，各基地均配備若干數量的FY系列無人機。為了完成目標偵查、通信中繼、作戰攻擊等任務，其中指派FY-1型無人機主要完成目標偵查及作戰攻擊，根據任務要求，無人機需完成偵查和打擊的目標群為A01～A10，每個目標群包含多個地面目標，周圍均配有雷達站。無人機基地的相關信息如表1所示。

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

1.1 多機協同任務規劃的目標函數

多無人機多目標協同任務規劃主要從時域協同和空域協同兩個方面進行建模分析，給出這兩方面的4個規劃目標函數。對于時域協同：以完成任務所需的時間代價為子目標函數，無人機從不同的基地出發，分別以不同時間點到達任務目標的指定位置，體現了無人機在任務規劃時間上的無縫銜接。對于空域協同：以無人機可飛行空域內滯留雷達區的路程、完成攻擊目標任務時的收益以及執行偵查任務時造成的威脅代價為各子目標函數，保障無人機能夠安全到達目標區域，避免防空威脅以及碰撞。

1)飛行總路程

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

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

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

(1)

2)攻擊目標收益

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

(2)

(3)

3)完成任務所需時間

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

t= maxti

(4)

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

(5)

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

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

(6)

1.2 任務規劃模型

多無人機協同任務規劃是多基地的無人機針對多目標群進行偵查和打擊等任務，實質上是多目標優化與決策問題[16]。通過建模分析，運用線性加權和法將多目標規劃轉化為單目標規劃問題。由于在轉化過程中各目標函數有不同的量綱，采用線性變換法進行歸一化處理，將各目標函數的量綱轉變為[0,1]內的具體數值。因此可以得到多無人機協同的任務規劃模型為：

(7)

約束條件：

(8)

式(7)、式(8)中：ω={ω1,ω2,ω3,ω4}為各目標函數所占的權重；d()表示無人機從目標群飛回基地的距離；M為無人機最大航程；s為燃料安全系數；xij∈{0,1}為決策變量，xij=1表示第i架無人機對第j個目標群執行任務；N表示目標群數量；Oi為第i架無人機的任務載荷。

約束條件使得無人機至少偵查一個目標，并且所有目標有且僅有一次被無人機偵查。因此，各無人機之間軌跡無重合?？紤]到無人機在各點之間飛行需要轉向，為增大安全性，經過初步計算一架無人機不能飛完全程，設定轉彎次數為目標數量的一般，即34次，每次轉彎角度為180°，目標群數量N為10，安全系數s為1.05。

2 基于改進遺傳算法的模型求解

2.1 算法改進方案

多無人機協同任務規劃模型的求解實質上可以看成是對多旅行商(MTSP)問題的求解。由于旅行商問題屬于NP問題，因此通常采用啟發式優化算法對模型進行求解。

由于傳統的遺傳算法在求解MTSP問題時，容易陷入局部最優解。為了提高算法的執行效率，較快得到全局最優解，對算法進行以下改進：1)只保留最優父代，加速收斂;2)采用多島遺傳形式[17]，保持解的多樣性;3)使用無性繁殖策略[18]，提升了收斂速度，并通過多種交叉和變異方式，避免提前收斂于局部最優解。

2.2 算法實現

2.2.1編碼

每一個體的染色體長度為n+m-1,其中染色體前n位為隨機的整數,呈亂序排列，按大小排序后即為無人機偵查各目標點的順序。后m-1位為斷點位置的標號，斷點用來表示目標在不同無人機之間的分配。一條染色體G={4,7,1,9,3,6,3,…|2,5}。其中該染色體對應的目標數為n，其對應的無人機數量為m=3，后半部分的斷點2和5表示三架無人機分別偵查攻擊以下標號的目標為：4→7; 1→9→3; 6→3→…→n。

2.2.2種群

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

2.2.3適應度計算及選擇策略

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

2.2.4遺傳運算

采用多種遺傳方式來生成子代，具體規則如下：

步驟(1)對換染色體前半段的任意兩個數;

步驟(2)對換染色體前半段的兩個數段，即同時將多個數進行對換;

步驟(3)對染色體前半段的數進行左移操作;

步驟(4)隨機更新染色體后半段;

步驟(5)同時進行步驟(1)和步驟(4);

步驟(6)同時進行步驟(2)和步驟(4);

步驟(7)同時進行步驟(3)和步驟(4);

步驟(8)染色體不變。

2.2.5終止規則

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

2.2.6算法流程圖

算法流程如圖1所示。

圖1 算法流程框圖

2.3 計算各指標的權重

通常計算權重的方法可以分為主觀賦權法和客觀賦權法。前者如層次分析法、專家調查法等，該方法反映了決策者的意向，導致了評價和結果具有很大的主觀隨意性。后者如主成分分析法、熵值法等，該方法雖然具有客觀的理論依據，但沒有考慮決策者的意向。故采取主客觀綜合賦權法[19](基于熵權的組合賦權法)確定各目標函數的權重。

通過將不同指標上的專家主觀信息與客觀信息進行融合，計算相鄰指標間的客觀熵權值之比，進而得到各指標的權重。具體步驟如下：

步驟1由專家確定指標的重要性排序。在指標體系準則層中共有L個準則，而在第i個準則層共有Mi項指標。專家需要對K個待評估對象給出不同準則下所有∑Mi個指標的重要性排序(i=1,2,…,L)。

步驟2計算各指標所對應的熵權值。設第k個待評估對象在第i個準則第j項指標下的數據為vij，特征比重為hijk，則

(9)

式(9)中：i=1,2,…,L;j=1,2,…,Mi;k=1,2,…,K。設eij為第i個準則層第j項指標的熵值，則：

(10)

第i個準則層第j項指標的熵權值為μij，則：

(11)

步驟3計算相鄰指標的重要程度。設ri, j-1為第i個準則中第j-1項指標的重要程度,則有：

(12)

式(12)中：i=1,2,…,L;j=2,…,Mi。

步驟4計算指標對準則的權重。設fi,Mi為第i個準則下第Mi項指標對準則i的權重，則：

(13)

第i個準則下其他Mi-1項指標的權重可通過其后一項指標的權重計算得到，即：

fi, j-1=ri, j-1·fi, j

(14)

步驟5計算指標權重。設μi為第i個準則的熵權，ri-1為相鄰的第i-1個準則相對于第i個準則的重要程度，則有：

(15)

(16)

設ωL為第L個準則的權重，則：

(17)

其他L-1個準則的權重為：

ωi-1=ri-1·ω

(18)

因此，第i個準則第j項指標的權重為：

ωij=fij·ωi

(19)

式(19)中：i=1,2,…,L;j=1,2,…,Mi。

多無人機協同任務規劃能力的評價指標體系如圖2所示。

圖2 任務規劃能力的評價指標體系框圖

3 仿真分析

為了驗證多無人機多目標任務協同規劃模型及改進遺傳算法，在PC機配置為Intel(R)Core i5-4210M @2.60 GHz,MatlabR2017a環境下完成模型和算法的仿真實驗。無人機上加載的S-1、S-2兩種載荷用于對目標群實現偵查和攻擊任務。設定無人機飛行速度為200 km/h，高度為1 500 m，最大飛行時間為10 h，無人機每次只能加載一種載荷。目標群數量N=10，目標點個數n=68,各目標函數的權重ω={0.352,0.287,0.145,0.216}，根據改進遺傳算法流程，設置最大迭代次數為200。計算得到了所有目標點間的任務規劃如圖3所示。

圖3 目標點間任務規劃結果

由于無人機上加載S-1和S-2兩種載荷，根據目標點間任務規劃的結果，分別對無人機加載兩種載荷后的航跡進行優化。給出了加載兩種載荷的無人機任務規劃示意圖如圖4和圖5。

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

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

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

加載S-1型載荷的無人機協同任務規劃仿真結果如圖6所示，A4目標群局部任務規劃仿真結果放大圖如圖7。

圖6 加載S-1型載荷的協同任務規劃仿真結果

加載S-2型載荷的無人機協同任務規劃仿真結果如圖8所示，A4目標群局部任務規劃放大圖如圖9，改進遺傳算法與傳統遺傳算法如圖10所示，協同任務規劃調度方案內容見表2。

由于載荷S-1為光學成像傳感器，采用廣域搜索模式對目標進行成像，達到一定的目標識別精度。載荷S-2是目標指示器，為制導炸彈提供目標指示，用于攻擊作戰任務。S-1載荷帶寬為2 km，S-2載荷要求距被攻擊目標的距離小于7.5 km，對每個目標安排S-1、S-2兩種載荷各自至少使用一次，而且兩種載荷對同一目標的偵查間隔不超過4 h。因此，仿真結果中兩種載荷對任務規劃路線優化的航跡點不同，實現了無人機目標偵查和作戰任務的協同規劃。

圖7 S1-A4目標群局部任務規劃放大圖

圖8 加載S-2型載荷的協同任務規劃仿真結果

圖9 S2-A4目標群局部任務規劃放大圖

圖10 兩種算法的比較

表2 多機協同任務規劃調度方案內容

4 結論

在分析影響任務規劃關鍵指標的基礎上，以考慮雷達站影響下無人機飛行總航程、攻擊目標收益、執行任務的威脅代價以及任務完成時間等指標為目標函數，建立了多機協同任務規劃模型。運用主客觀綜合賦權法確定了各指標所占比重，使得模型更加準確。結合改進的遺傳算法對模型進行求解，加快了收斂速度，任務規劃效率顯著提高。最后考慮到無人機的轉彎以及載荷約束，對任務規劃路線進行了優化。仿真結果驗證了本文方法的有效性。