考慮目標期望摧毀概率的多無人機任務分配方法

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

(1.西北工業大學 深圳研究院, 廣東 深圳 518057; 2.西北工業大學 自動化學院, 陜西 西安 710072;3.長安大學 地質工程與測繪學院, 陜西 西安 710054)

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

目前，求解任務分配的算法大致可分為數學規劃方法[7-8]、基于合同網的任務分配方法[4,9]以及啟發式智能優化算法[3,10]三大類。

數學規劃方法作為一種確定性算法，可以給出任務分配問題的最優解。然而，求解大規模分配問題時，由于求解難度劇增會導致耗時增加，在有限時間內該方法無法保證給出滿意的規劃結果[1]。

基于合同網的方法將任務分配視為一個協商過程，買賣雙方以出價的形式競爭獲得任務的執行權。但基于合同網的任務分配方法需任務執行主體間多次協商，在問題規模較大時勢必造成通信量增大以及耗時增加的問題。

以遺傳算法、蟻群算法等為代表的智能優化算法，由于其不要求目標函數的連續性以及可導性，在任務分配方面引起了許多學者的研究興趣[10-11]。智能優化算法在優化過程中，整個種群中的所有個體同時向全局最優逐漸收斂。但由于智能優化算法存有大量隨機性搜索嘗試，致使在求解任務分配問題時會出現效率和精度不高的現象[1]。

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

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

1 RUAV、UCAV任務分配模型

1.1 問題描述

本文考慮如下作戰場景。在T時刻監測到有Nt個具有不同威脅程度的目標來襲，防御者擁有RUAVs和UCAVs攔截目標。Ns個RUAVs用來捕獲跟蹤目標，從而引導Nw個UCAVs對其進行摧毀。不同RUAV、UCAV對不同目標的捕獲跟蹤、摧毀能力不同。如何將這些RUAVs和UCAVs協同高效進行分配，達到有效抵御的目的是本文研究的關鍵問題。

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

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

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

(1)

假設不同RUAV和UCAV對目標的成功捕獲和摧毀事件是相互獨立的事件。則目標k被成功捕獲追蹤的概率可通過(2)式計算

(2)

式中，pik為目標k被第i個RUAV成功捕獲追蹤的概率。同樣目標k被成功摧毀的概率計算公式為

(3)

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

Pdes(k)=

(4)

1.2 分配模型收益函數

本文設計了一種高效的RUAVs/UCAVs、目標任務分配模型,目標函數為最大化摧毀敵方目標的價值(或最大化減少敵對目標威脅值)。

(5)

式中：R為分配方案對應收益值;vk表示目標k的威脅值(目標價值);α(k)為目標k的資源分配調節因子,其用于指導分配過程,確保資源分配的均衡性。

1.3 約束條件

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

(6)

(7)

為提高分配結果的經濟效能,引入目標期望摧毀概率約束。若某一目標已分配資源(RUAVs、UCAVs)滿足摧毀該目標的概率不低于其摧毀期望值(expected probability of destruction,Pd),則停止對該目標分配資源,避免造成資源的浪費;否則根據分配規則繼續參與分配過程,直到分配結束。

(8)

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

2 RUAV、UCAV任務分配方法

2.1 輔助決策矩陣

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

2.2 約束處理方法

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

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

同樣在分配過程中,當目標k的摧毀概率滿足期望摧毀概率Pd(k)時,將涉及目標k的分配方案從分配集合中刪除,加快分配進程實現高效任務分配。

2.3 任務分配規則

本文在建立目標函數基礎上,采用邊緣收益最大的貪心原則進行任務分配。同時為保證資源分配的均衡性,在目標函數中增加了調節因子α。

1) 邊緣受益最大原則

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

(9)

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

(10)

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

在任務分配開始階段,任務分配的受益為0。當新增加任務分配方案xijk時,由于增加的xijk所帶來的收益增加ΔRijk計算方法如下所示

式中：R1為xijk增加之前分配方案的收益值；R2為增加xijk之后的收益值；ΔRijk為前后分配方案的收益差值。按照邊緣受益最大原則,優先選擇給分配方案帶來最大收益max{ΔRijk}的分配組合xijk,直到任務分配結束。

2)調節因子α

α(k)=

(14)

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

2.4 任務分配流程

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

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 仿真數據產生

本文中所有算例數據均在允許范圍內隨機產生,目標威脅程度(價值)產生方法如(15)式所示

vk=vl+(vu-vl)×rand

(15)

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

表1 數據上下限值

3.2 仿真算例

1) 對比算法

為驗證所提模型以及算法的有效性,本文選擇、設計了以下對比算法。文獻[12]中的MRBCH算法、加入目標期望摧毀概率的MRBCH-Pd算法以及加入調節因子(revision factor,RF)α的MRBCH-RF算法。

2) 仿真算例

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

表2 仿真數據

3.3 仿真結果與分析

為驗證所提模型方法的有效性,從算例運行時間、分配結果以及影響因素三方面對結果進行統計分析。

1) 算例仿真時間與結果

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

表3 算例1～6仿真運行時間表 s

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

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

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

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

圖1 算例2不同算法分配方案中各目標摧毀概率的箱線圖

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

圖2 算例2不同算法分配方案部分目標摧毀概率值

以MRBCH和MRBCH-Pd算法為參考基準, 圖3為算例4各算法獲得分配方案的摧毀概率差異圖。MRBCH和MRBCH-Pd算法求解的分配方案中目標10和30所分配資源為0,加入分配調節因子的MRBCH-RF與GA-MMR算法放棄高收益的分配方案將6和11的資源分配給目標10和30,加強了資源分配的均勻性。針對算例5～8,RUAV/UCAV數量遠大于目標數。此時,MRBCH算法將所有資源全部分配給目標,因此該算法所得分配方案具有高收益值;而GA-MMR算法引入了目標期望摧毀概率的約束,當目標摧毀概率滿足設置期望摧毀概率時就會停止任務分配,避免了資源的過度分配。

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

2) 目標期望摧毀概率對任務分配結果的影響

任務分配方案經濟性指標與方案總收益、資源消耗成本以及作戰效能均有關。為了定量對分配方案進行衡量,本文設計、提出了一種資源分配方案經濟性指標用來衡量分配結果的質量。計算方式如公式(16)～(19)所示

(16)

C=w1*NUs+w2*NUw

(17)

(18)

(19)

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

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

4 結 論

1) 本文提出了一種考慮目標期望摧毀概率的多無人機任務分配方法,可為解決實時任務分配問題提供參考。

2) 通過在模型目標函數中加入分配調節因子,彌補了原有方法出現資源分配不均的不足;引入目標期望摧毀概率作為約束條件,避免了出現資源過度分配的情形。

3) 當任務可用RUAVs/UCAVs數量遠大于任務需求時,本文所提模型算法,能夠給出滿足決策者不同目標期望摧毀概率的分配方案,在滿足作戰效能的基礎上又提高了經濟效能,改善了任務分配質量。

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