基于聚类分组的异构多机器人任务分配算法研究
2022-10-11郑习羽徐梓毓王京华
郑习羽，徐梓毓，王京华，2*
(1. 长春理工大学 机电工程学院，长春 130022； 2. 长春理工大学 跨尺度微纳制造教育部重点实验室，长春 130022)
0 引 言
诸如无人机、 无人车的无人系统(机器人)近年来发展十分迅速，凭借其优秀的自主规划与执行能力，在许多领域得到了广泛应用，包括救援搜索、 行星探索、 军事行动、 生产调度、 资源分配等。现代的工程及军事任务变得越来越复杂，往往一个总体任务包含许多个不同类型的子任务，如战场环境中的任务包含探索、 打击和毁伤评估等，单个机器人已经无法满足解决大范围内的复杂任务，需要构建多机器人系统协同完成多项不同类型的子任务。
多机器人任务分配(MRTA)问题是多机器人系统协同控制的一个重要研究方向。该问题需要多个机器人在一定约束条件下，规划出无冲突的任务分配策略，并获得全局收益良好的解。这个问题在规定时间内求解是困难的，求解全局最优解需要花费大量的时间和计算量。当分配问题比较复杂时，解集无法穷举出来，几乎不可能求出最优解，所以为了保证算法的效率，通常用近似算法提供一个可接受的次优解。
任务分配方法可以分为集中式和分布式两种。集中式方法需要中央处理器为整个系统生成任务计划，然后将结果传递给各个机器人。蚁群算法、 粒子群算法、 遗传算法等集中式智能优化算法在解决MRTA问题方面都具有较优的解。虽然集中式方法结果全局较优，但是依赖大量的通信负载和计算量。此外，集中式方法的鲁棒性比较差，机器人容易出现单点故障，且对动态变化的通信响应较慢。分布式方法不需要中央处理器，每个机器人在内部生成任务清单，再和周围的机器人通过通信解决冲突。分布式系统能够快速响应外部环境的变化、 对通信带宽的依赖性比较小。虽然优化结果不如集中式，但是算法效率和鲁棒性更高，单点故障的影响更小，能够很好地应对野外复杂环境的不确定性。分布式方法主要分为基于博弈论的机制和基于市场的机制，其中博弈论需要相对更长的收敛时间，目前基于市场机制的拍卖算法是广泛应用的高效方法。
Choi等结合拍卖机制和信息共识机制，提出了基于一致性的束算法(CBBA)，与传统的拍卖算法不同，该算法不需要有中间拍卖商，每个机器人内部具有一致的任务投标规则。CBBA被证明可以在较短时间内收敛于至少50%的纳什均衡解。一些研究在CBBA的基础上进行了改进，使其适应更复杂的问题。Johnson等提出了异步解决任务冲突的规则，减少不必要的通信，尽量降低通信负载，实现了CBBA的异步通信。Buckman等考虑到时间敏感和动态出现的约束，提出一种重规划的CBBA-RP，提高任务快速协调性。基于任务优先级约束，Binetti等提出了一种分散关键任务分配算法(DCTAA)，将标记的关键任务优先分配给机器人，实现最大化奖励且保证关键任务被全部分配。Ye等考虑到任务之间的耦合约束，通过引入插入位置可行性处理有冲突的任务规划，并改进了任务规划策略，减少不必要的任务选择计算。一些研究受到CBBA的启发，其中性能影响(PI)算法是针对搜救场景开发的，在解决时间约束问题上有良好的表现。但是过快的迭代容易使算法陷入局部最优。Whitbrook等改进PI算法，提出了PI-softmax算法，极大提高了算法的任务完成度和任务奖励，但算法的收敛时间在规模较大的人物场景中是难以接受的。
针对大规模的任务场景，上述研究无法获得很好的分配结果。Fu等将机器人分成若干个组，每组各自生成任务计划，再由每个组的领头机器人传递给其他组，用两层共识规则将大规模问题细分为一个个小规模问题。Jang等利用博弈论方法，自组织地将机器人按照距离和任务喜好进行任务分配，解决了大规模机器人的分配问题。但是机器人之间的通信量依然没有减少，且算法效率也比较低。
本文针对大规模任务分配问题，在有时间窗的约束下，改进CBBA算法，提出一种基于聚类分组的一致性的束算法(C-CBBA)，解决了大规模问题的有限通信问题，在减少通信量的前提下，提高算法效率，保持任务分配结果具有较高的任务完成度和全局任务奖励。
本文的主要贡献为：
(1) 任务点和机器人的聚类分组
基于距离因素，用K-means算法对任务点进行分组，然后利用延迟接受(DA)算法将机器人分配给各个分组，减少任务分配算法消耗的通信量，提高算法效率。
(2) 改进任务序列包添加策略
建立未选择任务包，将未被选择的任务尽可能加入任务序列包中，提高任务完成度。
1 问题描述
本文的MRTA问题属于单任务单机器人延时分配(ST-SR-TA)问题，即每个任务只需要一个机器人完成，每个机器人一次只能完成一个任务。作战场景如图1所示，场景中有异构的无人机和无人车，要求在时间窗的约束下，分别完成多个任务。任务类型分为探索、 打击和评估毁伤目标。针对本文研究的任务环境，做如下假设：
假设1 每个机器人在地图中都是匀速移动的，具有相同的态势感知(SA)，且通信数据不会丢失。
假设2 地图中没有任何障碍物，机器人和任务之间的距离由欧氏距离或曼哈顿距离表示。
图1 城市作战场景示意图
1.1 异构机器人和任务的类型
假设系统一共有个异构机器人和个不同类型的任务，机器人和任务集合分别为
={,,, …,, …,}
(1)
={,,, …,, …,}
(2)
本文考虑四种机器人： 固定翼无人机、 旋翼无人机、 小型侦察车和大型武装车。其中固定翼无人机和大型武装车只能执行打击和毁伤评估任务，旋翼无人机和小型侦察车只能执行探索和毁伤评估任务。规定任务分组的组数为。
由于时间窗的约束，机器人执行任务的起始时间必须在规定的时间窗以内，满足：
(3)
(4)
1.2 大规模MRTA问题目标函数
本文主要的目标是保证算法效率和通信量足够低的基础上，最大化每个分组的任务完成度和全局任务奖励。其目标函数可以表示为
(5)
(6)
(7)
其约束为
(8)
(9)
(10)
C-CBBA算法整体流程框架如图2所示。
图2 C-CBBA算法整体流程框架
2 任务点聚类分组
在三维空间中，既有高空任务，也有地面任务。受限于地面机器人无法执行高空任务，为了保证分配给各组的机器人能够完成任务，在任务分组阶段，将高空任务和地面任务区分开，单独划分出高空任务，其他地面任务再进行分组。即其中一组为高空组，剩余的-1组为地面任务组。
2.1 聚类算法
聚类算法属于无监督学习，通过对任务点坐标值的无标记样本训练，对任务点的分组进行区分。考虑到训练的目标只有任务点的坐标值，本文用K-means的方法对任务点进行分组。
K-means和K-medoid是两种最常见的聚类分组算法。K-medoid对噪声鲁棒性比较好，可以避免“噪声”对聚类结果的影响，但计算速度较慢。K-means的计算效率更高，针对大样本学习的情况，少数的“噪声”任务点对整体聚类中心的影响不大。所以, K-means更适应大规模任务点的聚类分组。
2.1.1 预定义聚类中心
针对聚类分组问题，K-means算法需要事先预定聚类中心，通常随机寻找个任务点作为初始聚类中心。但在分布式系统中会造成不一致的分组，需要预定统一的初始聚类中心。
首先，定义高空任务组的初始聚类中心，假设任务点的出现在三维空间中服从高斯分布，将地图正中心点作为高空组的初始聚类中心，组别为=1，其坐标向量可以表示为
(11)
式中：,,分别为地图极限值。
然后，定义剩余的-1组地面任务组的初始聚类中心。假设地面组的初始全局中心为
(12)
如图3所示，以地面中心为圆心，各分组聚类中心围绕其圆心均匀分布。各分组聚类中心三个坐标轴的坐标值分别表示为
(13)
(14)
(15)
式中：=π/4。
图3 地面分组聚类中心分布
2.1.2 K-means聚类
根据任务点坐标的样本集={,, …,}，以及初始定义的任务聚类组={,, …,}，K-means的目的为最小化每个任务距离所在聚类分组的平方误差：
(16)
算法流程如图4所示，分别计算每个任务点距离聚类中心的距离，将任务点加入到距离最近的分组。循坏迭代访问直到分组聚类中心不再更新为止。
2.2 任务点分组重规划
K-means只是对任务分组的初步规划，仅依靠任务点的距离关系进行分组，没有考虑到分配给各组的异构机器人的数量是否满足每个组的任务需求。本文提出了任务分组重规划机制，最小化每个组的机器人数量需求总和，使每个组的任务需求能够满足提供的机器人数量，增大任务完成度。
2.2.1 分组任务类型
在任务点初步分组之后，计算每个组中三种任务的数量，表示为分组需求矩阵：
(17)
式中：，，分别为探索、 打击、 毁伤评估任务的数量。
算法1 任务点初始分组算法输入: 任务坐标点样本集D、 聚类分组数K输出: 任务点分组划分S过程: (1)按式(11)～(15)计算每个组的初始聚类中心μ(2)while(3)初始化Ss=∅(1≤s≤K)(4)for j=1, 2, …, NT do(5)计算任务j与各分组中心μs的距离: djs=dj-μs2(6)根据距离确定任务j的分组ξj=argmins∈{1, 2, …, K}djs(7)将任务j归入相应的分组: Sξj=Sξj∪{j}; (8)end for(9)for s=1, 2, …, K do(10)计算新的分组聚类中心μ′s=1Ss∑d∈Ssd; (11)if μ′s≠μs then(12)μi←μ′i(13)else(14)保持当前分组聚类中心不变(15)end if(16)end for(17)until当前分组聚类中心不再更新(18)end
2.2.2 机器人供应数量问题模型
(18)
目的是最小化机器人供应数量，目标函数为
(19)
其约束为
(20)
(21)
(22)
≤
(23)
(24)
(25)
式中：为每个机器人可执行的最大任务数量；为旋翼无人机与小型侦察车数量之和；为固定翼无人机与大型武装车数量之和。
当机器人数量需求不满足式(23)～(25)时，则需求数量超量，此时需要将某些分组的任务点调整到其他分组，降低机器人数量需求。建立每个分组可接受任务的余量矩阵：
(26)
任务点分组重规划算法如图5所示，先判断机器人数量是否超量，然后确定超量机器人的类型，选择任务余量空间最大的分组，将多余的任务分配到其他有余量的分组。
算法2 任务点分组重规划输入: 分组需求矩阵Ω、 机器人数量分布Φ、 余量矩阵Ψ、 任务聚类分组S输出: 分组需求矩阵Ω∗、 机器人数量分布Φ∗、 余量矩阵Ψ∗、 任务聚类分组S∗过程: (1)if式(23)～(25)不成立 then(2)寻找需要调整的任务点分组s∗=argmaxs∈{1, 2, …, K}ms(3)计算需要调整的任务点数量nad=LT-ms∗(4)while(5)for j=1→Ss组对应任务类型数量do(6)选择距离最近的转移分组ξj=argmins∈{1, 2, …, K}{s∗}djs(7)if djs 循环迭代地执行算法2，直到式(23)～(25)满足约束条件为止，则可以保证每个组的任务理论上可以全部完成。 假设任务开始时，所有机器人已经分布在地图上，按照距离最近的原则，将机器人分配到相应的任务分组上。 目的是最小化机器人到对应的分组的距离之和，为了简化计算，以机器人和各分组聚类中心的距离作为机器人与各分组的距离，其目标函数为 (27) 其约束为 (28) (29) 式中：为机器人距离分组的距离；∈{0, 1}为机器人分配组别的决策变量；为分配给每个组的机器人总数。 将机器人分配到各任务分组的问题建模为一对多类型的稳定匹配问题，匹配度由机器人到聚类分组中心的距离决定。 初始定义机器人分组表示为 ={,, …,} (30) 图6为机器人分组算法，即延迟接受(DA)。首先每个机器人计算与聚类分组中心的距离，然后每个分组都系统性地从上到下遍历机器人的最近距离分组，选择距离自己最近的若干机器人，若机器人和另外的分组更匹配，则将该机器人让给其他分组。经过多轮迭代后得到一个稳定的匹配结果。 算法3机器人分组算法输入: 机器人集合R、 任务聚类分组S、 机器人数量分布Φ输出: 机器人聚类分组A过程: (1) while(2)for i=1→NR do(3)ζi=argmins∈{1, 2, …, K}dis(4)将机器人i与分组ζi匹配(5)if分组机器人需求数没满 then(6)Aζi=Aζi∪{i}(7)else if分组机器人需求数已满 then(8)分组Aζi删除组内距离最远的机器人k(9)Aζi=Aζi{k}, Aζi=Aζi∪{i}(10)end if(11)end for(12) until所有机器人都已分配到各聚类分组 利用CBBA算法对每个机器人-任务分组进行任务分配规划，得到最终的任务规划解。 CBBA的主要工作是，首先利用贪婪选择算法构建任务序列包，然后使用共识规则建立任务冲突协商机制来解决机器人任务包之间的冲突。 4.1.1 任务包的建立 任务序列包的建立是在每个机器人内部并行运行的，然后通过投标信息解决冲突。投标信息主要包括： (1)任务包∈(∪{∅})，储存了机器人选择的任务。 (2)任务序列包∈(∪{∅})，代表按执行顺序排列的任务集合。 (3)任务的中标报价列表∈()，其中∈(=1, 2, …,)为执行任务的最高报价，表示每个机器人内部执行该任务的奖励。在共识协商阶段，每个机器人之间对任务进行报价竞争，更新当前最高的任务奖励(最高报价)。 (4)中标机器人列表∈(∪{∅})为对任务报价最高的机器人，表示在共识协商阶段，机器人获取任务的执行权，将其序号储存在中标机器人列表中。 任务序列包构建阶段，机器人利用贪婪算法，每次将当前奖励值最大的任务添加到包中，直到不能再继续添加任务。每添加一个任务，除了将任务序号记录在任务包和任务序列包中，还会在报价列表中记录其任务奖励，作为对任务的竞标报价，并在中标机器人列表中记录自己的机器人序号。 4.1.2 共识协商机制 在冲突协商阶段，机器人利用共识协商策略调节任务冲突，即出价最高的机器人获得任务的执行权，其他落选机器人将包中的任务删除，之后所有机器人更新中标报价列表和中标机器人列表，记录当前最高的报价(任务奖励)和中标机器人序号。共识规则如表1所示。列表和的更新操作可以表示为 (31) 式中： update为中标报价和中标机器人两个列表进行更新，保存当前最高报价和提供报价的机器人序号。Reset为当前任务进行重置，删除列表相关任务的数据。Leave为不做任何修改，保持列表原有报价不变。 显然，将大规模机器人和任务进行分组以后，每个机器人内部可选择的任务减少了，同时省略了不同分组机器人之间的多余通信，大大降低了算法中机器人的通信总量。 基线CBBA的任务奖励函数是严格基于边际增益函数(DMG)计算的，当任务执行时间超过任务开启时间，奖励函数将趋于0，导致任务无法选择。在计算任务点奖励时设置固定奖励，使得奖励永远大于成本代价，保证每个任务尽量被选择。目标奖励函数表示为 (32) ≥· (33) = (34) 式中：和分别为机器人执行任务的奖励和代价；为机器人到任务点的距离公式，根据机器人的异构性，空中机器人采用三维欧氏距离，地面机器人采用二维曼哈顿距离；为距离代价常系数；为任务固定奖励；为及时完成任务的奖励。本文假设奖励函数是非负的，所以固定奖励不小于代价。 表1 机器人i与机器人k的共识协商规则 基线CBBA中，机器人在每次迭代过程中选择任务时，总是要从上到下依次遍历所有任务，这样会造成已经竞价失败的任务重新添加到包中，且容易忽略到后续被所有机器人都忽略的任务，使任务完成度较低。 算法4 任务序列包构建算法输入: 迭代次数t-1过程中的bi(t-1), Pi(t-1), yi(t-1), zi(t-1),ti(t-1)输出: 迭代次数t过程中的bi(t), Pi(t), yi(t), zi(t), ti(t)过程: (1)bi(t)=bi(t-1), Pi(t)=Pi(t-1), yi(t)=yi(t-1), zi(t)=zi(t-1), ti(t)=ti(t-1)(2)构建任务未选包bnoi: bnoi=T∩(P1∪P2∪…∪Pa)(3)whilebi(t)≤LT do(4)cij(Pi) = maxn≤PiViPin{ j}-ViPi(5)hij=Π(cij>yij)(6)Ji=argmaxj(cij(Pi)×hij)(7)ni, Ji=argmaxjVPi⊕n{j}i(8)ti, ni, Ji=max[ti, ni, Ji-1+(Vni, Jii-Vni, Ji-1i)/vi, t0, ni, Ji](9)bi=bi⊕end{Ji}, Pi=Pi⊕ni, Ji{Ji}(10)yi, Ji(t)=ci, Ji, zi, Ji(t)=i, ti, Ji(t)=ti, ni, Ji(11)end while 通过改进的任务序列包构建算法，在每次任务访问阶段，都优先搜索还没有被选择的任务，提高任务完成度的同时，也减少了无用任务访问的频次，提高算法效率。通过任务序列包构建和共识协商两个阶段的循环迭代，最终收敛到任务完成度最大的无冲突分配方案。 为了测试C-CBBA的性能，在Intel(R) Core(TM) i7-10700K CPU @ 3.80 GHz and 16 GB RAM的PC上，用MATLAB2019a进行仿真。并和基线CBBA、 具有任务耦合约束的CBBA(TCC)进行对比。 在5 km×5 km×1 km的三维场景下，异构机器人团队在总体时间窗[0, 5 000 s]内完成任务的调度。机器人最大任务数量=15，任务固定奖励=30，任务完成奖励=100，任务价值随时间衰减因子=0.1。实验中，模拟了五种机器人-任务点规模，分别为10-100，30-300，50-500，80-800，100-1 000，任务和机器人分组组数=5。每种规模分别进行了100次蒙特卡洛随机模拟，每次模拟时算法的迭代次数最多为100次，当任务规划迭代次数超过100，算法将强制停止，输出当前的最优解。此外，为了显示预设分组组数对任务分配结果的影响，对30-300规模的分配问题，分别模拟了分组组数为3, 4, 5, 6四种情况下的实验。 为了清晰地展示机器人的任务路线图，选择展示在10-100规模下=5时的某一次实验结果。实验中最小的规模为10-100，其任务执行路线图比较清楚，且在=5的情况下，任务分组的结果比较稀疏，有利于最终结果的观察。相关信息如表2～3所示。 表2 机器人相关信息 表3 任务目标相关信息 图8为任务分配路线图，为了便于观察，忽略了高度，只显示二维平面的路线轨迹。表4为机器人分配方案，即机器人执行任务顺序。 其中，算法收敛时间0.311 s，任务完成度100%，通信量(通信频次)150次，全局任务奖励4 083.396。 不同规模下机器人及任务的类型数量分布采用相同的比例构成，任务分组组数都为=5。表5为机器人和任务的类型数量分布情况与编号对应的类型，四种机器人的类型比例分布为0.3∶0.2∶0.3∶0.2，三种任务的类型数量比例分布为0.33∶0.33∶0.34。 通过算法在五种不同规模下的仿真，总体性能由算法收敛时间、 通信量(通信频次)、 任务完成度、 全局任务奖励、 任务平均花费时间五个方面体现。 其中算法收敛时间的计算从系统开始分组到最终输出任务分配结果结束，运行时间依赖于实验PC条件。多机器人之间的通信量依赖于系统通信模型、 机器人通信方式、 机器人拓扑连接方式、 通信损耗等多方面的因素，研究简化了其通信量的计算，用机器人之间的通信频次(冲突解调阶段机器人之间的通信次数)作为通信量的计算依据，两个机器人之间的一次冲突解调为1个通信频次。每一次任务包构建和冲突解调的迭代为一轮通讯，一轮通讯中的通信频次依赖于拓扑连接形式，本文按照全连接的形式进行通信，故一轮通讯的通信频次为(-1)2，为每个分组的机器人数量。 表6～10分别表示不同规模下，五个性能指标的仿真实验结果对比。可见在算法收敛时间、 通信量、 任务完成度方面，C-CBBA的性能是最优的，可以解决大规模任务分配问题的最大化算法效率和最小化通信量问题，并能保证大部分任务被机器人选中并执行。 图8 各聚类分组的机器人任务路线图 (1) 算法收敛时间和通信量方面，预先对任务和机器人进行了分组，每个分组的规模都变小了，任务分配算法需要计算访问的对象缩减，提高了收敛的效率，同时也减少了机器人之间通信的总量，每个机器人只需要和自己组内的机器人进行通信。 (2) 任务完成度方面，在每次任务规划阶段，重点考虑了全局未被选择的任务，所以C-CBBA可以规划出接近100%的任务完成度，而基线CBBA和TCC需要频繁地删除任务重新规划。三种算法的任务奖励都是按照边际效益递减的规律进行计算的，为了贴合实际任务执行时，开始时间越晚，收益越低的情况，引入了边际效益递减因子。因此，算法对时间的增加比较敏感，CBBA算法的任务奖励会随着时间的增加快速降低，没有任务固定奖励，收益将小于0，导致任务无法选择。而TCC虽然也引入了固定奖励，但是算法执行时依然要频繁地删除任务，也会导致任务完成度不高。C-CBBA算法在引入固定奖励的基础上，还加入了未选任务优先访问机制，尽量将全局未选择的任务加入任务序列包中。 表4 不同规模下机器人及任务的类型数量分布 表5 机器人任务分配方案 表6 三种算法的收敛时间 表7 三种算法的通信量(通信频次) 表8 三种算法的任务完成度 表9 三种算法的全局任务奖励 表10 三种算法的任务平均用时 (3) 全局任务奖励和平均任务花费时间方面，由于聚类分组本身会缩小分配解集，可能会将最优的解排除，所以C-CBBA的总奖励并不是最高的，说明分配策略的奖励不是最高的。其原因为C-CBBA的任务完成度高，机器人需要执行的任务多，任务平均花费时间相应增加，在时间窗约束下，部分任务的执行时间无法在任务开启时立刻执行，导致任务奖励不能达到理论最大值。 不同的分组组数对算法也有影响，对30-300规模的机器人-任务组进行仿真，分别将其划分为3, 4, 5, 6组。 不同组数的算法性能如表11所示。在不同分组组数下，随着组数的增加，算法收敛时间和通信量明显降低，任务完成度和全局任务奖励变小。这是因为分组越细，默认忽略的分配解集越多，增加算法收敛速度，降低了解的质量。所以在不同场合，应该根据不同的需求进行取舍。 表11 不同组数的算法性能 结合前两种仿真情况，C-CBBA在收敛时间、 通信量、 任务完成度方面具有优势，算法的设定条件是任务的位置和类型预先已知，机器人提前布置在任务环境中，且机器人和任务的类型数量是提前设定好的，这意味着在任务分配前的机器人分组调配必须是有解的，否则将造成算法失效。本文适用于具有时间窗约束的大型任务场景下的大规模任务分配问题中，最大化任务完成度及最小化的收敛时间的情况。表6显示，从规模80-800开始，算法收敛时间超过了60 s，针对超大规模的任务分配问题，C-CBBA算法只能适用于静态任务，不再适用于动态任务。针对规模小于50-100的问题，C-CBBA算法具有较好的适应能力。 本文针对具有时间窗约束的大规模MRTA问题，提出了基于聚类分组的一致性的束算法(C-CBBA)，解决算法效率和降低通信量的问题。首先利用K-means算法对任务点按照距离分组，并用任务点重规划机制最小化所需机器人资源，然后用DA算法将机器人分配到各聚类分组，最后改进CBBA算法，求解划分好的若干小规模问题。仿真实验结果表明，该算法能够在较短的时间内，用较少的通信量达到可接受的任务完成度和全局任务奖励。但是在性能检验方面，通信量受系统通信模型、 机器人拓扑连接方式等多种因素影响，本文对通信量的计算比较理想化，未来研究还应考虑实际情况，对通信进一步细化研究。而且聚类分组可能会忽略全局最优解，在更大范围内，机器人并不能获得所有其他机器人的信息。未来将考虑机器人之间的具体通信模型，并改进任务和机器人分组机制，在最小化资源需求的基础上，最大化全局任务奖励。3 机器人分组调配
3.1 机器人分组问题模型
3.2 延迟接受(DA)算法
4 分组任务分配
4.1 基线CBBA
4.2 任务奖励函数
4.3 任务选择优化
5 算法仿真实验
5.1 场景参数设置
5.2 算法结果展示
5.3 不同规模的算法性能对比
5.4 不同分组规模的仿真
6 结 论
