通信約束下異構(gòu)多無人機任務(wù)分配方法

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

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

2. 中國飛行試驗研究院，西安 710089

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

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

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

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

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

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

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

1 問題描述及建模

1.1 任務(wù)過程分析

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

假設(shè)各無人機定高飛行，無人機的運動學(xué)模型可表示為

(5)

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

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

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

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

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

Rs>2Rr

(6)

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

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

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

(7)

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

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

1) 無人機聯(lián)盟資源約束

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

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

(8)

2) 無人機的有限資源約束

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

R(Α(i))≤RUi

(9)

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

3) 無人機的最大可飛行時長約束

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

(10)

4) 死鎖約束

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

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 多無人機的通信拓?fù)?Hmax=2)

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

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

(12)

(13)

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

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

(14)

(15)

其中：ETA(i,j)為無人機Ui到達目標(biāo)的預(yù)計到達時間。

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

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

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

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

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

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

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

各競標(biāo)無人機在獲取了其與待拍賣目標(biāo)的預(yù)計到達時間后，向聯(lián)盟長機發(fā)送投標(biāo)信息(或稱為標(biāo)書)，競標(biāo)無人機Uk發(fā)送的投標(biāo)信息Qk可表示為

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

(16)

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

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

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

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

(17)

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

步驟4執(zhí)行階段

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

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

(18)

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

2.2 無人機資源消耗計算

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

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

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

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

(19)

(20)

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

圖3 多無人機資源消耗示例

3 仿真實驗及分析

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

3.1 異構(gòu)多無人機察打任務(wù)示例場景

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

表1 初始時刻各無人機的信息

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

圖4 t=24.1 s 時各無人機的狀態(tài)

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

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

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

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

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

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

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

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

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

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

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

3.3 通信約束下算法性能

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

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

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

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

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

4 結(jié) 論

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

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

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