通信約束下異構多無人機任務分配方法

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

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

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

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

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

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

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

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

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

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

1 問題描述及建模

1.1 任務過程分析

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

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

1.2 無人機和目標模型

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

(5)

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

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

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

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

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

Rs>2Rr

(6)

1.3 目標函數和約束條件

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

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

(7)

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

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

1) 無人機聯盟資源約束

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

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

(8)

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

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

R(Α(i))≤RUi

(9)

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

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

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

(10)

4) 死鎖約束

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

(11)

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

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

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

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

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

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

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

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

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

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

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

步驟1任務發布

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

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

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

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

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

(12)

(13)

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

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

(14)

(15)

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

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

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

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

步驟2投標申請階段

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

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

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

各競標無人機在獲取了其與待拍賣目標的預計到達時間后，向聯盟長機發送投標信息(或稱為標書)，競標無人機Uk發送的投標信息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的投標申請，聯盟長機收到了局部通信網絡中競標無人機向其發送的投標申請Q。考慮到目標的資源約束，單架無人機可能無法完成目標的攻擊任務，這就需要聯盟長機根據一定的準則在所有的競標無人機中選擇一個無人機聯盟執行該目標的同時攻擊任務。

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

(17)

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

步驟4執行階段

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

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

(18)

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

2.2 無人機資源消耗計算

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

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

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

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

(19)

(20)

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

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

3 仿真實驗及分析

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

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

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

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

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

圖4 t=24.1 s 時各無人機的狀態

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

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

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

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

3.2 不同聯盟構建算法性能

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

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

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

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

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

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

3.3 通信約束下算法性能

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

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

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

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

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

4 結 論

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

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

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