一种未知动态环境下异构无人机集群分布式联盟形成方法

郑红星，郭继峰，谢旭东，颜 鹏

(哈尔滨工业大学航天学院，哈尔滨 150001)

0 引 言

异构无人机集群自主作业可以有效地提升集群的任务执行效率及环境适应性。异构无人机集群进行自主协作的关键在于高效的任务分配机制。树搜索、遗传算法、多目标进化等集中式任务分配方法，已经被应用于许多具有现实意义的任务场景中。然而，集中式方法通常难以在线应用，且不容易被扩展到存在大量任务/无人机的复杂场景中。

机载通信、计算及感知设备的能力提升，使无人机可以被视为具有决策能力的智能系统，这促使分布式任务分配问题及其求解方法得到了广泛的关注。文献[10]针对威胁环境下的多无人机分布式协同决策问题，提出了一种基于多智能体深度确定性策略梯度的多机决策算法，该算法具有较高的收敛速度与学习效率。文献[11]提出了一种多耦合任务智能决策方法，有效地解决了无人机集群的协同目标分配和突防轨迹规划问题。文献[12]通过基于共识的捆绑算法，有效地解决了存在局部通信条件下的异构多智能体任务分配问题。文献[13]提出了分布式匈牙利算法，该算法在全局通信条件下，可以获得任务分配问题的最优解。上述方法基于分布式的框架有效地处理了多类任务分配问题，但问题中大多不考虑单任务的多机协同作业，其难以用于联盟形成问题的处理。

联盟形成属于一类特殊的任务分配问题，任务通常具有复杂的资源、动作等约束，需要多架无人机组成联盟进行协同作业。文献[14]提出基于分割与合并的联盟形成算法(Coalition formation algorithm based on merge and split，CF-MS)，有效地解决了动态场景下的机器人协作联盟形成问题，但该算法对于较大规模联盟形成问题的处理能力有限。文献[15]提出基于随机移民与精英机制的遗传算法用于解决联盟形成问题，该算法在相对简单的应用场景中可以快速地求解出高质量的次优解。文献[16]提出了一种具有多项式复杂度的分阶次优联盟快速组建算法，有效的解决了多无人机协同打击任务场景中的联盟形成问题。现有的联盟形成算法大多集中式地部署，其难以在线地处理较为复杂的联盟形成问题。

蒙特卡洛树搜索在围棋、游戏等博弈优化及大规模决策问题中发挥出色，特别是在围棋领域超越专业选手的表现使其受到了极大的关注。本文提出基于蒙特卡洛树搜索的分布式联盟形成方法(Distributed coalition formation method based on Monte Carlo tree search, DCF-MCTS)，用于解决未知动态环境下的异构无人机集群的分布式联盟形成问题。异构无人机集群在无先验信息的环境下作业，目标/任务将动态地出现在场景中。异构无人机集群需要在地空、空空通信链路的支持下进行分布式的任务协调，构建满足任务时间及资源限制的联盟。本文的主要工作及创新之处如下：

1)设计了未知动态环境下异构无人机集群的联盟任务处理自动机，实现了异构无人机集群在未知动态环境下的自主行为控制及分布式的任务协调。

2)提出了基于蒙特卡洛树搜索的分布式联盟形成方法，算法可在分布式框架下实施，并在任意时间内终止返回当前的最优解。

3)通过仿真校验了DCF-MCTS算法的有效性。并在不同工况下对DCF-MCTS算法、基于独立联盟合并的蒙特卡洛树搜索算法(Monte Carlo tree search algorithm based on independent coalition merging, ICM-MCTS)以及CF-MS算法进行了对比，说明了DCF-MCTS算法在不同工况下的优越性。

1 无人机集群联盟形成问题定义与建模

1.1 异构无人机定义

任务场景中的异构无人机集群由架装载不同资源的无人机构成，令={,,…,}表示异构无人机集合。对于任意无人机∈，其资源向量表示为=[(1),(2),…,()]，()≥0，=1,2,…,，代表异构无人机集群具备的资源类型数量。如果无人机未装载第种资源，则()=0，否则()>0。代表无人机的探测半径。

1.2 联盟的定义

令表示一个异构无人机联盟，其为异构无人机集合的非空子集。对于无人机∈，其在同一时间仅属于一个联盟，仅含一架无人机的联盟被称作独立联盟。=[(1),(2),…,()]表示与无人机联盟关联的资源向量，()≥0，=1,2,…,。考虑资源具有累加性，因此

()=∑∈()

(1)

1.3 任务与限制条件定义

目标将动态地出现在场景中的任意位置，假设无人机于时刻发现目标并生成任务，Δ表示该任务的持续时间，则任务最晚于=+Δ时刻执行。令=[(1),(2),…,()]代表任务的资源需求向量，其中()代表任务对于第种资源的需求值。对于任意无人机联盟，除需满足任务的持续时间限制外，还需满足其资源限制：

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

(2)

1.4 地空、空空通信链路下联盟的组织形式

异构无人机集群在地空/空空链路的支持下进行作业。地空链路支持的最大分簇节点数为，其表示地面中心支持的最大通信节点数量。空空链路的簇内最大节点数为，其表示空空链路支持的最大通信节点数量，，分别表示地空/空空链路的最大通信距离。假设联盟()在时刻处于搜索状态，则对于任意的无人机∈()，其与联盟中的另一架无人机∈()的距离必须小于，否则将从联盟()中脱离。若联盟()在时刻处于任务处理状态，则该联盟不必遵循此规则。若无人机∈()与另一联盟中的无人机∈()之间的距离小于，则()被称作()的直连联盟，否则()被称作联盟()的非直连联盟。联盟()中至多只有一架无人机∈()拥有地空链路通信权限，若加入其它联盟，则其将地空通信权限转交至距其最近的无人机∈()。若地面中心的分簇节点数未达上限，地面中心会将地空通信权限下放给与其距离在内，距其最近的无权限联盟。

1.5 联盟形成问题建模

假设任务于时刻被发起，()表示参加此次联盟组建的联盟集合，其由无人机集群′⊆组成，联盟结构∏()={,,…,}表示此时′的划分形式，∏表示其所有可能划分形式的全集，则联盟组建的目标是找到′的最优划分形式∏∈∏，使其期望效用值：

(∏)=∑∈∏()

(3)

达到最大化。对于给定的任务，联盟结构的期望效用函数可以写为

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

(4)

因为仅有最终执行任务的联盟∈∏可以从任务处获取相应的期望效用，因此(∏，)=(,)。对于给定的任务及联盟，定义其期望效用函数如下

(5)

(6)

其中，,,与>0代表各项指标的权重;为一个小量，用于确保第二项指标的分母不为0;(,)为无人机抵达任务位置的最小航迹长度;为标准化参数，一般取任务区域的边长;为无人机的飞行速度。

(7)

(,)的第一项用于衡量联盟对任务资源需求的满足程度。第二项用于衡量联盟的资源占用率，其值过高则代表联盟占用了过多的资源。第三项用于衡量异构无人机集群的飞行航迹长度。第四项用于衡量联盟中的无人机是否可在任务截止之前抵达。

2 联盟的任务处理自动机

联盟通过任务自动机进行场景中任务的协调与处理，设计联盟具有6种状态，分别为：目标搜索状态、联盟组建提议状态、地空链路投标状态、空空链路投标状态、联盟形成状态与任务处理状态。图1展示了联盟任务处理自动机的具体形式，上述6种状态间的转移规则如下：

图1 联盟的任务处理自动机Fig.1 Task automaton of a coalition

1)如果联盟处于目标搜索状态，其联盟成员将在场景中进行随机搜索。若无人机∈发现目标并生成任务，则联盟将判断其是否满足任务的资源及时间约束。如果满足上述约束，则联盟从目标搜索状态转移至联盟形成状态。否则联盟从目标搜索状态转移至联盟组建提议状态。若多架无人机同时发现同一目标，则距离目标最近的无人机将作为本次联盟组建提议的发起者。

2)如果联盟收到其他联盟通过地空/空空链路发来的联盟组建提议，则从目标搜索状态转至地空/空空链路联盟组建投标状态，其将发布本联盟的联盟资源以及满足任务截止时间的无人机的航迹距离。随后将持续监听地空/空空链路发布的联盟组建结果消息，若组建联盟成功，则转至任务处理状态，失败则转至目标搜索状态。

3)如果联盟处于联盟组建提议状态，当该联盟收到其他联盟∈(),≠的投标反馈，则联盟由联盟组建提议状态转至联盟形成状态。若联盟无法通过通信链路与地面或其他联盟通信，则联盟由联盟组建提议状态转回目标搜索状态。

4)如果联盟处于联盟形成状态，()表示参与任务联盟组建过程的联盟集合，则联盟将通过基于蒙特卡洛树的分布式联盟形成方法生成()的最优联盟结构。若在时间内联盟组建成功，则联盟由联盟形成状态转至任务处理状态。否则，联盟转至目标搜索状态。

5)如果联盟处于任务处理状态，当任务被完成，联盟由任务处理状态转至目标搜索状态。

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

蒙特卡洛树搜索是一种针对博弈优化问题的最优决策方法，其通过增量非对称的方式进行搜索树的构建。图2展示了基本蒙特卡洛树搜索算法的运行流程，其迭代过程包括四个环节：

图2 蒙特卡洛树搜索的运行流程Fig.2 The running process of Monte Carlo tree search

1)选择：以蒙特卡洛树的根节点作为起点，递归地应用节点选择策略进行子节点的选择，直到达到可扩展节点。可扩展节点的定义为其非终端节点且尚有子节点未被扩展。

2)扩展：如果被选择的节点不是终端节点，且其尚有子节点未被扩展，则为其添加一个子节点。

3)模拟：对于新添加的子节点，该节点状态的价值通过模拟进行估计，模拟一般通过默认的策略实施，模拟以新子节点作为起点，通过默认策略不断地进行随机选择与扩展，直到达到终端状态。

4)反向传播：新节点的估计价值将沿被选择的节点反向传播至根节点，更新此路径上从新节点至根节点间所有节点的价值估计信息。

4 基于蒙特卡洛树搜索的分布式联盟形成算法

4.1 两阶段蒙特卡洛搜索树结构

DCF-MCTS算法包括两个阶段，第一阶段是基于联盟合并的树搜索阶段，其目标是快速获得满足资源及时间限制的可行联盟；第二阶段是基于个体分割的树搜索阶段，其目标是分割不必要的联盟成员，实现联盟结构的进一步优化。在基于联盟合并的蒙特卡洛树搜索阶段，树的根节点={}，其中是发起联盟组建提议的联盟，此阶段的蒙特卡洛树通过联盟合并操作进行节点的扩展。第一阶段蒙特卡洛树搜索的终止条件为运行时间达到联盟形成的最大允许时间Δ或有可行联盟生成。图3为基于联盟合并的蒙特卡洛树结构示例，在该示例中发起联盟组建提议的联盟为，即={}，其子节点,,,是节点通过联盟合并操作后形成的。以为例，其是节点合并联盟后形成的，即={}∪{}。同理的子节点是合并联盟后形成的，即={,}∪{}。

图3 基于联盟合并的蒙特卡洛树结构Fig.3 Monte Carlo tree structure based on coalition merging operation

在基于个体分割的蒙特卡洛树搜索阶段，蒙特卡洛树的根节点是可行联盟的无人机集合，此阶段的蒙特卡洛树通过个体分割操作进行节点的扩展。例如节点′={,}是节点={,,}通过分割后形成的子节点。第二阶段的终止条件为运时间达到联盟形成的时间上限Δ。

4.2 树节点的选择

(8)

其中，为常值系数。假设当前节点为，()代表节点搜索可能的子节点，则被选择的子节点为=argmax′∈()(′)。根据UCB公式可知，若常值系数=0，则算法总会选择当前期望效用值最大的节点，此时蒙特卡洛树搜索相当于深度优先搜索算法。UCB启发式公式第二项的意义在于提升被选择过少节点的被选择机会，当一个节点被选择的次数过少，那么该节点期望效用值的置信度很低，其不能反映该节点对应联盟结构的实际效用。

4.3 树节点的扩展

如果树节点∈()被选择，且其所有可能的子节点()并未全部存在于搜索树中，则为节点扩展一个新的子节点′∈()。

4.4 DCF-MCTS算法的模拟策略

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

{,,,,}

(9)

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

(10)

据此，节点′的期望效用值可以被初始化为

(11)

其中，(′)代表模拟过程中产生的模拟节点集合。序列化地执行上述模拟过程，不断地进行期望效用值的评估将占用较大的计算资源，因此基于回退机制来加速这一过程，以基于联盟合并的树搜索为例，模拟过程的单次操作改为同时合并两个联盟，若转移的新状态使得模拟进程终止，则移除其中一个联盟。

4.5 反向传播

(12)

其中，+1为节点在反向传播路径中的子节点。

4.6 基于根节点并行化的分布式实施

基于根节点的并行化方法是将根节点的子一级节点作为新的根节点对树结构进行拆分，并将拆分后的子树分配至()中的无人机进行分布式的计算。令表示()中无人机的数量，表示根据子一级节点拆分后的子树数量。若<，则为每架无人机分配[]个子树，剩余子树进行随机分配。若≥，则对部分子树以子二级节点作为新的根节点进行进一步拆分。根节点拆分及最终联盟结构的确定由发起联盟组建提议的无人机实施。

5 仿真校验

本节将通过仿真实验对提出的DCF-MCTS算法进行有效性以及性能测试：1)通过仿真示例场景验证提出的DCF-MCTS算法的有效性，2)对比分析DCF-MCTS算法、ICM-MCTS算法以及CF-MS算法在不同仿真条件下的表现。

5.1 仿真示例场景与结果分析

为了校验提出的DCF-MCTS算法有效性，设计一个包含1个地面控制中心、15架异构无人机的仿真示例场景，任务区域为10 km×10 km的矩形区域。地空通信链路的最大分簇节点数为8，最大通信距离为8 km。空空通信链路的最大簇内节点数为5，最大通信距离为3 km。无人机飞行速度为50 m/s、最小转弯半径为200 m、探测半径为1250 m。异构无人机集群的资源配置见表1。

表1 异构无人机集群资源配置Table 1 Heterogeneous UAV swarm resource allocation

异构无人机被分为5种类型，其中无人机～、～、～、～、～被设定为1～5型。场景时间跨度为320 s，目标将在随机时刻出现任意位置，其需求的资源为=[15, 22, 20, 20, 16]，设定目标持续时间为80s。期望效用函数权重=1/3、=1/6、=1/6、=1/3。UCB参数=20、=30。联盟形成时间上限设为5 s。

异构无人机集群于29.8 s时的联盟结构如图4所示，联盟的成员发现于29.8 s出现在场景的，联盟的成员包括无人机与，此时联盟装载的资源为=[8, 11, 9, 7, 5]，而任务的资源需求为=[15, 22, 20, 20, 16]，联盟不满足的资源需求。联盟随即通过地空/空空链路向其直连联盟,,与非直连联盟,,发布联盟组建提议。

图4 无人机集群29.8 s时的联盟划分Fig.4 The coalition partition of UAV swarm at 29.8 s

图5展示了联盟组建结果，新联盟通过联盟,合并后分割无人机,形成，新联盟的资源为=[17, 22, 22, 22, 17]，其满足的资源需求。图6展示了异构无人机集群在29.8～83.1 s间的轨迹，新联盟中的成员于83.1 s已全部抵达位置。因此，新组建的联盟同时满足了任务的资源以及时间限制。通过上述仿真结果可知，异构无人机集群可在未知动态环境下自主地进行分布式的任务协调，提出的算法可以有效地组建满足目标资源及时间限制的联盟。

图5 任务T1的联盟组建结果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算法的性能表现，设置了6组具有不同特征的仿真测试集，6组仿真测试集的主要参数设置见表2，场景中存在5类资源，无人机及任务的各类资源配置/需求按照表2中的资源配置/需求范围进行随机生成。其他参数与示例场景保持一致。ICM-MCTS算法的根节点为发起联盟组建提议的无人机，其通过个体合并操作进行树结构的扩展与模拟，其UCB参数与DCF-MCTS算法的第一阶段保持一致。三种算法分别在各测试用例中运行150次。

表2 仿真测试集主要参数设置Table 2 Main parameter settings of simulation test set

..不同无人机集群规模下的算法性能对比分析

通过仿真测试用例1～3对比不同无人机集群规模下DCF-MCTS、ICM-MCTS和CF-MS算法的性能差异。图7展示了不同无人机集群规模下三种算法的平均任务完成率对比结果。图8展示了不同无人机集群规模下三种算法的平均联盟期望效用值对比结果。

图7 DCF-MCTS、ICM-MCTS及CF-MS算法在测试用例1～3 中的平均任务完成率对比结果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 中的平均联盟期望效用值对比结果Fig.8 Comparison results of average coalition expected utility values of DCF-MCTS, ICM-MCTS and CF-MS algorithms in test cases 1～3

从对比结果中可知，提出的DCF-MCTS算法随着集群规模的增长，其平均任务完成率的中位数始终保持上升趋势，而其他两种算法在测试用例3中的平均任务完成率的中位数要低于其在测试用例2中的表现，说明随着集群规模的增长，ICM-MCTS、CF-MS算法的联盟形成能力呈下降趋势，这是由于集群规模的增长导致决策空间的规模变大，ICM-MCTS、CF-MS算法本质上是集中式方法难以应对较大的集群规模。在测试用例1～3中，DCF-MCTS算法的平均任务完成率明显高于其他两种算法。以测试用例1为例，DCF-MCTS算法的平均任务完成率中位数约为67%，而ICM-MCTS及CF-MS算法的平均任务完成率中位数约为48%及56%。这说明DCF-MCTS算法可以明显地提升异构无人机集群的任务响应能力。

..不同目标出现频率下的算法性能对比分析

通过仿真测试用例4～6对比不同目标出现频率下DCF-MCTS、ICM-MCTS和CF-MS算法的性能差异。图9展示了不同目标出现频率下三种算法的平均任务完成率对比结果。图10展示了不同目标出现频率下三种算法的平均联盟期望效用值对比结果。

图9 DCF-MCTS、ICM-MCTS及CF-MS算法在测试用例4～6中的平均任务完成率对比结果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中的平均联盟期望效用值对比结果Fig.10 Comparison results of average coalition expected utility values of DCF-MCTS, ICM-MCTS and CF-MS algorithms in test cases 4～6

从对比结果中可知，随着目标出现频率的增长三种算法的平均任务完成率均呈下降趋势，这是由于目标出现频率的增加使得无人机平台及相应的资源被持续占用，导致可行联盟的形成概率降低，但DCF-MCTS算法的平均任务完成率仍明显高于其他两种算法。说明通过DCF-MCTS算法形成的联盟对异构无人机平台及资源的占用率较低,可以在最大允许时间内获得更高质量的联盟结构。从平均联盟期望效用值角度分析，ICM-MCTS算法的平均联盟期望效用值最高，然而其平均任务完成率是最低的，说明其难以在最大允许时间内给出合理的联盟结构。

6 结 论

本文针对异构无人机集群在未知、动态环境下自主作业时的分布式联盟形成问题，构建了无人机联盟任务自动机，实现了异构无人机集群对任务的自主响应及分布式协调。考虑蒙特卡洛树搜索在大型决策优化领域的出色表现，提出了一种基于蒙特卡洛树搜索的分布式联盟形成算法，算法具有可在任意时间终止、可分布式并行实施的特点，通过仿真说明了提出的DCF-MCTS算法可以有效应对大规模集群、高任务频率的任务场景，并且可以在有限时间内组建无人机平台、资源占用率较低的联盟。