潘 登，高 東，鄭建華

(1. 中國科學(xué)院國家空間科學(xué)中心 復(fù)雜航天系統(tǒng)電子信息技術(shù)重點(diǎn)實(shí)驗(yàn)室, 北京 100190; 2. 中國科學(xué)院大學(xué), 北京 101407)

近十幾年，隨著相關(guān)技術(shù)的突破和發(fā)展，無人機(jī)群協(xié)同合作完成任務(wù)成為無人機(jī)領(lǐng)域研究的熱點(diǎn)和趨勢。在任務(wù)環(huán)境日益復(fù)雜、任務(wù)規(guī)模日趨擴(kuò)大、任務(wù)內(nèi)容日漸多樣的趨勢下，無人機(jī)集群任務(wù)規(guī)劃問題的規(guī)模和復(fù)雜性也在不斷增加[1]。若缺乏科學(xué)高效的決策和規(guī)劃，不僅無法體現(xiàn)出無人機(jī)集群的優(yōu)勢，還會因?yàn)闊o人機(jī)之間在任務(wù)、時間、空間上的沖突導(dǎo)致資源浪費(fèi)甚至任務(wù)失敗。為此，需要根據(jù)任務(wù)需求、環(huán)境約束和無人機(jī)平臺特性等，進(jìn)行科學(xué)高效的任務(wù)規(guī)劃，確定各無人機(jī)的任務(wù)計劃和飛行計劃，以提高整體執(zhí)行任務(wù)的效能。這就是研究無人機(jī)集群任務(wù)規(guī)劃的意義所在。

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

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

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

1 任務(wù)規(guī)劃問題描述

大規(guī)模異構(gòu)無人機(jī)集群任務(wù)規(guī)劃的復(fù)雜性體現(xiàn)在以下幾點(diǎn)：

1)任務(wù)數(shù)量多，任務(wù)需求復(fù)雜，不同任務(wù)的需求不同，一個任務(wù)可能需要具備不同能力的無人機(jī)合作完成。這組相互合作完成同一個任務(wù)的無人機(jī)稱為無人機(jī)聯(lián)盟。

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

3)任務(wù)地理范圍廣，存在多個出發(fā)位置(地面站)，各站點(diǎn)儲備的無人機(jī)平臺資源量不同。對于執(zhí)行遠(yuǎn)距離任務(wù)的無人機(jī)，前往任務(wù)地區(qū)的路程消耗不可忽視。

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

圖1 無人機(jī)集群任務(wù)規(guī)劃示意圖Fig.1 Task planning of UAV swarm

1.1 任務(wù)對象

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

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

(1)

任務(wù)屬性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)為任務(wù)i的位置坐標(biāo)，CTi為執(zhí)行任務(wù)i的任務(wù)代價，包含所需平臺資源種類和數(shù)量；CTsi、CTri分別為執(zhí)行任務(wù)i的消耗性資源和重用性資源。

(5)

(6)

根據(jù)任務(wù)規(guī)劃，所有任務(wù)通過聚類形成了NC個任務(wù)子集合。任務(wù)子集合的集合

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

(7)

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

RTC{Position,Cost}

(8)

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

(9)

RTCi={PTi,CTCi,WCTCi}

(10)

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

1.2 無人機(jī)平臺

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

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

(11)

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

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

(12)

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

RU{Position,Resource}

(13)

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

(14)

式中：PUj(xUj,yUj,zUj)表示無人機(jī)j的位置坐標(biāo)，SUj表示無人機(jī)j具有的資源種類和數(shù)量；STsj、STrj分別為無人機(jī)j具有的消耗性資源和重用性資源?？筛鶕?jù)實(shí)際情況設(shè)置重用性資源轉(zhuǎn)化為某消耗性資源的比例系數(shù)。

(15)

(16)

無人機(jī)根據(jù)任務(wù)規(guī)劃組成MC個無人機(jī)聯(lián)盟，假設(shè)同一聯(lián)盟中無人機(jī)均屬于同一個地面站，任務(wù)過程中作為一個整體行動。無人機(jī)聯(lián)盟集合

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

(17)

無人機(jī)聯(lián)盟屬性RUC可由一個二元組來表示：

RUC{Position,Resource}

(18)

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

(19)

RUCj={PUCj,SUCj}

(20)

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

1.3 約束條件

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

(21)

對于任意一個任務(wù)集合，只能被某個無人機(jī)聯(lián)盟執(zhí)行一次；所有的任務(wù)都需要被執(zhí)行，即

(22)

(23)

(24)

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

(25)

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

圖2 經(jīng)緯M300飛行時間Fig.2 Flight time of Matrice 300

1.4 規(guī)劃目標(biāo)

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

任務(wù)規(guī)劃的目標(biāo)如下：

(26)

(27)

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

2 基于均衡聚類市場機(jī)制的任務(wù)規(guī)劃算法

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

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

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

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

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

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

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

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

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

5)重復(fù)步驟3、4直至迭代結(jié)束。得到歷史最優(yōu)的規(guī)劃方案，根據(jù)該方案中聯(lián)盟的任務(wù)完成情況，對無人機(jī)聯(lián)盟進(jìn)行調(diào)整保證任務(wù)完成率。例如某無人機(jī)聯(lián)盟的任務(wù)完成率不到100%,表示該聯(lián)盟具有的資源不足以完成整個任務(wù)計劃。根據(jù)其缺少的資源類型和數(shù)量，給該聯(lián)盟增加具有對應(yīng)資源的無人機(jī)，增加的數(shù)量根據(jù)資源缺少量來確定。

2.1 均衡市場拍賣機(jī)制

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

Pj=Di+β×Cj

(28)

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

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

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

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

(29)

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

(30)

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

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

(31)

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

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

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

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

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

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

表1 LKH-2算法檢測結(jié)果

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

2.3 任務(wù)聚類中心的形成和更新

K-means算法是任務(wù)目標(biāo)聚類最常用的算法[3-5,13,24]，通過迭代反復(fù)修改聚類中心和聚類來達(dá)到最滿意的聚類結(jié)果，具有計算簡單、能快速處理大數(shù)據(jù)集等優(yōu)點(diǎn)。傳統(tǒng)K-means算法的初始聚類中心是從數(shù)據(jù)對象中隨機(jī)選取的，但K-means算法對初始聚類中心敏感，不同初始中心對應(yīng)的聚類結(jié)果可能有很大的區(qū)別[25]。為了保證聚類效果，不至于出現(xiàn)某些任務(wù)簇內(nèi)無任務(wù)的情況，將初始聚類中心盡可能分散[7]。

已知任務(wù)目標(biāo)集合T,定義任務(wù)聚類中心集合CL,需要生成的聚類中心數(shù)量NTC，任務(wù)目標(biāo)Ti和Tj之間的歐氏距離為DT(i,j)；k為CL中已有聚類中心的個數(shù),初值為0；SD(j)為T中第j個任務(wù)到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任務(wù)從T中抽出放入CL中，然后在T中抽取使SD最大的任務(wù)Tpk+1，作為新選取的聚類中心放入CL中。重復(fù)該抽取過程直至CL中的聚類中心個數(shù)k等于NTC，至此完成初始聚類中心的計算。

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

表2 聚類中心分配示例

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

圖5為一次基于均衡市場拍賣機(jī)制的任務(wù)規(guī)劃中，總消耗CostAll和負(fù)載均衡程度μave隨迭代次數(shù)的變化?？梢钥闯觯疚牡腂CMA法在迭代中，能有效抑制μave的突增，同時使CostAll整體呈下降趨勢。

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

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

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

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

3.1 任務(wù)目標(biāo)均勻分布

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

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

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

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

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

(a) K-means法任務(wù)規(guī)劃結(jié)果(a) Task planning results of K-means

3.2 任務(wù)目標(biāo)位置非均勻分布

對任務(wù)的分布區(qū)域進(jìn)行限定，其他設(shè)置與3.1小節(jié)同。圖8為任務(wù)分布在地圖右半?yún)^(qū)域時的仿真結(jié)果。

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

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

3.3 任務(wù)目標(biāo)類型非均勻分布

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

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

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

3.4 實(shí)驗(yàn)結(jié)果分析

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

從仿真結(jié)果上看，K-means法的總消耗和總時間表現(xiàn)最佳。然而K-means法總消耗較少，一方面是因?yàn)槁烦潭?，另一方面是因?yàn)槠淙蝿?wù)完成率較低，部分任務(wù)未被執(zhí)行；其總時間較短，一方面是因?yàn)槁眯袝r間短，另一方面則是因?yàn)閷?shí)驗(yàn)沒有設(shè)置執(zhí)行任務(wù)的時間，未體現(xiàn)任務(wù)代價不均衡對總時間的影響。實(shí)際上執(zhí)行任務(wù)的時間越長，K-means法負(fù)載不均衡對總時間的影響會更容易得到凸顯。

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

4 結(jié)論

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

2)建立了無人機(jī)集群合作型任務(wù)規(guī)劃問題的通用模型，引入了任務(wù)集合和無人機(jī)聯(lián)盟雙重策略，更適應(yīng)于無人機(jī)集群發(fā)展的實(shí)際需求。在此基礎(chǔ)上進(jìn)行了任務(wù)規(guī)劃對比試驗(yàn)，驗(yàn)證了本文BCMA任務(wù)規(guī)劃方法的有效性。

3)要指出的是，本文中的任務(wù)規(guī)劃方法雖然應(yīng)用于全局的靜態(tài)集群任務(wù)規(guī)劃，但其基于市場拍賣的機(jī)制和分布式的系統(tǒng)結(jié)構(gòu)也適用于局部的動態(tài)集群任務(wù)規(guī)劃。由于線上動態(tài)規(guī)劃需要考慮到集群通信等問題，具體規(guī)劃方法有待進(jìn)一步的研究。