考慮目標(biāo)期望摧毀概率的多無(wú)人機(jī)任務(wù)分配方法

周謙, 高社生, 高朝輝, 夏娟, 洪根元

(1.西北工業(yè)大學(xué) 深圳研究院, 廣東 深圳 518057; 2.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院, 陜西 西安 710072;3.長(zhǎng)安大學(xué) 地質(zhì)工程與測(cè)繪學(xué)院, 陜西 西安 710054)

在現(xiàn)代、信息化作戰(zhàn)系統(tǒng)中，傳感器(雷達(dá))和武器(導(dǎo)彈、火炮)的合理高效利用對(duì)作戰(zhàn)任務(wù)效果具有重要影響。如何快速、有效地分配RUAVs和UCAVs實(shí)現(xiàn)對(duì)大規(guī)模目標(biāo)進(jìn)行監(jiān)測(cè)以及攻擊是目前作戰(zhàn)規(guī)劃中一項(xiàng)極具挑戰(zhàn)性的熱點(diǎn)問(wèn)題[1-4]。通常可將此類(lèi)分配問(wèn)題分為偵查無(wú)人機(jī)-目標(biāo)(RUAVs-Target,RUAVs-T)分配問(wèn)題以及攻擊無(wú)人機(jī)-目標(biāo)(UCAVs-Target,UCAVs-T)分配問(wèn)題。RUAVs-T與UCAVs-T分配問(wèn)題同屬任務(wù)分配，多目標(biāo)協(xié)同偵查、監(jiān)測(cè)和追蹤任務(wù)為典型的RUAVs-T分配問(wèn)題[5-6]；火力打擊任務(wù)分配即為UCAVs-T分配問(wèn)題[2-3]。本文針對(duì)RUAVs和UCAVs對(duì)敵作戰(zhàn)的任務(wù)分配問(wèn)題進(jìn)行研究，將偵查無(wú)人機(jī)、目標(biāo)、攻擊無(wú)人機(jī)結(jié)合起來(lái)統(tǒng)一考慮，采用協(xié)同分配模型，實(shí)現(xiàn)RUAVs、UCAVs以及目標(biāo)的協(xié)同高效、快速分配。

目前，求解任務(wù)分配的算法大致可分為數(shù)學(xué)規(guī)劃方法[7-8]、基于合同網(wǎng)的任務(wù)分配方法[4,9]以及啟發(fā)式智能優(yōu)化算法[3,10]三大類(lèi)。

數(shù)學(xué)規(guī)劃方法作為一種確定性算法，可以給出任務(wù)分配問(wèn)題的最優(yōu)解。然而，求解大規(guī)模分配問(wèn)題時(shí)，由于求解難度劇增會(huì)導(dǎo)致耗時(shí)增加，在有限時(shí)間內(nèi)該方法無(wú)法保證給出滿(mǎn)意的規(guī)劃結(jié)果[1]。

基于合同網(wǎng)的方法將任務(wù)分配視為一個(gè)協(xié)商過(guò)程，買(mǎi)賣(mài)雙方以出價(jià)的形式競(jìng)爭(zhēng)獲得任務(wù)的執(zhí)行權(quán)。但基于合同網(wǎng)的任務(wù)分配方法需任務(wù)執(zhí)行主體間多次協(xié)商，在問(wèn)題規(guī)模較大時(shí)勢(shì)必造成通信量增大以及耗時(shí)增加的問(wèn)題。

以遺傳算法、蟻群算法等為代表的智能優(yōu)化算法，由于其不要求目標(biāo)函數(shù)的連續(xù)性以及可導(dǎo)性，在任務(wù)分配方面引起了許多學(xué)者的研究興趣[10-11]。智能優(yōu)化算法在優(yōu)化過(guò)程中，整個(gè)種群中的所有個(gè)體同時(shí)向全局最優(yōu)逐漸收斂。但由于智能優(yōu)化算法存有大量隨機(jī)性搜索嘗試，致使在求解任務(wù)分配問(wèn)題時(shí)會(huì)出現(xiàn)效率和精度不高的現(xiàn)象[1]。

任務(wù)分配過(guò)程中不確定性事件是不可避免的，追求全局最優(yōu)的方法勢(shì)必很難滿(mǎn)足任務(wù)分配實(shí)時(shí)性的要求[12]。因此，次優(yōu)、快速的任務(wù)分配方法在解決大規(guī)模任務(wù)規(guī)劃問(wèn)題時(shí)的實(shí)時(shí)性?xún)?yōu)勢(shì)會(huì)更加明顯。文獻(xiàn)[12]提出了一種高效的基于邊緣收益構(gòu)造的啟發(fā)式方法(an efficient marginal-return-based constructive heuristic,MRBCH)用于解決傳感器-武器任務(wù)分配問(wèn)題，該算法可快速解決任務(wù)分配問(wèn)題。然而任務(wù)分配問(wèn)題，除實(shí)時(shí)性要求外，分配結(jié)果的合理性也至關(guān)重要。本文側(cè)重提高任務(wù)分配結(jié)果。在以作戰(zhàn)收益最大化的目標(biāo)函數(shù)中，加入調(diào)節(jié)因子與期望摧毀概率的約束條件[13]，使任務(wù)分配結(jié)果既滿(mǎn)足作戰(zhàn)效能又注重經(jīng)濟(jì)效能。

綜上所述，本文提出了一種考慮目標(biāo)期望摧毀概率的RUAVs/UCAVs快速、次優(yōu)任務(wù)分配方法。該方法通過(guò)改進(jìn)設(shè)計(jì)分配模型的目標(biāo)函數(shù)以及約束條件，保證資源的均衡分配以及避免過(guò)度分配，提高分配結(jié)果質(zhì)量。改進(jìn)設(shè)計(jì)了基于邊緣受益最大化的貪婪算法(greedy algorithm based on maximum marginal-return,GA-MMR)對(duì)提出的分配模型進(jìn)行求解。仿真結(jié)果表明，所提算法可快速高效地進(jìn)行任務(wù)分配，并且明顯改善了資源分配不均與資源過(guò)度分配的情形。

1 RUAV、UCAV任務(wù)分配模型

1.1 問(wèn)題描述

本文考慮如下作戰(zhàn)場(chǎng)景。在T時(shí)刻監(jiān)測(cè)到有Nt個(gè)具有不同威脅程度的目標(biāo)來(lái)襲，防御者擁有RUAVs和UCAVs攔截目標(biāo)。Ns個(gè)RUAVs用來(lái)捕獲跟蹤目標(biāo)，從而引導(dǎo)Nw個(gè)UCAVs對(duì)其進(jìn)行摧毀。不同RUAV、UCAV對(duì)不同目標(biāo)的捕獲跟蹤、摧毀能力不同。如何將這些RUAVs和UCAVs協(xié)同高效進(jìn)行分配，達(dá)到有效抵御的目的是本文研究的關(guān)鍵問(wèn)題。

假設(shè)每個(gè)RUAV與UCAV同時(shí)只能偵查和攻擊一個(gè)目標(biāo),且UAVs具有單一的偵查或者攻擊功能。用Y=[yik]Ns×Nt和Z=[zjk]Nw×Nt分別表示RUAV和UCAV與目標(biāo)之間的分配集合(RUAV-T,UCAV-T),當(dāng)yik/zjk為1時(shí)表示第i(i=1,2,3,…,Ns)個(gè)RUAV或第j(j=1,2,3,…,Nw)個(gè)UCAV分配給第k(k=1,2, 3,…,Nt)個(gè)目標(biāo),為0則相反。

Ps(k)表示目標(biāo)k被RUAV捕獲及追蹤的概率,Pdes(k)表示目標(biāo)k被摧毀的概率,Pw(k)表示目標(biāo)k在RUAV引導(dǎo)下被UCAV摧毀的條件概率。則三者滿(mǎn)足以下公式

Pdes(k)=Ps(k)×Pw(k)

(1)

假設(shè)不同RUAV和UCAV對(duì)目標(biāo)的成功捕獲和摧毀事件是相互獨(dú)立的事件。則目標(biāo)k被成功捕獲追蹤的概率可通過(guò)(2)式計(jì)算

(2)

式中，pik為目標(biāo)k被第i個(gè)RUAV成功捕獲追蹤的概率。同樣目標(biāo)k被成功摧毀的概率計(jì)算公式為

(3)

式中，qjk為目標(biāo)k被第j個(gè)UCAV摧毀的概率[13]。于是可得目標(biāo)k被RUAV成功捕獲追蹤,且在指導(dǎo)下被UCAV成功摧毀的概率為

Pdes(k)=

(4)

1.2 分配模型收益函數(shù)

本文設(shè)計(jì)了一種高效的RUAVs/UCAVs、目標(biāo)任務(wù)分配模型,目標(biāo)函數(shù)為最大化摧毀敵方目標(biāo)的價(jià)值(或最大化減少敵對(duì)目標(biāo)威脅值)。

(5)

式中：R為分配方案對(duì)應(yīng)收益值;vk表示目標(biāo)k的威脅值(目標(biāo)價(jià)值);α(k)為目標(biāo)k的資源分配調(diào)節(jié)因子,其用于指導(dǎo)分配過(guò)程,確保資源分配的均衡性。

1.3 約束條件

該分配模型中單一RUAV只能用于捕獲追蹤一個(gè)敵方目標(biāo);同樣單一UCAV只能用于攻擊一個(gè)敵方目標(biāo)。

(6)

(7)

為提高分配結(jié)果的經(jīng)濟(jì)效能,引入目標(biāo)期望摧毀概率約束。若某一目標(biāo)已分配資源(RUAVs、UCAVs)滿(mǎn)足摧毀該目標(biāo)的概率不低于其摧毀期望值(expected probability of destruction,Pd),則停止對(duì)該目標(biāo)分配資源,避免造成資源的浪費(fèi);否則根據(jù)分配規(guī)則繼續(xù)參與分配過(guò)程,直到分配結(jié)束。

(8)

式中：a(i,j,k)為任務(wù)所包含分配方案集合,表示將第i個(gè)RUAV和第j個(gè)UCAV分配給目標(biāo)k;Pd(k)為第k個(gè)目標(biāo)期望摧毀概率;remove(a(*,*,k))表示將分配方案a(*,*,k)從集合A中刪除。

2 RUAV、UCAV任務(wù)分配方法

2.1 輔助決策矩陣

本文研究RUAVs/UCAVs的目標(biāo)分配問(wèn)題,對(duì)作戰(zhàn)任務(wù)而言,RUAVs與UCAVs分配相互依賴(lài)。RUAVs提供目標(biāo)的位置信息,UCAVs對(duì)目標(biāo)進(jìn)行攻擊,消除威脅。本文采用三維矩陣X=[xijk]Ns×Nw×Nt表示任務(wù)分配方案集合[12],xijk為1時(shí)表示RUAV(i)與UCAV(j)分配給目標(biāo)k,xijk為0則相反。在三維矩陣的輔助下,可以更清楚描述RUAVs和UCAVs與目標(biāo)三者之間的關(guān)系。

2.2 約束處理方法

為保證分配方案滿(mǎn)足約束條件(6)、(7)式,分別用變量NUs、NUw表示每個(gè)RUAV以及UCAV的使用次數(shù)。在任務(wù)分配過(guò)程中,若出現(xiàn)RUAV(i)/

UCAV(j)的使用次數(shù)NUs(i)/NUw(j)大于1時(shí),則停止對(duì)RUAV(i)/UCAV(j)進(jìn)行分配,將涉及RUAV(i)/UCAV(j)的分配集合從集合A中刪除。既滿(mǎn)足約束條件又可加快分配進(jìn)程,減少時(shí)間消耗。

同樣在分配過(guò)程中,當(dāng)目標(biāo)k的摧毀概率滿(mǎn)足期望摧毀概率Pd(k)時(shí),將涉及目標(biāo)k的分配方案從分配集合中刪除,加快分配進(jìn)程實(shí)現(xiàn)高效任務(wù)分配。

2.3 任務(wù)分配規(guī)則

本文在建立目標(biāo)函數(shù)基礎(chǔ)上,采用邊緣收益最大的貪心原則進(jìn)行任務(wù)分配。同時(shí)為保證資源分配的均衡性,在目標(biāo)函數(shù)中增加了調(diào)節(jié)因子α。

1) 邊緣受益最大原則

在計(jì)算邊緣收益之前,需定義概率更新規(guī)則。對(duì)于目標(biāo)k而言,若無(wú)RUAVs分配則該目標(biāo)未被成功捕獲追蹤的概率就為1;若分配的RUAVs越多,則該目標(biāo)未被捕獲追蹤的概率就應(yīng)越小,定義如下Pmis(k)更新規(guī)則[12]。

(9)

同理,定義如下Qmis(k)更新規(guī)則

(10)

式中：Pmis(k)表示目標(biāo)k未被其已分配RUAVs成功捕獲的概率；Qmis(k)表示目標(biāo)k未被其已分配UCAVs成功摧毀的概率。{Sk},{Wk}分別為分配給目標(biāo)k的RUAVs和UCAVs集合。

在任務(wù)分配開(kāi)始階段,任務(wù)分配的受益為0。當(dāng)新增加任務(wù)分配方案xijk時(shí),由于增加的xijk所帶來(lái)的收益增加ΔRijk計(jì)算方法如下所示

式中：R1為xijk增加之前分配方案的收益值；R2為增加xijk之后的收益值；ΔRijk為前后分配方案的收益差值。按照邊緣受益最大原則,優(yōu)先選擇給分配方案帶來(lái)最大收益max{ΔRijk}的分配組合x(chóng)ijk,直到任務(wù)分配結(jié)束。

2)調(diào)節(jié)因子α

α(k)=

(14)

式中：sum(NUs+NUw)為已參與分配任務(wù)的RUAVs、UCAVs數(shù)量總和;min(Ns,Nw,Nt)為三者中的最小值;NUw(ε)和NUw(k)為目標(biāo)ε和k已分配的武器個(gè)數(shù),ε=1,2,…,k-1,k+1,…,Nt。當(dāng)所有目標(biāo)均未被分配武器或分配達(dá)到最小輪次時(shí),調(diào)節(jié)因子全為1;當(dāng)某一目標(biāo)k已被分配RUAV/UCAV,且存有仍未被分配RUAV/UCAV的目標(biāo)時(shí),將k所對(duì)應(yīng)的調(diào)節(jié)因子α(k)賦值為0。通過(guò)調(diào)節(jié)因子修正,可避免出現(xiàn)資源分配不均勻的情形,達(dá)到資源均衡分配。

2.4 任務(wù)分配流程

本文提出一種改進(jìn)的基于邊緣受益最大的貪婪算法(GA-MMR)用于解決RUAVs/UCAVs、目標(biāo)分配問(wèn)題,具體步驟如下所示:

Input:Ns,Nw,Nt,NUs,NUw,{v}1*Nt,{pik}Ns*Nt,{qjk}Nw*Nt;

Output:X,Y,Z,R;

1.Initialization:X←0,Y←0,Z←0,α←1,Pmis(k)←1,Qmis(k)←1;

2.Set upA=[a(i,j,k)]o*3,o=Ns*Nw*Nt,i=1 toNs,j=1 toNw,k=1 toNt;

3.while(～is empty(A))

3.1 fork=1 toNt

CalculateR1(k)

end

3.2.ifa(i,j,k) violates (6)(7)

Deletea(i,j,k);

end

3.3.ifPdes(k)>Pd

Deletea(*, *,k);

end

3.4.fork=1 toNt

CalculateR2(k) and ΔRi,j,k;

end

End while

3 仿真算例與分析

3.1 仿真數(shù)據(jù)產(chǎn)生

本文中所有算例數(shù)據(jù)均在允許范圍內(nèi)隨機(jī)產(chǎn)生,目標(biāo)威脅程度(價(jià)值)產(chǎn)生方法如(15)式所示

vk=vl+(vu-vl)×rand

(15)

式中，vl與vu分別為目標(biāo)價(jià)值的上下限值。RUAVs成功捕獲追蹤目標(biāo)的概率和UCAVs成功摧毀目標(biāo)的概率均采用上述方法產(chǎn)生,其范圍如表1所示。

表1 數(shù)據(jù)上下限值

3.2 仿真算例

1) 對(duì)比算法

為驗(yàn)證所提模型以及算法的有效性,本文選擇、設(shè)計(jì)了以下對(duì)比算法。文獻(xiàn)[12]中的MRBCH算法、加入目標(biāo)期望摧毀概率的MRBCH-Pd算法以及加入調(diào)節(jié)因子(revision factor,RF)α的MRBCH-RF算法。

2) 仿真算例

根據(jù)RUAV/UCAV的數(shù)量和目標(biāo)數(shù)量,本文設(shè)計(jì)了3種情況的仿真算例。情形一:RUAV/UCAV組合數(shù)量小于目標(biāo)數(shù)量;情形二:RUAV/UCAV組合數(shù)量與目標(biāo)數(shù)量相同;情形三:RUAV/UCAV組合數(shù)量大于目標(biāo)數(shù)量。為了驗(yàn)證目標(biāo)期望概率對(duì)分配結(jié)果的影響,特在情形三中額外設(shè)置了一組對(duì)比實(shí)驗(yàn)。仿真算例采用的數(shù)據(jù)如表2所示。

表2 仿真數(shù)據(jù)

3.3 仿真結(jié)果與分析

為驗(yàn)證所提模型方法的有效性,從算例運(yùn)行時(shí)間、分配結(jié)果以及影響因素三方面對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)分析。

1) 算例仿真時(shí)間與結(jié)果

不同情形下仿真算例的運(yùn)行時(shí)間如表3所示,目標(biāo)期望摧毀概率設(shè)置為0.85。每種算法獨(dú)立運(yùn)行11次,算法運(yùn)行時(shí)間取11次平均值,單位為s。從表3可以看出,文中4種算法所用時(shí)間在一定程度內(nèi)均可滿(mǎn)足任務(wù)實(shí)時(shí)性的要求。

表3 算例1～6仿真運(yùn)行時(shí)間表 s

在求解算例1,3時(shí)，本文所提算法GA-MMR與MRBCH-Pd算法在運(yùn)行時(shí)間上表現(xiàn)相近，且在求解算例2,4,5～8時(shí)GA-MMR算法比MRBCH、MRBCH-Pd及MRBCH-RF算法所需運(yùn)行時(shí)間少;在算例5、6中,當(dāng)RUAV/UCAV數(shù)量大于100時(shí),所提算法相比改進(jìn)前算法,運(yùn)行時(shí)間分別減少27.5%和46.80%。

從表4可以看出,MRBCH算法求出分配方案的收益值最高。MRBCH-Pd、MRBCH-RF與GA-MMR 3種算法在求解算例2,4,5～8時(shí),由于調(diào)節(jié)因子或目標(biāo)期望概率約束條件的原因,未能得到收益值最大的分配方案。

表4 算例1～6分配方案收益值

圖1為算例2分配方案中中各目標(biāo)摧毀概率的箱線(xiàn)圖。算例2中MRBCH-Pd與GA-MMR算法得到的RUAVs/UCAVs分配方案與其它算法相比,目標(biāo)摧毀概率值更均勻。

圖1 算例2不同算法分配方案中各目標(biāo)摧毀概率的箱線(xiàn)圖

由于算例2中的目標(biāo)期望摧毀概率設(shè)置為0.85,當(dāng)目標(biāo)1,5,6,39,41,45的摧毀概率大于0.85后,其不再參與分配過(guò)程。因此,MRBCH-Pd 與GA-MMR算法未能選擇收益較大的方法,將資源分給目標(biāo)2,3,7,13,15以及目標(biāo)23,避免了資源的過(guò)度分配,其各目標(biāo)的摧毀概率如圖2所示。

圖2 算例2不同算法分配方案部分目標(biāo)摧毀概率值

以MRBCH和MRBCH-Pd算法為參考基準(zhǔn), 圖3為算例4各算法獲得分配方案的摧毀概率差異圖。MRBCH和MRBCH-Pd算法求解的分配方案中目標(biāo)10和30所分配資源為0,加入分配調(diào)節(jié)因子的MRBCH-RF與GA-MMR算法放棄高收益的分配方案將6和11的資源分配給目標(biāo)10和30,加強(qiáng)了資源分配的均勻性。針對(duì)算例5～8,RUAV/UCAV數(shù)量遠(yuǎn)大于目標(biāo)數(shù)。此時(shí),MRBCH算法將所有資源全部分配給目標(biāo),因此該算法所得分配方案具有高收益值;而GA-MMR算法引入了目標(biāo)期望摧毀概率的約束,當(dāng)目標(biāo)摧毀概率滿(mǎn)足設(shè)置期望摧毀概率時(shí)就會(huì)停止任務(wù)分配,避免了資源的過(guò)度分配。

圖3 算例4不同算法分配方案中各目標(biāo)摧毀概率的差異圖

2) 目標(biāo)期望摧毀概率對(duì)任務(wù)分配結(jié)果的影響

任務(wù)分配方案經(jīng)濟(jì)性指標(biāo)與方案總收益、資源消耗成本以及作戰(zhàn)效能均有關(guān)。為了定量對(duì)分配方案進(jìn)行衡量,本文設(shè)計(jì)、提出了一種資源分配方案經(jīng)濟(jì)性指標(biāo)用來(lái)衡量分配結(jié)果的質(zhì)量。計(jì)算方式如公式(16)～(19)所示

(16)

C=w1*NUs+w2*NUw

(17)

(18)

(19)

表5 算例6～8 GA-MMR和MRBCH分配方案結(jié)果

其中min(Pdes)為分配結(jié)果中各目標(biāo)摧毀概率的最小值。據(jù)表5可知,隨著目標(biāo)期望摧毀概率的增大,參與任務(wù)的RUAV/UCAV數(shù)量以及仿真運(yùn)行時(shí)間也不斷增加。另外,分配結(jié)果中所有目標(biāo)摧毀概率最小值均滿(mǎn)足設(shè)置的目標(biāo)期望摧毀概率,驗(yàn)證了分配模型的有效性。當(dāng)目標(biāo)期望摧毀概率設(shè)置為0.85,0.9以及0.95時(shí),GA-MMR算法所得分配方案的經(jīng)濟(jì)指標(biāo)分別比MRBCH高68.4%,25.75%以及3.34%。由于任務(wù)分配初期等量RUAV/UCAV給總方案帶來(lái)的收益比后期等量資源帶來(lái)的收益高,因此當(dāng)期望摧毀概率為0.85時(shí),經(jīng)濟(jì)效能最高。通過(guò)本文所提模型與算法,任務(wù)規(guī)劃者通過(guò)設(shè)置不同的目標(biāo)期望摧毀概率,可以為任務(wù)決策者提供更多可供選擇的任務(wù)分配方案,在滿(mǎn)足作戰(zhàn)效能的基礎(chǔ)上提高了經(jīng)濟(jì)效能。

4 結(jié) 論

1) 本文提出了一種考慮目標(biāo)期望摧毀概率的多無(wú)人機(jī)任務(wù)分配方法,可為解決實(shí)時(shí)任務(wù)分配問(wèn)題提供參考。

2) 通過(guò)在模型目標(biāo)函數(shù)中加入分配調(diào)節(jié)因子,彌補(bǔ)了原有方法出現(xiàn)資源分配不均的不足;引入目標(biāo)期望摧毀概率作為約束條件,避免了出現(xiàn)資源過(guò)度分配的情形。

3) 當(dāng)任務(wù)可用RUAVs/UCAVs數(shù)量遠(yuǎn)大于任務(wù)需求時(shí),本文所提模型算法,能夠給出滿(mǎn)足決策者不同目標(biāo)期望摧毀概率的分配方案,在滿(mǎn)足作戰(zhàn)效能的基礎(chǔ)上又提高了經(jīng)濟(jì)效能,改善了任務(wù)分配質(zhì)量。

下一步,將更加注重任務(wù)分配的質(zhì)量和效率,加入多功能UAV執(zhí)行任務(wù)的情形,進(jìn)一步增加所提方法的適用性。