基于混合算法的多机器人协作任务均衡规划研究_王喜敏.pdf

第40卷第2期2023年3月新疆大学学报（自然科学版）（中英文）Journal of Xinjiang University(Natural Science Edition in Chinese and English)Vol.40,No.2Mar.,2023基于混合算法的多机器人协作任务均衡规划研究王喜敏，袁 杰(新疆大学 电气工程学院，新疆 乌鲁木齐 830017)摘要：针对机器人完成任务不均衡问题展开分析，提出了基于混合算法的规划算法，包括适应度值分类的K-means聚类实现任务分配、黏菌算法提高整体搜索效率、头脑风暴算法机器人内进行局部更新操作和机器人间进行全局更新操作完成重规划操作、交叉操作和大规模邻域搜索操作用以更新个体 实验结果表明：基于混合算法的任务均衡规划方法能够均衡规划多机器人任务，优化任务规划结果，提升任务的完成效率关键词：任务均衡；任务重规划；K-means；黏菌算法；头脑风暴算法；大规模邻域搜索DOI：10.13568/ki.651094.651316.2022.04.25.0002中图分类号：TP393文献标识码：A文章编号：2096-7675(2023)02-0210-012引文格式：王喜敏,袁杰.基于混合算法的多机器人协作任务均衡规划研究J.新疆大学学报(自然科学版)(中英文),2023,40(2):210-221.英文引文格式：WANG Ximin,YUAN Jie.Research on multi-robot cooperative task equilibrium planning based onhybrid algorithmJ.Journal of Xinjiang University(Natural Science Edition in Chinese and English),2023,40(2):210-221.Research on Multi-Robot Cooperative Task Equilibrium PlanningBased on Hybrid AlgorithmWANG Ximin,YUAN Jie(School of Electrical Engineering,Xinjiang University,Urumqi Xinjiang 830017,China)Abstract：Based on the analysis of the problem of unbalanced tasks completed by robots,a planning algorithmbased on hybrid algorithm is proposed.It includes fitness value classification of K-means clustering for taskallocation,slime mold algorithm to improve the overall search efficiency,brainstorming algorithm for local updateoperation in robot and global update operation in robot for re-planning operation,crossover operation and large-scale neighborhood search operation to update individuals.The experimental results show that the task balancingplanning method based on hybrid algorithm can balance multi-robot tasks,improve task planning results andimprove task completion efficiency.Key words：task balancing;task re-planning;K-means;slime mold algorithm;brainstorming algorithm;large-scale neighborhood search0引 言针对多机器人协作任务规划（Cooperative Multi-Robot Task Planning,CMRTP）问题，通过代价函数评价能够使任务规划结果获取较大的系统效能，但必须考虑任务规划结果的均衡性1，如果规划过程中某个机器人的任务量过于繁重，将出现任务规划失衡的情况，那么即使能够获取较大的整体效能，也会使部分机器人因任务量繁重而过早损坏，并且不利于系统整体执行效率的提高 所以在满足系统整体效能和移动机器人个体任务要求的基础上，考虑机器人任务规划的均衡性，尽量实现公平分配 机器人团队高效完成整体任务时，需要平衡各机器人的工作，只专注最小化总代价往往会导致劳动力失衡，所以在协作团队中满足总距离最小时，最小收稿日期：2022-04-25基金项目：国家自然科学基金“非结构环境下机器人羽流寻源自主演进策略研究”（62263031），“机器人化单分子病毒可控侵染细胞及原位定量表征方法研究”（62073227）；新疆维吾尔自治区自然科学基金“非结构环境下机器人建图与主动安全方法研究”（2022D01C53）作者简介：王喜敏（1995-），女，硕士生，从事群智能优化的研究，E-mail:通讯作者：袁杰（1975-），男，博士，教授，主要从事计算机应用的研究，E-mail:第2期王喜敏，等：基于混合算法的多机器人协作任务均衡规划研究211化所有机器人最大距离同样具有实际意义，否则会出现不正确的任务均衡效果现今对于CMRTP问题，熊衍捷等2为解决多通道资源负载均衡问题，提出基于NJW谱聚类的资源负载均衡调度算法，通过聚类划分一定的簇数量，进行加权的K-means算法完成聚类等方法提高负载均衡度，这促使我们应用一种简单的标准的聚类技术来解决多旅行商问题（Multiple Traveling Salesman Problem,MTSP）/均衡多机器人任务分配（Balanced Multi-Robot Task Allocation,BMRTA）问题 毛科技等3针对无线传感器网络的数据传输问题，提出能耗均衡的层次路由协议，通过划分不同规模的簇，实现网络能耗均衡 朱姗等4运用组合优化和聚类分析理论来缩短求解空间的方法，为大规模超市中的订单拆分问题提供了新思路 解决相关问题的同时提高求解效率，将不同算法进行融合来发挥算法的各自优势，克服或抑制各自的缺陷，实现算法优势互补姚泽玮等5针对移动设备多边缘的负载均衡问题，提出粒子群遗传算法（Particle Swarm Optimization-GeneticAlgorithm,PSO-GA）融合算法，通过任务调度来最小化边缘集合中最大的任务响应时间，缩短了边缘的任务响应时间并改善了用户体验 董亚倩等6在引导车选址中，利用调度最小生成树，解决任务均衡分配并优化了行进路径 罗海峰7设计一种局部搜索和大规模邻域搜索混合搜索的方法，利用局部搜索的局部性和大规模邻域的全局性，求解容量约束的车辆路由问题 胡士娟8、张硕航9等通过在杂草算法中引入繁殖机制产生的后代进行遗传操作，解决了工作量平衡的MTSP，从而改善快递员配送环节的任务平衡问题Venkatesh等10在求解单仓库MTSP中，提出采用人工蜂群算法最小化所有旅行商的总距离，采用基于入侵杂草优化算法最小化所有旅行商所走的最大行驶距离 李道全等11考虑网络区域能耗的均衡问题，改进蚁群算法提高覆盖率和平衡网络能量的消耗Bernardino等12提出一种分支切割算法与局部搜索结合的混合算法获得高质量的解本文在研究任务均衡规划问题时，将CMRTP问题表述为MTSP的一个复杂变体13，研究如何均衡机器人团队的所有机器人的行走距离，即如何最小化所有机器人的最长行走距离 为了能够达到任务均衡效果，对其聚类进行改进，将机器人总距离最小作为优化目标函数；在整体效能方面采用最小化最大路程作为目标函数基于多种群智能的算法，使用黏菌算法和交叉操作相互结合来解决局部问题；结合头脑风暴优化算法思想以降低问题的复杂度和求解全局问题；利用最小化最大路径的方式求解任务规划问题的任务均衡问题 即不断地调整任务由哪个机器人完成，以及调整任务方案上完成任务的顺序为了保证机器人系统完成任务之间的均衡性，使得每个机器人完成任务的代价尽量均衡，通过分析均衡度评价机器人团队的任务均衡性 本文分为两个阶段：第一阶段通过改进K-means聚类进行初步任务分配，第二阶段通过头脑风暴优化算法进行重规划、任务规划，获得较优的任务顺序方案，以便提高机器人利用效率和任务均衡性1协作任务均衡规划问题分析与建模多移动机器人协作任务规划问题中，存在机器人集合R=r1,r2,rm，任务集合T=t1,t2,tn，任务ti的坐标(xti,yti)，任务子集合S=S1,S2,Sm，其中Sk(k=1,2,m)表示第k个机器人完成任务序列集合C是一个N N维代价矩阵，其中cij表示机器人从任务ti到tj的距离，同时规定c(ti,ti)=0，i1,2,n表示相同任务之间的代价为0；c(ti,tj)=c(tj,ti)，i1,2,n表示代价矩阵C为对称矩阵针对任务均衡规划问题，CMRTP问题考虑机器人工作均衡性，将其问题转为最小化所有机器人的最大距离更有实际意义 机器人位置、任务位置及从一个任务位置到另一个任务位置的代价矩阵是已知的 假设代价矩阵C是对称的，目标是规划任务和机器人，使得优化每个机器人完成任务的代价值较小和机器人完成任务代价之间均衡度较小1.1优化目标Dij=(xtixtj)2(ytiytj)2(1)其中：xti和xtj表示任务ti和tj的横坐标，yti和ytj是任务ti和tj的纵坐标，dij是任务(ti,tj)距离，代价矩阵D=|d11.d1n.dn1.dnn|假设第i台机器人完成p(pn)个任务，机器人起点t1，行走路径为L=(t1,t2,tn1,t1)，则212新疆大学学报（自然科学版）（中英文）2023年机器人行走路径长度为：Cij=N1k=1(D(t1,ti)+D(ti,tj)+D(tj,t1),i,j k(2)1）适应度值1 机器人集合完成任务所行走的总距离：zk=minninjcijxijk,k=1,2,m(3)2）适应度值2 机器人行走的最长路程，目标函数为最小化最长距离：zk=cijxijk(4)minmax(z1,z2,zm)(5)其中：zk(k=1,2,m)为第k个机器人完成任务子集合Si(i=1,2,m)行走路程1.2约束条件针对任务均衡规划问题，任务和机器人需要满足以下约束条件nj=2x1j=m(6)ni=2xi1=m(7)ni=1,i/=jxij=1,j=2,n(8)nj=1,i/=jxij=1,i=2,n(9)xij=1,0,机器人从任务i到任务j其它(10)uiuj+(nm)xijnm+1,2i=j n(11)1uinm,i=2,3,n(12)Si=,i=1,2,m(13)mi=1Si=T(14)SiSj=,i=j,i=1,2,m,j=1,2,m(15)其中：公式（6）和（7）表示约束所有机器人从集合出发点出发；公式（8）和（9）表示约束每个任务仅被机器人完成一次；公式（10）表示任务当前状态，任务完成情况；公式（11）和（12）表示机器人行走路线包含起始点；公式（13）、（14）和（15）表示任务间关系1.3对多移动机器人系统的任务规划问题作如下假设1）机器人工作的空间是二维平面；2）机器人执行任务的成本代价用机器人行走的距离长度表示；3）机器人在各自目标任务位置处执行任务消耗的代价忽略不计；4）机器人从相同的集合点出发，且各机器人完成任务之后回到集合点第2期王喜敏，等：基于混合算法的多机器人协作任务均衡规划研究2132算法介绍黏菌算法14（Slime Mould Algorithm,SMA）是一种基于种群的新启发式算法，基于黏菌在自然界中的觅食行为，类似于细菌觅食优化算法15 通过不断地移动和变化，筛选出通往食物的最短路径Nakagaki等16发现黏菌在迷宫中觅食，自由移动形成觅食路径，即迷宫问题的最优解 利用SMA算法参数少、寻优效果强的优点，以解决网络流、线性规划、路由和运输等问题17头脑风暴算法18（Brain Storm Optimization,BSO）与模仿生物遗传和觅食等群体行为的演化算法不同，模拟人类通过交流互动提出新方法的头脑风暴过程，能够在全局探索和局部开发之间达到较好平衡19本质是将不同知识背景的人聚集在一起，将具有同样或相似想法的人进行分组，选出各组的代表，在各组内部进行新想法讨论，是一种局部开发的过程；组间进行相互交流提出更广的新想法，是一种全局探索的过程 采用聚类20进行分组，在对应组空间内进行局部搜索获取局部最优值，在不同的组空间之间进行全局搜索获取全局最优值CMRTP问题中，执行任务的顺序是提高机器人系统执行效率的关键 第一阶段采用基于代价适应度值的改进K-means聚类技术进行任务分配 通过对代价适应度值进行聚类，不再局限于空间维度的限制，能够减少计算量 第二阶段采用了一种混合智能优化算法，基于SMA、BSO类内局部更新和类间全局更新个体方式、交叉操作和大规模邻域搜索操作进行更替方法，进行任务规划2.1多机器人协作任务分配任务分配的目标是根据机器人的使用情况，将任务集合通过分区、分组的方式分为不同区域，给机器人集合规划不同的任务子集合来完成任务 在给定任务空间维度x1,x2,xn，假设两个任务之间相似度可以通过其欧几里得度量来衡量，将相似点归为一类，同时将不相似的点区分开，首先需要假设类的个数k为已知的，并且同一个任务点只属于某一类 因此聚类的问题就是寻找k个不相交的非空集合S1,S2,Sk，且满足约束条件（公式(13)(15)）K-means算法目的是对所有任务点进行预处理，根据任务集合点的分布将任务分成m个簇，找出中心点作为优化算法的起始点，优化每个群 在这种情况下，该算法将一个大问题分解成几个子问题，并求出中心点，以降低问题的复杂度由于K-means传统思想是对数据点进行划分，即根据每个点的位置，k个节点作为聚类中心，计算每个节点与该中心节点距离，采用将节点分配到最近的中心点的思想进行划分，然而这样划分的结果导致划分不均匀，从而导致任务均衡性相对较低 为了保证多机器人完成任务过程中任务均衡，对任务区域内的任务成本代价适应度值进行聚类，这样能够减少问题的复杂度，如图1所示图 1适应度值聚类过程步骤1：初始化任务集合、机器人集合、相关参数；步骤2：随机生成初始种群，计算任务点之间的距离作为距离矩阵D（见式(1)）；步骤3：在种群中随机选择m个个体作为聚类中心，并计算该m个聚类中心的适应度值1；步骤4：计算种群中个体的适应度值1与m个聚类中心的适应度值取差值绝对值，选择差值绝对值最小的作为聚类中心，同时将当前个体归为此类；步骤5：计算类中个体适应度值的平均值，将类中适应度值与平均值最接近的个体定为新的聚类中心；步骤6：保证所有任务点分配到不同的类中，否则，重复步骤42.2多机器人协作任务重规划针对所有任务是否完成以及是否获得合理的规划方案，对当前任务规划结果进行分析，判断当前任务规划方案的合理性和可行性 针对何时重规划以及如何重规划问题，本文采用任务和目标期望值判断依据解决任务重规划的选择问题 在头脑风暴优化算法中，图 2任务重规划框图214新疆大学学报（自然科学版）（中英文）2023年对机器人内部任务进行大规模邻域搜索，开展任务局部重规划，获得局部最优值；对机器人之间的任务进行交叉操作搜索，开展任务全局重规划，获得全局最优值，以此解决重规划问题 任务重规划判断流程如图2所示重规划过程如图3所示图 3任务重规划过程图3（a）中机器人内部当前规划方案存在均衡性较差问题，进行局部重规划获得较优规划方案 图3（b）中机器人之间当前规划方案存在均衡性较差问题，进行全局重规划获得较优规划方案3多机器人协作任务均衡规划算法为获得多移动机器人协作任务分配结果并保证所有机器人的任务均衡，每个机器人需要完成多个任务和优化路线方案 将CMRTP问题转化为MTSP模型求最优解，优化最小化机器人最长路程为最佳路线方案，使得每个机器人所走的距离都较短，从而得到总路径相对较小和每个机器人所走路程均衡，达到任务均衡效果，再通过均衡度、差异度、偏差率进行综合评价均衡效果优劣3.1算法设计1）种群初始化：初始种群通常是随机生成的，但是在保证个体多样性的前提下，不能同时获得较优的收敛速度，将会出现算法寻优速度慢的问题 所以本文将黏菌算法进行迭代生成的初始种群进行计算适应度值1，保留排序较优的个体作为初始种群，减少算法的寻优次数2）交叉算子：根据CMRTP问题的特点设计算法，有利于改善算法的性能 引入交叉算子产生尽可能多的新个体，提高搜索能力 交叉操作在机器人内部的交流是一种局部开发的过程，在机器人之间进行交流是一种全局探索的过程 交叉操作就是将亲代种群的个体片段进行选择性交换、匹配部分基因，产生新的高质量个体，如图4所示图 4交叉操作3）大规模邻域搜索操作2122：remove移除算子操作中随机选取移除的路线个数，在相邻的路线中移除i个任务，从当前解中选择一个任务i对任务进行初次排序，选择第一个点 采用repair算子操作能够得到不同类型的解，提高了解的质量4）扰动算子：采用随机个体聚类中心替换的策略，计算适应度值，比较更新当前个体 大规模邻域搜索操作对当前方案进行扰动操作，选择最优适应度值1作为最优方案3.2算法实现基于混合算法的多机器人协作任务均衡规划算法如图5所示4实验与分析4.1实验环境与参数设置在Windows 10操作系统、Matlab2020a编程软件进行测试实验 每个实例运行20次以确保95%的置信区间，记录每个机器人的行走路线和行走距离 在不同机器人数量和任务数量下开展研究，通过均衡度、偏差率和差异度评估本文算法性能和任务规划效果 种群为50，迭代次数为600，概率参数为：z=0.03、Pone=0.5、Ptwo=第2期王喜敏，等：基于混合算法的多机器人协作任务均衡规划研究2151Pone、Ponecenter=0.3、Ptwocenter=0.3、initial=1、final=0 对遗传算法（Genetic Algorithm,GA）、蚁群算法2324（Ant Colony Optimization,ACO）、SMA算法解决多机器人任务均衡规划问题的规划结果进行对比图 5任务均衡规划算法4.2实例验证及结果为验证所提算法的有效性，本文在TSPLIB国际标准测试库中，选取了三个不同规模的实例，采用不同算法验证规划结果的均衡性，记录相关数据并对实验结果进行具体分析和比较 实例中列举了不同实例和机器人数量的变化，如表1所示表 1测试实例实例（n）机器人数量（m）eil51，eil76，eil1013，4，5，10实例eil101中3、4、5、10个机器人的任务规划优化结果如图6所示 图6（a）代表机器人和任务分布，蓝色方格为机器人位置，红色圆圈为任务位置以及任务的序号 图6（be）为任务规划结果，不同颜色代表不同机器人的任务以及完成任务过程中机器人完成任务的顺序由图6（e）可知，不同机器人完成的任务之间没有出现重复现象，说明每个任务只被一个机器人完成，同时展示出任务规划后的最优方案 可以获得机器人分配的任务完成顺序、任务数量以及成本代价，如表2所示根据10个机器人完成对应任务所需成本代价分别为112.487 5、113.202 5、109.504 9、109.965 6、113.701 4、109.615 9、106.780 0、112.756 4、110.212 9、109.710 1，得出本文改进算法的平均均衡度为9.69%、平均差异度为2.848%、平均偏差率为1.997%SMA算法的平均均衡度为14.059%、平均差异度为3.483%、平均偏差率为3.312%经比较分析，本文算法任务均衡规划结果均衡度相对提高，机器人之间的成本代价差异程度相对较小，任务成本代价相对平衡，保证了机器人之间任务的均衡性，表明本文算法在均衡机器人任务代价上具有较好的均衡性216新疆大学学报（自然科学版）（中英文）2023年图 6实例eil101的多机器人任务规划优化结果表 2实例eil101、机器人数量为10的任务规划结果机器人完成任务数量行走长度/m任务规划顺序111112.487 51605611644861784831852124113.202 51154314421310109.504 9131106219114964639030146109.965 6156236739412151113.701 41381615109.615 91762621737274752241572405853281710106.780 0151819713565662032701820112.756 4169896938591981003787979259999695941310127199110.212 91884736464588248711014109.710 1133379783429242555548068775014.3算法性能分析采用多个评估指标综合评价任务均衡规划结果的均衡性 机器人之间的行走距离的平均差异程度越小，其均衡性越好SMA、GA、ACO和本文算法在不同实例上的任务规划结果、记录机器人行走最长距离的最优值（m）和平均值（m）如表3所示SMA和本文算法任务规划结果的机器人团队总路径的最优值（m）和平均值（m）如表4所示 本文算法和SMA算法任务规划结果的平均偏差率PDav（%）、平均均衡度（%）和平均差异度CV（%）如表5所示 平均值25反映算法的平均优化精度，平均值越小证明算法的优化精度越好；最优值越小表示优化路径越短 平均均衡度和平均差异度CV越小，说明机器人之间行走路径相近，任务成本代价差异程度相对较小，任务均衡性越优，任务规划效果就越好 平均偏差率PDav越小，表明任务规划结果的机器人总行走距离相对误差越小4.3.1均衡性评估指标1）任务均衡度：=maxLiminLjmaxLi100%(16)第2期王喜敏，等：基于混合算法的多机器人协作任务均衡规划研究217其中：maxLi表示第i(i=1,2,m)个机器人的最长路程，minLj表示第j(j=1,2,m)个机器人的最短路程，i=j，m为机器人总个数2）平均偏差率：PDav=平均长度最优长度最优长度100%(17)其中：平均长度为20次独立运行所得最优解的平均值，最优解是已知最优解3）路径长度平均差异度CV26反映各机器人路径长度的差异程度：CV=路径长度平均差平均路径长度100%(18)4.3.2本文算法的收敛效果分析为了验证本文算法的收敛效果，给出3个实例中不同机器人数量完成不同任务数量的规划结果，本文算法和黏菌算法迭代到全局最优值的收敛曲线，如图7所示图 7不同实例的迭代收敛曲线图7（b）是实例eil101中机器人数量为4时的任务规划结果，收敛曲线的迭代早期为20时，本文算法约为195，而SMA算法约为200，前者起初找到全部最优值相对较优，所需要的迭代次数较少，收敛速度相对较快；本文算法寻得全局最优值为182.5，而SMA算法寻得全局最优值为184，精度提高约0.82%，可以得知本文算法在寻优精度方面效果较佳 图7（d）是实例eil101中机器人数量为10时的任务规划结果，本文算法在迭代次数100内寻得全局最优值，在较早的迭代过程寻得全局最优值为113.701 4，体现出较优的收敛速度，而SMA算法表现出陷入局部最优值的现象，寻得全局最优值为115.097 7，本文算法寻得全局最优值的精度提高约1.21%综上所述，本文算法在不同实例中的搜索效率具有不同程度的提高，相对SMA算法，本文算法收敛效果较佳，全局搜索效果较好 本文算法的收敛曲线均位于SMA算法的下方，在算法收敛早期快速搜索到全局最优值的迭代次数相对较少、最优值精度相对较高由表3可知，比较不同实例中机器人任务规划的最长路径，本文混合算法的最优值比SMA算法解的质量高不同实例中，本文算法收敛到全局最优值的过程中寻得全局最优值相对较优，而SMA算法迭代对应适应度值与218新疆大学学报（自然科学版）（中英文）2023年本文算法比较显出最优解的劣势 通过表4进行综合分析，改进算法不论最长路径最优值还是团队最优值都有不同程度提高 表4中本文算法最优解以及平均解都比SMA算法的解的质量高 结合表5中平均均衡度、平均差异度CV、平均偏差率PDav指标，可知本文算法的机器人总行走距离相对误差小，保证了算法解的均衡表 3机器人任务规划最长距离实例m本文算法SMAGAACO最优值平均值最优值平均值最优值平均值最优值平均值eil513159.571 5161.592 8165.824 8167.956 2218.691 7234.645 6175.400 0180.590 04129.945 4130.595 5132.138 3133.265 3187.332 0202.961 1167.180 0171.210 05118.539 6118.754 4124.276 0124.497 0159.293 3174.534 2128.720 0135.090 010112.071 4112.071 4112.071 4112.071 4118.386 1122.747 7112.450 0115.502 0eil763196.983 4203.406 5207.387 9214.563 8346.790 2365.545 2225.130 0233.560 04161.651 1163.510 6161.944 4164.562 8297.216 4312.747 5188.192 0191.252 05144.352 6146.255 6145.495 9147.524 6251.549 1268.486 2162.430 0224.560 010127.561 7127.561 7127.561 7127.561 7161.244 3175.071 4154.261 0156.124 0eil1013231.352 2236.434 3233.093 4240.269 1458.654 3481.676 1251.012 0253.132 04182.509 4183.515 9184.011 2185.114 5327.205 2369.177 6198.561 0203.492 05150.257 6153.626 5153.950 6156.595 2290.995 8315.603 3165.343 0171.457 010113.701 4113.927 5115.097 7115.327 5176.405 6201.232 5143.259 0151.399 0表 4机器人团队任务规划总路径实例m最优值平均值本文算法SMA本文算法SMAeil513474.667 0494.304 8481.230 8502.195 64517.354 3520.496 6519.281 9522.921 55581.521 6589.486 3587.020 0595.322 610898.568 31 020.705 0935.532 11 066.001 0eil763591.094 0621.065 2606.611 1639.619 34642.521 1637.096 5648.119 8645.234 15706.764 9719.451 6722.126 9735.623 0101 154.527 01 147.772 01 168.353 01 165.561 0eil1013690.442 6706.480 8703.965 2724.607 34721.230 1729.873 0728.231 6738.458 05742.769 5760.219 8759.280 6779.859 0101 073.859 61 094.897 01 095.306 91 131.159 0由表5可知，从平均均衡度分析，评估了最长行走距离和最短行走距离之间的差异，在任务数量较少安排机器人较少的情况下平均均衡度都在3%左右，机器人数量为5时，相对SMA算法提高了4%左右，均衡性相对较优；实例eil51-10中，机器人数量较多时平均在20%左右，本文算法在寻找最优任务规划效果上均衡性从31%降到28%，均衡性有所提高；实例eil101-10中，平均均衡度从14.059%降低到9.690%，最长行走距离和最短行走距离差距缩短，任务规划效果合理 从平均差异度CV分析，评估了机器人团队中所有机器人行走距离之间的差异程度，很好地展现了机器人之间的差距，从不同实例得出本文算法在实例eil51-10中提高6%左右，其它情况下提高1%左右，将所有机器人之间的差异程度降到相对较低，本文算法的平均差异度CV相比SMA算法更小，进一步保证了机器人之间良好的均衡性 从平均偏差率PDav分析，将所有机器人的整体效益进行对比，本文算法相比SMA算法具有更小的平均偏差率，说明更接近最优值，取得规划效果较佳SMA、GA、ACO、本文算法在不同实例中的任务规划结果和任务规划结果的机器人最大距离对比柱状图如图8所示；总距离对比柱状图如图9所示 图中不同颜色代表不同算法数据值：橘色柱形为GA、绿色柱形为ACO、紫色柱形为SMA、黄色柱形为本文算法第2期王喜敏，等：基于混合算法的多机器人协作任务均衡规划研究219由图8可知，黄色柱形的最大距离最优值最高点均位于其它算法的下方，说明比较后的最大距离相对较小，全局最优值相对较优，优化路线方案效果明显表 5均衡性评估指标实例m/%CV/%PDav/%本文算法SMA本文算法SMA本文算法SMAeil5131.8741.8830.5400.6601.3831.59642.6092.8310.5280.9540.3730.46652.9767.3611.1002.7750.9820.9901028.50031.3032.8489.3844.1144.438eil7631.2673.1120.6021.2632.6252.98841.7152.9350.6991.0540.8711.27753.0343.4120.9461.1852.1742.2481015.75516.8594.8294.9831.1981.550eil10131.0611.6850.3780.6501.9592.56642.0502.2760.6850.7310.9711.17652.5043.4830.8751.0602.2222.583109.69014.0592.8483.4831.9973.312图 8实例eil51、eil76和eil101不同算法最优值对比图 9实例eil51、eil76和eil101不同算法总距离对比由图9可知，黄色柱形与其它颜色柱形进行比较，总距离整体较低，总距离值相对较小，体现出本文算法在全局搜索方面的优越性 可以看出本文算法的机器人最长距离最优解要比其它算法的最优解较优；获得机器人团队总距离也小于其它算法的值 综上所述，改进算法的寻优效果优于其它比较算法，任务规划结果较优4.3.3任务规划结果的均衡性分析为了验证任务均衡性能的好坏，获取本文算法在不同实例中的最优均衡规划结果的路程分布如图10所示不同颜色代表任务规划中机器人的行走距离，进而计算每个机器人之间的行走距离的均衡度和路径长度平均差异度图10（a）代表实例eil51中机器人数量为3时，机器人1的行走路程为158.993 5，机器人2的行走路程为159.5715，机器人3的行走路程为158.236 2，平均均衡度为1.874%，路径长度平均差异度CV为0.540%，平均偏差率PDav为1.383%，机器人之间任务成本代价相对差异在2%以下，均衡效果与SMA算法相比有所提高 图10（b）代表机器人数量为10时的路径分布，平均均衡度为28.500%，路径长度平均差异度CV为2.848%，平均均衡度大的原因是任务数量少的情况下安排的机器人数量多，使得出现总体规划效果差的现象，通过路径长度平均差异度CV分220新疆大学学报（自然科学版）（中英文）2023年析，本文算法的路径长度平均差异度为2.848%，而SMA算法相对较高，均衡效果劣于本文算法，本文算法任务规划结果相对合理图10（c）代表实例eil101中机器人数量为10时，机器人1行走路程为112.487 5，机器人2行走路程为113.202 5，机器人3行走路程为109.504 9，机器人4行走路程为109.965 6，机器人5行走路程为113.7014，机器人6行走路程为109.615 9，机器人7行走路程为106.780 0，机器人8行走路程为112.756 4，机器人9行走路程为110.212 9，机器人10行走路程为109.710 1，平均均衡度为9.690%，路径长度平均差异度CV为2.848%，平均偏差率PDav为1.997%SMA算法中平均均衡度为14.059%，路径长度平均差异度CV为3.483%，平均偏差率PDav为3.312%，与本文算法比较相对较高，成本代价差异大，造成在机器人之间任务均衡效果不佳图 10实例eil51、eil101路径分布图5结 论在解决多移动机器人任务均衡规划问题中，为了使机器人的工作量相对接近，机器人之间任务均衡，同时提高机器人团体效益 本文在任务分配问题中采用基于适应度值的K-means聚类进行分类，减少了计算复杂度；利用黏菌算法三阶段搜索策略提高了求解问题的全局搜索能力，利用头脑风暴算法的机器人内进行局部更新操作和机器人间进行全局更新操作对任务子集合进行重规划，任务集合内进行任务规划，获取较优任务路线方案；采用交叉操作和大规模邻域搜索操作提高了该任务规划算法的全局搜索和局部搜索能力 实验结果表明：基于混合优化算法的任务均衡规划方法能够合理均衡规划多移动机器人系统中的任务和机器人，机器人之间的路径成本代价平均差异度相比SMA算法低，体现出成本代价之间的均衡效果较优，能实现多移动机器人的均衡规划，提升完成任务效率 所提出的算法在多移动机器人任务均衡规划问题中具有较好的均衡性参考文献：1卢厚清,王辉东,黄杰,等.任务均分的多旅行商问题J.系统工程,2005,23(2):19-21.2熊衍捷,高镇,李根.基于谱聚类的BaaS资源负载均衡调度算法J.重庆大学学报,2021,44(11):40-47.3毛科技,孙俊生,颜世航.一种能耗均衡的WSNs层次路由协议研究J.传感器与微系统,2020,39(1):18-21+25.4朱姗,张博,胡祥培.“一地多仓”型网上超市多品订单的拆分优化决策方法J/OL.中国管理科学,1-122022-01-17https:/doi.org/10.16381/ki.issn1003-207x.2021.0799.5姚泽玮,林嘉雯,胡俊钦,等.基于PSO-GA的多边缘负载均衡方法J.计算机科学,2021,48(S2):456-463.6董亚倩,杨帆,翟艺颖.考虑执行任务均衡的仓储多自动引导车路径优化方法J.制造业自动化,2021,43(12):62-65.7罗海峰.基于混合局部搜索方法的大规模车辆路由问题求解研究J.安徽职业技术学院学报,2019,18(2):5-8.8胡士娟,鲁海燕,黄洋,等.求解工作量平衡多旅行商问题的改进遗传算法J.计算机工程与应用,2019,55(17):150-155+231.9张硕航,郭改枝.多旅行商模型及其应用研究综述J.计算机科学与探索,2022,16(7):1516-1528.10VENKATESH P,SINGH A.Two meta