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

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

0 引言

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

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

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

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

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

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

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

1 任務(wù)描述及建模

1.1 任務(wù)場景

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

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

1.2 無人機和目標(biāo)建模

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

(1)

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

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

(2)

1.3 約束條件

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

1) 資源約束。

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

(3)

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

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

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

(4)

3) 時間約束。

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

(5)

4) 通信約束。

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

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

(6)

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

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

(7)

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

3) 總體收益為

(8)

2 基于CNP的實時局部任務(wù)分配方法

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

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

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

1) 任務(wù)發(fā)布。

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

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

(9)

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

通信受限下U0的局部通信網(wǎng)絡(luò)如圖1所示。

圖1 通信受限下U0的局部通信網(wǎng)絡(luò)

算法1 任務(wù)發(fā)布

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

5 end if

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

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

9Pi←Pk

10 end if

11 end if

12 end for。

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

2) 招標(biāo)申請。

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

(10)

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

4) 簽訂合約。

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

1) Gini系數(shù)。

1912年,意大利統(tǒng)計學(xué)家GINI提出了Gini系數(shù)來衡量財富分配均衡程度。無人機機群攜帶的攻擊資源等價于財富收入,UAV攻擊資源分配的均衡程度可以采用Gini系數(shù)作為衡量指標(biāo)。本文采用文獻(xiàn)[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值的設(shè)置。

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

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

3 實驗與分析

3.1 異構(gòu)多無人機協(xié)同任務(wù)場景

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

表1 任務(wù)目標(biāo)的相關(guān)信息

表2 UAV的相關(guān)信息

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

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

圖3 T1與中UAV的直線距離

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

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

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

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

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

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

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

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

圖6 剩余資源分析

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

4 結(jié)論

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