一種未知動態(tài)環(huán)境下異構(gòu)無人機集群分布式聯(lián)盟形成方法

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

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

0 引 言

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

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

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

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

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

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

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

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

1.1 異構(gòu)無人機定義

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

1.2 聯(lián)盟的定義

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

()=∑∈()

(1)

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

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

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

(2)

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

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

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

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

(∏)=∑∈∏()

(3)

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

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

(4)

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

(5)

(6)

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

(7)

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

2 聯(lián)盟的任務(wù)處理自動機

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

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

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

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

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

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

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

3 基本蒙特卡洛樹搜索算法

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

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

1)選擇：以蒙特卡洛樹的根節(jié)點作為起點，遞歸地應(yīng)用節(jié)點選擇策略進行子節(jié)點的選擇，直到達到可擴展節(jié)點?？蓴U展節(jié)點的定義為其非終端節(jié)點且尚有子節(jié)點未被擴展。

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

3)模擬：對于新添加的子節(jié)點，該節(jié)點狀態(tài)的價值通過模擬進行估計，模擬一般通過默認的策略實施，模擬以新子節(jié)點作為起點，通過默認策略不斷地進行隨機選擇與擴展，直到達到終端狀態(tài)。

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

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

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

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

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

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

4.2 樹節(jié)點的選擇

(8)

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

4.3 樹節(jié)點的擴展

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

4.4 DCF-MCTS算法的模擬策略

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

{,,,,}

(9)

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

(10)

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

(11)

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

4.5 反向傳播

(12)

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

4.6 基于根節(jié)點并行化的分布式實施

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

5 仿真校驗

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

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

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

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

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

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

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

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

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

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

5.2 不同仿真場景下算法的性能對比測試

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

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

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

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

圖7 DCF-MCTS、ICM-MCTS及CF-MS算法在測試用例1～3 中的平均任務(wù)完成率對比結(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算法在測試用例1～3 中的平均聯(lián)盟期望效用值對比結(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

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

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

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

圖9 DCF-MCTS、ICM-MCTS及CF-MS算法在測試用例4～6中的平均任務(wù)完成率對比結(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算法在測試用例4～6中的平均聯(lián)盟期望效用值對比結(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

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

6 結(jié) 論

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