基于MILP的多無人機(jī)對敵防空火力壓制

顏驥，李相民，劉波，劉立佳

（1.海軍航空工程學(xué)院a.研究生管理大隊(duì)；b.兵器科學(xué)與技術(shù)系，山東煙臺(tái)264001；2.光電控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，河南洛陽471009）

基于MILP的多無人機(jī)對敵防空火力壓制

顏驥1a，李相民1b，劉波2，劉立佳1a

（1.海軍航空工程學(xué)院a.研究生管理大隊(duì)；b.兵器科學(xué)與技術(shù)系，山東煙臺(tái)264001；2.光電控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，河南洛陽471009）

建立了基于混合整數(shù)線性規(guī)劃（Mixed Integer Linear Program，MILP）的多無人機(jī)編隊(duì)對敵防空火力壓制協(xié)同任務(wù)分配模型，以0-1決策變量表征無人機(jī)—任務(wù)指派關(guān)系，引入連續(xù)時(shí)間決策變量來表示任務(wù)的執(zhí)行時(shí)間，并通過對決策變量之間的線性等式和不等式的數(shù)學(xué)描述，建立無人機(jī)之間和無人機(jī)執(zhí)行任務(wù)之間合理的協(xié)同約束關(guān)系。采用商用軟件CPLEX對模型求解，仿真驗(yàn)證了模型的合理性。

對敵防空火力壓制；任務(wù)分配；混合整數(shù)線性規(guī)劃；多機(jī)協(xié)同

當(dāng)代軍事對抗越來越依賴于空中力量的使用，近幾次局部戰(zhàn)爭表明，對敵防空火力壓制（Ssuppression of Enemy Air Defenses，SEAD）是空中軍事力量的關(guān)鍵，并發(fā)揮日益重要的作用[1]。SEAD是一種以破壞和（或）干擾的方式使敵地基防空（主要是面對空導(dǎo)彈防御系統(tǒng)和防空火炮系統(tǒng)）能力失效，或暫時(shí)失效的活動(dòng)。許多軍事平臺(tái)，彈藥和作戰(zhàn)行動(dòng)都可用于對敵防空火力壓制活動(dòng)，但主要是通過使用電子戰(zhàn)飛機(jī)在信號層或信息層對敵地面防御系統(tǒng)壓制或欺騙干擾，使用空對地攻擊戰(zhàn)斗機(jī)或SEAD飛機(jī)攜帶反輻射武器摧毀敵地面防御系統(tǒng)實(shí)體，以最大限度摧毀敵目標(biāo)的同時(shí)提高我方空中力量生存概率[2]?，F(xiàn)代導(dǎo)彈防御系統(tǒng)的移動(dòng)性、隱蔽性、高命中精度及雷達(dá)預(yù)警系統(tǒng)與發(fā)射裝置分離等特性，使利用常規(guī)遠(yuǎn)程巡航導(dǎo)彈和有人戰(zhàn)斗機(jī)執(zhí)行對敵防空火力壓制任務(wù)變得低效能和高風(fēng)險(xiǎn)。無人機(jī)因輕便、智能、無需人類飛行員駕駛等特性，越來越多地用于執(zhí)行危險(xiǎn)復(fù)雜的軍事任務(wù)[2]。文獻(xiàn)[3]通過改進(jìn)的Voronoi圖為無人戰(zhàn)斗機(jī)規(guī)劃安全路徑，以提高其生存概率。文獻(xiàn)[4]采用混合整數(shù)線性規(guī)劃方法來求解具有時(shí)序約束的多無人機(jī)多任務(wù)分配問題，但其需要枚舉所有航路點(diǎn)間的最短路徑及所有可行路徑的組合以滿足時(shí)間約束。文獻(xiàn)[5]采用編碼方式為雙染色體的矩陣遺傳算法對該問題求解，但編碼方式復(fù)雜且在表現(xiàn)任務(wù)時(shí)間約束上不直觀。文獻(xiàn)[6]采用混合重分配策略和混合細(xì)菌覓食算法來解決動(dòng)態(tài)環(huán)境下的多UCAV協(xié)同任務(wù)分配問題。文獻(xiàn)[7]設(shè)計(jì)了基于相鄰局部通信的分布式拍賣算法，實(shí)現(xiàn)了多無人機(jī)協(xié)同任務(wù)分配問題的優(yōu)化求解，考慮了任務(wù)時(shí)序性要求，但缺乏對無人機(jī)之間時(shí)間約束的考慮。文獻(xiàn)[8]采用合同網(wǎng)實(shí)現(xiàn)任務(wù)執(zhí)行過程中的任務(wù)分配，但各無人機(jī)間的通信復(fù)雜，并缺乏對算法實(shí)時(shí)性的分析。文獻(xiàn)[9-11]雖考慮了無人機(jī)、任務(wù)的時(shí)序約束和時(shí)間約束，但研究對象是處于不同位置的任務(wù)，與對敵防空火力壓制中每個(gè)目標(biāo)需依次執(zhí)行識(shí)別、打擊和毀傷評估的作戰(zhàn)任務(wù)存在較大區(qū)別。

1 問題描述

無人機(jī)編隊(duì)對敵防空火力壓制決策過程[1]如圖1所示。一般由4架無人機(jī)組成1個(gè)作戰(zhàn)編隊(duì)，按預(yù)定模式在目標(biāo)區(qū)域上空巡邏搜索，當(dāng)發(fā)現(xiàn)敵潛在目標(biāo)時(shí)，將各目標(biāo)的識(shí)別、攻擊和毀傷效果評估任務(wù)協(xié)同地分配給各架無人機(jī)，若為有效目標(biāo)，則攻擊之，并執(zhí)行后續(xù)的評估任務(wù)；若目標(biāo)不符合攻擊準(zhǔn)則，則放棄對該目標(biāo)的攻擊，并重新規(guī)劃編隊(duì)的作戰(zhàn)任務(wù)；評估作戰(zhàn)周期的效果，以確定是繼續(xù)還是結(jié)束作戰(zhàn)。

圖1 對敵防空火力壓制決策流程圖Fig.1 Decision making flow chart of SEAD

為便于說明問題，作如下假設(shè)：①編隊(duì)由具備自治能力的無人戰(zhàn)斗機(jī)組成，具備發(fā)射兵器，偵察和識(shí)別潛在敵方目標(biāo)，規(guī)避威脅的能力。②除非被敵方擊落，編隊(duì)成員數(shù)目不變，無人機(jī)攻擊目標(biāo)將導(dǎo)致所攜帶彈藥的消耗，彈藥耗盡后只能執(zhí)行識(shí)別和評估任務(wù)。③將目標(biāo)識(shí)別和攻擊任務(wù)歸為一個(gè)任務(wù)，每個(gè)目標(biāo)必須依次執(zhí)行?識(shí)別與攻擊；?毀傷評估2項(xiàng)任務(wù)。通過合理的無人機(jī)—任務(wù)分派，使無人機(jī)任務(wù)執(zhí)行代價(jià)、時(shí)間最小[3，8]或收益最大[7]，或者對上述多個(gè)目標(biāo)的同時(shí)優(yōu)化[9-10]，最終為每架無人機(jī)分配一條任務(wù)執(zhí)行路線[6]是解決該問題的一般思路。

設(shè)經(jīng)前期偵察發(fā)現(xiàn)地理上分散的n個(gè)目標(biāo)，紅方無人機(jī)數(shù)量為w，用n+w+1個(gè)節(jié)點(diǎn)來表示無人機(jī)執(zhí)行任務(wù)的狀態(tài)轉(zhuǎn)換圖，節(jié)點(diǎn)1,2,…,n位于發(fā)現(xiàn)目標(biāo)的位置，節(jié)點(diǎn)n+1,n+2,…,n+w位于無人機(jī)的初始位置，入節(jié)點(diǎn)n+w+1為虛擬節(jié)點(diǎn)。若無人機(jī)沒有分配任務(wù)，則進(jìn)入入節(jié)點(diǎn)執(zhí)行對區(qū)域內(nèi)未知目標(biāo)的搜索任務(wù)，不再參與當(dāng)前的任務(wù)分配。

圖2表示3架無人機(jī)與2個(gè)靜止目標(biāo)交戰(zhàn)時(shí)的狀態(tài)轉(zhuǎn)換圖。與文獻(xiàn)[4]不同，本文狀態(tài)轉(zhuǎn)換圖在目標(biāo)結(jié)點(diǎn)上添加自環(huán)邊以表示無人機(jī)攻擊目標(biāo)后折返再執(zhí)行對該目標(biāo)的毀傷評估任務(wù)。

圖2 2個(gè)目標(biāo)3架無人機(jī)時(shí)的狀態(tài)轉(zhuǎn)換圖Fig.2 State transition diagram for 2 targets 3 vehicles

2 MILP模型

MILP模型用狀態(tài)轉(zhuǎn)換圖節(jié)點(diǎn)間的分段距離表示無人機(jī)的航路，以最小化交戰(zhàn)時(shí)間為目標(biāo)。

2.1 決策變量

2.1.1 0-1決策變量

如圖1所示，若無人機(jī)v被指派從節(jié)點(diǎn)i飛向節(jié)點(diǎn)j執(zhí)行任務(wù)k，則0-1決策變量，否則為0。其中，i=1,2,…,n+w，j=1,2,…,n，i≠j，v=1,2,…,w，k=1,2；若無人機(jī)被指派從節(jié)點(diǎn)i飛向入節(jié)點(diǎn)n+w+1，則決策變量，否則為0。其表明，該無人機(jī)被指派執(zhí)行戰(zhàn)場搜索任務(wù)而不參與當(dāng)前目標(biāo)任務(wù)的分配，其中，v=1,2,…,w，i=1,2,…,n+w。

2.1.2 連續(xù)時(shí)間決策變量

引入如下2類連續(xù)時(shí)間決策變量：①在目標(biāo)j上執(zhí)行任務(wù)k的時(shí)間為，k=1,2，j=1,2,…,n；②無人機(jī)v離開初始位置j=n+v的時(shí)間為tv，v=1,2,…,w。

2.2 目標(biāo)函數(shù)

本文目標(biāo)函數(shù)為最小化交戰(zhàn)時(shí)間：

至此，求解本文多無人機(jī)多任務(wù)分配問題的決策變量如表1所示。0-1決策變量為2n2w+(2n+1)w個(gè)，連續(xù)決策變量為w+2n+1個(gè)。

2.3 非時(shí)間約束

為獲得期望的無人機(jī)協(xié)同任務(wù)分配關(guān)系，應(yīng)包括以下非時(shí)間約束。

1）每個(gè)目標(biāo)的每項(xiàng)任務(wù)只能被執(zhí)行1次：

2）每個(gè)目標(biāo)上要執(zhí)行2項(xiàng)任務(wù)，1架無人機(jī)最多訪問1個(gè)目標(biāo)2次（依次執(zhí)行任務(wù)1和2），

并且，每架無人機(jī)只能進(jìn)入入節(jié)點(diǎn)1次，

表1 決策變量Tab.1 Decision variables

3）一架無人機(jī)被指派執(zhí)行攻擊任務(wù)的次數(shù)不大于其攜帶的彈藥數(shù)Mv，設(shè)Mv=3，

4）無人機(jī)不可能離開其未曾訪問過的節(jié)點(diǎn)，

從狀態(tài)轉(zhuǎn)換圖上可理解為，無人機(jī)v從其他節(jié)點(diǎn)進(jìn)入節(jié)點(diǎn)j執(zhí)行任務(wù)2的邊數(shù)與該無人機(jī)由節(jié)點(diǎn)j飛向其他節(jié)點(diǎn)執(zhí)行任意任務(wù)的邊數(shù)之和相等，該約束不包括折返的自環(huán)邊。

5）包括被指派去入節(jié)點(diǎn)執(zhí)行區(qū)域搜索任務(wù)，所有無人機(jī)都離開源節(jié)點(diǎn)，

6）無人機(jī)只有進(jìn)入某節(jié)點(diǎn)后才有可能選擇自環(huán)邊執(zhí)行后續(xù)的評估任務(wù)，

以上6個(gè)約束中，v=1,2,…,w，k=1,2。

2.4 時(shí)間約束

若無人機(jī)離開目標(biāo)節(jié)點(diǎn)執(zhí)行任務(wù)1，則線性化的時(shí)間約束可表示為：

若無人機(jī)離開目標(biāo)節(jié)點(diǎn)后折返執(zhí)行任務(wù)2，則：

若無人機(jī)離開目標(biāo)節(jié)點(diǎn)去其他目標(biāo)節(jié)點(diǎn)執(zhí)行任務(wù)2，則：

式（14）～（15）中：i=1,2,…,n；j=1,2,…,n，i≠j；v=1,2,…,w；k=1,2。

以上約束影響由其他目標(biāo)節(jié)點(diǎn)飛來執(zhí)行任務(wù)的無人機(jī)所需時(shí)間。

時(shí)間約束還包括：

式（16）～（17）中，j=1,2,…,n；k=1,2；v=1,2,…,w。

此類約束影響每架無人機(jī)從源節(jié)點(diǎn)出發(fā)執(zhí)行的首個(gè)任務(wù)。

考慮任務(wù)1與2之間的時(shí)間延遲，引入約束：

其中，α為任務(wù)1的最小處理時(shí)間。

由分析可知，非時(shí)間約束數(shù)為3nw+3w+2n，時(shí)間約束為6nw+8n(n-1)w+2n。

3 算例分析

設(shè)下述例子初始條件用無人機(jī)及目標(biāo)節(jié)點(diǎn)間的相對飛行時(shí)間表示，且無人機(jī)由節(jié)點(diǎn)i飛向節(jié)點(diǎn)j執(zhí)行任務(wù)k的時(shí)間與無人機(jī)及任務(wù)無關(guān)，則常量可用ti,j表示，所有無人機(jī)的最大飛行時(shí)間均為100。用矩陣T表示相對飛行時(shí)間[4]，列表示開始節(jié)點(diǎn)i，行表示終節(jié)點(diǎn)j，對角線元素表示無人機(jī)在執(zhí)行完任務(wù)1后折返執(zhí)行任務(wù)2的最小時(shí)間。

3.1 2架無人機(jī)1個(gè)目標(biāo)

該場景下，n=1，w=2，0-1決策變量數(shù)為10，連續(xù)時(shí)間決策變量數(shù)為4，為最小化交戰(zhàn)時(shí)間，引入附加連續(xù)決策變量tf，共計(jì)15個(gè)決策變量。

0-1決策變量為：

連續(xù)決策變量

目標(biāo)函數(shù)

由約束1得：x1+x3=1，x2+x4+x5+x6=1；

由約束2得：x7+x9≤1，x8+x10≤1，x5+x2≤2，x6+x4≤2；

由約束3得：x1≤3，x3≤3；

由約束4得：x9=x2，x10=x4；

由約束5得：x1+x2+x7=1，x3+x4+x8=1；

由約束6得：x5=x1，x6=x3；

此處只有1個(gè)目標(biāo)節(jié)點(diǎn)，因而等式（10）、（11）和（14）、（15）沒有意義。

由等式（12）、（13）和（16）、（17）得到的時(shí)間約束為：

由等式（18）得：x13≤x14-α，其中α〉0為一小的正常量，本文設(shè)α=0.1，表示目標(biāo)前導(dǎo)任務(wù)的處理時(shí)間。

最后，由等式（19）得：x14≤x15。

用軟件CPLEX求解上述混合整數(shù)規(guī)劃問題得：xi=1,i=1,4,6，xi=0,i=2,3,5,7,8，xi=0,i=9,10，x11=5.83，x12=7.07，x13=7.07。這表示，無人機(jī)1，2立即離開源節(jié)點(diǎn)，無人機(jī)1在t=5.83時(shí)刻執(zhí)行對目標(biāo)的識(shí)別和攻擊任務(wù)，無人機(jī)2在t=7.07時(shí)刻執(zhí)行對目標(biāo)的毀傷評估任務(wù)。若無人機(jī)執(zhí)行任務(wù)1耗時(shí)α=2.0，則有x10=0.76，x12=7.83，此時(shí)無人機(jī)2要等待0.76才從源節(jié)點(diǎn)出發(fā)來完成對目標(biāo)任務(wù)2的處理。

3.2 多目標(biāo)多無人機(jī)場景

該算例為用如圖3所示的節(jié)點(diǎn)圖表示的4個(gè)目標(biāo)5架無人機(jī)的最優(yōu)任務(wù)分配結(jié)果。

圖3 4個(gè)目標(biāo)5架無人機(jī)時(shí)的最優(yōu)任務(wù)分配Fig.3 Optimal assignment for 4 targets 5 vehicles

表2為不同問題規(guī)模時(shí)，利用CPLEX求解模型的運(yùn)行時(shí)間。

表2 問題規(guī)模與求解時(shí)間Tab.2 Scale of the problem and solution time

由表2可知，當(dāng)由4架無人機(jī)組成的編隊(duì)在處理不超過3個(gè)目標(biāo)時(shí)，運(yùn)用該模型可得到實(shí)時(shí)的最優(yōu)分配結(jié)果，而對更大規(guī)模的問題可按分層分級的方法來分解求解。

4 結(jié)論

建立了耦合時(shí)序約束和時(shí)間約束的多無人機(jī)多任務(wù)分配問題的混合整數(shù)線性規(guī)劃模型，引入連續(xù)時(shí)間決策變量，以描述任務(wù)執(zhí)行時(shí)間和無人機(jī)離開源位置時(shí)間以滿足時(shí)間約束。該模型還可提供多種目標(biāo)函數(shù)表達(dá)式，以滿足不同的任務(wù)完成評價(jià)指標(biāo)。仿真實(shí)驗(yàn)表明，對符合實(shí)戰(zhàn)的問題規(guī)模，利用商用軟件可得到實(shí)時(shí)的可行優(yōu)化解。

[1] CANDIR A A.Discrete event simulation of a suppression of enemy air defenses（SEAD）mission[D].Ohio：Air Force Institute of Technology，2008.

[2] SURANZYNSKI.Miniaturized unmanned aerial systems（UAS）in SEAD m issions during electromagnetic conflicts[R].London：International Quality and Productivity Center，2006：912-913.

[3] 張雷，孫振江，王道波，等.一種用于SEAD任務(wù)的改進(jìn)型Voronoi圖[J].國防科技大學(xué)學(xué)報(bào)，2010，32（3）：121-125. ZHANG LEI，SUN ZHENGJIANG，WANG DAOBO，et al.An improved voronoi diagram for suppression of enemy air defense[J].Journal of National University of Defense Technology，2010，32（3）：121-125.（in Chinese）

[4] SCHUMACHER C，CHANDLER，P R.Optimization of air vehicle operations using m ixed-integer linear programm ing，0704-0188[R].W right Patterson：Air Force Research Laboratory，2006.

[5] SHIMA T，RASMUSSEN S J.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J].Computers&Operations Research，2006，33：3252-3269.

[6] 楊尚君，王社偉，陶軍，等.動(dòng)態(tài)環(huán)境下的多UCAV協(xié)同任務(wù)分配研究[J].電光與控制，2012，19（7）：32-36. YANG SHANGJUN，WANG SHEWEI，TAO JUN，et al. Multi-UCAV cooperative task allocation in dynam ic environment[J].Electronics Optics＆Control，2012，19（7）：32-36.（in Chinese）

[7] 邸斌，周銳，丁全心.多無人機(jī)分布式協(xié)同異構(gòu)任務(wù)分配[J].控制與決策，2013，28（2）：274-278. DI BIN，ZHOU RUI，DING QUANXIN.Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J].Control and Decision，2013，28（2）：274-278.（in Chinese）

[8] 龍濤，沈林成，朱華勇，等.面向協(xié)同任務(wù)的多UCAV分布式任務(wù)分配與協(xié)調(diào)技術(shù)[J].自動(dòng)化學(xué)報(bào)，2007，33（7）：731-737. LONG TAO，SHEN LINCHENG，ZHU HUAYONG，et al.Distributed task allocation&coordination technique of multiple UCAV for cooperative tasks[J].Acta Automatica Sinica，2007，33（7）：731-737.（in Chinese）

[9] 宋磊，黃長強(qiáng)，吳文超，等.多UCAV協(xié)同目標(biāo)攻擊決策[J].系統(tǒng)工程與電子技術(shù)，2011，33（7）：1548-1552. SONG LEI，HUANG CHANGQIANG，WU WENCHAO，et al.Target attack decision-making for cooperating multi-UCAV[J].Systems Engineering and Electronic，2011，33（7）：1548-1552.（in Chinese）

[10] 程聰，吳慶憲，劉敏，等.UCAV協(xié)同攻擊多目標(biāo)的任務(wù)分配技術(shù)研究[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2012，30（6）：609-615. CHENG CONG，WU QINGXIAN，LIU MIN，et al.Research on task allocation for ucavs cooperatively attacking multiple targets[J].Journal of Jilin University：Information Science Edition，2012，30（6）：609-615.（in Chinese）

[11] 張健，彭志紅，李波.考慮時(shí)間代價(jià)及硬時(shí)間窗的UCAVs多任務(wù)分配[C]//中國控制學(xué)會(huì)第31屆學(xué)術(shù)會(huì)議.華盛頓：IEEE計(jì)算機(jī)學(xué)會(huì)，2012：2448-2452. ZHANG JIAN，PENG ZHIHONG，LI BO.Multi-task allocation of UCAVs considering time cost and hard time w indow constraints[C]//Proceedings of the 31st Chinese Control Conference.Washing，D.C.：IEEE Computer Society，2012：2448-2452.（in Chinese）

Multi UAV Suppression of on Enemy Air Defense Based on MILP

YAN Ji1a,LI Xiang-min1b,LIU Bo2,LIU Li-jia1a
（1.Naval Aeronautical and Astronautical University a.Graduate Students'Brigade; b.Department of Ordnance Science and Technology,Yantai Shandong 264001,China; 2.Science and Technology on Electro-Optic Control Laboratory,Luoyang Henan 471009,China）

A problem of assigning cooperating uninhabited aerial vehicles to perform multiple tasks on multiple targets in a suppression of enemy air defense(SEAD)mission was proposed as a mixed integer linear program(MILP).Additions to the binary task assignment decision variable,a serial of continuous decision variables were introduced to represent the task precedence.The equality and inequality non-timing and timing constraints of decision variables take into account the unique requirements of UAVs and tasks were constructed.The problem was solved by CPLEX,and simulations demonstrated the viability of the model.

suppression of enemy air defenses;task allocation;mixed integer linear program(MILP);cooperating multi air vehicle

V279

A

1673-1522（2014）04-0369-05

10.7682/j.issn.1673-1522.2014.04.015

2014-03-03；

2014-04-28

航空科學(xué)基金資助項(xiàng)目（20135184008）

顏驥（1984-），男，博士生。