基于混合算法的多机器人协作任务均衡规划研究_王喜敏.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（