鄭紅星，郭繼峰，謝旭東，顏 鵬

(哈爾濱工業(yè)大學(xué)航天學(xué)院，哈爾濱 150001)

0 引 言

異構(gòu)無(wú)人機(jī)集群自主作業(yè)可以有效地提升集群的任務(wù)執(zhí)行效率及環(huán)境適應(yīng)性。異構(gòu)無(wú)人機(jī)集群進(jìn)行自主協(xié)作的關(guān)鍵在于高效的任務(wù)分配機(jī)制。樹(shù)搜索、遺傳算法、多目標(biāo)進(jìn)化等集中式任務(wù)分配方法，已經(jīng)被應(yīng)用于許多具有現(xiàn)實(shí)意義的任務(wù)場(chǎng)景中。然而，集中式方法通常難以在線應(yīng)用，且不容易被擴(kuò)展到存在大量任務(wù)/無(wú)人機(jī)的復(fù)雜場(chǎng)景中。

機(jī)載通信、計(jì)算及感知設(shè)備的能力提升，使無(wú)人機(jī)可以被視為具有決策能力的智能系統(tǒng)，這促使分布式任務(wù)分配問(wèn)題及其求解方法得到了廣泛的關(guān)注。文獻(xiàn)[10]針對(duì)威脅環(huán)境下的多無(wú)人機(jī)分布式協(xié)同決策問(wèn)題，提出了一種基于多智能體深度確定性策略梯度的多機(jī)決策算法，該算法具有較高的收斂速度與學(xué)習(xí)效率。文獻(xiàn)[11]提出了一種多耦合任務(wù)智能決策方法，有效地解決了無(wú)人機(jī)集群的協(xié)同目標(biāo)分配和突防軌跡規(guī)劃問(wèn)題。文獻(xiàn)[12]通過(guò)基于共識(shí)的捆綁算法，有效地解決了存在局部通信條件下的異構(gòu)多智能體任務(wù)分配問(wèn)題。文獻(xiàn)[13]提出了分布式匈牙利算法，該算法在全局通信條件下，可以獲得任務(wù)分配問(wèn)題的最優(yōu)解。上述方法基于分布式的框架有效地處理了多類任務(wù)分配問(wèn)題，但問(wèn)題中大多不考慮單任務(wù)的多機(jī)協(xié)同作業(yè)，其難以用于聯(lián)盟形成問(wèn)題的處理。

聯(lián)盟形成屬于一類特殊的任務(wù)分配問(wèn)題，任務(wù)通常具有復(fù)雜的資源、動(dòng)作等約束，需要多架無(wú)人機(jī)組成聯(lián)盟進(jìn)行協(xié)同作業(yè)。文獻(xiàn)[14]提出基于分割與合并的聯(lián)盟形成算法(Coalition formation algorithm based on merge and split，CF-MS)，有效地解決了動(dòng)態(tài)場(chǎng)景下的機(jī)器人協(xié)作聯(lián)盟形成問(wèn)題，但該算法對(duì)于較大規(guī)模聯(lián)盟形成問(wèn)題的處理能力有限。文獻(xiàn)[15]提出基于隨機(jī)移民與精英機(jī)制的遺傳算法用于解決聯(lián)盟形成問(wèn)題，該算法在相對(duì)簡(jiǎn)單的應(yīng)用場(chǎng)景中可以快速地求解出高質(zhì)量的次優(yōu)解。文獻(xiàn)[16]提出了一種具有多項(xiàng)式復(fù)雜度的分階次優(yōu)聯(lián)盟快速組建算法，有效的解決了多無(wú)人機(jī)協(xié)同打擊任務(wù)場(chǎng)景中的聯(lián)盟形成問(wèn)題?，F(xiàn)有的聯(lián)盟形成算法大多集中式地部署，其難以在線地處理較為復(fù)雜的聯(lián)盟形成問(wèn)題。

蒙特卡洛樹(shù)搜索在圍棋、游戲等博弈優(yōu)化及大規(guī)模決策問(wèn)題中發(fā)揮出色，特別是在圍棋領(lǐng)域超越專業(yè)選手的表現(xiàn)使其受到了極大的關(guān)注。本文提出基于蒙特卡洛樹(shù)搜索的分布式聯(lián)盟形成方法(Distributed coalition formation method based on Monte Carlo tree search, DCF-MCTS)，用于解決未知?jiǎng)討B(tài)環(huán)境下的異構(gòu)無(wú)人機(jī)集群的分布式聯(lián)盟形成問(wèn)題。異構(gòu)無(wú)人機(jī)集群在無(wú)先驗(yàn)信息的環(huán)境下作業(yè)，目標(biāo)/任務(wù)將動(dòng)態(tài)地出現(xiàn)在場(chǎng)景中。異構(gòu)無(wú)人機(jī)集群需要在地空、空空通信鏈路的支持下進(jìn)行分布式的任務(wù)協(xié)調(diào)，構(gòu)建滿足任務(wù)時(shí)間及資源限制的聯(lián)盟。本文的主要工作及創(chuàng)新之處如下：

1)設(shè)計(jì)了未知?jiǎng)討B(tài)環(huán)境下異構(gòu)無(wú)人機(jī)集群的聯(lián)盟任務(wù)處理自動(dòng)機(jī)，實(shí)現(xiàn)了異構(gòu)無(wú)人機(jī)集群在未知?jiǎng)討B(tài)環(huán)境下的自主行為控制及分布式的任務(wù)協(xié)調(diào)。

2)提出了基于蒙特卡洛樹(shù)搜索的分布式聯(lián)盟形成方法，算法可在分布式框架下實(shí)施，并在任意時(shí)間內(nèi)終止返回當(dāng)前的最優(yōu)解。

3)通過(guò)仿真校驗(yàn)了DCF-MCTS算法的有效性。并在不同工況下對(duì)DCF-MCTS算法、基于獨(dú)立聯(lián)盟合并的蒙特卡洛樹(shù)搜索算法(Monte Carlo tree search algorithm based on independent coalition merging, ICM-MCTS)以及CF-MS算法進(jìn)行了對(duì)比，說(shuō)明了DCF-MCTS算法在不同工況下的優(yōu)越性。

1 無(wú)人機(jī)集群聯(lián)盟形成問(wèn)題定義與建模

1.1 異構(gòu)無(wú)人機(jī)定義

任務(wù)場(chǎng)景中的異構(gòu)無(wú)人機(jī)集群由架裝載不同資源的無(wú)人機(jī)構(gòu)成，令={,,…,}表示異構(gòu)無(wú)人機(jī)集合。對(duì)于任意無(wú)人機(jī)∈，其資源向量表示為=[(1),(2),…,()]，()≥0，=1,2,…,，代表異構(gòu)無(wú)人機(jī)集群具備的資源類型數(shù)量。如果無(wú)人機(jī)未裝載第種資源，則()=0，否則()>0。代表無(wú)人機(jī)的探測(cè)半徑。

1.2 聯(lián)盟的定義

令表示一個(gè)異構(gòu)無(wú)人機(jī)聯(lián)盟，其為異構(gòu)無(wú)人機(jī)集合的非空子集。對(duì)于無(wú)人機(jī)∈，其在同一時(shí)間僅屬于一個(gè)聯(lián)盟，僅含一架無(wú)人機(jī)的聯(lián)盟被稱作獨(dú)立聯(lián)盟。=[(1),(2),…,()]表示與無(wú)人機(jī)聯(lián)盟關(guān)聯(lián)的資源向量，()≥0，=1,2,…,。考慮資源具有累加性，因此

()=∑∈()

(1)

1.3 任務(wù)與限制條件定義

目標(biāo)將動(dòng)態(tài)地出現(xiàn)在場(chǎng)景中的任意位置，假設(shè)無(wú)人機(jī)于時(shí)刻發(fā)現(xiàn)目標(biāo)并生成任務(wù)，Δ表示該任務(wù)的持續(xù)時(shí)間，則任務(wù)最晚于=+Δ時(shí)刻執(zhí)行。令=[(1),(2),…,()]代表任務(wù)的資源需求向量，其中()代表任務(wù)對(duì)于第種資源的需求值。對(duì)于任意無(wú)人機(jī)聯(lián)盟，除需滿足任務(wù)的持續(xù)時(shí)間限制外，還需滿足其資源限制：

()≥()，=1,2,…,

(2)

1.4 地空、空空通信鏈路下聯(lián)盟的組織形式

異構(gòu)無(wú)人機(jī)集群在地空/空空鏈路的支持下進(jìn)行作業(yè)。地空鏈路支持的最大分簇節(jié)點(diǎn)數(shù)為，其表示地面中心支持的最大通信節(jié)點(diǎn)數(shù)量?？湛真溌返拇貎?nèi)最大節(jié)點(diǎn)數(shù)為，其表示空空鏈路支持的最大通信節(jié)點(diǎn)數(shù)量，，分別表示地空/空空鏈路的最大通信距離。假設(shè)聯(lián)盟()在時(shí)刻處于搜索狀態(tài)，則對(duì)于任意的無(wú)人機(jī)∈()，其與聯(lián)盟中的另一架無(wú)人機(jī)∈()的距離必須小于，否則將從聯(lián)盟()中脫離。若聯(lián)盟()在時(shí)刻處于任務(wù)處理狀態(tài)，則該聯(lián)盟不必遵循此規(guī)則。若無(wú)人機(jī)∈()與另一聯(lián)盟中的無(wú)人機(jī)∈()之間的距離小于，則()被稱作()的直連聯(lián)盟，否則()被稱作聯(lián)盟()的非直連聯(lián)盟。聯(lián)盟()中至多只有一架無(wú)人機(jī)∈()擁有地空鏈路通信權(quán)限，若加入其它聯(lián)盟，則其將地空通信權(quán)限轉(zhuǎn)交至距其最近的無(wú)人機(jī)∈()。若地面中心的分簇節(jié)點(diǎn)數(shù)未達(dá)上限，地面中心會(huì)將地空通信權(quán)限下放給與其距離在內(nèi)，距其最近的無(wú)權(quán)限聯(lián)盟。

1.5 聯(lián)盟形成問(wèn)題建模

假設(shè)任務(wù)于時(shí)刻被發(fā)起，()表示參加此次聯(lián)盟組建的聯(lián)盟集合，其由無(wú)人機(jī)集群′?組成，聯(lián)盟結(jié)構(gòu)∏()={,,…,}表示此時(shí)′的劃分形式，∏表示其所有可能劃分形式的全集，則聯(lián)盟組建的目標(biāo)是找到′的最優(yōu)劃分形式∏∈∏，使其期望效用值：

(∏)=∑∈∏()

(3)

達(dá)到最大化。對(duì)于給定的任務(wù)，聯(lián)盟結(jié)構(gòu)的期望效用函數(shù)可以寫為

(∏，)=∑S∈∏(,)

(4)

因?yàn)閮H有最終執(zhí)行任務(wù)的聯(lián)盟∈∏可以從任務(wù)處獲取相應(yīng)的期望效用，因此(∏，)=(,)。對(duì)于給定的任務(wù)及聯(lián)盟，定義其期望效用函數(shù)如下

(5)

(6)

其中，,,與>0代表各項(xiàng)指標(biāo)的權(quán)重;為一個(gè)小量，用于確保第二項(xiàng)指標(biāo)的分母不為0;(,)為無(wú)人機(jī)抵達(dá)任務(wù)位置的最小航跡長(zhǎng)度;為標(biāo)準(zhǔn)化參數(shù)，一般取任務(wù)區(qū)域的邊長(zhǎng);為無(wú)人機(jī)的飛行速度。

(7)

(,)的第一項(xiàng)用于衡量聯(lián)盟對(duì)任務(wù)資源需求的滿足程度。第二項(xiàng)用于衡量聯(lián)盟的資源占用率，其值過(guò)高則代表聯(lián)盟占用了過(guò)多的資源。第三項(xiàng)用于衡量異構(gòu)無(wú)人機(jī)集群的飛行航跡長(zhǎng)度。第四項(xiàng)用于衡量聯(lián)盟中的無(wú)人機(jī)是否可在任務(wù)截止之前抵達(dá)。

2 聯(lián)盟的任務(wù)處理自動(dòng)機(jī)

聯(lián)盟通過(guò)任務(wù)自動(dòng)機(jī)進(jìn)行場(chǎng)景中任務(wù)的協(xié)調(diào)與處理，設(shè)計(jì)聯(lián)盟具有6種狀態(tài)，分別為：目標(biāo)搜索狀態(tài)、聯(lián)盟組建提議狀態(tài)、地空鏈路投標(biāo)狀態(tài)、空空鏈路投標(biāo)狀態(tài)、聯(lián)盟形成狀態(tài)與任務(wù)處理狀態(tài)。圖1展示了聯(lián)盟任務(wù)處理自動(dòng)機(jī)的具體形式，上述6種狀態(tài)間的轉(zhuǎn)移規(guī)則如下：

圖1 聯(lián)盟的任務(wù)處理自動(dòng)機(jī)Fig.1 Task automaton of a coalition

1)如果聯(lián)盟處于目標(biāo)搜索狀態(tài)，其聯(lián)盟成員將在場(chǎng)景中進(jìn)行隨機(jī)搜索。若無(wú)人機(jī)∈發(fā)現(xiàn)目標(biāo)并生成任務(wù)，則聯(lián)盟將判斷其是否滿足任務(wù)的資源及時(shí)間約束。如果滿足上述約束，則聯(lián)盟從目標(biāo)搜索狀態(tài)轉(zhuǎn)移至聯(lián)盟形成狀態(tài)。否則聯(lián)盟從目標(biāo)搜索狀態(tài)轉(zhuǎn)移至聯(lián)盟組建提議狀態(tài)。若多架無(wú)人機(jī)同時(shí)發(fā)現(xiàn)同一目標(biāo)，則距離目標(biāo)最近的無(wú)人機(jī)將作為本次聯(lián)盟組建提議的發(fā)起者。

2)如果聯(lián)盟收到其他聯(lián)盟通過(guò)地空/空空鏈路發(fā)來(lái)的聯(lián)盟組建提議，則從目標(biāo)搜索狀態(tài)轉(zhuǎn)至地空/空空鏈路聯(lián)盟組建投標(biāo)狀態(tài)，其將發(fā)布本聯(lián)盟的聯(lián)盟資源以及滿足任務(wù)截止時(shí)間的無(wú)人機(jī)的航跡距離。隨后將持續(xù)監(jiān)聽(tīng)地空/空空鏈路發(fā)布的聯(lián)盟組建結(jié)果消息，若組建聯(lián)盟成功，則轉(zhuǎn)至任務(wù)處理狀態(tài)，失敗則轉(zhuǎn)至目標(biāo)搜索狀態(tài)。

3)如果聯(lián)盟處于聯(lián)盟組建提議狀態(tài)，當(dāng)該聯(lián)盟收到其他聯(lián)盟∈(),≠的投標(biāo)反饋，則聯(lián)盟由聯(lián)盟組建提議狀態(tài)轉(zhuǎn)至聯(lián)盟形成狀態(tài)。若聯(lián)盟無(wú)法通過(guò)通信鏈路與地面或其他聯(lián)盟通信，則聯(lián)盟由聯(lián)盟組建提議狀態(tài)轉(zhuǎn)回目標(biāo)搜索狀態(tài)。

4)如果聯(lián)盟處于聯(lián)盟形成狀態(tài)，()表示參與任務(wù)聯(lián)盟組建過(guò)程的聯(lián)盟集合，則聯(lián)盟將通過(guò)基于蒙特卡洛樹(shù)的分布式聯(lián)盟形成方法生成()的最優(yōu)聯(lián)盟結(jié)構(gòu)。若在時(shí)間內(nèi)聯(lián)盟組建成功，則聯(lián)盟由聯(lián)盟形成狀態(tài)轉(zhuǎn)至任務(wù)處理狀態(tài)。否則，聯(lián)盟轉(zhuǎn)至目標(biāo)搜索狀態(tài)。

5)如果聯(lián)盟處于任務(wù)處理狀態(tài)，當(dāng)任務(wù)被完成，聯(lián)盟由任務(wù)處理狀態(tài)轉(zhuǎn)至目標(biāo)搜索狀態(tài)。

3 基本蒙特卡洛樹(shù)搜索算法

蒙特卡洛樹(shù)搜索是一種針對(duì)博弈優(yōu)化問(wèn)題的最優(yōu)決策方法，其通過(guò)增量非對(duì)稱的方式進(jìn)行搜索樹(shù)的構(gòu)建。圖2展示了基本蒙特卡洛樹(shù)搜索算法的運(yùn)行流程，其迭代過(guò)程包括四個(gè)環(huán)節(jié)：

圖2 蒙特卡洛樹(shù)搜索的運(yùn)行流程Fig.2 The running process of Monte Carlo tree search

1)選擇：以蒙特卡洛樹(shù)的根節(jié)點(diǎn)作為起點(diǎn)，遞歸地應(yīng)用節(jié)點(diǎn)選擇策略進(jìn)行子節(jié)點(diǎn)的選擇，直到達(dá)到可擴(kuò)展節(jié)點(diǎn)。可擴(kuò)展節(jié)點(diǎn)的定義為其非終端節(jié)點(diǎn)且尚有子節(jié)點(diǎn)未被擴(kuò)展。

2)擴(kuò)展：如果被選擇的節(jié)點(diǎn)不是終端節(jié)點(diǎn)，且其尚有子節(jié)點(diǎn)未被擴(kuò)展，則為其添加一個(gè)子節(jié)點(diǎn)。

3)模擬：對(duì)于新添加的子節(jié)點(diǎn)，該節(jié)點(diǎn)狀態(tài)的價(jià)值通過(guò)模擬進(jìn)行估計(jì)，模擬一般通過(guò)默認(rèn)的策略實(shí)施，模擬以新子節(jié)點(diǎn)作為起點(diǎn)，通過(guò)默認(rèn)策略不斷地進(jìn)行隨機(jī)選擇與擴(kuò)展，直到達(dá)到終端狀態(tài)。

4)反向傳播：新節(jié)點(diǎn)的估計(jì)價(jià)值將沿被選擇的節(jié)點(diǎn)反向傳播至根節(jié)點(diǎn)，更新此路徑上從新節(jié)點(diǎn)至根節(jié)點(diǎn)間所有節(jié)點(diǎn)的價(jià)值估計(jì)信息。

4 基于蒙特卡洛樹(shù)搜索的分布式聯(lián)盟形成算法

4.1 兩階段蒙特卡洛搜索樹(shù)結(jié)構(gòu)

DCF-MCTS算法包括兩個(gè)階段，第一階段是基于聯(lián)盟合并的樹(shù)搜索階段，其目標(biāo)是快速獲得滿足資源及時(shí)間限制的可行聯(lián)盟；第二階段是基于個(gè)體分割的樹(shù)搜索階段，其目標(biāo)是分割不必要的聯(lián)盟成員，實(shí)現(xiàn)聯(lián)盟結(jié)構(gòu)的進(jìn)一步優(yōu)化。在基于聯(lián)盟合并的蒙特卡洛樹(shù)搜索階段，樹(shù)的根節(jié)點(diǎn)={}，其中是發(fā)起聯(lián)盟組建提議的聯(lián)盟，此階段的蒙特卡洛樹(shù)通過(guò)聯(lián)盟合并操作進(jìn)行節(jié)點(diǎn)的擴(kuò)展。第一階段蒙特卡洛樹(shù)搜索的終止條件為運(yùn)行時(shí)間達(dá)到聯(lián)盟形成的最大允許時(shí)間Δ或有可行聯(lián)盟生成。圖3為基于聯(lián)盟合并的蒙特卡洛樹(shù)結(jié)構(gòu)示例，在該示例中發(fā)起聯(lián)盟組建提議的聯(lián)盟為，即={}，其子節(jié)點(diǎn),,,是節(jié)點(diǎn)通過(guò)聯(lián)盟合并操作后形成的。以為例，其是節(jié)點(diǎn)合并聯(lián)盟后形成的，即={}∪{}。同理的子節(jié)點(diǎn)是合并聯(lián)盟后形成的，即={,}∪{}。

圖3 基于聯(lián)盟合并的蒙特卡洛樹(shù)結(jié)構(gòu)Fig.3 Monte Carlo tree structure based on coalition merging operation

在基于個(gè)體分割的蒙特卡洛樹(shù)搜索階段，蒙特卡洛樹(shù)的根節(jié)點(diǎn)是可行聯(lián)盟的無(wú)人機(jī)集合，此階段的蒙特卡洛樹(shù)通過(guò)個(gè)體分割操作進(jìn)行節(jié)點(diǎn)的擴(kuò)展。例如節(jié)點(diǎn)′={,}是節(jié)點(diǎn)={,,}通過(guò)分割后形成的子節(jié)點(diǎn)。第二階段的終止條件為運(yùn)時(shí)間達(dá)到聯(lián)盟形成的時(shí)間上限Δ。

4.2 樹(shù)節(jié)點(diǎn)的選擇

(8)

其中，為常值系數(shù)。假設(shè)當(dāng)前節(jié)點(diǎn)為，()代表節(jié)點(diǎn)搜索可能的子節(jié)點(diǎn)，則被選擇的子節(jié)點(diǎn)為=argmax′∈()(′)。根據(jù)UCB公式可知，若常值系數(shù)=0，則算法總會(huì)選擇當(dāng)前期望效用值最大的節(jié)點(diǎn)，此時(shí)蒙特卡洛樹(shù)搜索相當(dāng)于深度優(yōu)先搜索算法。UCB啟發(fā)式公式第二項(xiàng)的意義在于提升被選擇過(guò)少節(jié)點(diǎn)的被選擇機(jī)會(huì)，當(dāng)一個(gè)節(jié)點(diǎn)被選擇的次數(shù)過(guò)少，那么該節(jié)點(diǎn)期望效用值的置信度很低，其不能反映該節(jié)點(diǎn)對(duì)應(yīng)聯(lián)盟結(jié)構(gòu)的實(shí)際效用。

4.3 樹(shù)節(jié)點(diǎn)的擴(kuò)展

如果樹(shù)節(jié)點(diǎn)∈()被選擇，且其所有可能的子節(jié)點(diǎn)()并未全部存在于搜索樹(shù)中，則為節(jié)點(diǎn)擴(kuò)展一個(gè)新的子節(jié)點(diǎn)′∈()。

4.4 DCF-MCTS算法的模擬策略

{,}→{,,}→{,,,}→

{,,,,}

(9)

{,,,}→{,,}→{,}

(10)

據(jù)此，節(jié)點(diǎn)′的期望效用值可以被初始化為

(11)

其中，(′)代表模擬過(guò)程中產(chǎn)生的模擬節(jié)點(diǎn)集合。序列化地執(zhí)行上述模擬過(guò)程，不斷地進(jìn)行期望效用值的評(píng)估將占用較大的計(jì)算資源，因此基于回退機(jī)制來(lái)加速這一過(guò)程，以基于聯(lián)盟合并的樹(shù)搜索為例，模擬過(guò)程的單次操作改為同時(shí)合并兩個(gè)聯(lián)盟，若轉(zhuǎn)移的新?tīng)顟B(tài)使得模擬進(jìn)程終止，則移除其中一個(gè)聯(lián)盟。

4.5 反向傳播

(12)

其中，+1為節(jié)點(diǎn)在反向傳播路徑中的子節(jié)點(diǎn)。

4.6 基于根節(jié)點(diǎn)并行化的分布式實(shí)施

基于根節(jié)點(diǎn)的并行化方法是將根節(jié)點(diǎn)的子一級(jí)節(jié)點(diǎn)作為新的根節(jié)點(diǎn)對(duì)樹(shù)結(jié)構(gòu)進(jìn)行拆分，并將拆分后的子樹(shù)分配至()中的無(wú)人機(jī)進(jìn)行分布式的計(jì)算。令表示()中無(wú)人機(jī)的數(shù)量，表示根據(jù)子一級(jí)節(jié)點(diǎn)拆分后的子樹(shù)數(shù)量。若<，則為每架無(wú)人機(jī)分配[]個(gè)子樹(shù)，剩余子樹(shù)進(jìn)行隨機(jī)分配。若≥，則對(duì)部分子樹(shù)以子二級(jí)節(jié)點(diǎn)作為新的根節(jié)點(diǎn)進(jìn)行進(jìn)一步拆分。根節(jié)點(diǎn)拆分及最終聯(lián)盟結(jié)構(gòu)的確定由發(fā)起聯(lián)盟組建提議的無(wú)人機(jī)實(shí)施。

5 仿真校驗(yàn)

本節(jié)將通過(guò)仿真實(shí)驗(yàn)對(duì)提出的DCF-MCTS算法進(jìn)行有效性以及性能測(cè)試：1)通過(guò)仿真示例場(chǎng)景驗(yàn)證提出的DCF-MCTS算法的有效性，2)對(duì)比分析DCF-MCTS算法、ICM-MCTS算法以及CF-MS算法在不同仿真條件下的表現(xiàn)。

5.1 仿真示例場(chǎng)景與結(jié)果分析

為了校驗(yàn)提出的DCF-MCTS算法有效性，設(shè)計(jì)一個(gè)包含1個(gè)地面控制中心、15架異構(gòu)無(wú)人機(jī)的仿真示例場(chǎng)景，任務(wù)區(qū)域?yàn)?0 km×10 km的矩形區(qū)域。地空通信鏈路的最大分簇節(jié)點(diǎn)數(shù)為8，最大通信距離為8 km?？湛胀ㄐ沛溌返淖畲蟠貎?nèi)節(jié)點(diǎn)數(shù)為5，最大通信距離為3 km。無(wú)人機(jī)飛行速度為50 m/s、最小轉(zhuǎn)彎半徑為200 m、探測(cè)半徑為1250 m。異構(gòu)無(wú)人機(jī)集群的資源配置見(jiàn)表1。

表1 異構(gòu)無(wú)人機(jī)集群資源配置Table 1 Heterogeneous UAV swarm resource allocation

異構(gòu)無(wú)人機(jī)被分為5種類型，其中無(wú)人機(jī)～、～、～、～、～被設(shè)定為1～5型。場(chǎng)景時(shí)間跨度為320 s，目標(biāo)將在隨機(jī)時(shí)刻出現(xiàn)任意位置，其需求的資源為=[15, 22, 20, 20, 16]，設(shè)定目標(biāo)持續(xù)時(shí)間為80s。期望效用函數(shù)權(quán)重=1/3、=1/6、=1/6、=1/3。UCB參數(shù)=20、=30。聯(lián)盟形成時(shí)間上限設(shè)為5 s。

異構(gòu)無(wú)人機(jī)集群于29.8 s時(shí)的聯(lián)盟結(jié)構(gòu)如圖4所示，聯(lián)盟的成員發(fā)現(xiàn)于29.8 s出現(xiàn)在場(chǎng)景的，聯(lián)盟的成員包括無(wú)人機(jī)與，此時(shí)聯(lián)盟裝載的資源為=[8, 11, 9, 7, 5]，而任務(wù)的資源需求為=[15, 22, 20, 20, 16]，聯(lián)盟不滿足的資源需求。聯(lián)盟隨即通過(guò)地空/空空鏈路向其直連聯(lián)盟,,與非直連聯(lián)盟,,發(fā)布聯(lián)盟組建提議。

圖4 無(wú)人機(jī)集群29.8 s時(shí)的聯(lián)盟劃分Fig.4 The coalition partition of UAV swarm at 29.8 s

圖5展示了聯(lián)盟組建結(jié)果，新聯(lián)盟通過(guò)聯(lián)盟,合并后分割無(wú)人機(jī),形成，新聯(lián)盟的資源為=[17, 22, 22, 22, 17]，其滿足的資源需求。圖6展示了異構(gòu)無(wú)人機(jī)集群在29.8～83.1 s間的軌跡，新聯(lián)盟中的成員于83.1 s已全部抵達(dá)位置。因此，新組建的聯(lián)盟同時(shí)滿足了任務(wù)的資源以及時(shí)間限制。通過(guò)上述仿真結(jié)果可知，異構(gòu)無(wú)人機(jī)集群可在未知?jiǎng)討B(tài)環(huán)境下自主地進(jìn)行分布式的任務(wù)協(xié)調(diào)，提出的算法可以有效地組建滿足目標(biāo)資源及時(shí)間限制的聯(lián)盟。

圖5 任務(wù)T1的聯(lián)盟組建結(jié)果Fig.5 The coalition formation results of task T1

圖6 無(wú)人機(jī)集群29.8～83.1 s的飛行軌跡Fig.6 Flight trajectory of UAV swarm during 29.8～83.1 s

5.2 不同仿真場(chǎng)景下算法的性能對(duì)比測(cè)試

為了全面地測(cè)試DCF-MCTS算法的性能表現(xiàn)，設(shè)置了6組具有不同特征的仿真測(cè)試集，6組仿真測(cè)試集的主要參數(shù)設(shè)置見(jiàn)表2，場(chǎng)景中存在5類資源，無(wú)人機(jī)及任務(wù)的各類資源配置/需求按照表2中的資源配置/需求范圍進(jìn)行隨機(jī)生成。其他參數(shù)與示例場(chǎng)景保持一致。ICM-MCTS算法的根節(jié)點(diǎn)為發(fā)起聯(lián)盟組建提議的無(wú)人機(jī)，其通過(guò)個(gè)體合并操作進(jìn)行樹(shù)結(jié)構(gòu)的擴(kuò)展與模擬，其UCB參數(shù)與DCF-MCTS算法的第一階段保持一致。三種算法分別在各測(cè)試用例中運(yùn)行150次。

表2 仿真測(cè)試集主要參數(shù)設(shè)置Table 2 Main parameter settings of simulation test set

..不同無(wú)人機(jī)集群規(guī)模下的算法性能對(duì)比分析

通過(guò)仿真測(cè)試用例1～3對(duì)比不同無(wú)人機(jī)集群規(guī)模下DCF-MCTS、ICM-MCTS和CF-MS算法的性能差異。圖7展示了不同無(wú)人機(jī)集群規(guī)模下三種算法的平均任務(wù)完成率對(duì)比結(jié)果。圖8展示了不同無(wú)人機(jī)集群規(guī)模下三種算法的平均聯(lián)盟期望效用值對(duì)比結(jié)果。

圖7 DCF-MCTS、ICM-MCTS及CF-MS算法在測(cè)試用例1～3 中的平均任務(wù)完成率對(duì)比結(jié)果Fig.7 Comparison results of average task completion rate of DCF-MCTS, ICM-MCTS and CF-MS algorithms in test cases 1～3

圖8 DCF-MCTS、ICM-MCTS及CF-MS算法在測(cè)試用例1～3 中的平均聯(lián)盟期望效用值對(duì)比結(jié)果Fig.8 Comparison results of average coalition expected utility values of DCF-MCTS, ICM-MCTS and CF-MS algorithms in test cases 1～3

從對(duì)比結(jié)果中可知，提出的DCF-MCTS算法隨著集群規(guī)模的增長(zhǎng)，其平均任務(wù)完成率的中位數(shù)始終保持上升趨勢(shì)，而其他兩種算法在測(cè)試用例3中的平均任務(wù)完成率的中位數(shù)要低于其在測(cè)試用例2中的表現(xiàn)，說(shuō)明隨著集群規(guī)模的增長(zhǎng)，ICM-MCTS、CF-MS算法的聯(lián)盟形成能力呈下降趨勢(shì)，這是由于集群規(guī)模的增長(zhǎng)導(dǎo)致決策空間的規(guī)模變大，ICM-MCTS、CF-MS算法本質(zhì)上是集中式方法難以應(yīng)對(duì)較大的集群規(guī)模。在測(cè)試用例1～3中，DCF-MCTS算法的平均任務(wù)完成率明顯高于其他兩種算法。以測(cè)試用例1為例，DCF-MCTS算法的平均任務(wù)完成率中位數(shù)約為67%，而ICM-MCTS及CF-MS算法的平均任務(wù)完成率中位數(shù)約為48%及56%。這說(shuō)明DCF-MCTS算法可以明顯地提升異構(gòu)無(wú)人機(jī)集群的任務(wù)響應(yīng)能力。

..不同目標(biāo)出現(xiàn)頻率下的算法性能對(duì)比分析

通過(guò)仿真測(cè)試用例4～6對(duì)比不同目標(biāo)出現(xiàn)頻率下DCF-MCTS、ICM-MCTS和CF-MS算法的性能差異。圖9展示了不同目標(biāo)出現(xiàn)頻率下三種算法的平均任務(wù)完成率對(duì)比結(jié)果。圖10展示了不同目標(biāo)出現(xiàn)頻率下三種算法的平均聯(lián)盟期望效用值對(duì)比結(jié)果。

圖9 DCF-MCTS、ICM-MCTS及CF-MS算法在測(cè)試用例4～6中的平均任務(wù)完成率對(duì)比結(jié)果Fig.9 Comparison results of average task completion rate of DCF-MCTS, ICM-MCTS and CF-MS algorithms in test cases 4～6

圖10 DCF-MCTS、ICM-MCTS及CF-MS算法在測(cè)試用例4～6中的平均聯(lián)盟期望效用值對(duì)比結(jié)果Fig.10 Comparison results of average coalition expected utility values of DCF-MCTS, ICM-MCTS and CF-MS algorithms in test cases 4～6

從對(duì)比結(jié)果中可知，隨著目標(biāo)出現(xiàn)頻率的增長(zhǎng)三種算法的平均任務(wù)完成率均呈下降趨勢(shì)，這是由于目標(biāo)出現(xiàn)頻率的增加使得無(wú)人機(jī)平臺(tái)及相應(yīng)的資源被持續(xù)占用，導(dǎo)致可行聯(lián)盟的形成概率降低，但DCF-MCTS算法的平均任務(wù)完成率仍明顯高于其他兩種算法。說(shuō)明通過(guò)DCF-MCTS算法形成的聯(lián)盟對(duì)異構(gòu)無(wú)人機(jī)平臺(tái)及資源的占用率較低,可以在最大允許時(shí)間內(nèi)獲得更高質(zhì)量的聯(lián)盟結(jié)構(gòu)。從平均聯(lián)盟期望效用值角度分析，ICM-MCTS算法的平均聯(lián)盟期望效用值最高，然而其平均任務(wù)完成率是最低的，說(shuō)明其難以在最大允許時(shí)間內(nèi)給出合理的聯(lián)盟結(jié)構(gòu)。

6 結(jié) 論

本文針對(duì)異構(gòu)無(wú)人機(jī)集群在未知、動(dòng)態(tài)環(huán)境下自主作業(yè)時(shí)的分布式聯(lián)盟形成問(wèn)題，構(gòu)建了無(wú)人機(jī)聯(lián)盟任務(wù)自動(dòng)機(jī)，實(shí)現(xiàn)了異構(gòu)無(wú)人機(jī)集群對(duì)任務(wù)的自主響應(yīng)及分布式協(xié)調(diào)。考慮蒙特卡洛樹(shù)搜索在大型決策優(yōu)化領(lǐng)域的出色表現(xiàn)，提出了一種基于蒙特卡洛樹(shù)搜索的分布式聯(lián)盟形成算法，算法具有可在任意時(shí)間終止、可分布式并行實(shí)施的特點(diǎn)，通過(guò)仿真說(shuō)明了提出的DCF-MCTS算法可以有效應(yīng)對(duì)大規(guī)模集群、高任務(wù)頻率的任務(wù)場(chǎng)景，并且可以在有限時(shí)間內(nèi)組建無(wú)人機(jī)平臺(tái)、資源占用率較低的聯(lián)盟。