異構UAV編隊反雷達作戰中任務分配方法

林君燦, 賈高偉, 侯中喜

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

0 引 言

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

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

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

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

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

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

1 問題描述

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

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

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

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

2 基于MILP模型的任務分配

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

2.1 決策變量

表1 MILP決策變量

2.2 目標函數

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

(1)

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

(2)

2.3 約束條件

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

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

(3)

和

(4)

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

≤1,k=1,3

(5)

和

≤1

(6)

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

≤1

(7)

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

≤1

(8)

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

≤1

(9)

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

≤1

(10)

和

(11)

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

(12)

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

(13)

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

(14)

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

(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既執行分類任務又執行攻擊任務的情況,還需要另外的線性時間約束:

(21)

(22)

(23)

(24)

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

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

(25)

(26)

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

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

(27)

(28)

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

(29)

(30)

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

2.4 仿真分析

表2 目標任務信息

表3 目標任務執行時間窗

表4 無人機性能參數

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

(1) 決策變量

其余為0;

(2) 搜索任務決策變量

其余為0。

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

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

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

其余UAV出發時間為任務開始時刻。

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

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

圖1 MILP最優任務分配結果Fig.1 Optimal task assignment of MILP

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

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

3.1 算法描述

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

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

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

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

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

3.2 算法流程

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

步驟1初始化參數

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

步驟2個體編碼

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

步驟3選擇操作

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

(31)

Fitness(i)=1/Fitness(i)

步驟4交叉操作

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

圖2 交叉操作Fig.2 Crossover operation

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

圖3 調整編碼Fig.3 Code adjustment

步驟5變異操作

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

圖4 變異操作Fig.4 Mutation operation

步驟6合并父代和經過選擇、交叉、變異操作后產生的子代種群,生成混合種群。

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

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

3.3 仿真分析

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

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

最優個體對應的任務執行順序甘特圖如圖6所示。

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

圖6 任務執行甘特圖Fig.6 Task execution Gantt chart

4 對比與分析

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

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

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

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

5 結 論

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