異構UAV編隊反雷達作戰(zhàn)中任務分配方法

林君燦, 賈高偉, 侯中喜

(國防科技大學空天科學學院, 湖南 長沙 410073)

0 引 言

防空雷達是空情預警的核心裝備,各類防空雷達裝備技術的快速發(fā)展,使得傳統(tǒng)電子戰(zhàn)飛機的作戰(zhàn)效能大大降低。同時,傳統(tǒng)的電子戰(zhàn)飛機雷達反射截面積較大,導致隱身性能差,易被發(fā)現(xiàn)與攻擊。

小型無人飛行器系統(tǒng)具有尺寸小、成本低、突防能力強等特點,且雷達散射回波通常較弱,能夠遂行復雜電磁環(huán)境下的電子干擾、誘騙及攻擊任務。同時,隨著無人機自主控制能力的提高,無人機編隊戰(zhàn)術引起了廣泛關注。將不同載荷不同平臺的無人機編隊(異構無人機編隊)用于對敵方雷達陣地實施偵察、定位、打擊、評估,是摧毀敵方防空預警系統(tǒng)的重要作戰(zhàn)樣式,受到國內(nèi)外的高度關注。

在異構無人機編隊的應用中,任務分配是頂層的規(guī)劃設計,研究意義重要[1]。

國外的研究團隊設計建立了多類任務分配模型,包括車輛路徑問題(vehicle routing problem,VRP)模型[2]、多旅行商問題(multiple traveling salesman problem,MTSP)模型[3]、混合整數(shù)線性規(guī)劃(mixed integer linear programming,MILP)模型[4]等。應用MILP方法可以納入時間等連續(xù)約束條件,可以精確得到更加符合實際情況下的任務分配問題的最優(yōu)解。文獻[5]利用MILP模型分析解決了多個相同無人機(同構無人機)執(zhí)行廣域搜索地攻擊任務分配問題。此外,文獻[6]將遺傳算法應用于多無人機任務分配問題上,凸顯了遺傳算法的計算時效性。

國內(nèi)方面,文獻[7]結合基于時間窗的MILP任務分配模型,給出多架同構無人機協(xié)同對地攻擊優(yōu)化問題的任務分配方案。文獻[8]在MILP模型中加入目標的威脅因素, 提高了完成任務的準確性。文獻[9]通過對適應度值做了標定,改進了遺傳算法,解決了多約束下多無人機協(xié)同任務分配問題。文獻[10]采用一種改進的非支配排序遺傳算法,任務分配結果的Pareto最優(yōu)解集。

對比發(fā)現(xiàn),在多無人機任務分配方法研究中,MILP和遺傳算法是兩類常用的方法[11-15]?，F(xiàn)有的MILP類方法大多應用在同構無人機編隊間的任務分配,未考慮異構無人機編隊在飛行平臺差異化、載荷功能差異化、時空協(xié)同復雜化方面的影響[16];而現(xiàn)有應用于任務分配的遺傳算法及其改進型,未考慮異構無人機編隊的任務功能多樣化以及嚴格的時間窗約束。為了解決異構無人機編隊復雜的任務分配問題,有必要對現(xiàn)有MILP方法和遺傳算法進行改進。本文提出了一種基于時間窗的異構無人機編隊MILP模型,建立了無人機之間、執(zhí)行任務之間合理的協(xié)同約束關系。此外,提出了基于時間窗的多層編碼遺傳算法實現(xiàn)異構無人機編隊任務分配,結合時空四維約束,清晰地表達出異構無人機編隊執(zhí)行任務時的時序關系。

1 問題描述

異構無人機編隊對敵方雷達陣地進行攻擊作戰(zhàn)過程中,編隊內(nèi)的無人機能夠獨立進行搜索、分類、攻擊、評估等任務。當編隊中任何一架無人機進行信息更新(例如發(fā)現(xiàn)一個新雷達目標時),編隊內(nèi)的無人機均能共享該信息。當發(fā)現(xiàn)潛在或可疑的目標時,啟動分類任務。分類是從另一個觀察視角對目標進行第二次搜索探測,從而提高目標識別的置信水平。待可疑目標被分類確認后,對其執(zhí)行攻擊任務。在本想定中,執(zhí)行攻擊任務的無人機通過自身攜帶的彈藥部摧毀目標。

一般地,對雷達站目標的打擊需要在特定的時間窗口內(nèi)進行(例如雷達的開機時間內(nèi))。隨后還需由另一架飛機進行探測核實以確認目標是否已被摧毀。

任務描述如下:在某作戰(zhàn)區(qū)域內(nèi),我方區(qū)域內(nèi)分布有V架無人機,敵方區(qū)域上分布N個地面雷達站,我方無人機對敵方區(qū)域進行搜索,在被探測到的敵方雷達站上依次執(zhí)行分類,攻擊和毀傷評估任務,在滿足無人機分配邏輯和任務到達先后次序的前提下,總的任務執(zhí)行時間最小,沒有分配到任務或完成任務的無人機繼續(xù)對目標進行搜索。

結合實際作戰(zhàn)情況,想定如下:①地面雷達站為固定目標,位置坐標均已知,無人機當前位置坐標也已知;②同一個目標上的任務執(zhí)行順序為:先分類后攻擊再評估;③同一架無人機在同一個目標上最多執(zhí)行兩次任務,即允許執(zhí)行分類任務后立刻執(zhí)行攻擊任務;④無人機攻擊目標后自爆自毀,將不再接受任務分配;⑤由于飛行時間遠大于執(zhí)行任務的時間,故忽略任務執(zhí)行時間。

2 基于MILP模型的任務分配

基于MILP模型的任務分配描述如下,假設有N+V+1個節(jié)點:N個目標節(jié)點、V個無人機源節(jié)點和一個搜索節(jié)點。節(jié)點1,2,…,N對應N個目標位置,節(jié)點N+1,N+2,…,N+V對應V個無人機源節(jié)點,節(jié)點N+V+1是搜索節(jié)點。當下一步?jīng)]有別的任務指派給無人機時,將使用搜索節(jié)點,當所有任務都被執(zhí)行或者沒有指派其他的任務時,將到達搜索節(jié)點。實際上,當一個無人機到達搜索節(jié)點時,它將執(zhí)行對作戰(zhàn)區(qū)域的搜索任務。

2.1 決策變量

表1 MILP決策變量

2.2 目標函數(shù)

≤tf,j=1,2,…,N

(1)

代價函數(shù)是對所有目標執(zhí)行完任務的總時間最小化,然而,只要對最后一個目標執(zhí)行任務時沒有延遲,該代價函數(shù)就不會對單個目標執(zhí)行任務時產(chǎn)生的延遲進行補償。因此,為提高性能,可以增加一個小的權重,以激勵對每個單獨目標也盡快執(zhí)行完任務。這樣,代價函數(shù)變?yōu)?/p>

(2)

2.3 約束條件

將MILP模型應用于異構無人機任務分配問題的最大難點是把約束條件轉化為合理的數(shù)學表達式。實現(xiàn)所期望的飛行器行為需要囊括必要的約束條件。完整的約束條件集合包括非時間約束和時間約束兩種:

(1) 對于每個目標,3個任務都只能完成一次:

(3)

和

(4)

(2) 每個目標j的任務k最多只能由一架UAV執(zhí)行:

≤1,k=1,3

(5)

和

≤1

(6)

(3) 每個UAVv從外部最多訪問一次目標節(jié)點j:

≤1

(7)

(4) 每個UAVv只能進入搜索節(jié)點一次:

≤1

(8)

(5) 每個UAVv最多離開節(jié)點j最多一次:

≤1

(9)

(6) 由于UAVv執(zhí)行一次攻擊任務之后,就不能再使用了,這樣,每個UAVv最多只能攻擊一個目標。UAV最多進入目標j一次,因此它不能攻擊目標節(jié)點j再離開該節(jié)點:

≤1

(10)

和

(11)

(7) 如果UAVv對目標節(jié)點j執(zhí)行分類任務,則該無人機必須離開目標節(jié)點或者對目標節(jié)點j執(zhí)行攻擊任務:

(12)

(8) 所有的UAV必須離開它們的源節(jié)點,即使是被指派直接飛往搜索節(jié)點:

(13)

(9) UAVv不能離開尚未指派進入的節(jié)點j:

(14)

(10) 一個UAV不能從節(jié)點j出來再攻擊目標j,除非它進入節(jié)點j的目的是執(zhí)行分類任務:

(15)

對于式(1)～式(11),其中i=1,2,…,N+V;j=1,2,…,N;v=1,2,…,V;k=1,2,…,K。

(11) 對于時間約束的線性關系表示可以采用一系列的線性不等式約束。令

(16)

為所有飛行器中最長的剩余飛行時間。這樣線性時間約束可以表示為

(17)

(18)

(19)

(20)

式中,i=1,2,…,N;j=1,2,…,N;i≠j;v=1,2,…,V;k=1,3。

(12)另外對于飛行器v對目標j既執(zhí)行分類任務又執(zhí)行攻擊任務的情況,還需要另外的線性時間約束:

(21)

(22)

(23)

(24)

式中,i=1,2,…,N;j=1,2,…,N;i≠j;v=1,2,…,V。

(13) 每個UAV執(zhí)行的第一個任務,其約束如下:

(25)

(26)

式中,i=1,2,…,N;v=1,2,…,V;k=1,2,3。

(14)任務優(yōu)先級次序必須滿足:

(27)

(28)

(15)在同一個目標上的兩個相鄰任務(如分類和攻擊任務,攻擊和毀傷評估任務)間由于信號延遲或者煙霧干擾等原因,中間需要加入時間延遲間隔α[α1,α2],可有如下約束:

(29)

(30)

建立了MILP模型后,通過求解約束優(yōu)化方程,能夠得到任務分配結果。

2.4 仿真分析

表2 目標任務信息

表3 目標任務執(zhí)行時間窗

表4 無人機性能參數(shù)

對上述MILP問題利用LINGO軟件求解,用時為30 min,求解結果如下:

(1) 決策變量

其余為0;

(2) 搜索任務決策變量

其余為0。

(3) 連續(xù)時間變量:任務出發(fā)時刻(min)

t1=44.7,t2=38.7,t3=33.4,

t7=19.1,t8=22.4,t9=31.8,t10=29.2

其余UAV出發(fā)時間為任務開始時刻。

(4) 目標任務結束時刻(min)

上述任務分配結果如圖1所示。

圖1 MILP最優(yōu)任務分配結果Fig.1 Optimal task assignment of MILP

圖1表示的任務分配為10架異構無人機編隊4個目標時的最優(yōu)任務分配: UAV-01和UAV-02分別在任務開始44.7 min和38.7 min后出發(fā),分別經(jīng)過45.3 min和31.3 min到達目標3和目標1,并對他們執(zhí)行毀傷評估任務;UAV-03在任務開始33.4 min后出發(fā),經(jīng)過36.6 min到達目標2執(zhí)行毀傷評估任務,又經(jīng)過21.2 min達到目標4執(zhí)行毀傷評估任務;UAV-04、UAV-05、 UAV-06未分配到任務,故一直呈編隊狀態(tài)執(zhí)行搜索任務;UAV-07在任務開始19.1 min后出發(fā),經(jīng)過32.6 min到達目標2執(zhí)行分類任務,隨后對目標2執(zhí)行攻擊任務,自爆;UAV-08在任務開始19.1 min后出發(fā),經(jīng)過35.9 min到達目標1執(zhí)行分類任務,隨后對目標1執(zhí)行攻擊任務,自爆;UAV-09在任務開始31.8 min后出發(fā),經(jīng)過43.2 min到達目標3執(zhí)行分類任務,隨后對目標3執(zhí)行攻擊任務,自爆;UAV-10在任務開始29.2 min后出發(fā),經(jīng)過45.8 min到達目標4執(zhí)行分類任務,隨后對目標3執(zhí)行攻擊任務,自爆。

3 基于時間窗的多層編碼遺傳算法

3.1 算法描述

為避免前述MILP模型優(yōu)化方法的復雜性,并加快一個良好可行方案的收斂速度,可以采用遺傳算法。該類方法不需要計算問題的梯度,可以并行運算,且不會陷入局部極小點,但也可能得不到最優(yōu)方案。

基于時間窗的多層編碼遺傳算法中染色體的編碼是求解過程中的一個主要工作,染色體可以充分表達簡單問題的潛在解;然而,對于較復雜的多目標、多約束優(yōu)化求解問題,染色體則難以充分表達問題的解。為了解決這個問題,我們改進了編碼方式,提出了多層編碼遺傳算法,把染色體編碼從一層拓展為多層,每層編碼表達一個或多個約束關系,多層編碼共同表達了問題的完整解。

本文染色體編碼方式為整數(shù)編碼,每個染色體個體映射為目標的執(zhí)行順序和無人機編號。針對本文的問題,我們?nèi)∪旧w為二層編碼,當目標總數(shù)為n,每個目標需要執(zhí)行k項任務,則染色體的長度為2×n×k。其中,第一層染色體編碼表示所有目標的執(zhí)行順序,第二層編碼表示執(zhí)行上層對應位置對應的任務的無人機編號。以如下個體為例:

解碼后任務順序表示為:301 302 101 201 303 401 102 402 202 103 203 403。以301為例,其中3表示目標編號,01表示任務編號。從中可以看出,染色體的長度為12×2,任務分配結果如下:UAV-01首先攻擊目標3,然后對目標2進行毀傷評估;UAV-02對目標4執(zhí)行分類任務,然后再以自爆自毀的方式攻擊目標1;UAV-03和UAV-04分別對目標3和目標1執(zhí)行分類任務,然后再執(zhí)行毀傷評估任務;UAV-05和UAV-06都以自爆自毀的方式對分別目標2和目標4執(zhí)行打擊任務;UAV-07對目標2執(zhí)行分類任務后,對目標3執(zhí)行毀傷評估任務。

在無人機任務規(guī)劃過程中,通常有某個任務要求必須在某個指定的時間范圍內(nèi)完成,則該時間范圍就稱為時間窗約束。異構無人機編隊在反雷達作戰(zhàn)中,對敵方雷達站執(zhí)行打擊任務時,打擊時間設定在雷達的開機時間[t,t+Δt1]窗口內(nèi),對于打擊效果的毀傷評估任務為了避免煙塵等影響,需要在打擊任務結束后的Δt2時間內(nèi)進行,超過這兩個時間窗口限制,目標狀態(tài)將發(fā)送改變,導致任務效能降低。

3.2 算法流程

基于時間窗的多層編碼遺傳算法流程描述如下。

步驟1初始化參數(shù)

種群初始化,確定初始種群規(guī)模、選擇概率、交叉概率、變異概率、最大進化代數(shù)。

步驟2個體編碼

根據(jù)打擊任務的時間窗口推算分類任務和毀傷評估任務的執(zhí)行時間,對不符合任務時間窗要求的染色體進行修復,生成合適的染色體進行后續(xù)步驟,可以提高算法的計算速度,染色體適應度值的計算根據(jù)式(2)給出。

步驟3選擇操作

采用輪盤賭法,根據(jù)選擇概率,在原始種群中選擇適應度較好的染色體個體保留到下一代種群中,個體選擇概率為

(31)

Fitness(i)=1/Fitness(i)

步驟4交叉操作

根據(jù)交叉概率,從種群中選取兩個染色體,隨機確定染色體上的交叉位置,將兩個染色體上層對應交叉位置的基因編碼進行交叉操作。操作方法如圖2所示。

圖2 交叉操作Fig.2 Crossover operation

由于將合理染色體的編碼順序交叉后容易出現(xiàn)某些目標的任務多余而某些目標任務缺失,因此需要進行編碼的調(diào)整和修復:把任務多余的基因位調(diào)整為任務缺失的基因,并且按交叉操作之前編碼第二層所對應的無人機編號來調(diào)整編碼,調(diào)整操作方法如圖3所示。

圖3 調(diào)整編碼Fig.3 Code adjustment

步驟5變異操作

根據(jù)變異概率,在種群中隨機選擇變異個體,隨機選擇染色體的兩個變異位置,把染色體中兩個變異位置對應的基因以及下層編碼對應的無人機編號進行交換。操作方法如圖4所示。

圖4 變異操作Fig.4 Mutation operation

步驟6合并父代和經(jīng)過選擇、交叉、變異操作后產(chǎn)生的子代種群,生成混合種群。

步驟7計算混合種群適應度值。

步驟8判斷是否滿足循環(huán)終止條件,若不滿足,跳轉到步驟2,循環(huán)直至滿足終止條件,最終輸出最優(yōu)任務分配方案。

3.3 仿真分析

算法的基本參數(shù)為:種群數(shù)目為50,最大迭代次數(shù)為100,選擇概率為0.94,交叉概率為0.8,變異概率為0.1。仿真平臺與上述相同,求解用時為4.5 s,算法的搜索過程如圖5所示,表示隨著遺傳代數(shù)的進化,種群最優(yōu)解與均值的變化關系。算法在第80代時得到最優(yōu)解,最優(yōu)解為92.8 min。

圖5 算法搜索過程Fig.5 Algorithm search process

最優(yōu)個體對應的任務執(zhí)行順序甘特圖如圖6所示。

結果說明: UAV-01在任務時刻出發(fā),經(jīng)過36.6 min到達目標2執(zhí)行分類任務,在43.5 min時刻開始經(jīng)過30 min至目標1執(zhí)行毀傷評估任務;UAV-02在任務開始51.6 min后出發(fā),經(jīng)過36.6 min到達目標2執(zhí)行毀傷評估任務;UAV-03未分配到任務,故一直呈編隊狀態(tài)執(zhí)行搜索任務;UAV-04在任務開始40.9 min后出發(fā),經(jīng)過39.5 min到達目標4執(zhí)行攻擊任務,自爆;UAV-05未分配到任務,故一直呈編隊狀態(tài)執(zhí)行搜索任務;UAV-06在任務開始19.9 min后出發(fā),經(jīng)過42.8 min到達目標1執(zhí)行攻擊任務,自爆;UAV-07在任務開始49.6 min后出發(fā),經(jīng)過43.2 min到達目標3執(zhí)行毀傷評估任務;UAV-08在任務時刻出發(fā),經(jīng)過45.8 min到達目標4執(zhí)行分類任務,在53 min時刻開始經(jīng)過21.2 min至目標2執(zhí)行攻擊任務,自爆;UAV-09在任務開始38.3 min后出發(fā),經(jīng)過43.2 min到達目標3執(zhí)行攻擊任務,自爆;UAV-10在任務開始時刻出發(fā),經(jīng)過35.9 min到達目標1執(zhí)行分類任務,而后經(jīng)過21.2 min到達目標3執(zhí)行分類任務,在60.9 min時刻開始經(jīng)過30 min對目標4執(zhí)行毀傷評估任務。

圖6 任務執(zhí)行甘特圖Fig.6 Task execution Gantt chart

4 對比與分析

本文利用MILP和基于時間窗的多層編碼遺傳算法解決異構無人機編隊在反雷達作戰(zhàn)中的協(xié)同任務分配問題,仿真結果表明二者都能得出可行最優(yōu)分配方案及任務執(zhí)行時序圖。對比發(fā)現(xiàn):①在相同的平臺下,基于時間窗的多層編碼遺傳算法的求解時間遠快于MILP方法;②MILP方法得到任務執(zhí)行最短時間為91.2 min,而基于時間窗的多層編碼遺傳算法得到的最短執(zhí)行時間為92.8 min。經(jīng)過分析,由于MILP方法通過搜索得到的是目標函數(shù)的全局最優(yōu)解,故其精度更高。

仿真分析表明,MILP模型通過數(shù)學表達式可以方便地將時間、空間、物理、邏輯約束聯(lián)系起來,將一個實際的作戰(zhàn)任務轉化成數(shù)學問題,能夠求解有時間窗要求的任務分配問題。但用數(shù)學表達式將所有的約束問題融入到一個MILP模型中,將導致NP-Hard優(yōu)化問題,且計算量隨著求解規(guī)模呈指數(shù)遞增。以本次仿真采用的計算平臺為例,一般地,對于規(guī)模大于2個目標,且每個目標有3個任務的問題,難以實現(xiàn)實時求解。鑒于MILP在分配最優(yōu)性方面的優(yōu)勢,對于中等規(guī)模的問題,可以采用MILP離線方式尋找到最優(yōu)分配方案。

基于時間窗的多層編碼遺傳算法亦可以得到異構無人機編隊任務分配方案,便于利用甘特圖直觀表示任務執(zhí)行時序,其顯著特點是算法執(zhí)行時間大大小于MILP方法。在算法中,編碼是迭代處理的前提,染色體編碼難以精確體現(xiàn)所有約束,因此求解方案的最優(yōu)性將會受到一些影響,但仍可以得到可行的任務分配結果。

概括來講,基于MILP的任務分配能夠得到全局最優(yōu)解,但當問題規(guī)模較大時難以滿足實時性,適用于小規(guī)模任務分配實時解算;基于時間窗的多層編碼遺傳算法具有明確的計算優(yōu)勢,但可能得到局部最優(yōu)解,適用于為較大規(guī)模任務分解實時提供初始任務分配方案。

5 結 論

本文利用MILP和基于時間窗的多層編碼遺傳算法解決異構無人機編隊在反雷達作戰(zhàn)中的協(xié)同任務分配的問題。MILP模型將實際作戰(zhàn)任務轉化成數(shù)學規(guī)劃問題,簡明易懂,對于小規(guī)模的問題可以在線運行得出最優(yōu)的分配方案。相對于MILP模型,基于時間窗的多層編碼遺傳算法計算效率高,通過能夠?qū)崟r給出良好的分配方案,在異構無人機編隊任務分配中,可根據(jù)任務分配規(guī)模、用戶需求選擇使用兩類算法。