均衡聚類市場拍賣機制的異構無人機集群任務規劃方法*

潘 登，高 東，鄭建華

(1. 中國科學院國家空間科學中心 復雜航天系統電子信息技術重點實驗室, 北京 100190; 2. 中國科學院大學, 北京 101407)

近十幾年，隨著相關技術的突破和發展，無人機群協同合作完成任務成為無人機領域研究的熱點和趨勢。在任務環境日益復雜、任務規模日趨擴大、任務內容日漸多樣的趨勢下，無人機集群任務規劃問題的規模和復雜性也在不斷增加[1]。若缺乏科學高效的決策和規劃，不僅無法體現出無人機集群的優勢，還會因為無人機之間在任務、時間、空間上的沖突導致資源浪費甚至任務失敗。為此，需要根據任務需求、環境約束和無人機平臺特性等，進行科學高效的任務規劃，確定各無人機的任務計劃和飛行計劃，以提高整體執行任務的效能。這就是研究無人機集群任務規劃的意義所在。

無人機集群任務規劃問題從屬于多機器人任務規劃問題(multi-robot task allocation，MRTA)，根據任務是否全部已知分為靜態任務規劃(static MRTA，S-MRTA)和動態任務規劃(dynamic MRTA，D-MRTA)[2]。目前大部分無人機集群靜態任務規劃的研究都是針對特定場景建模，任務類型或無人機種類單一，存在規模較小、通用性不足的問題。部分學者對大規模復雜集群任務規劃問題做了研究，文獻[3-7]通過聚類的方式，將任務劃分成多個任務簇，再將任務簇分配給無人機個體，有效降低了大規模任務規劃問題的解算難度；文獻[8-11]通過無人機聯盟的方式解決異構無人機的任務規劃問題。

另外，集群任務規劃的研究大多集中在最小化整體成本上，而較少把重點放在提高無人機群的利用率上，即平衡無人機之間的負載。事實上，無人機群在任務中的負載均衡對降低任務總時間和動態任務規劃有重要意義。無人機的消耗一方面用于執行任務，一方面用于往返任務地點，兩者均對無人機的負載均衡程度有較大影響。一些學者對移動機器人或無人機群任務規劃的負載均衡做了研究。文獻[3]通過均衡移動機器人個體之間的路程長度，最小化完成任務的總時間，但任務規模較小且不考慮機器人執行任務的消耗。文獻[5]先使用K-means法進行任務聚類，再將任務簇分配給各機器人，使旅行消耗達到最均衡，但其聚類過程中沒有考慮任務時序、任務代價和出發位置的影響，影響了均衡效果，且其解算使用的窮舉法不適用于大規模的任務規劃問題。文獻[7]先通過限制簇內任務數量、縮短簇內任務距離來保證任務簇之間的負載均衡，再將任務簇分配給機器人組成聯盟，這種方式在聚類階段未考慮任務類別以及出發位置對負載均衡的影響。文獻[2]通過引入旅行商問題先確定任務時序和路徑，然后將路徑碎片化再分配給移動機器人個體，從而將任務時序和路程消耗納入規劃中，在負載均衡分配方面有較好表現，但其先規劃路徑的方式可能會造成較高的旅行成本。以上方法一定程度改善了任務規劃中無人機群的負載均衡程度，但在通用性、均衡程度和降低整體成本方面還有更進一步的空間。

本文提出了一種基于均衡聚類市場拍賣機制的任務規劃方法(task planning based on balanced clustering market auction mechanism，BCMA)，目的是解決無人機領域的全局集群任務規劃問題，適用于存在合作型任務、異構無人機群以及多出發位置的復雜任務場景。該方法結合了任務聚類和無人機聯盟兩種策略的優勢，降低了大規模異構無人機集群任務規劃問題的解算難度，且在形成任務集合的時候就已規劃好任務時序；深度融合K-means法的迭代機制與市場拍賣機制，并在市場拍賣機制中引入自適應平衡參數，將路程代價和任務代價同時納入考慮，形成一種不只考慮空間距離的聚類方法，保證了無人機群的負載均衡。仿真結果表明，本文的任務規劃方法能夠快速完成較大規模的異構無人機集群任務規劃，且規劃結果在總消耗、總時間和負載均衡上都有較好的表現。

1 任務規劃問題描述

大規模異構無人機集群任務規劃的復雜性體現在以下幾點：

1)任務數量多，任務需求復雜，不同任務的需求不同，一個任務可能需要具備不同能力的無人機合作完成。這組相互合作完成同一個任務的無人機稱為無人機聯盟。

2)無人機數量多，且無人機掛載資源的種類和能力不同，一架無人機可能參與多個任務。這組任務稱為任務集合。

3)任務地理范圍廣，存在多個出發位置(地面站)，各站點儲備的無人機平臺資源量不同。對于執行遠距離任務的無人機，前往任務地區的路程消耗不可忽視。

任務規劃的目的是將所有任務分解并分配給適合的無人機，確定各無人機的任務計劃，同時最優化整體效能。引入任務集合和無人機聯盟的機制后，任務規劃則需要形成合適的任務集合和無人機聯盟，并將任務集合分配給無人機聯盟，形成任務計劃，示意圖如圖1所示。

圖1 無人機集群任務規劃示意圖Fig.1 Task planning of UAV swarm

1.1 任務對象

任務對象由N個位置不同的任務目標組成，完成任務需要的平臺資源共m類，可分為消耗性資源(例如電量、耗油量、炮彈量)和重用性資源(例如相機、雷達)，假設有m1種消耗性資源和m2種重用性資源。使用重用性資源的同時，一般會額外使用一定量的消耗性資源，例如使用雷達功能需要消耗額外電量。任務總集合

T={Ti|i=1,2,3,…,N}

(1)

任務屬性RT可由一個二元組來表示：

RT{Position,Cost}

(2)

RT={RTi|i=1,2,3,…,N}

(3)

RTi={PTi,CTi}={(xTi,yTi,zTi),(CTsi，CTri)}

(4)

式中：PTi(xTi,yTi,zTi)為任務i的位置坐標，CTi為執行任務i的任務代價，包含所需平臺資源種類和數量；CTsi、CTri分別為執行任務i的消耗性資源和重用性資源。

(5)

(6)

根據任務規劃，所有任務通過聚類形成了NC個任務子集合。任務子集合的集合

TC={TCi|i=1,2,3,…,NC}

(7)

任務子集合屬性RTC可由一個二元組來表示：

RTC{Position,Cost}

(8)

RTC={RTCi|i=1,2,3,…,NC}

(9)

RTCi={PTi,CTCi,WCTCi}

(10)

式中：PTi為任務子集合i中執行的第一個任務的位置坐標；CTCi(CTCsi，CTCri)為無人機執行任務子集合i中所有任務的任務代價，包含所需平臺資源種類和數量，CTCsi、CTCri分別為執行任務子集合i的消耗性資源和重用性資源；WCTCi為一架無人機按照規劃的任務時序完成任務子集合i的路程代價。

1.2 無人機平臺

無人機平臺由Ns個地面站和M架具有不同資源的無人機組成。無人機平臺具有的資源共m類，與任務所需平臺資源的種類對應。地面站集合

S={Si|i=1,2,3,…,Ns}

(11)

式中，Si(xSi,ySi,zSi)為地面站的位置坐標。無人機集合

U={Uj|j=1,2,3,…,M}

(12)

無人機屬性RU可由一個二元組來表示：

RU{Position,Resource}

(13)

RUj={PUj,SUj}={(xUj,yUj,zUj),(STsj，STrj)}

(14)

式中：PUj(xUj,yUj,zUj)表示無人機j的位置坐標，SUj表示無人機j具有的資源種類和數量；STsj、STrj分別為無人機j具有的消耗性資源和重用性資源。可根據實際情況設置重用性資源轉化為某消耗性資源的比例系數。

(15)

(16)

無人機根據任務規劃組成MC個無人機聯盟，假設同一聯盟中無人機均屬于同一個地面站，任務過程中作為一個整體行動。無人機聯盟集合

UC={UCj|j=1,2,3,…,MC}

(17)

無人機聯盟屬性RUC可由一個二元組來表示：

RUC{Position,Resource}

(18)

RUC={RUCj|j=1,2,3,…,MC}

(19)

RUCj={PUCj,SUCj}

(20)

式中：PUCj為無人機聯盟j所屬地面站的位置坐標，SUCj(SUCsj，SUCrj)為無人機聯盟j具有的資源種類和數量，SUCsj、SUCrj分別為無人機聯盟j內所有無人機的消耗性資源和重用性資源總和。

1.3 約束條件

為了保障無人機群在執行任務過程中的協同，對所建立的模型添加一定的約束條件。定義任務分配決策矩陣XMC×NC，Xji為矩陣第j行、第i列的元素，其意義如下：

(21)

對于任意一個任務集合，只能被某個無人機聯盟執行一次；所有的任務都需要被執行，即

(22)

(23)

(24)

執行所有任務的代價不得超出無人機群的總資源。無人機是否還具有執行任務的能力通常取決于兩方面：一是續航時間，也就是消耗性資源中的能源量，設置為STsj(1)；二是除能源量以外的消耗性資源，例如炮彈量。由于初步判斷的時候任務時序和路程都未知，無法得到準確的路程代價，因此需要保持一定的資源余量，使用α表示資源富余的程度，式(25)表示了總任務代價與無人機群總資源的約束關系。α實際代表任務過程中，任務代價占無人機總資源的比例，可根據無人機的特性設置。ηk為第k種重用性資源CTrk轉化為能源量STsj(1)的比例系數。

(25)

例如，圖2為經緯M300不同負載(重用性資源)和空載時的飛行時間[12]，最大負載時的續航時間約為空載時的56%，即表示經緯M300約44%的能源消耗在任務負載上。根據經緯M300及市面上一些無人機的情況，本文中α設定在0.5。

圖2 經緯M300飛行時間Fig.2 Flight time of Matrice 300

1.4 規劃目標

評估任務規劃結果優劣的指標包括：①總消耗CostAll，包括執行所有任務的任務消耗和各無人機從出發到返回地面站的路程消耗；②任務完成率TAR，雖然初始判斷的時候保留了一定資源余量(式(25))，規劃完成后，仍可能會出現完成任務子集合的總消耗高于對應無人機聯盟的總資源，這種情況下會有部分任務無法完成；③總時間ET，假設所有無人機同時出發，以耗時最長的無人機聯盟回到地面站的時間作為總時間；④無人機群負載均衡程度μave，使用各無人機聯盟資源利用率的標準差表示，μave越小表示負載均衡程度越好。

任務規劃的目標如下：

(26)

(27)

其中，UTave為無人機聯盟的平均資源利用率，NUCj為任務子集合i對應聯盟j的無人機數量，NTCi為任務子集合i的任務個數，NTCFi為任務子集合i能被完成的任務個數，ETj為無人機聯盟j完成任務回到地面站的時間。

2 基于均衡聚類市場機制的任務規劃算法

無人機集群任務規劃本質是解決一個復雜的多目標優化問題[13]，常用的任務規劃方法有：傳統數學規劃法、基于市場機制的方法、基于圖論的方法和智能優化算法(如蟻群算法、遺傳算法、禁忌搜索算法)等?；谑袌鰴C制的拍賣算法最早由Bertsekas提出[14]，模擬人類交互中常見的拍賣行為，通過信息互相共享和傳遞得到分配方案。市場拍賣算法因其高時效性和分布式結構，被廣泛應用于無人機的任務分配問題[15-18]。

市場拍賣算法的基本流程[19]：拍賣者生成一個商品拍賣輪次方案，按照方案順序發布合同；競標者分別計算競拍商品的收益和代價等信息，作為競拍依據并反饋給拍賣者；拍賣者根據收到的競標信息選擇中標者，并向中標者發布合同；循環直至拍賣輪次結束，所有商品都被競拍完畢。

在基于市場拍賣算法的無人機集群任務規劃中，被拍賣的商品是無人機執行的任務，競拍者為無人機。競拍完成則所有任務被劃分為多個任務集合分配給參與競拍的無人機聯盟，從而形成了整體的任務規劃方案。然而，單純的市場拍賣算法一方面受到拍賣順序的影響，其任務規劃結果具有很大的隨機性，效果無法得到保證；另一方面，雖然可以通過在競拍依據里引入任務代價均衡，使得規劃結果的任務代價趨向均衡，卻沒有辦法引入路程代價，也就無法真正保證無人機群的總負載均衡。

因此本文提出BCMA任務規劃方法，將K-means法的聚類迭代機制和市場拍賣算法融合，將路程代價和任務代價通過平衡參數引入市場拍賣算法中，使由市場拍賣算法形成的規劃結果能夠在迭代中逐漸優化。BCMA任務規劃方法的算法流程如圖3所示，基本思想如下：

圖3 基于均衡聚類市場拍賣機制的任務規劃算法流程Fig.3 Task planning algorithm flow based on balanced clustering market auction mechanism

1)根據異構無人機群的分布式結構或資源類型，初始化無人機聯盟的數量和組成，使每個聯盟的資源總量和比例基本相同。任務所需各類資源的總量決定各類無人機的數量(式(25))，各類資源的比例決定無人機聯盟內異構無人機的組成比例。初始聯盟數量在可選范圍內盡可能多，即在保證聯盟能力全面的同時，最小化聯盟規模。

2)使用改進K-means法生成初始聚類中心，形成初次規劃方案。

3)從第二次迭代起，無人機聯盟通過逐一拍賣的方式，將任務聚類形成多個任務集合。

4)拍賣完畢后，通過評估任務集合的負載均衡程度，修正拍賣依據中的平衡參數并判斷是否使用更新聚類中心。如需更新聚類中心，使用K-means法生成新的聚類中心。

5)重復步驟3、4直至迭代結束。得到歷史最優的規劃方案，根據該方案中聯盟的任務完成情況，對無人機聯盟進行調整保證任務完成率。例如某無人機聯盟的任務完成率不到100%,表示該聯盟具有的資源不足以完成整個任務計劃。根據其缺少的資源類型和數量，給該聯盟增加具有對應資源的無人機，增加的數量根據資源缺少量來確定。

2.1 均衡市場拍賣機制

保證無人機聯盟負載均衡的核心在于市場拍賣過程的競拍依據P考慮了各無人機聯盟之間的資源消耗均衡程度。定義Pj為聯盟j對當前被拍賣任務的競拍依據，Pj由路程增量代價Di、任務均衡代價Cj以及平衡參數β組成，如式(28)所示。給出最小P的無人機聯盟即為中標者，獲得被競拍任務。

Pj=Di+β×Cj

(28)

路程增量代價Di：由于拍賣時任務集合還未完全形成，無法獲得準確的路程代價增量，故定義當前被拍賣任務到任務集合i聚類中心的距離為Di，作為衡量路程增量代價的參數。Di越大，則Pj越大，該聯盟競拍到任務的可能性就越小。

任務均衡代價Cj：定義無人機聯盟j當前拍賣到的任務總資源與各聯盟平均任務資源的差值為Cj，作為任務均衡代價。Cj越大，則Pj越大，任務被分到聯盟j對應的任務集合i的可能性就越小。

由于路程增量代價和任務均衡代價屬于不同性質的決策因素，需要通過一定的方式轉化到同一衡量體系。1.3小節中提到，無人機執行任務的能力取決于兩方面，一是能源量，二是除能源量以外的消耗性資源。將路程增量代價和任務均衡代價轉化到能源量這一體系中。

路程增量代價通過比例系數η直接轉化為能源量(見式(29))；任務均衡代價中的重用性資源部分，通過比例系數ηk轉化為能源量，比例系數根據實際情況而定，不同的重用性資源比例系數不同；任務均衡代價中的除能源量外的消耗性資源按對應任務數量占比λk并入能源量中(見式(30))。

(29)

式中，(xnew,ynew,znew)為當前被拍賣任務目標的位置坐標，(xi,yi,zi)為任務集合i的聚類中心坐標，η為路程轉化成能源量的比例系數。

(30)

式中，ΔSUCj為聯盟j完成當前已拍賣到的任務所需的能源量與各聯盟平均的差值，λk為使用第k種消耗性資源的任務數量占比，ηk為使用第k種重用性資源轉化為能源量的比例系數，Cj(k)為無人機聯盟j當前已拍賣到的任務所需第k種重用性資源與各聯盟平均的差值。

因為Di僅為路程增量的估計值，沒有考慮任務時序和多出發位置的影響，故引入平衡參數β。每次迭代中任務拍賣完成后，分別計算每個任務集合使路程最短的任務時序，進一步求得無人機聯盟之間的負載均衡程度μave。如果μave同比上次迭代增加較多，說明本次迭代效果不理想，選擇不更新聚類中心，并適當增大平衡參數β，使下次迭代中均衡程度的影響變大；反之，則更新聚類中心，并適當減小β，以增大拍賣算法的探索范圍。

(31)

式中，β初值設為0.6，算法會根據負載均衡程度自動調整β，在一定范圍內β初值對計算結果沒有明顯影響。μave_old為上一次規劃結果的負載均衡程度，γ為判斷μave過大的閾值。圖4所示為不同數值的γ對算法收斂時的迭代次數的影響，根據該圖將γ設為1.2，使算法在各種情形下都能較快達到收斂。

圖4 判斷閾值γ對算法收斂的影響Fig.4 Influence of judgment threshold γ on algorithm convergence

2.2 LKH-2算法求解旅行商問題

為獲得無人機聯盟的負載均衡程度μave，需要在每次形成任務集合后，分別計算各個任務集合使路程最短的任務時序，這是典型的旅行商問題(travelling salesman problem, TSP)。BCMA任務規劃方法需要解算較多次數的旅行商問題，旅行商問題的求解速度是影響算法效率的最大因素。

本文使用LKH-2算法對旅行商問題進行求解。LKH-2算法是一種啟發式局部搜索算法，是目前求解對稱旅行商問題的最優或近似最優解最成功的方法之一。Helsgaun于1999年提出LKH(Lin-Kernighan heuristic)算法[20]，是當時除窮舉法外精確度最高的旅行商問題搜索算法，且收斂速度較快[21]。2009年，Helsgaun進一步改進LKH形成LKH-2算法[22]，使其更適用于求解大規模的旅行商問題。

為了驗證LKH-2算法適用于求解本文任務規劃中的旅行商問題，使用TSPLIB[23]中已知最優解(最短路程)的部分中小型規模問題作為LKH-2算法的檢驗樣本,TSP編號名稱中包含的數字即為城市數量。對每個樣本進行100次重復試驗，仿真結果見表1。

表1 LKH-2算法檢測結果

由表1可知，LKH-2算法隨著城市數量的增多，其解算時間整體呈上升趨勢。在解算100個城市以內的旅行商問題上，單次解算速度基本穩定在0.1 s以內，且都能達到最優解。在解算50個城市以內的旅行商問題上，單次解算速度基本穩定在0.03 s以內。例如某次任務規劃中，迭代20次，需要形成5個任務集合，每個集合內的任務數量不多于50個，則整個過程需要求解100次旅行商問題，解算時間1～4 s。因此，使用LKH-2算法求解旅行商問題能夠保證本文任務規劃方法的時效性。

2.3 任務聚類中心的形成和更新

K-means算法是任務目標聚類最常用的算法[3-5,13,24]，通過迭代反復修改聚類中心和聚類來達到最滿意的聚類結果，具有計算簡單、能快速處理大數據集等優點。傳統K-means算法的初始聚類中心是從數據對象中隨機選取的，但K-means算法對初始聚類中心敏感，不同初始中心對應的聚類結果可能有很大的區別[25]。為了保證聚類效果，不至于出現某些任務簇內無任務的情況，將初始聚類中心盡可能分散[7]。

已知任務目標集合T,定義任務聚類中心集合CL,需要生成的聚類中心數量NTC，任務目標Ti和Tj之間的歐氏距離為DT(i,j)；k為CL中已有聚類中心的個數,初值為0；SD(j)為T中第j個任務到CL中所有聚類中心的距離之和，則有

DT(p1,p2)=maxDT(i,j)，i∈[1,N]，j∈[1,N]

(32)

(33)

SD(pk+1)=maxSD(j)，j∈[1,N-k]

(34)

如果NTC=2，選擇Tp1和Tp2作為初始聚類中心；如果NTC>2，先將Tp1和Tp2任務從T中抽出放入CL中，然后在T中抽取使SD最大的任務Tpk+1，作為新選取的聚類中心放入CL中。重復該抽取過程直至CL中的聚類中心個數k等于NTC，至此完成初始聚類中心的計算。

根據各地面站具有的無人機聯盟數量比例，將聚類中心按該比例和到各地面站距離分配給合適的地面站。表2所示為一次聚類中心分配的示例，計算得到的6個聚類中心CL1～CL6需要分配到3個地面站S1～S3，三個地面站的無人機聯盟數量比例為3 ∶1 ∶2，即表示三個地面站分別匹配3、1、2個聚類中心。按照聚類中心編號順序，分配該聚類中心到距離最近的地面站，如該地面站已經滿員，則按照距離從近到遠往后順延。這種分配方式不一定能達到最優解，但過程簡單，能夠滿足初次分配的需求。

表2 聚類中心分配示例

聚類中心的更新機制與K-means算法一致，即新的聚類中心為該任務簇中所有任務目標坐標的均值。通過這種更新機制，能夠完成對數據空間比較全面的快速搜索。

圖5為一次基于均衡市場拍賣機制的任務規劃中，總消耗CostAll和負載均衡程度μave隨迭代次數的變化?？梢钥闯?，本文的BCMA法在迭代中，能有效抑制μave的突增，同時使CostAll整體呈下降趨勢。

(a) 總消耗隨迭代的變化(a) Total cost with iteration

3 仿真實驗

設置任務目標范圍1 000×1 000，有兩個位置不同的地面站S1(300,300)和S2(700,700)。平臺資源的種類有四種，其中一種為消耗性資源CTs1，假設為電量；三種為重用性資源CTri(i=1，2，3)，假設分別為可見光傳感器、紅外傳感器、激光探測儀。任務數量N取40～150，位置在規定范圍內隨機生成，所需無人機到達任務目標位置即完成任務。完成某個任務需要1～3種重用性資源，即可能需要多架異構無人機合作完成。無人機數量M為12～45，單架無人機的初始CTs1=10 000，具有重用性資源中的一種，每使用該種功能完成一個任務需消耗200的電量，即ηk=200。路程轉化成消耗性資源的比例系數η=1。S1和S2兩個地面站的無人機數量比例為1 ∶2，具有三種重用性資源的無人機比例為1 ∶1 ∶1。

以文獻[7]中GCABTD算法的簇內相互距離和為聚類依據的改進貪婪聚類算法，在負載均衡方面有很好的表現。使用本文BCMA算法、K-means算法和改進貪婪聚類算法對不同規模和特點的異構無人機集群任務規劃進行對比仿真實驗。為使無人機聯盟功能全面，初始聯盟由3架具有不同資源的無人機組成。仿真結果為調整無人機聯盟之前的規劃結果，故可能存在任務完成率小于100%的情況。這種情況下需要根據資源缺少情況調整無人機聯盟，以保證所有任務完成。

3.1 任務目標均勻分布

任務目標數量N取40～150，以10為間隔，位置在全地圖隨機生成，每個任務所需資源種類隨機生成，控制需求每種資源的任務數量占總任務數量的2/3。對應無人機數量M取12～45，間隔為3。重復試驗100次，并計算平均的任務完成率TAR、總消耗CostAll、總時間ET和負載均衡程度μave?？倳r間ET由最長路程的長度表示，不考慮執行任務所需時間。仿真結果如圖6所示，其中總消耗、總時間和負載均衡程度的顯示以K-means法為基準(優于/劣于K-means法的百分比)。

(a) 任務完成率(a) Task accomplishment ratio

在任務均勻分布的情況下，本文的BCMA法在任務完成率上優于K-means法和改進貪婪聚類法，且隨著任務規模的增大而趨于100%。在總消耗和總時間上，BCMA法相較改進貪婪聚類法更有優勢。改進貪婪聚類法隨著任務規模的增大，負載均衡程度逐漸改善，規模較大時與BCMA法效果近似甚至略優于BCMA法。K-means法在任務均勻分布的情況下，總消耗和總時間表現較好，但負載均衡程度明顯較差，且其任務完成率也低于其他兩種方法。

圖7所示為任務數量N=60，無人機數量M=18，分為6個任務集合、任務均勻分布的情況下，K-means法、改進貪婪聚類法和本文BCMA法的一次任務規劃結果。五星代表地面站位置，圓點代表任務位置，菱形代表聚類中心/聚類起點，回環代表無人機聯盟完成任務的路線。

從圖7可以看出，在任務均勻分布的情況下，K-means法和BCMA法的聚類中心比較分散，集合內的任務也相對集中，因此路程長度較短，路程消耗和總時間都比較少。而改進貪婪聚類法的任務集合重疊較多，路程較長，所以在總消耗和總時間上表現較差。K-means法各任務集合中的任務數量差別較大，因此負載均衡程度表現較差。

(a) K-means法任務規劃結果(a) Task planning results of K-means

3.2 任務目標位置非均勻分布

對任務的分布區域進行限定，其他設置與3.1小節同。圖8為任務分布在地圖右半區域時的仿真結果。

(a) 任務完成率(a) Task accomplishment ratio

仿真結果表明，對于任務位置非均勻分布的情況，本文的BCMA法和改進貪婪聚類法的規劃效果比較相近，在任務完成率都接近100%的情況下，BCMA法在總消耗和總時間上更有優勢，但在均衡負載程度上稍差于改進貪婪聚類法。而K-means法由于路程短，路程消耗少，總消耗和總時間是三種方法中最小的，但K-means法的負載均衡程度很差，任務負載較多的無人機聯盟無法完成所有任務，且隨著任務規模的增大任務完成率進一步降低，不能滿足任務規劃的需求。

3.3 任務目標類型非均勻分布

任務位置在全地圖隨機生成，但對任務類型的分布區域進行限定，其他設置與3.1小節同。圖9所示為任務位置隨機分布，但需求重用性資源CTr3的任務限定在地圖左右各1/3區域時的仿真結果。

(a) 任務完成率(a) Task accomplishment ratio

由圖9可知，在任務類型非均勻分布的情況下，BCMA法和改進貪婪聚類法在任務完成率和負載均衡程度上整體優于K-means法。而在總消耗和總時間方面，從小到大分別為K-means法、BCMA法和改進貪婪聚類法。

3.4 實驗結果分析

通過以上仿真實驗可知，本文的BCMA任務規劃方法適用于不同規模、不同任務分布的全局任務規劃。尤其是在任務非均勻分布的情況下，依舊能保持高任務完成率，并在總時間、總消耗和負載均衡上均獲得較好的效果。

從仿真結果上看，K-means法的總消耗和總時間表現最佳。然而K-means法總消耗較少，一方面是因為路程短，另一方面是因為其任務完成率較低，部分任務未被執行；其總時間較短，一方面是因為旅行時間短，另一方面則是因為實驗沒有設置執行任務的時間，未體現任務代價不均衡對總時間的影響。實際上執行任務的時間越長，K-means法負載不均衡對總時間的影響會更容易得到凸顯。

另外，BCMA法的任務完成率存在達不到100%的情況，尤其是在任務數量較少的時候。原因在于規劃初始，預估的任務代價占比為固定值(式(25)中α)。而當任務數量較少且分布分散時，任務代價占比低于該定值且偏離較多，導致對資源總量的預估低于實際需求量，少量任務無法完成。

4 結論

1)本文針對較大規模的異構無人機集群任務規劃問題，提出一種基于均衡聚類市場拍賣機制的任務規劃方法BCMA，結合了K-means法的迭代機制和市場拍賣機制，在均衡無人機負載的同時保證了總消耗的迭代優化。

2)建立了無人機集群合作型任務規劃問題的通用模型，引入了任務集合和無人機聯盟雙重策略，更適應于無人機集群發展的實際需求。在此基礎上進行了任務規劃對比試驗，驗證了本文BCMA任務規劃方法的有效性。

3)要指出的是，本文中的任務規劃方法雖然應用于全局的靜態集群任務規劃，但其基于市場拍賣的機制和分布式的系統結構也適用于局部的動態集群任務規劃。由于線上動態規劃需要考慮到集群通信等問題，具體規劃方法有待進一步的研究。