基于能量惩罚的多机器人任务分配优化方法

朱良恒，梁利东，贾文友，苏学满

基于能量惩罚的多机器人任务分配优化方法

朱良恒，*梁利东，贾文友，苏学满

（安徽工程大学机械工程学院，安徽，芜湖 241000）

针对多机器人任务分配中存在的能量消耗不均衡问题，提出了基于能量惩罚策略的遗传算法完成任务分配与任务序列的优化过程。首先，建立多机器人任务分配的数学模型，每项任务设定不同的难度系数，以机器人完成任务所消耗的总能量为优化目标，并确定安全能量的约束条件；然后在每次迭代中通过计算每个机器人相对平均能耗的超额进行能量惩罚以寻求能量均衡的最优解。仿真实验表明，在总能量消耗最低的寻优中有效提高了各机器人的能量平衡性。

多任务分配；遗传算法；能量惩罚

0 引言

近年来，机器人在越来越多领域得到广泛应用，对于解决复杂的多任务问题，单机器人已不能满足实际应用的需求，因此多机器人系统已成为近年来的研究热点和发展方向[1]。多机器人任务分配( Multi-Robot Task Allocation，MRTA) 是多机器人系统中重要的一部分，伴随着任务难度与机器人数量的不断增多，解决多机器人任务规划问题涉及数值计算方法和最优化理论，具有一定的研究意义和使用价值。

多机器人任务分配是将系统中多个任务分配给多机器人执行，以完成任务总时间最短、总消耗能量最优以及任务完成度最优等为目标[2]。近年来智能算法已广泛用于求解MRTA问题，如遗传算法[3]、蚁群算法[4-7]、蜜蜂算法[8-9]，布谷鸟搜索算法[10]等，其中文献[4]在传统蚁群算法中求解多机器人任务分配，收敛速度慢且易于陷入局部最优问题的基础上加入了局部优化的变异算子以及加入改进的模拟退火算法，仿真结果表明能够很好的解决任务分配中的问题；文献[10]利用改进的布谷鸟搜索算法可以根据任务的位置点信息，找到最佳的机器人位置以此来解决多机器人任务分配及路径规划的问题。这些方法分别从不同方向对多机器人任务规划问题进行探究。集中式分配和分布式分配是任务规划的主要方法，集中式任务分配模型包括多维旅行商模型[11]、多维动态网络流优化模型[12]、多维多选择背包问题模型[13]以及相关模型的改进，其中文献[11]利用模拟退火算法解决多旅行商中城市约束问题。分布式任务分配模型主要有博弈论模型[14]，拍卖算法模型[15]等。

以上算法通常仅针对最优消耗能量来解决任务分配问题，并未考虑到多机器人的能量均衡问题，因此本文基于遗传算法引入能量惩罚策略求解多机器人能量均衡的最优解，并通过仿真实验证明算法的有效性和可行性。

1 问题描述及数学模型

任务规划问题是指分配出最优或近似最优的任务的顺序与数量，使得每个机器人从起点开始执行分配给自己的任务总消耗能量是近似最少的，但是可能会出现多机器人消耗能量值差异较大的情况。因此在数学模型中加入了惩罚机制，可保持总能量最优的基础上控制每个机器人能量消耗趋于均衡，以方便对机器人和设备的统一维护。

1）机器人的数量约束

为表现机器人依次执行任务，因此要求每个机器人执行多个任务且每个任务只需被一个机器人执行，可表示为：

Q= 1或Q= 0

Q= 1表示第个机器人执行第个任务；Q= 0则表示不执行此任务。

机器人的序号。

任务的序号。

2）任务数量约束

4）机器人执行任务的运动距离

4）机器人所消耗的能量

A：每单位距离所消耗的能量，本文假设机器人均为匀速运动即为定值。

5）安全能量约束

安全能量为了保证机器人在完成执行任务后，确保能顺利安全的回到初始点，故预留安全能量，具体表示如下：

6）目标函数

文献[16]在传统遗传算法的基础上结合惩罚函数的方法根据系统超出量构造新的目标函数，解决由于目标函数设计不当造成系统反应速度慢和不稳定的问题。将系统的超出量作为惩罚项加入目标函数中，惩罚函数构造复杂，而且惩罚因子是连续变化的。本文与文献[16]相比则根据每个机器人消耗能量超出平均值的机制来构造惩罚能量，并设定一个可调整超出误差阈值，能在总能量消耗最优的基础上轻松达到多目标平衡，构造相对简单，可实施性更高，更贴切实际情况。

为保证各机器人的能量消耗趋于均衡，本文以消耗总能量和惩罚能量之和最小作为优化目标，表示为：

：能量百分比。

2 遗传算法求解MRTA问题

2.1 基本遗传算法描述

遗传算法(Genetic algorithm,GA)是一种按照自然界适者生存、优劣淘汰的遗传机制演化的随机性搜索算法，其主要特点表现为：直接对对象进行操作，具有较好的全局搜索能力；采用概率化的搜寻方法，能够自动获得和指引优化的搜索空间，自适应调整搜索的方向，不需要特定的规则[17]。目前遗传算法已经应用到组合优化，车辆调度与自适应控制方向，文献[18]采用连续权重平均法的遗传算法解决选择公交车道和公交信号优先控制的优化模型，文献[19]提出量子遗传算法求解含有配送时间与车辆承重约束的动态车辆调度模型，求出了车辆最优路径。本文应用遗传算法优化策略改进目标函数模型，求解出多任务分配在能量消耗最优的基础上保证各机器人能量消耗平衡。

2.2 编码方法

2.3 适应度函数

以最优能量值与能量惩罚值之和作为适应度函数。当适应度函数值越小时，种群越好，越易于遗传到下一代，适应度函数为：

当进行每一次迭代计算时，个体超出平均值后将给予能量惩罚，超出的越多，惩罚力度也会越大，使得每个机器人消耗能量向平衡角度发展。

2.4 选择算子

选择算子运算根据轮盘赌来选择，每个个体被选择的概率与其适应度函数值成反比。

适应度函数的值越小，说明这个种群被选择的概率越大，说明这个种群比较好，这组解中多机器人消耗的总能量低并且能量消耗也比较均衡。

2.5 交叉算子和变异算子

交叉运算和变异运算中每个个体是由任务的数量和任务的序列号组成。选择两个父体进行交叉运算，将父体中深色与浅色染色体片段交叉来构成下一代以此来提高种群的多样性。具体操作过程如图1所示。

图1 交叉操作过程结果图

变异运算是随机选出一个父代，根据变异运算概率和随机选择变异基因位置，使得机器人的任务数量和序列号得以改变，假设变异运算选择深色部分的基因型变异。变异操作过程结果如图2所示。

图2 变异操作过程结果图

2.6 算法实现

本文算法的主要步骤：

Step1：初始种群以及参数设置；

Step2：计算适应度函数值，并分析个体的优劣；

Step3：计算迭代一次每个机器人消耗的能量，并计算平均值，并根据惩罚机制计算惩罚能量；

Step4：计算目标函数值及每个机器人的能量标准差（用于分析能量消耗的均衡程度）；

Step5：在当前群体中选择较优个体遗传到下一代；通过交叉和变异操作产生新个体构成下一代种群，继续进行迭代；

Step6：重复Step2～Step5的步骤，达到要求的迭代次数，从中选出一个最优解并输出多机器人的任务数量和任务序列。

具体流程图如图3所示。

图3算法流程图

3 仿真实验

实验环境如下：软件采用Matlab R2019a，硬件包括：电脑设备名称戴尔G3 3590；处理器Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz；机带RAM8.00 GB；系统类型64 位操作系统, 基于 x64 的处理器。

实验1：3个机器人任务规划仿真结果

3个机器人执行任务数量及任务序列号仿真结果如图4所示，图5为多机器人消耗能量和总能量曲线图。具体实验运行参数结果如表1所示。

图4 3个机器人执行任务数量和序列图

图5 3个机器人消耗能量和总能量曲线图

表1 3个机器人本文算法与基本遗传算法运行参数比较

Table 1 Comparison of operation parameters between three robot algorithms and basic genetic algorithm

算法E1E2E3总能量标准差 本文算法220.1245.0204.6669.720.4 基本遗传算法174.6308.1218.1700.868.1

数据结果表明：加入惩罚机制遗传算法的总能量消耗相比未加入惩罚机制的总能量降低了4.4%，标准差也减少了70.0%。可见惩罚机制不仅能让系统消耗的总能量降低，而且使每个机器人消耗的能量也相对均衡。

实验2：4个机器人任务分配仿真结果

图6为4个机器人执行任务数量和任务序列号仿真结果，图7为多机器人消耗能量和总能量曲线图。算法运行参数结果比较如表2所示。

图6 4个机器人执行任务数量和序列图

图7 4个机器人消耗能量和总能量曲线图

表2 4个机器人本文算法与基本遗传算法运行参数比较

Table 2 Comparison of operation parameters of four robots and basic genetic algorithm

算法E1E2E3E4总能量标准差 本文算法180.4174.1181.1151.7687.313.8 基本遗传算法110.5140.8271.7197.7720.770.9

通过对比加入惩罚机制消耗的总能量比未加入惩罚机制消耗的总能量减少4.6%，标准差也相比较低了80.5%。仿真结果证明基于惩罚机制的遗传算法能够有效的解决总能量消耗最优及能量不均衡问题。

实验3：本文算法与文献[16]算法仿真比较

为验证本文算法与文献[16]中算法的性能差异，采用5个机器人，30个任务点，且遗传算法中参数设置均相等进行仿真验算。5个机器人消耗能量和均衡性比较如图8所示。

图8 5个机器人消耗能量和总能量曲线图

从图中可以直观看出本文算法在迭代平稳时消耗的总能量较低，且5个机器人消耗的能量曲线更集中，说明本文算法性能优于文献中的算法。具体运行的参数如表3所示。

表3 5个机器人本文算法与文献算法运行参数比较

Table 3 Comparison of operation parameters between algorithms in this paper and those in literature for five robots

算法E1E2E3E4E5总能量标准差 本文算法141.6148.1145.091.9120.1646.723.6 文献算法98.7165.1152.0126.6157.3699.727.2

4 结论

本文采用能量惩罚机制的遗传算法对多机器人任务分配进行研究，考虑到以消耗总能量为目标函数分配任务时可能会导致每个机器人消耗能量不均匀的情况，所以在数学模型的设计上加上超出消耗能量平均值的惩罚机制，使得多机器人在执行任务消耗总量最小的基础上再让每个机器人消耗的能量尽可能的均衡。从仿真结果来看此机制能够很好地解决这一问题。

[1] 李功捷. 基于智能优化的仓储机器人任务分配研究[D].哈尔滨:哈尔滨工业大学,2013.

[2] Chopra S，Notarstefano G，Rice M，et al. DistributedVersion of the Hungarian Method for a Multi-robot Assignment[J]. IEEE Transactions on Robotics,2017(99) :1-16.

[3] 朱明哲,孙丙宇.基于遗传算法的工厂仓储系统多AGV调度策略研究[J].电子技术,2021,50(1):33-37.

[4] 秦新立,宗群,李晓瑜,等.基于改进蚁群算法的多机器人任务分配[J].空间控制技术与应用,2018, 44 (5): 55-59.

[5] 刘瑞轩.张永林.基于改进蚁群算法的多自主式水下机器人任务分配[J].中国舰船研究,2018,13(6):107-112.

[6] 段勇,王宇,喻祥尤.基于免疫遗传算法的多机器人环境探索[J].沈阳工业大学学报,2018,40(3):299-303.

[7] 冯珊珊. 基于适应度与蚁群分散搜索的多机器人任务分配[D].郑州:郑州大学,2018.

[8] 田微. 基于动态粒子蜜蜂算法的群机器人任务分配方法研究[D].长春:吉林大学,2017.

[9] 朱范炳. 基于蜂群算法与聚类的多机器人探索优化研究[D].郑州:中原工学院,2018.

[10] 谢永盛,曾箫潇,冯文健.改进布谷鸟搜索算法在多机器人任务分配及路径规划中的应用[J].计算机应用与软件, 2021, 38(2):285-290.

[11] 梁星星,马扬,冯旸赫,等.面向多旅行商问题的多目标模拟退火算法研究[J].南京师大学报:自然科学版,2017 ,40 (3):80-86.

[12] 万路军,姚佩阳,税冬东,等.多编组任务分配动态优化模型及IVFSA算法求解[J].电光与控制, 2014, 21 (5): 43-49,57.

[13] Duenas A, Martinelly C D, Tincgy. Amultidimensional multiple-choice knapsack model for re-source allocation in a construction equipment manufac-turer setting using an evolutionary algorithm[J]. IFIP Advances in Information ＆ Communication Technology,2016,438: 539-546.

[14] Kanakia A,Tourib, Correll N.Modeling-multi-robot task allocation with limited information as global game[J]. Swarm Intelligence,2016,10 (2) :147-160.

[15] Luo L,Chakraborty N,Sycara K. Provably-good distributed algorithm for constrained multi-robot task assignment for grouped tasks[J]. IEEE Transac-tions on Robotics,2015,31(1) : 19-30．

[16] 高兴泉,黄东冬,丁三毛.惩罚函数结合遗传算法的PID参数优化[J].吉林化工学院学报,2021,38(3):57-60.

[17] 梁肖,周湘贞. 基于遗传算法的小麦收割机路径智能优化控制研究[J].农机化研究,2018,40(2):56-60.

[18] 卢小林,潘述亮,邹难.公交专用道选址与公交优先控制组合优化模型[J].上海交通大学学报,2017,51(7):846-854.

[19] 陈潇. 基于云平台的物流配送车辆调度系统[D].西安:西安科技大学,2020.

MULTI ROBOTS TASK ALLOCATION OPTIMIZATION METHOD BASED ON ENERGY PENALTY

ZHU Liang-heng,*LIANG Li-dong, JIA Wen-you, SU Xue-man

School of Mechanical Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China）

In order to solve the problem of energy consumption imbalance in task allocation of multi robots, a genetic algorithm based on energy penalty strategy is proposed to optimize task allocation and task sequence. Firstly, the mathematical model of task assignment of multi robots is established. Each task is set with different difficulty coefficients. The total energy consumed by the robot to complete the task is the optimization goal. The constraints of the safety energy are determined. Then, in each iteration, the energy penalty is performed by calculating the excess energy consumption of each robot to find the optimal solution of energy balance. The simulation results show that the energy balance of each robot is effectively improved in the optimization of the lowest total energy consumption.

multitask assignment; genetic algorithm; energy penalty

1674-8085（2022）02-0088-06

TP242

A

10.3969/j.issn.1674-8085.2022.02.014

2021-09-07；

2021-11-26

安徽省教育厅科学技术研究项目（KJ2019A0147,KJ2018A0102）

朱良恒(1994-)，男，安徽淮北人，硕士生，主要从事智能计算与优化设计研究(E-mail:zhu_liangheng@126.com)；

*梁利东(1972-），男，山西忻州人，副教授，博士，主要从事计算机辅助设计制造及信息工程等研究(E-mail:mark_liang2003@126.com).