復(fù)雜環(huán)境下多目標(biāo)多無人機(jī)協(xié)同任務(wù)規(guī)劃

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

(1.南昌航空大學(xué)，南昌 330063；2.洪都航空工業(yè)集團(tuán)650所，南昌 330024)

在復(fù)雜戰(zhàn)場環(huán)境中，多無人機(jī)協(xié)同任務(wù)規(guī)劃已成為提高無人機(jī)作戰(zhàn)自主性和作戰(zhàn)效能的關(guān)鍵技術(shù)[1]。尤其是在復(fù)雜戰(zhàn)爭環(huán)境下，面對威脅源和大量搜索目標(biāo)群時，如何快速準(zhǔn)確地協(xié)同任務(wù)規(guī)劃是當(dāng)前的一大難題[2-5]。

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

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

1 多無人機(jī)協(xié)同任務(wù)規(guī)劃模型

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

表1 無人機(jī)基地的相關(guān)信息

1.1 多機(jī)協(xié)同任務(wù)規(guī)劃的目標(biāo)函數(shù)

多無人機(jī)多目標(biāo)協(xié)同任務(wù)規(guī)劃主要從時域協(xié)同和空域協(xié)同兩個方面進(jìn)行建模分析，給出這兩方面的4個規(guī)劃目標(biāo)函數(shù)。對于時域協(xié)同：以完成任務(wù)所需的時間代價為子目標(biāo)函數(shù)，無人機(jī)從不同的基地出發(fā)，分別以不同時間點(diǎn)到達(dá)任務(wù)目標(biāo)的指定位置，體現(xiàn)了無人機(jī)在任務(wù)規(guī)劃時間上的無縫銜接。對于空域協(xié)同：以無人機(jī)可飛行空域內(nèi)滯留雷達(dá)區(qū)的路程、完成攻擊目標(biāo)任務(wù)時的收益以及執(zhí)行偵查任務(wù)時造成的威脅代價為各子目標(biāo)函數(shù)，保障無人機(jī)能夠安全到達(dá)目標(biāo)區(qū)域，避免防空威脅以及碰撞。

1)飛行總路程

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

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

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

(1)

2)攻擊目標(biāo)收益

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

(2)

(3)

3)完成任務(wù)所需時間

完成任務(wù)所需時間定義為:

t= maxti

(4)

式(4)中，ti為第i架無人機(jī)完成規(guī)劃任務(wù)所花費(fèi)的時間?？紤]各無人機(jī)間任務(wù)分配和載荷資源的合理性，給出時間代價函數(shù)L3，即：

(5)

4)執(zhí)行任務(wù)時造成的威脅

當(dāng)無人機(jī)協(xié)同飛行時，假設(shè)第i架無人機(jī)經(jīng)過目標(biāo)群Cj后的生存概率為PBi,則PBi=1-PKj。對任一無人機(jī)來說，執(zhí)行n個任務(wù)時造成的威脅代價L4：

(6)

1.2 任務(wù)規(guī)劃模型

多無人機(jī)協(xié)同任務(wù)規(guī)劃是多基地的無人機(jī)針對多目標(biāo)群進(jìn)行偵查和打擊等任務(wù)，實(shí)質(zhì)上是多目標(biāo)優(yōu)化與決策問題[16]。通過建模分析，運(yùn)用線性加權(quán)和法將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃問題。由于在轉(zhuǎn)化過程中各目標(biāo)函數(shù)有不同的量綱，采用線性變換法進(jìn)行歸一化處理，將各目標(biāo)函數(shù)的量綱轉(zhuǎn)變?yōu)閇0,1]內(nèi)的具體數(shù)值。因此可以得到多無人機(jī)協(xié)同的任務(wù)規(guī)劃模型為：

(7)

約束條件：

(8)

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

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

2 基于改進(jìn)遺傳算法的模型求解

2.1 算法改進(jìn)方案

多無人機(jī)協(xié)同任務(wù)規(guī)劃模型的求解實(shí)質(zhì)上可以看成是對多旅行商(MTSP)問題的求解。由于旅行商問題屬于NP問題，因此通常采用啟發(fā)式優(yōu)化算法對模型進(jìn)行求解。

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

2.2 算法實(shí)現(xiàn)

2.2.1編碼

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

2.2.2種群

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

2.2.3適應(yīng)度計(jì)算及選擇策略

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

2.2.4遺傳運(yùn)算

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

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

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

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

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

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

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

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

步驟(8)染色體不變。

2.2.5終止規(guī)則

將最大迭代次數(shù)作為終止條件，設(shè)置最大迭代次數(shù)為200。

2.2.6算法流程圖

算法流程如圖1所示。

圖1 算法流程框圖

2.3 計(jì)算各指標(biāo)的權(quán)重

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

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

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

步驟2計(jì)算各指標(biāo)所對應(yīng)的熵權(quán)值。設(shè)第k個待評估對象在第i個準(zhǔn)則第j項(xiàng)指標(biāo)下的數(shù)據(jù)為vij，特征比重為hijk，則

(9)

式(9)中：i=1,2,…,L;j=1,2,…,Mi;k=1,2,…,K。設(shè)eij為第i個準(zhǔn)則層第j項(xiàng)指標(biāo)的熵值，則：

(10)

第i個準(zhǔn)則層第j項(xiàng)指標(biāo)的熵權(quán)值為μij，則：

(11)

步驟3計(jì)算相鄰指標(biāo)的重要程度。設(shè)ri, j-1為第i個準(zhǔn)則中第j-1項(xiàng)指標(biāo)的重要程度,則有：

(12)

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

步驟4計(jì)算指標(biāo)對準(zhǔn)則的權(quán)重。設(shè)fi,Mi為第i個準(zhǔn)則下第Mi項(xiàng)指標(biāo)對準(zhǔn)則i的權(quán)重，則：

(13)

第i個準(zhǔn)則下其他Mi-1項(xiàng)指標(biāo)的權(quán)重可通過其后一項(xiàng)指標(biāo)的權(quán)重計(jì)算得到，即：

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

(14)

步驟5計(jì)算指標(biāo)權(quán)重。設(shè)μi為第i個準(zhǔn)則的熵權(quán)，ri-1為相鄰的第i-1個準(zhǔn)則相對于第i個準(zhǔn)則的重要程度，則有：

(15)

(16)

設(shè)ωL為第L個準(zhǔn)則的權(quán)重，則：

(17)

其他L-1個準(zhǔn)則的權(quán)重為：

ωi-1=ri-1·ω

(18)

因此，第i個準(zhǔn)則第j項(xiàng)指標(biāo)的權(quán)重為：

ωij=fij·ωi

(19)

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

多無人機(jī)協(xié)同任務(wù)規(guī)劃能力的評價指標(biāo)體系如圖2所示。

圖2 任務(wù)規(guī)劃能力的評價指標(biāo)體系框圖

3 仿真分析

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

圖3 目標(biāo)點(diǎn)間任務(wù)規(guī)劃結(jié)果

由于無人機(jī)上加載S-1和S-2兩種載荷，根據(jù)目標(biāo)點(diǎn)間任務(wù)規(guī)劃的結(jié)果，分別對無人機(jī)加載兩種載荷后的航跡進(jìn)行優(yōu)化。給出了加載兩種載荷的無人機(jī)任務(wù)規(guī)劃示意圖如圖4和圖5。

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

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

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

加載S-1型載荷的無人機(jī)協(xié)同任務(wù)規(guī)劃仿真結(jié)果如圖6所示，A4目標(biāo)群局部任務(wù)規(guī)劃仿真結(jié)果放大圖如圖7。

圖6 加載S-1型載荷的協(xié)同任務(wù)規(guī)劃仿真結(jié)果

加載S-2型載荷的無人機(jī)協(xié)同任務(wù)規(guī)劃仿真結(jié)果如圖8所示，A4目標(biāo)群局部任務(wù)規(guī)劃放大圖如圖9，改進(jìn)遺傳算法與傳統(tǒng)遺傳算法如圖10所示，協(xié)同任務(wù)規(guī)劃調(diào)度方案內(nèi)容見表2。

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

圖7 S1-A4目標(biāo)群局部任務(wù)規(guī)劃放大圖

圖8 加載S-2型載荷的協(xié)同任務(wù)規(guī)劃仿真結(jié)果

圖9 S2-A4目標(biāo)群局部任務(wù)規(guī)劃放大圖

圖10 兩種算法的比較

表2 多機(jī)協(xié)同任務(wù)規(guī)劃調(diào)度方案內(nèi)容

4 結(jié)論

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