基于CNP方法的多無人機實時任務分配

解 濤, 郭建勝, 張曉豐, 余稼洋

(空軍工程大學,西安 710000)

0 引言

無人機(UAV)擁有抗毀性強、成本低、作戰(zhàn)效費比高等優(yōu)勢,在軍事和民用領域被廣泛應用[1]。因為平臺自主性和傳感器/武器等功能單元載荷的限制,單UAV已經不能滿足日益復雜的應用環(huán)境,需要異構多無人機的協(xié)同使用[2]。

為解決多無人機任務分配問題,學者們提出許多集中式和分布式算法。其中經典的集中式算法有遺傳算法[3-4]、蟻群算法[5]和粒子群算法[6]等,該類算法都依賴于UAV與地面基站之間的持續(xù)通信,對動態(tài)變化響應緩慢。在分布式算法中,研究的重點在于類市場機制算法,主要包括合同網協(xié)議(Contract Net Protocol,CNP)[7]和拍賣算法(Auction Algorithm)[8]。在分布式算法中,每架UAV作為一個相對獨立的決策處理單元,可以直接處理任務信息,它具有很強的容錯性、靈活性和可靠性。CNP算法在動態(tài)環(huán)境下表現(xiàn)出優(yōu)越的實時性、魯棒性,被廣泛應用于多智能體實時任務分配中。文獻[9]根據(jù)UAV任務執(zhí)行過程中多參與者、多任務的特點,提出合作者的確定機制和順序任務的選擇機制,并對CNP算法進行擴展,設計一種基于事件觸發(fā)的動態(tài)任務分配策略,提高UAV在突發(fā)環(huán)境下的適應性和執(zhí)行任務的效率。

然而,許多研究的前提是UAV同質、目標信息已知,通信不受限等,在復雜的戰(zhàn)場環(huán)境中,這些假設往往不成立。例如,無人機在起飛前只知道任務的粗略信息,需要實時任務分配,還需要滿足資源、協(xié)同攻擊等限制。在戰(zhàn)場環(huán)境中,UAV面臨的任務是不可預測的,包括位置和攻擊資源需求等,這要求資源消耗分配足夠合理,保證UAV的剩余攻擊資源能夠成功地執(zhí)行后續(xù)任務。目前,大多數(shù)資源消耗分配方法采用Greedy算法,會導致部分UAV的資源過快地消耗完畢,失去執(zhí)行任務的能力。文獻[10]提出了一種以資源福利為資源消耗策略的方法,本質是一種均衡消耗資源的方法,能夠將UAV間的資源差異降到最低,但該方法沒有考慮到UAV因其所處任務區(qū)域的位置不同,執(zhí)行的任務數(shù)量也不同。

綜合來看,合理的任務分配不僅要考慮任務環(huán)境、目標、無人機類型和數(shù)量,還要考慮各種約束,包括資源、運動學、時間、通信等。本文對通信受限環(huán)境下異構多無人機任務分配問題的主要貢獻如下。

其一,提出一種基于CNP的局部實時任務分配方法。該方法應用于分布式架構,在打擊實時目標的任務分配時具有良好的性能。同時,將Dubins曲線應用于無人機航跡規(guī)劃,滿足最小轉彎半徑的約束。

其二,提出了一種限制接收者范圍的信息傳遞方法。在保證任務完成率的前提下,縮小招標范圍,避免傳統(tǒng)CNP算法泛洪式招標帶來的通信過載問題。

其三,提出基于Gini系數(shù)的資源消耗分配方法,使UAV間保持合理的資源差異,更好地執(zhí)行后續(xù)任務。

1 任務描述及建模

1.1 任務場景

在任務區(qū)域中,N架異構無人機先進行偵察,發(fā)現(xiàn)目標后執(zhí)行打擊任務。在無人機起飛時,目標相關信息是未知的,被發(fā)現(xiàn)后目標信息全部已知?；趨f(xié)同作戰(zhàn)的現(xiàn)實需求,發(fā)現(xiàn)目標的UAV與周圍的無人機組成攻擊聯(lián)盟,共同實施打擊任務。

本文在研究異構多無人機打擊任務中,同時考慮多種約束,主要是UAV性能約束、攻擊資源約束、同時攻擊的時間約束和UAV間的通信約束等。本文研究重點是通信受限下異構多無人機的實時任務分配。

1.2 無人機和目標建模

本文未考慮UAV的起飛和降落過程,采用高度分層實現(xiàn)UAV間的避碰,且飛行時的高度不發(fā)生變化。在二維平面中,無人機的飛行運動模型為

(1)

式中:(x,y)表示無人機在二維平面上的位置坐標;v為UAV的速度;ψ為偏航角;ωφ為偏航角速度。本文未考慮UAV姿態(tài),在攻擊任務末端,UAV不需要特定的飛行方向和角度。

在偵察任務開始前,設定的任務區(qū)域內共有N架UAV。UAV的異構設定為攻擊資源的種類和數(shù)目不同。無人機Ui(i=1,2,…,N)攜帶的攻擊資源為

(2)

1.3 約束條件

在通信受限環(huán)境下,異構多無人機執(zhí)行實時打擊任務分配問題考慮的約束如下。

1) 資源約束。

UAV起飛前攜帶的資源有限,摧毀目標Tj需要一定數(shù)量的資源,攻擊聯(lián)盟的各類資源的總數(shù)要滿足

(3)

式中,nc代表組建的攻擊聯(lián)盟中的UAV成員序號。

2) 無人機自身性能約束。

無人機攜帶的燃油資源應能夠保證無人機完成任務所要求的航程,否則不能參與到攻擊聯(lián)盟的組建中。設定燃料和飛行距離成正比,燃料約束可以轉換為飛行距離約束,無人機的飛行距離需要滿足

(4)

3) 時間約束。

本文無人機聯(lián)盟協(xié)同作戰(zhàn)的要求是聯(lián)盟中的無人機成員同時到達目標位置。航程較近、飛行時間少的UAV可以選擇增加路徑、盤旋、飛行速度放緩等方式來延長到達目標的時間,算式為

(5)

4) 通信約束。

1.4 目標函數(shù)

1) 聯(lián)盟的代價函數(shù)為

(6)

式中:Cj為攻擊目標Tj的聯(lián)盟;nC為攻擊目標Tj的無人機聯(lián)盟序號;τ為燃油消耗系數(shù);di為無人機Ui的航行里程;UValue為無人機的自身價值;TThreat∈[0,1],為目標的威脅程度。

2) 任務完成的收益函數(shù)為

(7)

式中:V(Tj)為初始時刻目標的價值;ζ(t)為時間衰減函數(shù);θ為目標的時敏性,值越大,目標價值隨時間增加降低得越快。

3) 總體收益為

(8)

2 基于CNP的實時局部任務分配方法

SMITH[11]于1980年首次將CNP用于解決分布式協(xié)商問題,在市場機制中模擬“招標、投標、中標”的協(xié)商過程,追求目標函數(shù)的最優(yōu)解。CNP方法已經被證明具有較好的擴展性、魯棒性和較快的協(xié)商效率,適用于實時的局部任務分配。

2.1 通信受限下的實時局部任務分配方法

針對通信受限環(huán)境下無人機群的局部實時任務,提出了一種基于CNP的異構多無人機協(xié)同任務分配方法,詳細介紹了UAV對目標“招標、投標、中標”的過程。

1) 任務發(fā)布。

無人機群在飛行中組建為Ad-hoc(點對點)網絡,通信方式按照是否有通信節(jié)點可以分為直接通信和間接通信,通信節(jié)點由中繼無人機擔任。無人機群往往采用泛洪法將信息傳遞給通信范圍內的其他無人機,該方法能夠確保所有的無人機都能接收到信息,但會存在內爆和廣播風暴的問題[12]。文獻[13]的研究表明限制廣播次數(shù)可以緩解上述問題發(fā)生。限制廣播次數(shù)的方式有兩類:其一是在任務發(fā)布階段限制無人機單鏈路通信之間的節(jié)點數(shù)目,即限制最大信息傳遞次數(shù)Hmax;其二是在招標申請階段對競標者的條件進行限制,避免違約發(fā)生,造成通信資源的浪費。

本文以減少UAV間的通信載荷為目的,提出以目標等級和資源需求為指標的自適應信息最大傳遞次數(shù)設置方法(AD-MITT),可以確保在攻擊重要目標時,盡可能成功地組建聯(lián)盟;在攻擊次要目標時,限制招標范圍,節(jié)約通信資源,加快聯(lián)盟形成,表示為

(9)

式中:?為權值系數(shù);Dj為Tj的任務等級;A為權值向量,表示將目標的摧毀資源需求轉換成摧毀的難易度;計算后向上取整得Hmax。

通信受限下U0的局部通信網絡如圖1所示。

圖1 通信受限下U0的局部通信網絡

算法1 任務發(fā)布

4Ui發(fā)送Oi給其通信直連的UAV

5 end if

6 fork=1:收到的招標信息數(shù)目do

7 if擁有Tj所需要的資源then

9Pi←Pk

10 end if

11 end if

12 end for。

算法1中,通信網絡中的UAV傳遞招標信息給其直連的UAV(1～5行),接收到招標信息的UAV判斷自身是否攜帶目標所需資源,同時從接收到的所有招標信息中選擇收益最高的任務去執(zhí)行。通過信息傳遞,局部通信網絡中的所有UAV對招標信息達成一致。

2) 招標申請。

任務發(fā)布后,局部通信網絡中的UAV保留著相同的招標信息。對Tj有招標意向的Uk首先計算出預計到達Tj的時間tk,然后向聯(lián)盟長機Ui發(fā)送競標信息Bk,Bk所含信息為

(10)

3) 聯(lián)盟組建。

4) 簽訂合約。

2.2 基于Gini系數(shù)的資源消耗分配方法

1) Gini系數(shù)。

1912年,意大利統(tǒng)計學家GINI提出了Gini系數(shù)來衡量財富分配均衡程度。無人機機群攜帶的攻擊資源等價于財富收入,UAV攻擊資源分配的均衡程度可以采用Gini系數(shù)作為衡量指標。本文采用文獻[14]的方法計算Gini系數(shù)(G),即

(11)

式中,Wi是從資源最少的UAV到第i架UAV占總資源的百分比。

2) 基于Gini系數(shù)的資源消耗分配方法。

算法2 基于Gini系數(shù)的資源消耗分配方法

1 initialize

2 forTj資源需求的類型數(shù)目kdo

3 for allUido

7 計算各個UAVk型資源的剩余

8 計算Gini系數(shù)

11 end if

12 end for

13 end for

14V=(V1,V2,V3,…,Vk)

15 end for

16 returnV。

3) 最優(yōu)G值的設置。

基于Gini系數(shù)的資源消耗分配方法能夠合理控制UAV間的資源差異,提升無人機機群的魯棒性,在任務完成的數(shù)量和應對突發(fā)任務的動態(tài)性上均得到改善。但其建立在選取合適G值的基礎上,所以需要根據(jù)任務場景的特性設置合適的G值。

G值設置受到多因素影響,比如任務總的數(shù)量、UAV規(guī)模、UAV所處位置、UAV初始攜帶的資源數(shù)量等。在通信距離受限的環(huán)境下,處于機群中央位置的UAV會承擔更多的攻擊任務,攜帶的資源需要多于邊緣的UAV。所以G值的選取受到UAV任務地位的影響。

3 實驗與分析

3.1 異構多無人機協(xié)同任務場景

任務場景的設定范圍是3500 m×3500 m。無人機群由7架察打一體型無人機組建而成,其中,各無人機攜帶攻擊資源的種類和數(shù)目均不同。任務區(qū)域中有2個任務目標,相關信息如表1所示。UAV起飛前只有自己執(zhí)行偵察任務的路徑信息,沒有關于目標和其他UAV的信息。直到某一無人機按照偵察路徑發(fā)現(xiàn)目標后,繼而轉為攻擊階段。UAV初始時刻的相關信息如表2所示。各UAV的偵察半徑、通信半徑和飛行速度都分別為300 m,1000 m和50 m/s。

表1 任務目標的相關信息

表2 UAV的相關信息

初始時刻,UAV按照路徑進行偵察,在第33.0 s,U4發(fā)現(xiàn)T1,發(fā)現(xiàn)自身的攻擊資源無法滿足摧毀目標的要求后,U4作為聯(lián)盟長機在其通信網絡內發(fā)送招標信息。按照式(9)計算出Hmax=2,此時U4的局部通信網絡如圖2所示。

圖2 每架UAV在第33.0 s時的狀態(tài)

圖3 T1與中UAV的直線距離

同理,U1,U5執(zhí)行對T2的攻擊任務。當執(zhí)行完所有任務時,UAV的完整路徑如圖4所示,可以看出,UAV的飛行軌跡滿足最小轉彎半徑約束。并且,UAV在執(zhí)行完任務后會繼續(xù)進行偵察,例如U1,U5。同時,UAV到達任務區(qū)域邊界時會以最短的路徑返回。

圖4 UAV執(zhí)行完任務的完整路徑

3.2 不同資源消耗分配方法性能對比

無人機間的資源消耗方式影響無人機機群執(zhí)行任務的魯棒性。本節(jié)通過設置不同的G值來分析G值對資源消耗合理性的影響,并通過仿真實驗對比了基于Gini系數(shù)的算法、貪婪算法和資源平衡算法3種資源消耗方法的性能。

在本節(jié)實驗中,6架無人機依次執(zhí)行任務集中的30個任務,任務目標需要3種攻擊資源去摧毀,每類資源的需求均為1～50之間的隨機整數(shù),任務級別為1～3之間的隨機整數(shù)。在每組參數(shù)設置下,都進行100次仿真實驗,對結果取平均值。當無人機G值從0到1變化時,無人機機群平均完成的任務數(shù)量如圖5所示。

圖5 隨G值增長平均的任務完成數(shù)

從圖5可以看出,G值在0.3～0.4范圍內都能取得一個較好的效果。原因是UAV在通信受限的環(huán)境下,處于任務區(qū)域中間位置的無人機往往會收到更多的聯(lián)盟組建請求,承擔更多的任務。所以在資源消耗的分配方案中,任務區(qū)域中間位置的無人機要與邊緣位置的UAV保持一定的資源差異。但資源差異過大同樣會導致任務邊緣位置UAV的資源過多被消耗,不能完成相應任務。

圖6(a)展示了3種不同資源方法的平均完成任務數(shù)量,其中,基于Gini系數(shù)的資源消耗分配方法中G值取0.3。圖6(b)～6(d)分別為3種方法完成一組任務集下的資源變換情況。

圖6 剩余資源分析

如圖6(a)所示,基于Gini系數(shù)的資源消耗分配算法在相同的任務場景下完成的任務數(shù)要多于其他兩種算法。圖6(b)表明,基于資源平衡的算法能夠將無人機之間的資源保持一致,其中,U1,U2和其他無人機資源差異較大的原因主要是其處于任務區(qū)域邊緣,參與攻擊的次數(shù)較少。圖6(c)展示了貪婪算法在執(zhí)行任務中過早地消耗某些UAV的資源,導致后續(xù)的任務不能完成。圖6(d)顯示了基于Gini系數(shù)的算法在執(zhí)行任務時的資源變化情況,可以看出,UAV之間的資源差異保持在一個合理的范圍內,考慮到了無人機任務區(qū)域位置不同帶來的差異。

4 結論

本文提出了一種改進的基于CNP的方法,能夠解決多約束下的UAV實時任務分配問題;提出的AD-MITT算法能夠限制招標范圍,減少通信負擔;提出了基于Gini系數(shù)的資源消耗分配方法,將UAV間的資源差異控制在合理范圍內,完成更多的任務。實驗結果表明,基于CNP的方法比對照算法在完成任務的時間和收益方面可以獲得更好的表現(xiàn)。在資源約束下,基于Gini系數(shù)的資源消耗分配方法在完成任務數(shù)上優(yōu)于貪婪算法和資源平衡算法,該方法可以合理調節(jié)無人機之間的資源差異,提高了UAV在想定任務場景中的動態(tài)性。