陳璞，嚴飛,*，劉釗，成果達

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

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

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

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

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

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

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

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

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

1 問題描述及建模

1.1 任務過程分析

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

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

1.2 無人機和目標模型

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

假設各無人機定高飛行，無人機的運動學模型可表示為

(5)

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

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

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

圖1 無人機的通信網絡示意圖

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

Rs>2Rr

(6)

1.3 目標函數和約束條件

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

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

(7)

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

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

1) 無人機聯盟資源約束

考慮到目標的資源需求，針對被發(fā)現目標Tj所構建的無人機聯盟的總可用資源需要滿足：

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

(8)

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

每架察打一體型無人機只能攜帶有限的攻擊型資源，且隨著使用而消耗。考慮到每架察打無人機能夠按分配順序攻擊多個目標，察打一體型無人機的資源需要滿足：

R(Α(i))≤RUi

(9)

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

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

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

(10)

4) 死鎖約束

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

(11)

5) 與飛行路徑相關的約束

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

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

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

2 基于合同網的任務分配方法

從1.1節(jié)的分析可知，異構多無人機執(zhí)行任務區(qū)域的察打任務時，若有新目標被發(fā)現，則觸發(fā)針對該目標的局部任務分配。由于無人機的通信范圍和時間延遲約束，多無人機在構建攻擊目標的聯盟時存在通信拓撲變化等情況。

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

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

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

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

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

步驟1任務發(fā)布

異構多無人機執(zhí)行察打任務中，當發(fā)現新目標，由發(fā)現目標的無人機作為招標無人機，向其局部通信網絡中的其他無人機發(fā)送聯盟構建的招標信息。

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

圖2 多無人機的通信拓撲(Hmax=2)

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

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

(12)

(13)

式中：tnow為該目標被發(fā)現時刻；δc為聯盟構建過程耗時的上界。

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

(14)

(15)

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

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

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

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

步驟2投標申請階段

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

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

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

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

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

(16)

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

步驟3聯盟構建

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

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

(17)

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

步驟4執(zhí)行階段

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

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

(18)

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

2.2 無人機資源消耗計算

當聯盟長機確定了執(zhí)行目標攻擊任務的聯盟成員后，聯盟成員需要共同承擔目標攻擊任務所需的資源。

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

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

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

(19)

(20)

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

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

3 仿真實驗及分析

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

3.1 異構多無人機察打任務示例場景

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

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

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

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

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

圖5 針對發(fā)現目標T1的任務分配結果(t=29.9 s)

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

圖6 針對發(fā)現目標T2的任務分配結果(t=55.4 s)

3.2 不同聯盟構建算法性能

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

通過Monte Carlo仿真試驗對比當無人機數目變化時，3種聯盟構建算法在多無人機協同察打任務中的性能，對比的指標為任務完成總時間和攻擊所有目標獲得的總效能。

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

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

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

圖7 無人機數目變化時3種聯盟構建算法的性能對比

3.3 通信約束下算法性能

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

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

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

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

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

4 結 論

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

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

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