陳璞，嚴(yán)飛,*，劉釗，成果達(dá)

1. 航空工業(yè)西安飛行自動(dòng)控制研究所，西安 710076

2. 中國(guó)飛行試驗(yàn)研究院，西安 710089

由于單架無(wú)人機(jī)(UAV)執(zhí)行任務(wù)時(shí)存在性能限制，利用多無(wú)人機(jī)協(xié)同配合，完成以往單無(wú)人機(jī)很難或是不能完成的任務(wù)成為了學(xué)界、工業(yè)界、軍方廣泛關(guān)注的熱點(diǎn)[1-2]。為了提高多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)的系統(tǒng)效能，首先需要將任務(wù)進(jìn)行分解，再使用任務(wù)分配方法將任務(wù)集合分配給無(wú)人機(jī)集群中的各無(wú)人機(jī)，以實(shí)現(xiàn)多機(jī)系統(tǒng)的高效協(xié)同。

多無(wú)人機(jī)任務(wù)分配問(wèn)題可以看作是組合優(yōu)化問(wèn)題，需要結(jié)合特定的任務(wù)場(chǎng)景對(duì)其進(jìn)行建模和求解[3]。在考慮特定場(chǎng)景下的任務(wù)要求、約束條件及無(wú)人機(jī)特性后，將任務(wù)分配問(wèn)題建模成幾種經(jīng)典的優(yōu)化問(wèn)題模型或是其變種問(wèn)題,常用的經(jīng)典優(yōu)化問(wèn)題模型有多旅行商問(wèn)題(MTSP)[4]、車(chē)輛路由問(wèn)題(VRP)[5-6]、混合整數(shù)線性規(guī)劃(MILP)[7-8]以及協(xié)同多任務(wù)分配問(wèn)題(CMTAP)[9-10]模型等。文獻(xiàn)[11-12] 分別考慮了無(wú)人機(jī)的有限資源和時(shí)敏目標(biāo)，將任務(wù)分配問(wèn)題分別建模為有容量限制的車(chē)輛路由模型(CVRP)和帶時(shí)間窗的車(chē)輛路由問(wèn)題(VRPTW)模型。文獻(xiàn)[9-10]將多無(wú)人機(jī)對(duì)多目標(biāo)依次執(zhí)行確認(rèn)、攻擊、毀傷評(píng)估的任務(wù)分配問(wèn)題建模為CMTAP問(wèn)題，并使用改進(jìn)遺傳算法對(duì)問(wèn)題進(jìn)行求解。

針對(duì)多無(wú)人機(jī)任務(wù)分配問(wèn)題的求解，常用的方法有最優(yōu)化方法、啟發(fā)式方法以及市場(chǎng)機(jī)制方法。最優(yōu)化方法[13-14]大多屬于確定性搜索方法，常用于集中式架構(gòu)下問(wèn)題規(guī)模較小時(shí)的離線任務(wù)分配。與最優(yōu)化方法不同，啟發(fā)式方法并不試圖遍歷整個(gè)搜索空間以獲取最優(yōu)解，而是在可接受的時(shí)間內(nèi)獲得優(yōu)化問(wèn)題的可行解。這類方法大多以模仿自然現(xiàn)象為主，常用蟻群算法[15](ACO)、遺傳算法[16](GA)、粒子群算法[17](PSO)、模擬退火算法[18](TS)、狼群算法[19]等。在分布式架構(gòu)下，使用最優(yōu)化方法和啟發(fā)式方法前往往需要先使用一致性算法[20]使得各無(wú)人機(jī)實(shí)現(xiàn)一致的態(tài)勢(shì)感知，但多無(wú)人機(jī)實(shí)現(xiàn)態(tài)勢(shì)感知一致性需要大量的通信和計(jì)算量。

因此有學(xué)者使用基于市場(chǎng)機(jī)制方法(如基于合同網(wǎng)的拍賣(mài)算法為多無(wú)人機(jī)進(jìn)行任務(wù)分配，其優(yōu)點(diǎn)主要體現(xiàn)在：① 大多數(shù)市場(chǎng)機(jī)制的任務(wù)分配方法并不需要各無(wú)人機(jī)達(dá)成一致的態(tài)勢(shì)感知，各無(wú)人機(jī)可根據(jù)其局部態(tài)勢(shì)感知實(shí)現(xiàn)多機(jī)協(xié)同；② 與 最優(yōu)化和啟發(fā)式方法不同，隨著問(wèn)題規(guī)模的增加，市場(chǎng)機(jī)制方法的計(jì)算量通常增加不大[21]。③ 市場(chǎng)機(jī)制的方法大多用于分布式架構(gòu)，不存在系統(tǒng)中心，單無(wú)人機(jī)可以方便地加入或退出系統(tǒng)，魯棒性和靈活性較強(qiáng)。

目前針對(duì)多機(jī)協(xié)同任務(wù)分配問(wèn)題的研究大多假定各無(wú)人機(jī)已經(jīng)獲得了任務(wù)區(qū)域內(nèi)全部目標(biāo)信息，并且根據(jù)無(wú)人機(jī)與目標(biāo)的數(shù)目關(guān)系將無(wú)人機(jī)與目標(biāo)的配比關(guān)系設(shè)為固定值。然而在實(shí)際作戰(zhàn)任務(wù)中，由于環(huán)境高度對(duì)抗，很難在開(kāi)始執(zhí)行任務(wù)時(shí)就獲得任務(wù)區(qū)域的態(tài)勢(shì)。比如多無(wú)人機(jī)執(zhí)行偵察和打擊任務(wù)時(shí)，無(wú)人機(jī)隨時(shí)可能發(fā)現(xiàn)新目標(biāo)，并且當(dāng)發(fā)現(xiàn)目標(biāo)時(shí)才能獲得攻擊目標(biāo)所需資源。在這種多無(wú)人機(jī)執(zhí)行察打任務(wù)的場(chǎng)景中，無(wú)人機(jī)集群需要對(duì)被發(fā)現(xiàn)目標(biāo)進(jìn)行實(shí)時(shí)任務(wù)分配，所分配的無(wú)人機(jī)集合還需滿足目標(biāo)資源約束和同時(shí)攻擊能力[22-23]。針對(duì)多無(wú)人機(jī)執(zhí)行偵察和打擊任務(wù)中發(fā)現(xiàn)目標(biāo)時(shí)的實(shí)時(shí)任務(wù)分配問(wèn)題，Sujit等[24]基于合同網(wǎng)協(xié)議提出了一種多項(xiàng)式時(shí)間聯(lián)盟構(gòu)建算法，能夠分配滿足目標(biāo)資源的無(wú)人機(jī)聯(lián)盟最快到達(dá)目標(biāo)。Kim等[25]基于經(jīng)濟(jì)學(xué)中資源福利概念提出了一種聯(lián)盟構(gòu)建算法，能夠使得各無(wú)人機(jī)以一種平衡的方式消耗資源，更好地應(yīng)對(duì)察打任務(wù)中隨時(shí)可能發(fā)現(xiàn)新目標(biāo)的動(dòng)態(tài)性。上述任務(wù)分配方法假定各無(wú)人機(jī)之間通信狀況良好。

然而，多無(wú)人機(jī)集群常常在拒止環(huán)境下執(zhí)行任務(wù)，各無(wú)人機(jī)的通信距離有限且存在通信時(shí)延[26-27]。

為解決上述問(wèn)題，本文針對(duì)多異構(gòu)無(wú)人機(jī)執(zhí)行任務(wù)區(qū)域的察打任務(wù)時(shí)，存在通信范圍和時(shí)間延遲等約束條件下，提出了一種基于合同網(wǎng)的分布式任務(wù)分配方法。當(dāng)發(fā)現(xiàn)目標(biāo)時(shí)，各無(wú)人機(jī)首先根據(jù)通信時(shí)延判斷其能否成為穩(wěn)定的中繼節(jié)點(diǎn)，并對(duì)任務(wù)發(fā)布者達(dá)成一致?？紤]目標(biāo)資源約束，提出了能夠最大化系統(tǒng)效能的聯(lián)盟構(gòu)建方法。

1 問(wèn)題描述及建模

1.1 任務(wù)過(guò)程分析

任務(wù)區(qū)域中存在多架異構(gòu)無(wú)人機(jī)，包括僅具備偵察能力的偵察無(wú)人機(jī)和同時(shí)具備偵察和攻擊能力的察打一體型無(wú)人機(jī)。初始時(shí)刻目標(biāo)的位置信息未知，異構(gòu)無(wú)人機(jī)集群先執(zhí)行協(xié)同偵察任務(wù)，當(dāng)發(fā)現(xiàn)新目標(biāo)，就觸發(fā)針對(duì)該目標(biāo)的攻擊任務(wù)。發(fā)現(xiàn)新目標(biāo)的無(wú)人機(jī)通過(guò)有限的通信距離與周邊相鄰無(wú)人機(jī)進(jìn)行通信，進(jìn)行協(xié)同任務(wù)分配?？紤]到對(duì)目標(biāo)實(shí)施攻擊需要滿足目標(biāo)的資源約束，單架無(wú)人機(jī)的資源可能無(wú)法滿足要求。因此可能分配一個(gè)無(wú)人機(jī)聯(lián)盟執(zhí)行目標(biāo)的攻擊任務(wù)。為最大化目標(biāo)毀傷效能，聯(lián)盟中的無(wú)人機(jī)要求對(duì)目標(biāo)執(zhí)行同時(shí)攻擊任務(wù)。無(wú)人機(jī)集群不斷發(fā)現(xiàn)新目標(biāo)并觸發(fā)針對(duì)新目標(biāo)的任務(wù)分配和同時(shí)攻擊，直到無(wú)人機(jī)集群發(fā)現(xiàn)并攻擊任務(wù)區(qū)域內(nèi)的所有目標(biāo)。

在本文所研究的多異構(gòu)無(wú)人機(jī)偵察和打擊任務(wù)中，還需要多種類型的約束，主要包括無(wú)人機(jī)的運(yùn)動(dòng)學(xué)約束、目標(biāo)資源約束、無(wú)人機(jī)通信范圍和時(shí)間延遲約束、多無(wú)人機(jī)同時(shí)到達(dá)、無(wú)人機(jī)機(jī)間防撞以及規(guī)避障礙物等。其中涉及無(wú)人機(jī)運(yùn)動(dòng)學(xué)、同時(shí)到達(dá)目標(biāo)路徑規(guī)劃等問(wèn)題的詳細(xì)解決方案可參考文獻(xiàn)[28-29],本文的研究重點(diǎn)是通信約束下多異構(gòu)無(wú)人機(jī)執(zhí)行偵察和打擊任務(wù)中，發(fā)現(xiàn)目標(biāo)時(shí)，針對(duì)新目標(biāo)所觸發(fā)的攻擊任務(wù)的任務(wù)分配方法。

1.2 無(wú)人機(jī)和目標(biāo)模型

根據(jù)1.1節(jié)的多異構(gòu)無(wú)人機(jī)執(zhí)行察打任務(wù)的過(guò)程描述，異構(gòu)集群執(zhí)行察打任務(wù)所包含的要素可以用如下五元組表示

(1)

其中：U為任務(wù)區(qū)域內(nèi)異構(gòu)無(wú)人機(jī)集合；T為任務(wù)區(qū)域內(nèi)目標(biāo)集合，需要說(shuō)明的是，異構(gòu)無(wú)人機(jī)系統(tǒng)在初始時(shí)刻沒(méi)有關(guān)于目標(biāo)的先驗(yàn)信息；E為任務(wù)區(qū)域；O為障礙物集合；C為異構(gòu)集群執(zhí)行察打任務(wù)所需考慮的約束條件集合。

設(shè)目標(biāo)集合為T(mén)={Tj|j=1,2,…,NT}，當(dāng)無(wú)人機(jī)發(fā)現(xiàn)某目標(biāo)，可以確定對(duì)其實(shí)時(shí)打擊任務(wù)所需的攻擊型資源，目標(biāo)的資源需求向量可表示為

(2)

集合Value={Va1,Va2,…,VaNt}表示任務(wù)區(qū)域中Nt個(gè)目標(biāo)的初始價(jià)值，無(wú)人機(jī)集群摧毀目標(biāo)的收益與目標(biāo)價(jià)值rej和時(shí)間有關(guān)，并隨著時(shí)間增大而衰減：

rej=Vaj·e-βj(tj-t0)

(3)

式中：t0為目標(biāo)Tj被發(fā)現(xiàn)的時(shí)刻；tj為分配了攻擊目標(biāo)Tj的無(wú)人機(jī)聯(lián)盟攻擊該目標(biāo)的到達(dá)時(shí)間；βj>0反映目標(biāo)價(jià)值隨時(shí)間下降的快慢，該值越大，攻擊目標(biāo)所獲得收益隨時(shí)間下降越快，反之亦然。

初始時(shí)刻，任務(wù)區(qū)域中共有Nr架偵察型無(wú)人機(jī)和Nc架察打一體型無(wú)人機(jī)，偵察型和察打一體型無(wú)人機(jī)都能攜帶不隨時(shí)間/使用而減少的偵察探測(cè)類設(shè)備，察打一體型無(wú)人機(jī)還能夠攜帶隨使用而消耗的攻擊型資源，對(duì)于察打一體型無(wú)人機(jī)Ui，其攜帶的攻擊型資源可表示為一個(gè)n維向量：

(4)

假設(shè)各無(wú)人機(jī)定高飛行，無(wú)人機(jī)的運(yùn)動(dòng)學(xué)模型可表示為

(5)

式中：(x,y)表示無(wú)人機(jī)的位置坐標(biāo)；v為無(wú)人機(jī)的飛行速度；χ為無(wú)人機(jī)的航向角；ωχ為無(wú)人機(jī)的航向角速度。

執(zhí)行偵察和攻擊任務(wù)的初始時(shí)刻，異構(gòu)多無(wú)人機(jī)沒(méi)有目標(biāo)的任何先驗(yàn)信息，由多架察打一體型和偵察型無(wú)人機(jī)構(gòu)成的集群先執(zhí)行任務(wù)區(qū)域的協(xié)同偵察任務(wù)。Rr和Rc分別表示偵察型和察打一體型無(wú)人機(jī)的探測(cè)半徑，并且有Rr>Rc。多異構(gòu)無(wú)人機(jī)采用隨機(jī)搜索[24]的方式進(jìn)行協(xié)同偵察。當(dāng)異構(gòu)集群中某架無(wú)人機(jī)探測(cè)到目標(biāo)，就可以獲得該目標(biāo)的價(jià)值信息Va、位置信息(xT，yT)以及對(duì)其實(shí)施打擊任務(wù)所需資源信息RT。

當(dāng)某架無(wú)人機(jī)發(fā)現(xiàn)某個(gè)目標(biāo)時(shí)，就觸發(fā)針對(duì)該目標(biāo)攻擊任務(wù)的任務(wù)分配?？紤]到目標(biāo)資源約束，發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)可能沒(méi)有足夠的資源去單獨(dú)攻擊該目標(biāo)，該無(wú)人機(jī)需要將被發(fā)現(xiàn)目標(biāo)的信息發(fā)送給其他無(wú)人機(jī)。實(shí)際任務(wù)環(huán)境中，無(wú)人機(jī)的通信范圍受限，無(wú)人機(jī)能夠與其通信范圍內(nèi)的其他無(wú)人機(jī)進(jìn)行直接通信，稱為直連通信。通過(guò)中繼無(wú)人機(jī)的機(jī)間通信傳遞，無(wú)人機(jī)能夠與不在其通信范圍內(nèi)的其他無(wú)人機(jī)相互通信，稱為非直連通信。對(duì)于任意一架無(wú)人機(jī)Ui，將能夠與其直連或是非直連通信的其他無(wú)人機(jī)稱為Ui的鄰域無(wú)人機(jī)，用Ls(Ui)表示。無(wú)人機(jī)之間的通信還存在時(shí)間延遲，兩架直連無(wú)人機(jī)之間的通信，信息的發(fā)送方在t時(shí)刻發(fā)出信息，接收方在t+Δtd時(shí)刻才能收到信息，其中Δtd為通信時(shí)間延遲。圖1為多無(wú)人機(jī)機(jī)間通信的示意圖。在圖中，共有7架無(wú)人機(jī)，構(gòu)成了2個(gè)局部通信網(wǎng)絡(luò)；Rs表示單架無(wú)人機(jī)的通信范圍?？梢钥闯觯瑹o(wú)人機(jī)U1的鄰域無(wú)人機(jī)為L(zhǎng)s(U1)={U2,U3,U7}，從U1發(fā)出的信息要經(jīng)過(guò)2Δtd才能到達(dá)U7。

圖1 無(wú)人機(jī)的通信網(wǎng)絡(luò)示意圖

由于多異構(gòu)無(wú)人機(jī)執(zhí)行察打任務(wù)過(guò)程中，各無(wú)人機(jī)一直處于飛行狀態(tài)，因此多無(wú)人機(jī)系統(tǒng)的通信拓?fù)涫菚r(shí)變的，且有可能會(huì)出現(xiàn)多無(wú)人機(jī)系統(tǒng)被分成多個(gè)孤立的局部網(wǎng)絡(luò)，這種存在多個(gè)孤立局部網(wǎng)絡(luò)的情況也稱為系統(tǒng)通信不連通。當(dāng)多無(wú)人機(jī)系統(tǒng)的通信存在不連通時(shí)，會(huì)導(dǎo)致各無(wú)人機(jī)之間的態(tài)勢(shì)感知不同，從而使得多無(wú)人機(jī)協(xié)同完成任務(wù)時(shí)出現(xiàn)沖突。為了減小由通信不連通造成的協(xié)同沖突，要求無(wú)人機(jī)的通信范圍和探測(cè)范圍滿足：

Rs>2Rr

(6)

1.3 目標(biāo)函數(shù)和約束條件

異構(gòu)多無(wú)人機(jī)執(zhí)行偵察和打擊任務(wù)過(guò)程中，當(dāng)多無(wú)人機(jī)集群發(fā)現(xiàn)一個(gè)新目標(biāo)時(shí)，就觸發(fā)針對(duì)該目標(biāo)攻擊任務(wù)的協(xié)同任務(wù)分配。每次發(fā)現(xiàn)新目標(biāo)時(shí)觸發(fā)的攻擊任務(wù)的任務(wù)分配可以看作是全局任務(wù)的一次局部任務(wù)分配。

假設(shè)異構(gòu)無(wú)人機(jī)系統(tǒng)在某一時(shí)刻，無(wú)人機(jī)Ui發(fā)現(xiàn)新目標(biāo)Tj，并觸發(fā)針對(duì)該目標(biāo)的局部任務(wù)分配。發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)Ui與其鄰域Ls(Ui)構(gòu)成了一個(gè)局部無(wú)人機(jī)通信網(wǎng)絡(luò)，該網(wǎng)絡(luò)中共有Ni架無(wú)人機(jī)，令Call為該局部無(wú)人機(jī)通信網(wǎng)絡(luò)中所有無(wú)人機(jī)子集的集合。對(duì)于被發(fā)現(xiàn)目標(biāo)Tj的局部任務(wù)分配問(wèn)題的目的是找到一個(gè)無(wú)人機(jī)聯(lián)盟Cj?Call，使得該無(wú)人機(jī)聯(lián)盟執(zhí)行目標(biāo)Tj打擊任務(wù)所獲得的效能最大，該問(wèn)題的效能函數(shù)可表示為

(7)

式中：ω1和ω2為效能函數(shù)中目標(biāo)收益和無(wú)人機(jī)代價(jià)的權(quán)值系數(shù)，通過(guò)調(diào)整權(quán)值系數(shù)可以使得最終選定的無(wú)人機(jī)聯(lián)盟Cj獲得不同的效果。比如增大ω1可獲得飛行時(shí)間較短的無(wú)人機(jī)聯(lián)盟，適合于攻擊目標(biāo)價(jià)值隨時(shí)間下降較快的目標(biāo)。增大ω2可使得獲得的無(wú)人機(jī)聯(lián)盟代價(jià)較小，節(jié)省無(wú)人機(jī)聯(lián)盟的燃料。|Cj|為攻擊目標(biāo)Tj的聯(lián)盟Cj中的無(wú)人機(jī)數(shù)目。tj為聯(lián)盟Cj中無(wú)人機(jī)同時(shí)到達(dá)目標(biāo)Tj的耗時(shí)。

對(duì)于異構(gòu)多無(wú)人機(jī)協(xié)同執(zhí)行察打任務(wù)的局部任務(wù)分配問(wèn)題，需要考慮的約束條件有：

1) 無(wú)人機(jī)聯(lián)盟資源約束

考慮到目標(biāo)的資源需求，針對(duì)被發(fā)現(xiàn)目標(biāo)Tj所構(gòu)建的無(wú)人機(jī)聯(lián)盟的總可用資源需要滿足：

p=1,2,…,n;j=1,2,…,Nt

(8)

2) 無(wú)人機(jī)的有限資源約束

每架察打一體型無(wú)人機(jī)只能攜帶有限的攻擊型資源，且隨著使用而消耗?？紤]到每架察打無(wú)人機(jī)能夠按分配順序攻擊多個(gè)目標(biāo)，察打一體型無(wú)人機(jī)的資源需要滿足：

R(Α(i))≤RUi

(9)

式中：Α(i)表示無(wú)人機(jī)Ui的任務(wù)序列；R(Α(i))表示無(wú)人機(jī)Ui執(zhí)行其任務(wù)序列上所有目標(biāo)所消耗的攻擊型資源。

3) 無(wú)人機(jī)的最大可飛行時(shí)長(zhǎng)約束

當(dāng)察打一體型無(wú)人機(jī)在執(zhí)行任務(wù)過(guò)程中，若其剩余燃料不足，就不能分配其執(zhí)行相應(yīng)目標(biāo)的攻擊任務(wù)。因此，在局部任務(wù)分配中，察打一體型無(wú)人機(jī)的燃料約束能夠影響聯(lián)盟無(wú)人機(jī)的形成，其所攜帶的燃料約束可以等效為最大可飛行時(shí)長(zhǎng)，可表示為

(10)

4) 死鎖約束

考慮目標(biāo)資源約束和無(wú)人機(jī)的資源限制條件下，每架無(wú)人機(jī)可以攻擊多個(gè)目標(biāo)，執(zhí)行同一目標(biāo)攻擊任務(wù)的各無(wú)人機(jī)需要同時(shí)到達(dá)目標(biāo)。因此，各無(wú)人機(jī)在完成其任務(wù)序列的過(guò)程中，可能會(huì)互相等待而陷入死鎖狀態(tài)。一旦陷入死鎖狀態(tài)，各無(wú)人機(jī)會(huì)陷入無(wú)限等待的過(guò)程而無(wú)法完成任務(wù)。多架察打型無(wú)人機(jī)的任務(wù)序列不發(fā)生死鎖等價(jià)于以目標(biāo)為頂點(diǎn)的有向圖G(T,ε(Α))為有向無(wú)環(huán)圖[30](Directed Acyclic Graph,DAG)，可表示為

(11)

5) 與飛行路徑相關(guān)的約束

由式(7)可以看出，任務(wù)分配的效能函數(shù)需要獲取無(wú)人機(jī)聯(lián)盟同時(shí)攻擊目標(biāo)的時(shí)間，而準(zhǔn)確的同時(shí)攻擊時(shí)間依賴于同時(shí)到達(dá)路徑規(guī)劃的結(jié)算。因此異構(gòu)多無(wú)人機(jī)執(zhí)行察打任務(wù)中，任務(wù)分配與路徑規(guī)劃問(wèn)題相互耦合。需要考慮與飛行路徑相關(guān)的約束。

與飛行路徑相關(guān)的約束主要有無(wú)人機(jī)的運(yùn)動(dòng)學(xué)約束(曲率連續(xù)、最大曲率限制)、無(wú)人機(jī)路徑規(guī)避障礙物、無(wú)人機(jī)機(jī)間防撞以及同時(shí)攻擊目標(biāo)等約束。這部分內(nèi)容的詳細(xì)情況可以參考已發(fā)表的工作[28-29]。而本文將重點(diǎn)聚焦在通信約束(通信范圍和時(shí)間延遲)條件下，多異構(gòu)無(wú)人機(jī)針對(duì)被發(fā)現(xiàn)目標(biāo)的局部任務(wù)分配問(wèn)題上。

綜上所述，對(duì)于異構(gòu)無(wú)人機(jī)執(zhí)行察打任務(wù)，發(fā)現(xiàn)新目標(biāo)所觸發(fā)的局部任務(wù)分配問(wèn)題可以建模為約束優(yōu)化問(wèn)題，其目標(biāo)函數(shù)見(jiàn)式(7)，約束條件為式(8)～式(11)。

2 基于合同網(wǎng)的任務(wù)分配方法

從1.1節(jié)的分析可知，異構(gòu)多無(wú)人機(jī)執(zhí)行任務(wù)區(qū)域的察打任務(wù)時(shí)，若有新目標(biāo)被發(fā)現(xiàn)，則觸發(fā)針對(duì)該目標(biāo)的局部任務(wù)分配。由于無(wú)人機(jī)的通信范圍和時(shí)間延遲約束，多無(wú)人機(jī)在構(gòu)建攻擊目標(biāo)的聯(lián)盟時(shí)存在通信拓?fù)渥兓惹闆r。

本節(jié)基于合同網(wǎng)原理，設(shè)計(jì)了一種任務(wù)分配方法，該方法能夠有效解決存在通信范圍、時(shí)間延遲以及目標(biāo)資源需求等約束條件下的局部任務(wù)分配問(wèn)題。

合同網(wǎng)協(xié)議(Contract Net Protocol,CNP)最初是由Smith[31]提出，并用于處理分布式相關(guān)問(wèn)題的一種高層通信協(xié)議。該協(xié)議是一種協(xié)商機(jī)制，其通過(guò)模仿經(jīng)濟(jì)行為中的“招標(biāo)-投標(biāo)-中標(biāo)”機(jī)制[32]，使得分布式系統(tǒng)中的個(gè)體通過(guò)協(xié)商來(lái)實(shí)現(xiàn)任務(wù)/資源的分配。

在異構(gòu)多無(wú)人機(jī)執(zhí)行察打任務(wù)中，基于合同網(wǎng)的任務(wù)分配方法可以看作是由任務(wù)發(fā)布、投標(biāo)、授權(quán)以及執(zhí)行這4個(gè)步驟組成。在任務(wù)發(fā)布中，發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)作為招標(biāo)無(wú)人機(jī)，并由該無(wú)人機(jī)向其局部通信網(wǎng)絡(luò)中的其他無(wú)人機(jī)發(fā)送招標(biāo)邀請(qǐng)。在投標(biāo)階段，有能力執(zhí)行該任務(wù)的無(wú)人機(jī)計(jì)算執(zhí)行該任務(wù)的代價(jià)/效能，并作為投標(biāo)無(wú)人機(jī)向招標(biāo)無(wú)人機(jī)發(fā)送投標(biāo)信息。在授權(quán)階段，招標(biāo)無(wú)人機(jī)根據(jù)其收到的所有投標(biāo)信息選定執(zhí)行目標(biāo)任務(wù)的一架或多架無(wú)人機(jī)，并發(fā)送授權(quán)信息。在最后的執(zhí)行階段，收到任務(wù)授權(quán)信息的無(wú)人機(jī)執(zhí)行該任務(wù)。

2.1 考慮通信約束的局部任務(wù)分配方法

考慮無(wú)人機(jī)的探測(cè)范圍和通信時(shí)間延遲約束。在所提出的基于合同網(wǎng)的局部任務(wù)分配方法中：在任務(wù)發(fā)布階段，考慮無(wú)人機(jī)的通信范圍約束，給出能夠使同一局部通信網(wǎng)絡(luò)中各無(wú)人機(jī)達(dá)成信息一致的方法。在投標(biāo)階段，各無(wú)人機(jī)計(jì)算其在一個(gè)預(yù)測(cè)位置與目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間，作為其投標(biāo)代價(jià)。在聯(lián)盟構(gòu)建階段，考慮目標(biāo)的資源約束，提出了一種能夠最大化系統(tǒng)效能的聯(lián)盟構(gòu)建方法。下面給出該方法進(jìn)行聯(lián)盟構(gòu)建的4個(gè)步驟：

步驟1任務(wù)發(fā)布

異構(gòu)多無(wú)人機(jī)執(zhí)行察打任務(wù)中，當(dāng)發(fā)現(xiàn)新目標(biāo)，由發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)作為招標(biāo)無(wú)人機(jī)，向其局部通信網(wǎng)絡(luò)中的其他無(wú)人機(jī)發(fā)送聯(lián)盟構(gòu)建的招標(biāo)信息。

由于無(wú)人機(jī)集群始終處于飛行狀態(tài)，且無(wú)人機(jī)之間存在通信范圍和時(shí)間延遲約束。招標(biāo)無(wú)人機(jī)并不能實(shí)時(shí)獲取其局部通信網(wǎng)絡(luò)中的無(wú)人機(jī)數(shù)目以及通信拓?fù)浣Y(jié)構(gòu)。為了使信息在無(wú)人機(jī)之間可控的范圍內(nèi)傳播以及便于投標(biāo)無(wú)人機(jī)計(jì)算其執(zhí)行被發(fā)現(xiàn)目標(biāo)的代價(jià)。對(duì)于多無(wú)人機(jī)系統(tǒng)，通過(guò)設(shè)定信息最大傳輸次數(shù)Hmax來(lái)限制信息的最大跳躍(hop)次數(shù)。對(duì)于機(jī)間傳遞的任意信息，在信息初始化時(shí)將該信息的剩余跳躍次數(shù)設(shè)置為Hmax，并在之后每次轉(zhuǎn)發(fā)時(shí)將剩余跳躍次數(shù)減1。當(dāng)剩余跳躍次數(shù)為0時(shí)，該信息不可被再次轉(zhuǎn)發(fā)。例如，當(dāng)設(shè)置信息最大跳躍次數(shù)Hmax=2時(shí)，圖2中無(wú)人機(jī)U2發(fā)現(xiàn)目標(biāo)T并作為聯(lián)盟長(zhǎng)機(jī)向其他無(wú)人機(jī)發(fā)送招標(biāo)信息。圖2中虛線連接的無(wú)人機(jī)表示在通信范圍內(nèi)的直連通信。通過(guò)通信傳遞，橢圓圈內(nèi)的無(wú)人機(jī)能夠收到聯(lián)盟長(zhǎng)機(jī)U2的招標(biāo)信息，雖然無(wú)人機(jī)U6也在U2的局部通信網(wǎng)絡(luò)中，由于信息最大跳躍次數(shù)Hmax=2，而從U2傳遞到U6至少需要3次信息跳躍，因此，無(wú)人機(jī)U6無(wú)法收到U2發(fā)送的招標(biāo)信息，也就無(wú)法參與聯(lián)盟的構(gòu)建過(guò)程。

圖2 多無(wú)人機(jī)的通信拓?fù)?Hmax=2)

無(wú)人機(jī)存在通信范圍約束，無(wú)人機(jī)之間的信息傳遞需要中繼無(wú)人機(jī)的轉(zhuǎn)發(fā)，由于機(jī)間通信存在通信時(shí)延，因此，針對(duì)所發(fā)現(xiàn)新目標(biāo)的聯(lián)盟構(gòu)建過(guò)程不是瞬時(shí)完成的，其需要一定的時(shí)間。多無(wú)人機(jī)一直處于飛行狀態(tài)，在聯(lián)盟構(gòu)建的過(guò)程中，無(wú)人集群的通信拓?fù)涫请S時(shí)間動(dòng)態(tài)變化的。在聯(lián)盟構(gòu)建的過(guò)程中，有可能因?yàn)橥ㄐ磐負(fù)渥兓沟媚承o(wú)人機(jī)脫離局部無(wú)人機(jī)通信網(wǎng)絡(luò)使得聯(lián)盟構(gòu)建失敗。因此，當(dāng)某無(wú)人機(jī)收到其他無(wú)人機(jī)發(fā)送的信息時(shí)，該無(wú)人機(jī)首先需要判斷是否能夠成為穩(wěn)定的中繼節(jié)點(diǎn)。某架無(wú)人機(jī)能夠成為穩(wěn)定的中繼節(jié)點(diǎn)的條件是該無(wú)人機(jī)在聯(lián)盟構(gòu)建的時(shí)間段內(nèi)始終處于向其發(fā)送信息的直連無(wú)人機(jī)的通信范圍內(nèi)。根據(jù)聯(lián)盟構(gòu)建的過(guò)程可知，聯(lián)盟的構(gòu)建過(guò)程包括聯(lián)盟長(zhǎng)機(jī)招標(biāo)、投標(biāo)者申請(qǐng)、聯(lián)盟長(zhǎng)機(jī)通知中標(biāo)3個(gè)過(guò)程，因此，聯(lián)盟構(gòu)建過(guò)程耗時(shí)的上界可表示為

δc=3HmaxΔtd+tTA+δt

(12)

(13)

式中：tnow為該目標(biāo)被發(fā)現(xiàn)時(shí)刻；δc為聯(lián)盟構(gòu)建過(guò)程耗時(shí)的上界。

對(duì)于發(fā)現(xiàn)新目標(biāo)Tj的無(wú)人機(jī)Ui，該無(wú)人機(jī)作為聯(lián)盟長(zhǎng)機(jī)向其他無(wú)人機(jī)發(fā)送招標(biāo)信息可用向量Pi表示

(14)

(15)

其中：ETA(i,j)為無(wú)人機(jī)Ui到達(dá)目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間。

對(duì)于分布式多機(jī)執(zhí)行察打任務(wù)，存在一種情況：同一局部通信網(wǎng)絡(luò)的不同無(wú)人機(jī)同時(shí)發(fā)現(xiàn)了多個(gè)目標(biāo)。此時(shí)，在該局部通信網(wǎng)絡(luò)中存在多個(gè)聯(lián)盟長(zhǎng)機(jī)發(fā)送聯(lián)盟招標(biāo)信息。為了避免多個(gè)聯(lián)盟長(zhǎng)機(jī)同時(shí)招標(biāo)而造成系統(tǒng)資源浪費(fèi)，同一局部通信網(wǎng)絡(luò)中的各無(wú)人機(jī)需要對(duì)聯(lián)盟長(zhǎng)機(jī)以及招標(biāo)信息達(dá)成一致。局部通信網(wǎng)絡(luò)中的各無(wú)人機(jī)通過(guò)算法1對(duì)聯(lián)盟長(zhǎng)機(jī)以及招標(biāo)信息達(dá)成一致性。

算法1 無(wú)人機(jī)Ui(i∈1,2,…,Nu)的任務(wù)發(fā)布算法1.for 1: iter=1～Hmax2. if Pi(6)≥13. Pi(6)=Pi(6)-14. 無(wú)人機(jī)Ui向其直連無(wú)人機(jī)發(fā)送招標(biāo)信息Pi5. end6. fork=1～招標(biāo)請(qǐng)求數(shù)目7. 估算無(wú)人機(jī)Ui在時(shí)刻tnow+δc的位置PtcUi8. ifPtcUi 在無(wú)人機(jī)Uk的通信范圍內(nèi)9. ifPi(3)

在算法1中，Pi(b)表示聯(lián)盟招標(biāo)信息的第b個(gè)元素，如Pi(3)為無(wú)人機(jī)Ui執(zhí)行其發(fā)現(xiàn)目標(biāo)的預(yù)期收益，Pi(6)為該信息剩余可跳躍次數(shù)。對(duì)于局部通信網(wǎng)絡(luò)中的任一架無(wú)人機(jī)Ui，該無(wú)人機(jī)首先將其獲得的招標(biāo)信息向其直連無(wú)人機(jī)發(fā)送(第2～4行)，同時(shí)該無(wú)人機(jī)也能接收到其直連無(wú)人機(jī)向其發(fā)送的招標(biāo)信息(第6行)，若無(wú)人機(jī)Ui發(fā)現(xiàn)有其他無(wú)人機(jī)含有更優(yōu)的招標(biāo)信息(第9行)，Ui更新其保存的招標(biāo)信息(第10行)。由于信息的最大跳躍次數(shù)為Hmax，因此，各聯(lián)盟長(zhǎng)機(jī)發(fā)送的招標(biāo)信息最多經(jīng)過(guò)Hmax次跳躍，就能使發(fā)現(xiàn)目標(biāo)的局部無(wú)人機(jī)通信網(wǎng)絡(luò)對(duì)聯(lián)盟長(zhǎng)機(jī)下發(fā)的招標(biāo)信息達(dá)成一致。

步驟2投標(biāo)申請(qǐng)階段

經(jīng)過(guò)步驟1后，發(fā)現(xiàn)目標(biāo)的局部無(wú)人機(jī)通信網(wǎng)絡(luò)中各無(wú)人機(jī)保留了一致的招標(biāo)信息，也就是在同一局部通信網(wǎng)絡(luò)下不同的無(wú)人機(jī)Ui、Uj(i≠j)，其有相同的招標(biāo)信息Pi=Pj。

對(duì)于局部通信網(wǎng)絡(luò)中的無(wú)人機(jī)，根據(jù)其收到的招標(biāo)信息進(jìn)行判斷，若無(wú)人機(jī)含有目標(biāo)所需資源，則該無(wú)人機(jī)有資格成為競(jìng)標(biāo)無(wú)人機(jī)(Bidder UAV)。因此，能夠成為競(jìng)標(biāo)無(wú)人機(jī)并向聯(lián)盟長(zhǎng)機(jī)發(fā)送標(biāo)書(shū)的無(wú)人機(jī)需要滿足條件：① 信息最大跳躍限制；② 穩(wěn)定的中繼節(jié)點(diǎn)；③ 含有目標(biāo)所需資源。

競(jìng)拍無(wú)人機(jī)向聯(lián)盟長(zhǎng)機(jī)發(fā)送的標(biāo)書(shū)中需包括競(jìng)拍無(wú)人機(jī)執(zhí)行目標(biāo)的代價(jià)，用無(wú)人機(jī)與目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間(ETA)表示無(wú)人機(jī)執(zhí)行目標(biāo)的代價(jià)。由于多無(wú)人集群處于飛行狀態(tài)且節(jié)點(diǎn)之間存在通信延遲，若各無(wú)人機(jī)根據(jù)其收到標(biāo)書(shū)的時(shí)刻計(jì)算與目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間，在信息的交互過(guò)程中，預(yù)計(jì)到達(dá)時(shí)間會(huì)發(fā)生變化而造成任務(wù)分配的性能下降。因此各無(wú)人機(jī)需要商定一個(gè)統(tǒng)一時(shí)刻，并根據(jù)該時(shí)刻各無(wú)人機(jī)的位置來(lái)計(jì)算其與目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間。由于局部通信網(wǎng)絡(luò)中的各無(wú)人機(jī)都含有由聯(lián)盟長(zhǎng)機(jī)發(fā)送的聯(lián)盟構(gòu)建耗時(shí)δc，因此，各無(wú)人機(jī)根據(jù)當(dāng)前時(shí)刻估算其在δc時(shí)刻后的位置，通過(guò)該時(shí)刻的位置來(lái)計(jì)算其與目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間。對(duì)于局部通信網(wǎng)絡(luò)中的任意一架無(wú)人機(jī)Ui，該無(wú)人機(jī)在tnow+δc時(shí)刻的估計(jì)位置用GUi表示，無(wú)人機(jī)通過(guò)該位置計(jì)算其與目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間。

各競(jìng)標(biāo)無(wú)人機(jī)在獲取了其與待拍賣(mài)目標(biāo)的預(yù)計(jì)到達(dá)時(shí)間后，向聯(lián)盟長(zhǎng)機(jī)發(fā)送投標(biāo)信息(或稱為標(biāo)書(shū))，競(jìng)標(biāo)無(wú)人機(jī)Uk發(fā)送的投標(biāo)信息Qk可表示為

Qk=[Uk,Ui,Tj,RUk,ETA(k,j),H]

(16)

式中：Ui為聯(lián)盟長(zhǎng)機(jī)；Tj為待拍賣(mài)目標(biāo)；RUk為競(jìng)標(biāo)無(wú)人機(jī)Uk當(dāng)前時(shí)刻可用資源；ETA(i,j)為Uk的估計(jì)位置GUi到目標(biāo)Tj的預(yù)估到達(dá)時(shí)間；H為該信息剩余跳躍次數(shù)，并在該信息初始化時(shí)設(shè)置為Hmax。

步驟3聯(lián)盟構(gòu)建

經(jīng)過(guò)了步驟2的投標(biāo)申請(qǐng)，聯(lián)盟長(zhǎng)機(jī)收到了局部通信網(wǎng)絡(luò)中競(jìng)標(biāo)無(wú)人機(jī)向其發(fā)送的投標(biāo)申請(qǐng)Q?？紤]到目標(biāo)的資源約束，單架無(wú)人機(jī)可能無(wú)法完成目標(biāo)的攻擊任務(wù)，這就需要聯(lián)盟長(zhǎng)機(jī)根據(jù)一定的準(zhǔn)則在所有的競(jìng)標(biāo)無(wú)人機(jī)中選擇一個(gè)無(wú)人機(jī)聯(lián)盟執(zhí)行該目標(biāo)的同時(shí)攻擊任務(wù)。

聯(lián)盟長(zhǎng)機(jī)及其收到的競(jìng)標(biāo)無(wú)人機(jī)共同組成了潛在的聯(lián)盟成員，將所有潛在聯(lián)盟成員組成的集合記為Up。在希望聯(lián)盟成員數(shù)目最小的前提下，聯(lián)盟長(zhǎng)機(jī)先求出滿足目標(biāo)資源約束的所有可行聯(lián)盟集Cfeasible。之后，在所有可行聯(lián)盟中選擇具有最大效能的聯(lián)盟Cj作為攻擊目標(biāo)Tj的無(wú)人機(jī)聯(lián)盟：

(17)

式中:utility(C)表示聯(lián)盟C攻擊目標(biāo)的效能，可通過(guò)式(7)得出。

步驟4執(zhí)行階段

在這一階段，競(jìng)拍成功的無(wú)人機(jī)將待執(zhí)行目標(biāo)Tj的信息加入其任務(wù)序列：

A(i)=A(i)⊕[Tj]i∈Cj

(18)

其中：⊕表示將目標(biāo)Tj加入無(wú)人機(jī)任務(wù)序列中現(xiàn)有的任務(wù)之后。各無(wú)人機(jī)根據(jù)聯(lián)盟長(zhǎng)機(jī)下發(fā)的路徑及飛行速度執(zhí)行目標(biāo)攻擊任務(wù)。對(duì)于聯(lián)盟中的無(wú)人機(jī)，若其正在執(zhí)行偵察任務(wù)，則該無(wú)人機(jī)先按原狀態(tài)飛行至?xí)r刻tnow+δc，之后再按照聯(lián)盟長(zhǎng)機(jī)下發(fā)的攻擊路徑和速度執(zhí)行目標(biāo)攻擊任務(wù)。

2.2 無(wú)人機(jī)資源消耗計(jì)算

當(dāng)聯(lián)盟長(zhǎng)機(jī)確定了執(zhí)行目標(biāo)攻擊任務(wù)的聯(lián)盟成員后，聯(lián)盟成員需要共同承擔(dān)目標(biāo)攻擊任務(wù)所需的資源。

目前，針對(duì)多無(wú)人機(jī)執(zhí)行察打任務(wù)，在考慮目標(biāo)資源需求下，大多使用貪婪算法計(jì)算聯(lián)盟中各無(wú)人機(jī)的資源消耗，但這么做容易造成某些無(wú)人機(jī)的攻擊型資源過(guò)早耗盡。由于各無(wú)人機(jī)的資源消耗方式不平衡，過(guò)早耗盡攻擊型資源的無(wú)人機(jī)只能執(zhí)行偵察任務(wù)。對(duì)于不確定性和動(dòng)態(tài)性較高的任務(wù)場(chǎng)景，當(dāng)發(fā)現(xiàn)新目標(biāo)時(shí)，耗盡攻擊型資源的無(wú)人機(jī)無(wú)法參與到聯(lián)盟構(gòu)建過(guò)程中，這將會(huì)造成多無(wú)人機(jī)系統(tǒng)察打任務(wù)的魯棒性變差，尤其是當(dāng)無(wú)人機(jī)存在被擊落風(fēng)險(xiǎn)時(shí)，這種不平衡的資源消耗方式會(huì)產(chǎn)生更大隱患。

因此這里使用一種平衡的資源消耗方法[25]，聯(lián)盟中含有資源較多的無(wú)人機(jī)將消耗更多的資源，反之亦然，在對(duì)目標(biāo)執(zhí)行完攻擊任務(wù)后，盡量使各無(wú)人機(jī)的剩余資源趨近一致，使各無(wú)人機(jī)能夠保留一定的資源以應(yīng)對(duì)任務(wù)執(zhí)行過(guò)程中的動(dòng)態(tài)性和不確定性。

對(duì)于被發(fā)現(xiàn)的目標(biāo)Tj，目標(biāo)的資源需求為RTj，執(zhí)行目標(biāo)攻擊任務(wù)的聯(lián)盟記為Cj。對(duì)于聯(lián)盟Cj中的無(wú)人機(jī)，需要消耗目標(biāo)所需的p類型資源的無(wú)人機(jī)集合為Cj,p，即

(19)

(20)

其中：n(Cp,j)為集合Cj,p中無(wú)人機(jī)的數(shù)目。

圖3 多無(wú)人機(jī)資源消耗示例

3 仿真實(shí)驗(yàn)及分析

為了驗(yàn)證所提出的基于合同網(wǎng)的局部任務(wù)分配方法在多異構(gòu)無(wú)人機(jī)察打任務(wù)中的性能，本節(jié)設(shè)置了3組仿真實(shí)驗(yàn)。在3.1節(jié)中，將本文所提出的局部任務(wù)分配方法用于一個(gè)示例場(chǎng)景，用于說(shuō)明多異構(gòu)無(wú)人機(jī)協(xié)同察打任務(wù)的全過(guò)程。在3.2節(jié)中對(duì)比本文所提出聯(lián)盟構(gòu)建算法與另外兩種聯(lián)盟構(gòu)建算法的性能。在3.3節(jié)中，通過(guò)Monte Carlo仿真實(shí)驗(yàn)分析了本文所提出的分布式局部任務(wù)分配方法在不同的通信時(shí)間延遲Δtd和信息最大跳躍次數(shù)Hmax下的性能。所有的仿真實(shí)驗(yàn)在一臺(tái)個(gè)人PC機(jī)上實(shí)現(xiàn)，其參數(shù)為：Intel Core i5-4590 @3.3 GHz 8 GB 內(nèi)存，編程環(huán)境為MATLAB 2016b。

3.1 異構(gòu)多無(wú)人機(jī)察打任務(wù)示例場(chǎng)景

異構(gòu)集群由1架偵察型無(wú)人機(jī)和5架察打一體型無(wú)人機(jī)組成。任務(wù)區(qū)域中存在2個(gè)目標(biāo)，其資源需求分別為RT1={4,2}、RT2={4,3}，初始時(shí)刻各無(wú)人機(jī)沒(méi)有關(guān)于目標(biāo)的先驗(yàn)信息，各無(wú)人機(jī)協(xié)同執(zhí)行偵察任務(wù)直到有目標(biāo)被發(fā)現(xiàn)而觸發(fā)針對(duì)被發(fā)現(xiàn)目標(biāo)的局部任務(wù)分配。初始時(shí)刻各無(wú)人機(jī)的位置、資源、類型信息如表1所示。偵察型無(wú)人機(jī)和察打一體型無(wú)人機(jī)的探測(cè)半徑分別為400 m和500 m，各無(wú)人機(jī)的通信范圍為1 000 m。相關(guān)的通信約束參數(shù)為：通信時(shí)間延遲Δtd=0.1 s, 聯(lián)盟首領(lǐng)計(jì)算聯(lián)盟成員消耗時(shí)間tTA=0.2 s，人為設(shè)定的裕量δt=0.2 s，信息最大跳躍次數(shù)Hmax=2。

表1 初始時(shí)刻各無(wú)人機(jī)的信息

初始時(shí)刻，各無(wú)人機(jī)沒(méi)有關(guān)于目標(biāo)的任務(wù)先驗(yàn)信息，各無(wú)人機(jī)先執(zhí)行協(xié)同偵察任務(wù)，直到t=24.1 s時(shí)無(wú)人機(jī)U2發(fā)現(xiàn)目標(biāo)T1。由于該無(wú)人機(jī)所含有資源不足以單獨(dú)執(zhí)行目標(biāo)T1的攻擊任務(wù)，其需要在局部無(wú)人機(jī)通信網(wǎng)絡(luò)中構(gòu)建聯(lián)盟。該時(shí)刻下無(wú)人機(jī)U2的局部通信網(wǎng)絡(luò)如圖4所示。圖中“·”為t=24.1 s時(shí)各無(wú)人機(jī)的當(dāng)前位置，虛線連接的無(wú)人機(jī)表示可以直連相互通信。當(dāng)前時(shí)刻發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)U2的局部通信網(wǎng)絡(luò)為{U1,U2}，而這兩架無(wú)人機(jī)當(dāng)前所攜帶的總資源為R={2,2}，小于目標(biāo)T1所需資源，因此當(dāng)前時(shí)刻無(wú)法構(gòu)建聯(lián)盟，各無(wú)人機(jī)繼續(xù)執(zhí)行協(xié)同搜索任務(wù)。

圖4 t=24.1 s 時(shí)各無(wú)人機(jī)的狀態(tài)

當(dāng)t=29.9 s時(shí)，無(wú)人機(jī)U2發(fā)現(xiàn)目標(biāo)T1，該無(wú)人機(jī)的局部通信網(wǎng)絡(luò)為{U1,U2,U4}，所含有的總資源滿足目標(biāo)T1所需資源，利用提出的局部任務(wù)分配方法，構(gòu)建聯(lián)盟C1={U1,U4}執(zhí)行目標(biāo)T1的同時(shí)攻擊任務(wù)。聯(lián)盟中兩架無(wú)人機(jī)的PH路徑、路徑曲率以及同時(shí)到達(dá)目標(biāo)T1的剩余飛行時(shí)間分別如圖5 (a)～圖5(c)所示。從圖中可知，聯(lián)盟中的兩架無(wú)人機(jī)能夠同時(shí)到達(dá)目標(biāo)，且為其規(guī)劃的路徑滿足曲率連續(xù)和范圍約束。

圖5 針對(duì)發(fā)現(xiàn)目標(biāo)T1的任務(wù)分配結(jié)果(t=29.9 s)

執(zhí)行目標(biāo)T1攻擊任務(wù)的兩架無(wú)人機(jī)按照為其規(guī)劃的飛行路徑執(zhí)行目標(biāo)攻擊任務(wù)，其使用非線性模型控制(NMPC)方法跟飛為其規(guī)劃的PH路徑,在其跟飛過(guò)程中無(wú)人機(jī)依舊能夠執(zhí)行偵察任務(wù)。其他4架無(wú)人機(jī)仍然執(zhí)行協(xié)同偵察任務(wù)，當(dāng)t=55.4 s時(shí)，無(wú)人機(jī)U4發(fā)現(xiàn)目標(biāo)T2，該時(shí)刻下發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)的局部無(wú)人機(jī)通信網(wǎng)絡(luò)包含無(wú)人機(jī){U1,U2,U4,U5,U6}，并構(gòu)建聯(lián)盟C2={U2,U5}同時(shí)攻擊目標(biāo)T2。聯(lián)盟中兩架無(wú)人機(jī)的PH路徑、路徑曲率以及同時(shí)到達(dá)目標(biāo)T1的剩余飛行時(shí)間分別如圖6 (a)～圖6(c)所示。從圖中可知，聯(lián)盟中的兩架無(wú)人機(jī)能夠同時(shí)到達(dá)目標(biāo)，且為其規(guī)劃的路徑滿足曲率連續(xù)和范圍約束。

圖6 針對(duì)發(fā)現(xiàn)目標(biāo)T2的任務(wù)分配結(jié)果(t=55.4 s)

3.2 不同聯(lián)盟構(gòu)建算法性能

在所提出的局部任務(wù)分配方法的4個(gè)步驟中，第3步為聯(lián)盟構(gòu)建算法，是聯(lián)盟長(zhǎng)機(jī)根據(jù)投標(biāo)無(wú)人機(jī)的信息選擇最終執(zhí)行目標(biāo)攻擊任務(wù)的聯(lián)盟無(wú)人機(jī)的過(guò)程。本節(jié)在基于本文的局部任務(wù)分配方法的架構(gòu)下，通過(guò)仿真對(duì)比了3種不同的聯(lián)盟構(gòu)建算法的性能，分別為本文的聯(lián)盟構(gòu)建算法、多項(xiàng)式時(shí)間聯(lián)盟構(gòu)建算法[24](PTCFA)和基于資源福利(Resource Welfare-based)聯(lián)盟構(gòu)建算法[25]。

通過(guò)Monte Carlo仿真試驗(yàn)對(duì)比當(dāng)無(wú)人機(jī)數(shù)目變化時(shí)，3種聯(lián)盟構(gòu)建算法在多無(wú)人機(jī)協(xié)同察打任務(wù)中的性能，對(duì)比的指標(biāo)為任務(wù)完成總時(shí)間和攻擊所有目標(biāo)獲得的總效能。

仿真中任務(wù)區(qū)域的大小為5 000 m×5 000 m，任務(wù)區(qū)域內(nèi)共有8個(gè)靜態(tài)目標(biāo)，每個(gè)目標(biāo)需要兩種類型的資源，每種類型的資源需求量為1～5之間(包括1和5)隨機(jī)產(chǎn)生的整數(shù)。設(shè)置多組Monte Carlo仿真，每組實(shí)驗(yàn)中不同類型的無(wú)人機(jī)總數(shù)目分別為10、15、20、25、30，其中對(duì)應(yīng)的偵察型無(wú)人機(jī)數(shù)目分別為1～5。每組實(shí)驗(yàn)進(jìn)行200次仿真。每次仿真實(shí)驗(yàn)中，各無(wú)人機(jī)以不同的航向角從基地(坐標(biāo)原點(diǎn))出發(fā)，并在未發(fā)現(xiàn)目標(biāo)時(shí)執(zhí)行協(xié)同搜索任務(wù)。考慮無(wú)人機(jī)的通信范圍和時(shí)間延遲約束，令機(jī)間信息最大跳躍次數(shù)Hmax=3。當(dāng)無(wú)人機(jī)數(shù)目變化時(shí)，使用不同聯(lián)盟構(gòu)建算法時(shí)，完成搜索于攻擊任務(wù)的平均任務(wù)完成時(shí)間和平均系統(tǒng)效能分別如圖7 (a)和圖7(b)所示。

圖7(a)為無(wú)人機(jī)數(shù)目變化時(shí)，無(wú)人集群使用3種不同聯(lián)盟構(gòu)建算法用于多無(wú)人機(jī)協(xié)同搜索和攻擊任務(wù)的平均任務(wù)完成時(shí)間。從中可以看出，隨著無(wú)人機(jī)數(shù)目的增加，使用不同聯(lián)盟構(gòu)建算法的任務(wù)完成時(shí)間都隨之下降。3種算法中，使用PTCFA時(shí)，多無(wú)人機(jī)協(xié)同察打任務(wù)的耗時(shí)最短。這也符合PTCFA選擇聯(lián)盟的原則，該算法在聯(lián)盟構(gòu)建過(guò)程中，總是會(huì)選出執(zhí)行目標(biāo)攻擊任務(wù)耗時(shí)最短的聯(lián)盟。使用本文的聯(lián)盟構(gòu)建算法時(shí)，多無(wú)人集群的平均任務(wù)完成時(shí)間較PTCFA只是略有增加。

圖7(b)為無(wú)人機(jī)數(shù)目變化時(shí)，使用3種聯(lián)盟構(gòu)建算法，多無(wú)人機(jī)系統(tǒng)執(zhí)行所有目標(biāo)的攻擊任務(wù)后所獲得的平均系統(tǒng)效能?？梢钥闯觯S著無(wú)人機(jī)數(shù)目的增加，3種算法所獲得的系統(tǒng)效能大體上呈現(xiàn)增加趨勢(shì)。然而，當(dāng)使用PTCFA時(shí)，當(dāng)無(wú)人機(jī)數(shù)目從20增加到25架時(shí)，獲得的系統(tǒng)效能有小幅度的下降。這可能是由于PTCFA構(gòu)建的聯(lián)盟雖然攻擊目標(biāo)的耗時(shí)最短，但在無(wú)人機(jī)數(shù)目較多的情況下，聯(lián)盟中的無(wú)人機(jī)數(shù)目可能較多，導(dǎo)致聯(lián)盟的代價(jià)增大。同樣的情況也出現(xiàn)在使用基于資源福利的聯(lián)盟構(gòu)建算法中。從圖7(b)中還能看出，較之其他兩種聯(lián)盟構(gòu)建算法，本文算法能夠使得多無(wú)人集群獲得最大的系統(tǒng)效能。

圖7 無(wú)人機(jī)數(shù)目變化時(shí)3種聯(lián)盟構(gòu)建算法的性能對(duì)比

3.3 通信約束下算法性能

在實(shí)際任務(wù)環(huán)境中，無(wú)人集群執(zhí)行察打任務(wù)的性能還受到機(jī)間通信相關(guān)約束的影響。本節(jié)通過(guò)設(shè)置不同的最大信息跳躍次數(shù)Hmax和機(jī)間通信時(shí)間延遲Δtd，來(lái)分析通信相關(guān)約束對(duì)本文局部任務(wù)分配方法應(yīng)用于多無(wú)人機(jī)察打任務(wù)的影響。

仿真參數(shù)設(shè)置如下：任務(wù)區(qū)域內(nèi)中有8個(gè)目標(biāo)和10架察打一體型無(wú)人機(jī)，目標(biāo)和無(wú)人機(jī)位置、資源的初始化方式與3.2節(jié)相同。設(shè)置兩組仿真，并將察打一體型無(wú)人機(jī)的探測(cè)半徑分別設(shè)置為300 m和500 m(相應(yīng)的將通信范圍設(shè)置為600 m和1 000 m)。無(wú)人集群的機(jī)間通信時(shí)間延遲Δtd分別為0.02、0.1、1 s，信息最大跳躍次數(shù)Hmax從1～5變化，其中Hmax=1表示無(wú)人機(jī)只能與其直連無(wú)人機(jī)通信。在每組參數(shù)配置下，都進(jìn)行100次仿真試驗(yàn)并對(duì)結(jié)果取平均值。當(dāng)無(wú)人機(jī)的通信時(shí)間延遲和最大信息跳躍次數(shù)變化時(shí)，多無(wú)人機(jī)系統(tǒng)執(zhí)行察打任務(wù)所獲得的平均效能如圖8所示。

圖8 通信約束對(duì)任務(wù)分配方法的影響

從圖8(a)中可以看出，當(dāng)無(wú)人機(jī)的探測(cè)半徑為300 m，通信距離為600 m時(shí)，當(dāng)機(jī)間通信延遲Δtd=0.02 s時(shí)，隨著最大信息跳躍次數(shù)Hmax的增加，多無(wú)人機(jī)執(zhí)行察打任務(wù)所獲得的效能持續(xù)增大。這是由于隨著Hmax的增大，信息可以傳遞的次數(shù)就越多，發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)局部通信網(wǎng)絡(luò)中無(wú)人機(jī)的數(shù)目越多，這導(dǎo)致更容易獲得效能更大的聯(lián)盟。然而，當(dāng)Δtd=0.1 s和Δtd=1 s時(shí)，隨著Hmax的增大，多無(wú)人機(jī)所獲得總效能出現(xiàn)了先增大后減小的現(xiàn)象。這是由于在聯(lián)盟構(gòu)建的過(guò)程中，要求所有的潛在聯(lián)盟成員處于穩(wěn)定的通信狀態(tài)。而當(dāng)通信時(shí)間延遲較大時(shí)，隨著最大信息跳躍次數(shù)的增大，聯(lián)盟的構(gòu)建時(shí)間增長(zhǎng)，這導(dǎo)致能夠穩(wěn)定通信的無(wú)人機(jī)變少，系統(tǒng)效能降低。

同樣的現(xiàn)象也能夠在圖8(b)中發(fā)現(xiàn)，該圖為無(wú)人機(jī)探測(cè)半徑為500 m，通信距離為1 000 m時(shí)，通信時(shí)間延遲和最大跳躍次數(shù)變化對(duì)系統(tǒng)效能的影響?？梢钥闯?，當(dāng)通信時(shí)間延遲Δtd=0.1 s和Δtd=1 s時(shí)，隨著Hmax的增加，無(wú)人集群獲得的總效能也出現(xiàn)了先增大后減小的現(xiàn)象。但與圖8(b)相比，其峰值效能對(duì)應(yīng)的Hmax變大。這是由于，當(dāng)無(wú)人機(jī)的探測(cè)半徑和通信距離增大時(shí)，即使機(jī)間信息傳遞的時(shí)間延遲較大，也能夠保證發(fā)現(xiàn)目標(biāo)的無(wú)人機(jī)局部通信網(wǎng)絡(luò)中含有較多的無(wú)人機(jī)。

4 結(jié) 論

1) 提出了一種基于分布式合同網(wǎng)的多無(wú)人機(jī)任務(wù)分配方法，解決了存在無(wú)人機(jī)通信距離和時(shí)間延遲約束下異構(gòu)多無(wú)人機(jī)察打任務(wù)中的任務(wù)分配問(wèn)題。

2) 在所提出的任務(wù)分配方法中，聯(lián)盟構(gòu)建算法相較其他2種算法能夠獲得更大的系統(tǒng)效能。

3) 分析了無(wú)人機(jī)通信范圍和時(shí)間延遲約束對(duì)異構(gòu)多無(wú)人機(jī)執(zhí)行察打任務(wù)所獲得系統(tǒng)效能的影響。仿真試驗(yàn)結(jié)果說(shuō)明，在給定的通信時(shí)間延遲下，增大最大信息跳躍次數(shù)會(huì)使得系統(tǒng)效能先增大后減小。通過(guò)增大無(wú)人機(jī)的通信范圍，能夠延遲系統(tǒng)性能的下降。