基于聚类分组的异构多机器人任务分配算法研究
作者： 郑习羽 徐梓毓 王京华
摘 要：在城市作战环境中，具有时间窗约束的大规模任务目标需要调度多个空地异构机器人处理，为了保证战略执行的快速有效，需要快速计算出可接受的次优任务分配策略。本文提出了一种基于聚类分组的一致性的束算法（C-CBBA），该分布式算法用于具有时间窗约束的大规模任务分配问题中。算法首先对任务目标点和机器人进行分组，将大规模问题转化为小规模问题，其中分组算法包括三个阶段：（1）利用K-means算法按照距离最近原则对任务点进行初步分类;（2）将每个组的任务点组别进行调整，使其不超过每组预分配机器人的载荷上限;（3）利用延迟接受算法（DA）给每个组分配距离最近的机器人。最后改进基于一致性的束算法（CBBA），对每个子问题进行任务分配问题求解。仿真结果表明，提出的算法具有较高的任务完成度，并且有效减少机器人之间的通信量。
关键词：聚类分组;多机器人系统;时间窗;任务分配;CBBA算法;无人系统;作战
中图分类号：TJ810; V279
文献标识码：A
文章编号：1673-5048（2022）04-0100-10
DOI：10.12132/ISSN.1673-5048.2021.0249
0 引 言
诸如无人机、无人车的无人系统（机器人）近年来发展十分迅速，凭借其优秀的自主规划与执行能力，在许多领域得到了广泛应用，包括救援搜索[1]、行星探索[2]、军事行动[3]、生产调度[4]、资源分配[5]等。现代的工程及军事任务变得越来越复杂，往往一个总体任务包含许多个不同类型的子任务，如战场环境中的任务包含探索、打击和毁伤评估等，单个机器人已经无法满足解决大范围内的复杂任务，需要构建多机器人系统协同完成多项不同类型的子任务。
多机器人任务分配（MRTA）问题是多机器人系统协同控制的一个重要研究方向[6]。该问题需要多个机器人在一定约束条件下，规划出无冲突的任务分配策略，并获得全局收益良好的解。这个问题在规定时间内求解是困难的，求解全局最优解需要花费大量的时间和计算量。当分配问题比较复杂时，解集无法穷举出来，几乎不可能求出最优解，所以为了保证算法的效率，通常用近似算法提供一个可接受的次优解。
任务分配方法可以分为集中式和分布式两种。集中式方法需要中央处理器为整个系统生成任务计划，然后将结果传递给各个机器人。蚁群算法[7]、粒子群算法[8]、遗传算法[9]等集中式智能优化算法在解决MRTA问题方面都具有较优的解。虽然集中式方法结果全局较优，但是依赖大量的通信负载和计算量。此外，集中式方法的鲁棒性比较差，机器人容易出现单点故障，且对动态变化的通信响应较慢[10]。分布式方法不需要中央处理器，每个机器人在内部生成任务清单，再和周围的机器人通过通信解决冲突。分布式系统能够快速响应外部环境的变化、对通信带宽的依赖性比较小。虽然优化结果不如集中式，但是算法效率和鲁棒性更高，单点故障的影响更小，能够很好地应对野外复杂环境的不确定性[11]。分布式方法主要分为基于博弈论的机制和基于市场的机制，其中博弈论需要相对更长的收敛时间，目前基于市场机制的拍卖算法是广泛应用的高效方法。
Choi等[12]结合拍卖机制和信息共识机制，提出了基于一致性的束算法（CBBA），与传统的拍卖算法不同，该算法不需要有中间拍卖商，每个机器人内部具有一致的任务投标规则。CBBA被证明可以在较短时间内收敛于至少50%的纳什均衡解[13]。一些研究在CBBA的基础上进行了改进，使其适应更复杂的问题。Johnson等[14]提出了异步解决任务冲突的规则，减少不必要的通信，尽量降低通信负载，实现了CBBA的异步通信。Buckman等[15]考虑到时间敏感和动态出现的约束，提出一种重规划的CBBA-RP，提高任务快速协调性。基于任务优先级约束，Binetti等[16]提出了一种分散关键任务分配算法（DCTAA），将标记的关键任务优先分配给机器人，实现最大化奖励且保证关键任务被全部分配。Ye等[17]考虑到任务之间的耦合约束，通过引入插入位置可行性处理有冲突的任务规划，并改进了任务规划策略，减少不必要的任务选择计算。一些研究受到CBBA的启发，其中性能影响（PI）算法是针对搜救场景开发的，在解决时间约束问题上有良好的表现[18]。但是过快的迭代容易使算法陷入局部最优。Whitbrook等[19]改进PI算法，提出了PI-softmax算法，极大提高了算法的任务完成度和任务奖励，但算法的收敛时间在规模较大的人物场景中是难以接受的。
针对大规模的任务场景，上述研究无法获得很好的分配结果。Fu等[20]将机器人分成若干个组，每组各自生成任务计划，再由每个组的领头机器人传递给其他组，用两层共识规则将大规模问题细分为一个个小规模问题。Jang等[21]利用博弈论方法，自组织地将机器人按照距离和任务喜好进行任务分配，解决了大规模机器人的分配问题。但是机器人之间的通信量依然没有减少，且算法效率也比较低。
本文针对大规模任务分配问题，在有时间窗的约束下，改进CBBA算法，提出一种基于聚类分组的一致性的束算法（C-CBBA），解决了大规模问题的有限通信问题，在减少通信量的前提下，提高算法效率，保持任务分配结果具有较高的任务完成度和全局任务奖励。
本文的主要贡献为：
（1）任务点和机器人的聚类分组
基于距离因素，用K-means算法对任务点进行分组，然后利用延迟接受（DA）算法将机器人分配给各个分组，减少任务分配算法消耗的通信量，提高算法效率。
（2）改进任务序列包添加策略
建立未选择任务包，将未被选择的任务尽可能加入任务序列包中，提高任务完成度。
1 问题描述
本文的MRTA问题属于单任务单机器人延时分配（ST-SR-TA）问题[22]，即每个任务只需要一个机器人完成，每个机器人一次只能完成一个任务。作战场景如图1所示，场景中有异构的无人机和无人车，要求在时间窗的约束下，分别完成多个任务。任务类型分为探索、打击和评估毁伤目标。针对本文研究的任务环境，做如下假设：
假设1 每个机器人在地图中都是匀速移动的，具有相同的态势感知（SA），且通信数据不会丢失。
假设2 地图中没有任何障碍物，机器人和任务之间的距离由欧氏距离或曼哈顿距离表示。
1.1 异构机器人和任务的类型
假设系统一共有NR个异构机器人和NT个不同类型的任务，机器人和任务集合分别为
R={R1， R2， R3， …， Ri， …， RNR}（1）
T={T1， T2， T3， …， Tj， …， TNT}（2）
本文考虑四种机器人：固定翼无人机、旋翼无人机、小型侦察车和大型武装车。其中固定翼无人机和大型武装车只能执行打击和毁伤评估任务，旋翼无人机和小型侦察车只能执行探索和毁伤评估任务。规定任务分组的组数为K。
由于时间窗的约束，机器人i执行任务j的起始时间必须在规定的时间窗以内，满足：
1.2 大规模MRTA问题目标函数
本文主要的目标是保证算法效率和通信量足够低的基础上，最大化每个分组的任务完成度和全局任务奖励。其目标函数可以表示为
循环迭代地执行算法2，直到式（23）～（25）满足约束条件为止，则可以保证每个组的任务理论上可以全部完成。
3 机器人分组调配
假设任务开始时，所有机器人已经分布在地图上，按照距离最近的原则，将机器人分配到相应的任务分组上。
3.1 机器人分组问题模型
目的是最小化机器人到对应的分组的距离之和，为了简化计算，以机器人和各分组聚类中心的距离作为机器人与各分组的距离，其目标函数为
3.2 延迟接受（DA）算法
将机器人分配到各任务分组的问题建模为一对多类型的稳定匹配问题，匹配度由机器人到聚类分组中心的距离决定。
4 分组任务分配
利用CBBA算法对每个机器人-任务分组进行任务分配规划，得到最终的任务规划解。
4.1 基线CBBA
CBBA的主要工作是，首先利用贪婪选择算法构建任务序列包Pi，然后使用共识规则建立任务冲突协商机制来解决机器人任务包之间的冲突。
4.1.1 任务包的建立
任务序列包的建立是在每个机器人内部并行运行的，然后通过投标信息解决冲突。投标信息主要包括：
（1）任务包bi∈（T∪{}）LT，储存了机器人选择的任务。
（2）任务序列包Pi∈（T∪{}）LT，代表按执行顺序排列的任务集合。
（3）任务的中标报价列表yi∈（R+）NT，其中yij∈yi（j=1， 2， …， NT）为执行任务j的最高报价，表示每个机器人内部执行该任务j的奖励。在共识协商阶段，每个机器人之间对任务j进行报价竞争，更新当前最高的任务奖励（最高报价）。
（4）中标机器人列表zi∈（R∪{}）NT为对任务j报价最高的机器人i，表示在共识协商阶段，机器人i获取任务j的执行权，将其序号i储存在中标机器人列表中。
任务序列包构建阶段，机器人i利用贪婪算法，每次将当前奖励值最大的任务添加到包中，直到不能再继续添加任务。每添加一个任务，除了将任务序号j记录在任务包和任务序列包中，还会在报价列表中记录其任务奖励，作为对任务j的竞标报价cij，并在中标机器人列表中记录自己的机器人序号i。
4.1.2 共识协商机制
在冲突协商阶段，机器人利用共识协商策略调节任务冲突，即出价最高的机器人获得任务j的执行权，其他落选机器人将包中的任务j删除，之后所有机器人更新中标报价列表yi和中标机器人列表zi，记录当前最高的报价（任务奖励）和中标机器人序号。共识规则如表1所示。列表yi和zi的更新操作可以表示为
式中：update为中标报价和中标机器人两个列表进行更新，保存当前最高报价和提供报价的机器人序号。Reset为当前任务进行重置，删除列表相关任务j的数据。Leave为不做任何修改，保持列表原有报价不变。
显然，将大规模机器人和任务进行分组以后，每个机器人内部可选择的任务减少了，同时省略了不同分组机器人之间的多余通信，大大降低了算法中机器人的通信总量。
4.2 任务奖励函数
基线CBBA的任务奖励函数是严格基于边际增益函数（DMG）计算的，当任务执行时间超过任务开启时间，奖励函数将趋于0，导致任务无法选择。在计算任务点奖励时设置固定奖励，使得奖励永远大于成本代价[17]，保证每个任务尽量被选择。目标奖励函数表示为