基于多种群遗传算法的多机器人路径规划

周红勋

（湖北汽车工业学院机械工程学院 湖北省十堰市 442002）

随着机器人技术的日趋成熟，生产厂家为了保证产品质量、缩短生产周期，纷纷采用以机器人为核心的柔性生产线（简称机器人工作站），如在汽车白车身焊装生产线上，焊接机器人几乎分布在各个工位，它们相互协同完成焊接任务。为了更好的让机器人为人类服务，如何合理布局各工位上的机器人、分配各工位机器人的焊接任务以及优化各机器人的焊接路径（即多机器人路径规划）便成为机器人领域研究的热难点问题。文中默认机器人布局已经完成，只讨论多机器人路径规划问题，即在满足若干约束条件的前提下，以时间最短和系统安全性为基本目标，对每台机器人进行焊接任务分配以及无碰撞焊接路径优化。这是一个错综复杂的问题，其中涉及的参数变量多、不稳定且相互耦合，因此大多数学者采用粒子群算法、蚁群算法等智能算法来研究,但由于这些算法在解决此问题时本身存在不足之处，故它们规划的结果还有可提升的空间。国外Joon-woo lee 等人为避免蚁群算法在求解时陷入局部最优，对蚁群算法进行异构改进，但仍存在实时性不理想等不足。在前期遗传算法(genetic algorithm, GA)对单台机器人路径规划研究的基础上，为弥补它在进行多机器人路径规划时早熟收敛、对交叉变异参数敏感以及未能准确体现机器人之间的相互协作关系等不足，文中采用多种群遗传算法(multi-population genetic algorithm,MPGA)来求解。MPGA 先把研究的种群分为多个相对独立的子种群，再把GA 并行的应用到各子种群且采用不同的控制参数同时进化，并且进化过程中引入移民和人工选择两种算子，最后将MPGA、GA 分别用于某焊接工位上多机器人的路径规划仿真实验，从而对比验证MPGA 的可行性和优越性。

1 问题描述以及模型建立

多机器人最优焊接路径规划要为每台机器人进行焊点任务分配并找到一条最优或者次优的焊接路径，以保证所有机器人无碰撞完成各自所分配的焊接任务后所花费的时间最短或者所运动的总路程最短,这一规划过程要受到诸如焊接工艺、焊点分组方式、生产节拍以及机器人属性等若干因素的约束，此处为了便于建模，降低问题的复杂度，忽略部分因素，从而把焊接任务分配问题简化为多背包问题，即把n 个焊点的集合W={W,W,W,…,W}分配给m 台机器人的集合R={R,R,R,…,R}，使每台机器人无碰撞焊接完自己所有焊点所运动的总距离之和尽量小。用数字0 和1 来表示焊点与机器人的所属关系，X=1 表示焊点i 由机器人j 焊接，反之，则不是，D表示焊点i 与机器人j 之间的距离，则焊点分配多背包问题的目标函数M 为：

2 基于MPGA的路径规划

MPGA 是一种改进智能算法，通过将GA 引入到数个相对独立的子种群中进行同步优化搜寻的思想来提升进化效率，各子种群采用不同的遗传进化控制参数来克服算法对交叉、变异算子取值敏感的不足。每当各子种群进化一定代数时（一般取代数2），目标种群中的最差个体就会被移民算子从源种群里选中的最优良个体所替代，以此来体现各子种群之间的相互协同关系。各子种群在进化过程中每一代最优秀的个体会被人工选择算子挑选出来组成一个新种群，里面个体不再进行任何遗传进化操作。为了弱化MPGA 对进化代数的依赖，采用更为科学合理的算法停止进化判据，即以新种群中最佳个体最少不变代数作为判定算法终止依据。MPGA 将GA 并行的用于各子种群，用它们替代父种群进行协同搜索最优值，其求解多机器人路径规划步骤为：

2.1 编码

将焊点分配问题进行参数化并使用二进制编码，用数字0 和1 组成的n×m 维矩阵来表示焊点与机器人的所属关系；针对单台机器人路径优化，采用整数编码方式，即编码数列直接代表机器人的焊点焊接顺序。

2.2 初始化各子种群

为了能够快速的得到比较典型的高质量种群个体，采用随机挑选初始种群个体的形式，并把其随机分成10 个大小相同的相对独立的子种群。

2.3 设定适应度函数

在基于二进制编码的前提下，为避免各台机器人被分配到不合理的焊点，此处采用惩罚函数法来等效上述约束条件对多机器人系统中焊点分配问题的影响，则焊点分配问题的适应度函数Q 为：

2.4 选择操作

采用轮盘赌的选择方式，即个体被选上的概率取决于其适应度值的大小，它的值越大，说明个体越优秀，被选中的概率越大，故把适应度函数的倒数作为个体的适应度值。

2.5 交叉、变异操作

交叉算子、变异算子分别是各子种群产生新个体的首要因子、辅助因子，取值大小分别影响多种群遗传算法的全局、局部搜索能力，它们在各子种群中的取值不一样。对于焊点分配，采用单点交叉、单点变异操作；对于单台机器人路径优化，采用两点交叉、两点变异操作，且这两种操作都只在新个体适应度值优于旧个体时才更新个体 。

2.6 移民操作

各子种群在进化过程中产生联系的操作，是MPGA 不同于GA 的重要之处。每隔一定代数，用种群1 中最优个体替换种群2 中最差个体，……，种群10 中最优个体替换种群1 中最差个体。

2.7 人工选择操作

它把各子种群进化过程中每代最优秀的个体挑选到精英种群中加以保存并不再进行任何进化操作。同时判断精英种群中最优解是否达到最少保持代数，如果达到，则程序结束，解码并输出路径规划结果；反之，则重新从步骤（4）处执行，直至符合进化停止条件为止，流程图如图1 所示。

图1： MPGA 流程图

3 仿真实验结果分析

以某一焊接工位为例，此工位需要将99 个焊点（见附件）分配给4 台机器人进行焊接，另外Home1(900,-150,0)、Home2(2100,-150,0)、Home3(2100,1300,0)、Home4(900,1300,0) 分 别 为 机 器 人Robot1、Robot2、Robot3、Robot4 末端执行器的初始位置。对于MPGA：代沟、子种群个数、种群大小分别取0.9、10、1000，交叉以及变异概率分别在区间[0.7,0.9]、区间[0.001,0.05]随意生成，最优个体至少保持10 代；对于GA：代沟、种群大小、迭代次数、交叉概率、变异概率分别取0.9、1000、500、0.9、0.05。在MATLAB 中分别编写两种算法的路径规划程序并将仿真实验进行100 次，由仿真实验结果可知，MPGA 每次得到的结果一样，而GA 每次运行的结果基本都不一样。为了便于两者的比较，分别选择其中焊接路径之和最短的一次作为各自路径规划的最优解。表1 是两种算法的多机器人路径规划最优分配方案，图2、3 分别为两种算法最优解变化图，表2为两种算法路径规划结果的对比。由表1 可知，GA 最优路径规划分配给Robot1、Robot2、Robot3、Robot4 机器人的焊点数分别为25、22、25、27；MPGA 最优路径规划分配给Robot1、Robot2、Robot3、Robot4 机器人的焊点数分别为23、22、27、27。

表1： 两种算法的多机器人路径规划最优分配方案

表2： 两种算法路径规划结果

图2： GA 最优解变化图

图3： MPGA 运行3 次的最优解变化图

单从焊点分配均匀、无碰撞等方面来说，两种算法的分配结果都满足，但由于焊点多的机器人所需焊接的时间长一些，为了使四台机器人能够尽快同步协同完成焊接任务，就必须保证焊点少的机器人运动路径长一些，且各台机器人的焊接距离相差不大。由表2 可知，MPGA 规划得到的方案走过的总路径最优值较小，且任务分配更合理，更加利于机器人同步完成焊接任务。

由图2、3 以及表1、2 知，MPGA 提高了路径规划的进化效率，能够快速得到十分稳定的结果，7-12 代之间便可以搜寻到最优解，GA 在150 代左右才能搜索到最优解，且基于MPGA 所得的规划结果总路径长度平均值和最小值，都比GA 要小。

由上可知，在多机器人的路径规划方面，MPGA 在搜索速度、稳定性、路径长度等方面都比GA 具有优势，能提供更优的规划结果。

4 结论

（1）把GA 并行的应用到各子种群且采用不同的控制参数同时进化，能动态调整改进算法的局部和全局搜索能力；

（2）引进人工选择算子来挑选保留各子种群每代进化过程中的最优个体，并作为判断算法是否继续进化的依据更为科学；引进移民算子能保证最优解的获得是各子种群共同进化的结果；

（3）MPGA 在求解多机器人路径规划问题上具有显著优点，能够迅速、精确的找到更合理的解，相对于GA 能将进化搜索到最优解所需的代数至少缩减90%、路程最小值缩减2.14%。