基于不完備區(qū)間信息的多無(wú)人機(jī)任務(wù)分配

陳 俠,胡顯偉

(1.沈陽(yáng)航空航天大學(xué) 自動(dòng)化學(xué)院，沈陽(yáng) 110136； 2.沈陽(yáng)市化工學(xué)校 化機(jī)系，沈陽(yáng) 110122)

?

信息科學(xué)與工程

基于不完備區(qū)間信息的多無(wú)人機(jī)任務(wù)分配

陳 俠1,胡顯偉2

(1.沈陽(yáng)航空航天大學(xué) 自動(dòng)化學(xué)院，沈陽(yáng) 110136； 2.沈陽(yáng)市化工學(xué)校 化機(jī)系，沈陽(yáng) 110122)

在無(wú)人機(jī)作戰(zhàn)系統(tǒng)中，多無(wú)人機(jī)(UCAV)任務(wù)分配問題是一個(gè)重要研究課題。給出了一種不完備信息環(huán)境下的多無(wú)人機(jī)任務(wù)分配方法。首先考慮了任務(wù)分配的各項(xiàng)指標(biāo)，并分析指標(biāo)中的不完備信息，然后通過(guò)建立區(qū)間可能度公式，采用粒子群方法(PSO)，給出了多無(wú)人機(jī)任務(wù)分配方法。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該方法的可行性和有效性，可以有效且合理地解決不確定環(huán)境下的多無(wú)人機(jī)任務(wù)分配問題。

多無(wú)人機(jī);不完備信息;粒子群算法;任務(wù)分配

隨著作戰(zhàn)環(huán)境的日益復(fù)雜,無(wú)人機(jī)作戰(zhàn)任務(wù)也日益多樣化，多機(jī)作戰(zhàn)能夠?qū)崿F(xiàn)攻擊多個(gè)敵方目標(biāo)，且提高其殺傷概率，因而將成為未來(lái)空戰(zhàn)的主流趨勢(shì)。而多無(wú)人機(jī)任務(wù)分配是研究空戰(zhàn)問題的重要課題，目前任務(wù)分配研究方法主要有：多旅行商問題模型[1]、車輛路徑問題模型[2]、動(dòng)態(tài)網(wǎng)絡(luò)流模型[3]、混合整數(shù)線性規(guī)劃模型[4]。多UCAV(Unmanned Combat Aerial Vehicles)協(xié)同任務(wù)分配求解方法主要包含多目標(biāo)整數(shù)規(guī)劃、分支定界、網(wǎng)絡(luò)流量?jī)?yōu)化方法、蟻群算法[5]、遺傳算法[6-7]、基于市場(chǎng)競(jìng)拍機(jī)制算法[4]、粒子群優(yōu)化算法[8]等。雖然各國(guó)對(duì)于多無(wú)人機(jī)任務(wù)分配問題取得了大量的科研成果，可是在已經(jīng)獲得的成果中，我們獲得的戰(zhàn)場(chǎng)信息往往都是確定的。然而實(shí)際上，由于無(wú)人機(jī)在戰(zhàn)場(chǎng)環(huán)境中受到各種干擾及傳感器精度的限制，獲得的信息大多是不完全信息，在數(shù)學(xué)上將其描述成不完備信息。所以，在不確定環(huán)境情況下，需要把不完備的信息轉(zhuǎn)化成完備信息。因此，基于不完備信息的多UCAV任務(wù)分配是一個(gè)新的重要課題。在現(xiàn)有的文獻(xiàn)中，仍未有基于不完備信息的多無(wú)人機(jī)任務(wù)分配研究的報(bào)道。本文將粒子群算法和區(qū)間可能度公式結(jié)合，提出基于不完備信息的多無(wú)人機(jī)任務(wù)分配方法,最后通過(guò)仿真實(shí)例驗(yàn)證出此方法容易實(shí)現(xiàn)，并能有效完成多機(jī)任務(wù)分配。

1 多無(wú)人機(jī)任務(wù)分配建模

根據(jù)文獻(xiàn)[9]，可以給出多無(wú)人機(jī)任務(wù)分配模型。

1.1 UCAV攻擊地面目標(biāo)收益函數(shù)的建立

對(duì)于多UCAV在攻擊敵方目標(biāo)時(shí)所產(chǎn)生的價(jià)值收益，其總量越高越好。若P=[P1,P2,…,Pm]為UCAV對(duì)目標(biāo)的殺傷概率矩陣，則收益指標(biāo)函數(shù)為：

(1)

1.2 UCAV攻擊地面目標(biāo)毀傷代價(jià)函數(shù)和航程代價(jià)指標(biāo)函數(shù)的建立

(2)

(3)

1.3 多UCAV任務(wù)分配模型的建立

在應(yīng)用中，綜合考慮UCAV的收益、毀傷代價(jià)和航程代價(jià)，則多UCAV任務(wù)分配問題的數(shù)學(xué)模型可以表示為：

J=max(w1*R-w2*C1-w3*C2)

(4)

s.t.

(5)

(6)

w1+w2+w3=1

(7)

w1、w2和w3分別為目標(biāo)獲得收益、毀傷代價(jià)、航程代價(jià)的權(quán)重。公式(5)約束條件為每架無(wú)人機(jī)一次最多只能分配給一個(gè)目標(biāo)，公式(6)要求每個(gè)目標(biāo)每次最多被分配給一架UCAV。

2 基于不完備信息的決策方法

2.1 基于不完備區(qū)間的決策方法

(8)

則稱?x為區(qū)間數(shù)：

定義2[10-13]：若?x 為遺漏型的區(qū)間數(shù)，則其表示形式為以下三種情形之一：

(3) ?x=[*,*]="*"，表示區(qū)間數(shù)的下、上限值均遺漏。

定義3[10-13]：在不完備序區(qū)間值決策系統(tǒng)中，對(duì)?a∈AT,?x∈U，則有以下3 種填充形式:

2.2 基于區(qū)間可能度的求解多無(wú)人機(jī)任務(wù)分配方法

(9)

(10)

本文利用粒子群算法(Particle Swarm Optimization)來(lái)求解分配方案。粒子群算法最初是由模擬鳥群覓食行為發(fā)展而來(lái)的，它屬于群體協(xié)作的隨機(jī)搜索算法[15]。粒子群算法有很多優(yōu)點(diǎn)，如保持種群多樣性，收斂速度快等。也有很多文獻(xiàn)利用粒子群算法求解納什均衡問題[16-17]。本文先通過(guò)采用不完備信息的填充方法獲得區(qū)間數(shù)信息，再采用粒子群算法求解多UCAV任務(wù)分配問題。

當(dāng)前所有粒子達(dá)到最好位置為全局最優(yōu)粒子。將當(dāng)前個(gè)體最優(yōu)粒子的區(qū)間適應(yīng)度進(jìn)行兩兩比較，從而獲得可能度矩陣。然后利用互補(bǔ)可能度矩陣排序的方法，對(duì)區(qū)間適應(yīng)度從小到大排序，排名第一的粒子就成為全局最優(yōu)粒子。

2.3 算法流程

步驟1：初始化粒子群，在空間中，隨機(jī)產(chǎn)生位置和速度；

步驟2：將當(dāng)前的粒子作為個(gè)體最優(yōu)粒子，然后計(jì)算每個(gè)粒子相對(duì)應(yīng)的適應(yīng)度值，最后全局最優(yōu)粒子通過(guò)區(qū)間數(shù)排序方法計(jì)算得出；

步驟3：更新粒子，從而獲得新一代的粒子；

步驟4：計(jì)算每個(gè)粒子相對(duì)應(yīng)的適應(yīng)度值，將當(dāng)前的每個(gè)粒子與其對(duì)應(yīng)的個(gè)體最優(yōu)粒子進(jìn)行排序，從而獲得新的個(gè)體最優(yōu)粒子，再把所有的個(gè)體最優(yōu)粒子由大到小排序得到新的全局最優(yōu)粒子；

步驟5：重復(fù)步驟3和步驟4，達(dá)到最大迭代次數(shù)后，循環(huán)結(jié)束后，輸出全局最優(yōu)粒子。

3 實(shí)例分析

本文仿真實(shí)例為6架無(wú)人機(jī)攻擊10個(gè)地面任務(wù)，每個(gè)任務(wù)目標(biāo)僅被一架無(wú)人機(jī)攻擊，戰(zhàn)場(chǎng)環(huán)境信息如表1～10所示。

根據(jù)定義3，將不完備信息變成完備信息，設(shè)權(quán)重信息為[0.35 0.3 0.35 ]，粒子群算法中相關(guān)參數(shù)設(shè)置如下：種群規(guī)模設(shè)為50，最大迭代次數(shù)設(shè)為200,慣性權(quán)重設(shè)為0.5，學(xué)習(xí)因子分別為0.6和0.7，根據(jù)式(4a)和式(4b)，最優(yōu)分配方案和適應(yīng)度區(qū)間函數(shù)如表11和圖1所示。

表1 對(duì)于目標(biāo)1的各個(gè)指標(biāo)信息

表2 對(duì)于目標(biāo)2的各個(gè)指標(biāo)信息

表3 對(duì)于目標(biāo)3的各個(gè)指標(biāo)信息

表4 對(duì)于目標(biāo)4的各個(gè)指標(biāo)信息

表5 對(duì)于目標(biāo)5的各個(gè)指標(biāo)信息

表6 對(duì)于目標(biāo)6的各個(gè)指標(biāo)信息

表7 對(duì)于目標(biāo)7的各個(gè)指標(biāo)信息

表8 對(duì)于目標(biāo)8的各個(gè)指標(biāo)信息

表9 對(duì)于目標(biāo)9的各個(gè)指標(biāo)信息

表10 對(duì)于目標(biāo)10的各個(gè)指標(biāo)信息

表11 多無(wú)人機(jī)最優(yōu)分配方案

從表11和圖1可以看出，圖1中上面的線代表右端點(diǎn)適應(yīng)度，下面這條代表左端點(diǎn)適應(yīng)度，最優(yōu)解的適應(yīng)度區(qū)間值為[0.164 1 0.197 9]。最優(yōu)方案為UCAV2執(zhí)行第一個(gè)任務(wù)和第八個(gè)任務(wù)，UCAV3執(zhí)行第二個(gè)任務(wù)，UCAV1執(zhí)行第三個(gè)和第7個(gè)任務(wù)，UCAV4執(zhí)行第四個(gè)任務(wù)，UCAV5執(zhí)行第六和第十任務(wù)，UCAV6執(zhí)行第五個(gè)和第九個(gè)任務(wù)。

4 結(jié)論

針對(duì)基于不完備信息下的多無(wú)人機(jī)任務(wù)分配問題，本文首先對(duì)任務(wù)分配結(jié)果產(chǎn)生影響的各項(xiàng)指標(biāo)因素及其不確定性進(jìn)行了分析，然后將不完備信息完備為區(qū)間信息，通過(guò)將可能度與粒子群算法相結(jié)合，得出不完備信息的多UCAV任務(wù)分配方法；最后通過(guò)實(shí)例分析來(lái)確定無(wú)人機(jī)任務(wù)分配方案，有效解決了不完備信息的多無(wú)人機(jī)任務(wù)分配問題。需要指出的是，基于不完備信息下的多無(wú)人機(jī)任務(wù)分配問題是一個(gè)新研究課題，實(shí)際應(yīng)用中，如何根據(jù)不完備信息輸入，進(jìn)一步完善多UCAV任務(wù)分配算法仍有待深入研究。

圖1 適應(yīng)度區(qū)間值變化曲線

[1]O’Rourke K P,Bailey T G,Hill R,et al.Dynamic routing of unmanned aerial vehicles using reactive tabs search [J].Military Operations Research Journal,2001,6(1):5-30.

[2]Harder R W.A Java universal vehicle router in support of routing unmanned aerial vehicles air missions [J].Ohio:Air Force Institute of Technology.International Transactions in Operational Research,2004,11(3):259-275.

[3]Alighanbari M.Task Assignment Algorithms for Teams of UAVs in Dynamic Environments [D].Cambridge:Massachusetts Institute of Technology,2004:45-61.

[4]沈林成,陳璟,王楠.飛行器任務(wù)規(guī)劃技術(shù)綜述[J].航空學(xué)報(bào),2014,35(3):593-606.

[5]段海濱,丁全心,常俊杰,等.基于并行蟻群優(yōu)化的多UCAV任務(wù)分配仿真平臺(tái)[J].航空學(xué)報(bào),2008,29(5):192-197.

[6]Genshe C.Genetic algorithm for task allocation in UAV cooperative control [J].AIAA Guidance,Navigation,and Control Conference and Exhibit,2003:1121-1126.

[7]Shima T,Rasmuesen S J,Sparks A G,et al.Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms [J].Computers and Operations Research,2006,33(11):3252-3269.

[8]Curz J B,Jr C,Chen G.Particle swarm optimization for resource allocation in UAV cooperative control [J].AIAA Guidance,Navigation,and Control Conference and Exhibit,2004:16-19.

[9]葉媛媛.多UCAV協(xié)同任務(wù)規(guī)劃方法研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2005:41-47.

[10]周海軍,謝軍.不完備序區(qū)間值決策系統(tǒng)中所有可信規(guī)則的獲取[J].江蘇大學(xué)學(xué)報(bào),2014,35(2):201-206.

[11]王天擎,洪智勇.不完備序區(qū)間值決策系統(tǒng)中的可信規(guī)則的獲取[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2014,44(1):45-52.

[12]李丹.屬性加權(quán)及不完備數(shù)據(jù)的模糊聚類方法研究[D].大連:大連理工大學(xué),2011:45-75.

[13]舒才良,嚴(yán)宣輝,曾慶盛.不完備數(shù)據(jù)下的免疫分類算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(2):172-176.

[14]張全,樊治平,潘德惠.不確定性多屬性決策中區(qū)間數(shù)的一種排序方法[J].系統(tǒng)工程理論與實(shí)踐,1999(5):130-133.

[15]李煒,張偉.基于粒子群算法的多無(wú)人機(jī)任務(wù)分配方法[J].控制與決策,2010,25(9):1359-1363.

[16]施蓉花,吳慶憲,姜長(zhǎng)生.無(wú)人機(jī)協(xié)同攻擊的混合粒子群算法[J].火力與指揮控制,2009,34(9):10-13.

[17]陳俠,胡永新,徐光延.面向多無(wú)人機(jī)任務(wù)分配的二維編碼粒子群算法[J].系統(tǒng)仿真學(xué)報(bào),2013,25(12):3045-3056.

(責(zé)任編輯：劉劃 英文審校：劉敬鈺)

Multi-UCAV task assignment based on incomplete interval information

CHEN Xia1,HU Xian-wei2

(1.College of Automation,Shenyang Aerospace University,Shenyang 110136,China;2.Department of Chemical Process Equipment,Shenyang Chemical Industry School,Shenyang 110122,China)

In the UCAV combat system,the task assignment of multi-UCAV is one of the key technologies of task assigning system.The method of the multi-UCAV task assignment is presented based on incomplete information environment in this paper.First,the indicators of task assignment are considered,of which the incomplete information is analyzed.Then according to the possibility formula on interval numbers,the multi-UCAV task assignment is put forward by using PSO.Finally,the feasibility and effectiveness of the method are verified by simulation,which can effectively and reasonably solve the problem of multi-UCAV task assignment under the uncertain conditions.

Multi-UCAV;incomplete information;PSO;task assignment

2015-03-19

國(guó)家自然科學(xué)基金(項(xiàng)目編號(hào)：61074159)；沈陽(yáng)科技資助項(xiàng)目(項(xiàng)目編號(hào)：14042200、14231129)

陳俠(1962-)，女，遼寧新民人，教授,博士(后)，主要研究方向:無(wú)人機(jī)任務(wù)規(guī)劃，E-mail:xiachen1108@163.com。

2095-1248(2015)04-0050-07

TP391.9

A

10.3969/j.issn.2095-1248.2015.04.009