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

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

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

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

圖2表示3架無(wú)人機(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)邊以表示無(wú)人機(jī)攻擊目標(biāo)后折返再執(zhí)行對(duì)該目標(biāo)的毀傷評(píng)估任務(wù)。

圖2 2個(gè)目標(biāo)3架無(wú)人機(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)間的分段距離表示無(wú)人機(jī)的航路，以最小化交戰(zhàn)時(shí)間為目標(biāo)。

2.1 決策變量

2.1.1 0-1決策變量

如圖1所示，若無(wú)人機(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；若無(wú)人機(jī)被指派從節(jié)點(diǎn)i飛向入節(jié)點(diǎn)n+w+1，則決策變量，否則為0。其表明，該無(wú)人機(jī)被指派執(zhí)行戰(zhàn)場(chǎng)搜索任務(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；②無(wú)人機(jī)v離開(kāi)初始位置j=n+v的時(shí)間為tv，v=1,2,…,w。

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

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

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

2.3 非時(shí)間約束

為獲得期望的無(wú)人機(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架無(wú)人機(jī)最多訪問(wèn)1個(gè)目標(biāo)2次（依次執(zhí)行任務(wù)1和2），

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

表1 決策變量Tab.1 Decision variables

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

4）無(wú)人機(jī)不可能離開(kāi)其未曾訪問(wèn)過(guò)的節(jié)點(diǎn)，

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

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

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

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

2.4 時(shí)間約束

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

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

若無(wú)人機(jī)離開(kāi)目標(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)飛來(lái)執(zhí)行任務(wù)的無(wú)人機(jī)所需時(shí)間。

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

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

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

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

該場(chǎng)景下，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）沒(méi)有意義。

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

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

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

用軟件CPLEX求解上述混合整數(shù)規(guī)劃問(wèn)題得：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。這表示，無(wú)人機(jī)1，2立即離開(kāi)源節(jié)點(diǎn)，無(wú)人機(jī)1在t=5.83時(shí)刻執(zhí)行對(duì)目標(biāo)的識(shí)別和攻擊任務(wù)，無(wú)人機(jī)2在t=7.07時(shí)刻執(zhí)行對(duì)目標(biāo)的毀傷評(píng)估任務(wù)。若無(wú)人機(jī)執(zhí)行任務(wù)1耗時(shí)α=2.0，則有x10=0.76，x12=7.83，此時(shí)無(wú)人機(jī)2要等待0.76才從源節(jié)點(diǎn)出發(fā)來(lái)完成對(duì)目標(biāo)任務(wù)2的處理。

3.2 多目標(biāo)多無(wú)人機(jī)場(chǎng)景

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

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

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

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

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

4 結(jié)論

建立了耦合時(shí)序約束和時(shí)間約束的多無(wú)人機(jī)多任務(wù)分配問(wèn)題的混合整數(shù)線性規(guī)劃模型，引入連續(xù)時(shí)間決策變量，以描述任務(wù)執(zhí)行時(shí)間和無(wú)人機(jī)離開(kāi)源位置時(shí)間以滿足時(shí)間約束。該模型還可提供多種目標(biāo)函數(shù)表達(dá)式，以滿足不同的任務(wù)完成評(píng)價(jià)指標(biāo)。仿真實(shí)驗(yàn)表明，對(duì)符合實(shí)戰(zhàn)的問(wè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].國(guó)防科技大學(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] 邸斌，周銳，丁全心.多無(wú)人機(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] 宋磊，黃長(zhǎng)強(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]//中國(guó)控制學(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-），男，博士生。