双焊接机器人协同路径规划研究*

张瑞星，李秀娟，高 唤

(河南工业大学 电气工程学院，郑州 450000)

0 引言

焊接是汽车生产的主要工艺之一，其质量的高低会直接影响车身的性能。白车身作为汽车其它零件的载体[1]共有上千个焊点，单机器人系统已经无法快速的完成如此复杂的焊接任务，因此双机器人系统得以迅猛发展。文献[2]针对双机同步焊接问题，引入虚拟焊点将多个旅行商问题(Multiple Traveling Salesman Problem，MTSP)转换为旅行商问题(Traveling Saleman Problem，TSP)，建立双机同步焊接模型；文献[3]针对白车身双机同步焊接路径规划问题，采用栅格法建立同步焊接模型。文献[4]通过对机器人动作节拍的设计优化以及双机的互索设计，完成了双机协同控制。文献[5]以双机对称焊接为例，提出了双机协调镜像运动的协调轨迹方法。

传统焊接路径规划大都是基于技术人员的示教操作，这种方法不仅周期长且很难得出最优路径。随着人工智能的迅猛发展，目前已经提出了许多智能算法并将其应用到焊接机器人的路径规划中。文献[6]以生产节拍为约束条件，采用遗传算法(Genetic Algorithm，GA)进行焊接路径规划。文献[7]提出了一种结合莱维飞行的粒子群算法(Particle Swarm Optimization，PSO)来求解焊接任务。文献[8]以最短无碰撞为焊接约束条件，提出遗传粒子群优化算法解决焊接机器人的路径规划问题。文献[9]以时间最短为约束条件，提出了遗传混沌粒子群优化算法来解决焊接机器人路径规划问题，能够快速的得到全局最优解。

蚁群算法(Ant Colony Optimization，ACO)是Marco Dorigo[10]提出的一种具有正反馈调节能力的启发式算法。针对该算法的存在的问题，学者们提出了很多改进方法。文献[11]提出了对传统蚁群算从概率计算、最优路径二次优化等方面进行改进，增强了算法的鲁棒性与快速收敛性。文献[12]在蚁群算法的启发函数中引入人工势场思想的引力系数和避障系数，提高了算法的收敛速度。文献[13]引入约束因子，改进信息素的更新规则，加强了算法的全局搜索能力。文献[14]提出一种基于蚁群的并行协同算法，通过使用3-opt算法避免陷入局部最优，增强了算法的全局搜索能力。文献[15]提出了一种新的增强信息素更新机制，增强了未使用过的信息素，利用动态信息进行路径优化，提高了全局搜索能力。

由上述分析可知，解决双机协同焊接的核心就是正确建立协同焊接模型，本文选择MTSP作为焊接的数学模型。改进ACO算法的主要方式是提升算法的收敛速度和全局搜索能力。本文针对ACO算法和PSO算法进行分析，提出了一种基于蚁群粒子群的融合算法求解MTSP问题。实验结果表明该算法对于求解组合优化问题能够得到更优解。

1 问题描述

对于多机协同作业，在不考虑焊接工艺的前提下，可将其抽象为MTSP问题。MTSP问题是指给定N个城市的集合，M个商人分别从各自所在的城市出发，每一个商人走一条线路，使得每一个城市有且只有一个商人访问过，最后商人们返回出发的城市，要求商人所走的路径之和最短。解决MTSP问题的核心思想是对待优化问题进行带约束条件的分组，令MTSP问题转化为一般的TSP问题。本文构建的TSP模型为：

(1)

其中，Ld为路径长度；di,i+1为城市间的距离。

2 融合算法

2.1 蚁群算法的原理与改进

2.1.1 基本蚁群算法

(2)

其中，ηij(t)=1/dij为启发函数；allowk为蚂蚁k未访问城市的集合；α为信息度浓度重要因子；β为启发函数重要程度因子。当蚁群完成一次循环后，城市之间的信息素将会更新，更新公式为：

(3)

(4)

其中，Q为常数；Lk为本伦循环最短路径。

2.1.2 蚁群算法的改进

由于未对信息素浓度阈值进行设定，当多次循环后，信息素会聚集在几条相对较短的路径上，这些路径不一定是全局最优，有可能是局部最优解。为避免上述问题的发生，本文针对蚁群算法的缺点，提出了一种基于灾变策略的最大最小蚂蚁算法(Catastrophe Max Min Ant，CMMA)，具体实现如下：

(1)增加信息素浓度的阈值。在初始时，设置信息素浓度的上限max_ph与下限min_ph；设置信息素的初始浓度τ0=max_ph。

(2)更改状态转移规则。设常数p0,若rand>p0则按照公式(3)更新，若rand

(5)

(3)加入精英蚁群思想。将上次循环中的最优路径替换掉本次循环中的最劣路径，使得优秀信息可以保留。

(4)改变信息素更新规则。每次循环只允许最优路径参与信息素更新，令当前最优与历史最优路径交叉参与，完成信息素的一次更新，新的信息素增量公式为：

(6)

其中，Lk_best为历史最短路径；N为当前迭代次数。本次循环找出最优路径的蚂蚁为第i只，以信息素矩阵的第i行为蓝本进行信息素阈值更新，通过阈值完成信息素二次更新，信息素阈值的更新公式：

(7)

(5)灾变操作。若连续C次历史最短路径未发生变化，则进行灾变操作，将信息素矩阵重置。

(6)若达到结束条件则停止循环，否则重复上述过程。

2.2 粒子群算法的原理与改进

2.2.1 基本粒子群算法

在M维的空间里，n个粒子组成粒子群X，X=(X1,X2,...,Xn),第i个粒子为一个M维的向量Xi，Xi=(x1,x2,...,xM),表示粒子在M维空间中的位置，即一个待优化问题的可行解。粒子Xi的速度为Vi；其个体极值为Pi,表示第i个粒子的历史最优值；粒子群的群体极值为Pg,表示当前粒子群中的最优值。

粒子群算法的核心思想是在每次循环过程中，通过个体极值与群体极值跟踪粒子的速度与位置，使粒子的位置不断向最优解靠近，计算公式：

(8)

其中，ω为惯性权值，决定当前粒子速度对下次粒子速度的影响程度；k为当前的迭代次数；c1、c2为属于[0,1]的常数，分别决定了当前个体极值与群体极值对下次粒子速度的影响程度。

2.2.2 粒子群算法的改进

粒子群算法与其他智能算法相比，有着收敛迅速这一鲜明特点，但是粒子算法有着诸多不足，其中最为突出的是无法解决离散问题与易“早熟”。为解决上述问题本文提出一种混沌粒子群遗传算法(Chaos Particle Swarm Genetic，CHPG)。

(1)生成混沌种群

常见的混沌映射有一维logistic映射、二维Henon映射、三维Lorenz映射等。其中logistic映射被广泛的使用，本文使用的就是logistic混沌映射，logistic混沌映射的更新公式：

Xn+1=Xnμ(1-Xn)

(9)

其中，X为(0,1)的随机数；μ为[0,4]的随机数。混沌种群的产生过程如下所示：

1)设问题规模n,随机生成一个可行解X，X=(x1,x2,...,xn)；

2)将X归一化，使结果映射到[0,1]之间，转换公式如下所示，其中ε为常数：

(10)

3)根据公式(9)，生成序列Z对应的混沌序列ZCH。将混沌序列中的元素按从大到小排序，此时混沌元素对应的标签组成的元素就是一个混沌粒子；

4)根据种群规模重复上述过程m次，即可得到种群规模为m的混沌种群。

(2)交叉、变异的融合

引入遗传算法的交叉、变异策略克服粒子群算法无法解决离散问题的缺点；引入混沌种群，通过多种群信息交换，克服粒子群算法“早熟”的缺点。具体实现过程如下所示：

1)种群交叉：设粒子群为pop1，混沌种群为pop2，将两个种群交叉生成新的种群child1、child2。若子代优秀则更新父代；

2)群体极值交叉：pop1、pop2分别与各自的群体极值交叉，生成新的种群child1、child2。若子代优秀则更新父代；

3)一次变异：对于pop1、pop2中的每个粒子，分别选择两个交叉位，交换交叉位上的元素，生成新的种群child1、child2，若子代优秀则更新父代；

4)二次变异：对于pop1，pop2中的每个粒子，分别选择两个交叉位，翻转两个交叉位之间的元素，生成新的种群child1、child2。若子代优秀则更新父代；

5)找出最短路径。找出上述child1、child2的群体极值，进行比较找出最短路径；

6)灾变操作。若连续C次历史最短路径未发生变化时，则进行灾变操作，即重新生成pop1、pop2两个种群；

7)若达到结束条件则停止循环，否则重复上述过程。

2.3 融合算法思想

融合算法(Chaos Ant Particle Genetic，CHAPG)的核心思想就是充分的利用蚁群算法的正反馈调节机制。令经过优化的路径参与信息素的更新，在正反馈调节的作用下，指导蚁群在下一次循环中建立优秀的可行解空间，具体的操作如下：

(1)初始化算法参数；

(2)在改进后的状态转移规则的指导下构建解空间pop1，依据上述混沌种群的生成规则，构建解空间pop2；

(3)分别计算pop1、pop2的群体极值；

(4)进行种群交叉、群体极值交叉、一次变异操作、二次变异操作；

(5)计算经过优化后的两个种群的群体极值，并找出最优解；

(6)对pop1进行精英操作，将上次循环中pop1的最优路径代替本次循环中pop1中的最劣路径；

(7)判断是否满足灾变条件，若满足则初始化信息素与pop2；否则，令经优化过的路径参与信息素的更新，在改进后的信息素增量规则的指导下更新信息素，完成信息素一次更新，更新信息素的阈值，利用阈值再次更新信息素，完成信息素二次更新；

(8)若达到结束条件则停止循环，否则返回到步骤(2)继续循环。

3 算法的设计与仿真

3.1 算法设计

根据上述算法的工作原理，本文所提出的算法流程图如图1所示。

图1 CHAPG算法流程图

3.2 MATLAB 仿真与分析

为验证本文所提出CHAPG算法的有效性，在TSPLIB标准库中选择不同样本进行验证，与ACO、CMMA、CHPG算法的结果进行对比，得到的验证结果如表1～表3所示。

表1 Eil51试验结果

表2 Eli101试验结果

表3 Ch150实验结果

图4 双机器人焊接工作站

上表中分别列出了4种算法在不同样本集下运行10次结果。在不同样本试验中，ACO算法与其他3种算法相比，均陷入了局部最优，无法进行全局搜索；CMMA算法取得了较好全局最优解，但是搜索时间过长；CHPG在最优解与搜索时间上取得了较好的结果，但是算法的鲁棒性较差；CHAPG算法在5种指标中均取得了较好的结果，体现出了CHAPG算法良好的性能。试验表明CHAPG算法在处理不同规模数据时均拥有良好的全局搜索能力与快速收敛能力。

4 双机协同

对于双焊接机器人系统，不仅需要最短路径为准则，还需要增加一些约束条件，确保焊接的同步性，具体做法如下所示。

图5 焊点可达性分析

(1)根据焊点数据与机器人TCP之间的欧氏距离的大小进行焊点的初次分配。S1、S2分别为焊点到与机器TCP距离的集合，若S1

(2)分别计算出R1、R2对应的焊接距离L1、L2，计算L1与L2之间的差值，若小于常数D则跳出循环，否则继续。

图2 协同算法流程图

图6 干涉性检查

(3)S12为R1的TCP到n2的距离由小到大的集合，S21为R2的TCP到n1的距离由小到大的集合。若L1>L2，则将S21中最小值对应的焊点添加到n2中；若L2>L1，则将S12中最小值对应的焊点添加到n1中，完成焊点的更新，否则，跳转到(2)继续循环。

根据上述算法的工作原理，本文所提出的协同算法的流程图如图2所示。

5 ROBCAD仿真

5.1 双机器人路径规划

以某汽车白车身一侧为例，共192个焊点；CHAPG算法的参数设置如下：m=192，n=50，α=1，β=5，θ=0.1，设置迭代次数为200，在MATLAB中进行仿真实验，得到的路径如图3所示。

图3 双机器人路径规划(mm)

5.2 建立三维模型

将在CATIA中建立的白车身数模，导入ROBCAD中；将焊点数据导入在白车身上；在ROBCAD中建立双机器人工作站，如图4所示。

5.3 焊点可达性分析

将导入的焊点映射到白车身这一过程中，焊点自身的坐标系是随机生成的，标准的焊点坐标系是z轴垂直向上，x轴是向着焊枪的方向。对于点焊机器人来说，由于关节角的限制，机器人都有着自己的工作空间，因此必须通过ROBCAD的Spot模块进行可达性分析，如图5所示，当焊点坐标的x轴在蓝色区域则表明该机器人可以到达该焊点，当在红色区域时，则表示无法到达该焊点。依次调整焊点坐标系，确保每一个焊点都在对应机器人的工作空间。

5.4 机器人干涉检查

对于多机器人协同路径规划，一般都会存在干涉情况，因此需要通过使用ROBCAD中的Collision Setup模块进行干涉检查，找出发生干涉的位置。对于大多数发生干涉的位置，只需要通过调整焊点的坐标系或者机器人的姿态就可以。如图6所示，x轴的方向朝向车身，当焊枪进行焊接时会与车身发生干涉，旋转焊点坐标系，使焊点的x轴离开车身。对于一些特殊情况，不能通过上述方法进行调解时，可以通过增加过度焊点的方法解决。适当的增加过渡焊点，可以使焊枪避开工件或夹具。

6 结论

利用焊点与机器人TCP之间的欧式距离关系将焊点进行分配，将MTSP问题转换为TSP问题，依靠焊接路径之间的关系不断更新焊点，确保多机器人协同工作的同步性；在ACO算法中加入精英思想，改变状态转移规则与信息素更新方式，增加了算法的全局收缩能力；引入混沌总群，加入GA算法的进化思想，提高了算法的快速收敛能力。通过MATLAB的实验验证，本文所提出的CHAPG算法在求解组合优化问题时比ACO算法、CMMA算法、CHPG算法、CHPG算法具有更佳的效果。在ROBCAD平台上进行双机器人协同焊接仿真实验，解决了可达性与干涉性等在实际应用中存在的问题，提高了焊接效率。