基于改进蚁群算法的打磨机器人路径规划

蔡改贫，陈永康，周小云，李宇达，曾常熙

(江西理工大学机电工程学院，江西赣州 341000)

0 前言

打磨机器人是从事打磨加工的工业机器人，在机器人的末端安装抓取工具，进行运动控制，使抓取的工件可以到达并固定于刀具的特定位置，根据工件打磨形状的需要，机器人抓取工件进行相应的轨迹运动，完成工件弧形曲面的加工。打磨机器人路径规划目的是在空间环境中按照一定的规则，规划出由起点到终点用时最短或最光滑的路径，有利于深入研究机器人应用领域。

自20世纪以来，路径规划技术的研究已经取得了许多重要成果。许多二维路径规划建模方法沿用至今，如网格法、拓扑法、可见图法等。随着轨迹规划领域不断发展，出现了更多复杂的路径规划算法，如Dijkstra算法、Prim算法、模拟退火算法、蚁群算法、A算法、人工势场法和模糊逻辑控制算法，它们在工程实践中得到了广泛应用。其中，蚁群算法是一种分布式智能仿生算法，主要模拟蚁群在寻找食物过程中协同合作搜寻最佳路径的过程，搜寻过程具有正反馈性、并行性及较强的鲁棒性等优点。蚁群算法已广泛应用于车间调度、旅行规划、网络路由、机器人路径规划、电力系统、聚类分析、数据挖掘和图像处理等领域。在机器人路径规划领域，LEE等利用遗传算法优化蚁群算法参数，实现动态路径规划。邱莉莉和郑建立改进信息素初始化和状态转移概率，但该方法只能降低蚂蚁陷入死锁的可能性，不能完全避免死锁的发生。赵华东等提出相应的死角表，当蚂蚁陷入死锁时，可以使用罚函数来更新轨迹。

基于以上分析，根据打磨机器人工作方法的有效性和实时性的要求，针对具体打磨机器人的构型，对机器人进行D-H建模分析，再进行运动学分析与验证。针对路径规划问题，通过改进蚁群算法的信息素更新方法，将新的自适应计算方法应用于状态转移规则中，并通过引入阻尼系数改进启发式信息函数，在MATLAB中进行模拟实验，寻找到一条最优路径，验证该方法的可行性。

1 打磨机器人运动学分析

1.1 正运动学模型分析

当需要确定机器人在空间中的位置关系时，可以在机械手的三维空间中固定一个坐标系，然后分析该坐标系的原点位置与、、轴的位置关系，即建立D-H坐标系，分析得出各个连杆D-H参数；从第一个关节开始依次进行变换，直到最后一个关节被确定，这样就确定了机械手的总变换矩阵。图1所示为打磨机器人结构简图，图中右侧为打磨刀具。

图1 打磨机器人模型简图

各关节D-H参数如表1所示。

表1 各关节D-H参数

(=1,2,…,6)表示各个关节的D-H矩阵，则得出运动学方程如下：

(1)

其中：、、分别表示机械手末端坐标系的3个坐标轴上的单位向量投影到基座坐标系的方向余弦;表示末端坐标原点在基座坐标系的坐标值。

(2)

1.2 逆运动学分析

(3)

(4)

其中：

=sin=cos

=-[(+)-(-)]-

(-)

=[(+)-(-)]-

(-)

=-(+)-(-)

=-(+)-[(+)+

(-)]

=(+)-[(-)+

(+)]

=[(-)+(+)]+

(+)

=(+)-(-)

=--(-)-[(-)-

(+)]

令式(4)左右两边(2,3)和(2,4)元素对应相等，则有-=和-=。解该方程组得tan=(-)(-)，得的表达式为

=arctan[(-)(-)]

(5)

(6)

=-=

(7)

(8)

(9)

(10)

其中：

=sin(+)=cos(+)

=++-+

=cos==sin=

验证过程：设连杆参数=300 mm、=320 mm、=400 mm，并设6个关节角度均为30°，从而由运动方程求解得：

(11)

则可得、、、、、、、、、、、，将各数据代入各关节角度表达式，使用MATLAB得计算结果：=30004 9°、=30010 3°、=20931 3°、=29999 8°、=30006 4°、=30006 6°。

2 改进蚁群算法的路径规划

2.1 三维环境建模

路径规划中传统的环境建模方法包括可视图法、单元树法和二维栅格法，此类栅格法可推广到三维空间中。本文作者采用山峰式环境模型模拟机器人工作环境，将真实的机器人三维环境用抽象的山峰图形表示。为简化蚁群算法路径规划，以机器人自身基坐标系为基础，建立环境模型坐标系-。

实验环境是Window 10系统、MATLAB 2016a、RobotStudio6.0、英特奔腾CPU 1.70 GHz,内存12 GB,64位操作系统。图2所示为机器人工作环境，将工作空间中的其他设备与障碍物以山峰代替。如图3所示，在MATLAB 2016a中绘制立体抽象的山峰图形模拟机器人的工作环境。(0～100 km)轴表示经度方向距离，(0～100 km)轴表示纬度方向距离，(0～2 500 m)轴表示海拔高度。地形中的非平面部分可以理解为障碍物，凸起的曲面障碍物为斜坡，凹陷的曲面障碍物为沟渠。

图2 机器人工作环境

图3 三维环境模型

2.2 蚁群算法介绍

(12)

其中:是下一节点集合；()是路径(，)的信息素值；是信息素激励因子;是期望的启发式因子。启发式因子计算公式：

(13)

式中：为节点到目标节点的欧氏距离。

局部信息素会在蚂蚁搜寻下一个节点时进行更新：

(+1)=(1-)()

(14)

式中:()表示信息素在离散点(，，)上的浓度值；表示更新的次数；(0<<1)为全局信息素更新系数。

2.3 改进蚁群算法

利用蚁群算法进行路径规划时，要找到全局最优路径，搜索空间必须足够大，而且该算法搜索机制具有较强的不确定性，特别是在初始阶段，随机搜索使得它不可避免地产生大量的局部交叉路径、圆形路径和锯齿形路径，得出的规划曲线并不能达到预期的效果。对此，作出如下改进：

(1)改进信息素更新规则

当蚂蚁利用公式(14)完成局部信息素更新后，加入全局信息素更新，在已完成搜索的路径中，只更新最短路径中节点的信息素，减少信息素更新时所需的时间，提高了搜索效率。全局信息素更新规则如下：

(+1)=(1-)()+Δ

(15)

(16)

式中：()表示三维环境中离散点的信息素浓度；{()}表示蚂蚁(=1，2，…,)搜索的路径长度集;为常数。

(2)改进状态转移规则

为提高搜索效率和算法质量，采用伪随机状态转移规则。设蚂蚁在时位于节点，则在+1时的位置为

(17)

式中：为过渡比的基准速率,在(0，1)范围内；为一个随机数。

当<时，下一个节点直接由信息素浓度的最大值和启发式信息的实现决定；然后，采用轮盘赌方式确定节点。具体实现过程：根据公式(17)计算出所有允许路径的转移概率，将转移概率从大到小排序，用轮盘赌选择方法确定下一个节点。

(3)改进启发式信息函数

基本蚁群算法的启发式信息值与下一个节点到目标点的距离呈反比，但是在不考虑当前节点和下一个节点位置的情况下，选择的路径不一定是最短的，在搜索后期，为加快收敛速度，应该弱化启发式信息对路径选择的影响。为此，提出一种改进启发式信息函数的方法，通过引入阻尼系数，新的启发式信息函数如式(18)所示：

(18)

(19)

其中:为当前节点与下一节点之间的欧氏距离；为最大迭代次数；为当前迭代次数。

2.4 改进蚁群算法步骤

(1)参数初始化。初始化初始点位置、目标点位置、迭代次数、蚂蚁数、信息素启发式因子、期望启发式因子、全局信息素更新系数和阻尼系数。

(2)开始迭代，进行路径探索。发动蚂蚁开始正向搜索，根据公式和轮盘赌法选择下一个路径点。

(3)局部信息素更新。当蚂蚁搜寻到某一个点时，先进行局部的信息素更新，进而判断当前蚂蚁是否进入死锁状态。死锁状态时返回上一节点，更改下一节点位置；非死锁时进入下一步骤。

(4)路径搜索。根据伪随机状态转移规则确定节点后，蚂蚁持续进行搜索，最终判断当前蚂蚁是否完成路径搜索，若当前蚂蚁完成路径搜索，则下一只蚂蚁开始进行搜索。

(5)全局信息素更新。当所有蚂蚁完成搜索后，需要找到该迭代过程中所有完整路径中的最优路径和最差路径，并根据公式加强最优路径上的信息素以及减弱最差路径上的信息素。

(6)搜索结束。判断是否满足结束条件，如果满足，则输出最佳路径；否则继续循环执行，直到满足结束条件或达到最大迭代次数时终止。

图4 改进算法流程

3 仿真结果与分析

3.1 算法参数的选择与分析

蚁群算法中的参数选择对路径规划的效果有很大影响。仿真中采用经验和实验相结合的方法，通过设置不同的参数进行仿真实验，并分析实验结果的优缺点，选择最佳参数组合。当蚂蚁数量过多时，会削弱信息素浓度的影响。而当算法收敛速度过快时，则将削弱算法对全局搜索能力的影响。因此，在仿真实验中，在保持其他参数不变的情况下，不断比较和分析不同蚂蚁数量得出的仿真运算结果，最终设置蚂蚁数=100。

、是算法的重要参数，是信息素激励因子，反映信息素浓度对路径选择的重要性，是期望的启发式因子，反映启发式信息对路径的重要性。当大于时，经验因素占主导地位，蚂蚁可能重复行走路径，进而削减搜索的随机性；当小于时，确定性因素占主导地位，蚂蚁急于综合选择路径成本最小的路径，无法实现全局最优。同样，全局信息素更新系数和阻尼系数直接关系到全局搜索能力和算法收敛速度。在实际情况下，、、和不是独立的，而是相互影响、综合作用的。因此，通过尝试各种组合模拟，并分析所得结果，最终设置参数为=1、=6、=05、=0.8。

3.2 基本蚁群算法与改进蚁群算法的比较仿真

打磨机器人通常运用于大型工件的打磨，并且在实时环境中随时需要避开障碍物。因此,在抽象的山峰图形中模拟机器人的环境进行仿真实验时，采用2种蚁群算法对2组不同的初始点和目标点进行实验，并分析仿真结果。在实验1中设置初始点为(0 m，42 km，570 m)，目标点为(100 km，39 km，600 m)；在实验2中设置起始点为(20 km，0 m，530 m)，目标点为(33 km，100 km，730 m)。图5—图8所示为基本蚁群算法和改进蚁群算法的路径规划水平。

图5 实验1基本算法路径

图6 实验1改进算法路径

图7 实验2基本算法路径

图8 实验2改进算法路径

可以直观地看到:改进的蚁群算法路径更短，轨迹曲线更平滑。为对仿真结果作出更全面的分析，分析最佳路径长度与迭代次数的关系，结果如图9—图12所示。

图9 实验1基本算法最短路径长度变化曲线 图10 实验1改进算法最短路径长度变化曲线

图11 实验2基本算法最短路径长度变化曲线 图12 实验2改进算法最短路径长度变化曲线

实验1中,基本蚁群算法在迭代26次时得到最佳路径长度145 km，改进蚁群算法在迭代10次时得到最佳路径长度115 km，相比基本蚁群算法，改进蚁群算法迭代次数减少了61.5%，路径长度减少20.7%。实验2中，基本蚁群算法在迭代53次时得到最佳路径长度128 km，改进蚁群算法在迭代27次时得到最佳路径长度118 km，改进蚁群算法相比基本蚁群算法,迭代次数减少了49.1%，路径长度减少7.8%。由上述数据可知，改进后蚁群算法的最短路径长度平均减少了14.3%，迭代次数平均减少了55.3%。

由2组实验结果可以看出，最佳路径关系曲线迅速下降到某个最佳值后，迭代次数增加，最佳路径长度不变，曲线呈水平趋势。结果表明：改进后的蚁群算法能够在有效避开障碍物的同时缩短迂回路径；与此同时，搜索策略的改进有效提高了算法搜索能力。该方法可行、有效，具有重要的实际应用意义，可用于打磨机器人的路径规划。

4 结论

为解决打磨机器人在复杂环境下的路径规划存在收敛速度慢、准确性低等问题，运用改进蚁群算法进行路径规划。根据打磨机器人的实际结构建立了其运动学连杆模型；对其进行正逆运动学分析并验证，改进信息素更新规则，缩短信息素更新时间，从而有效提高效率；采用伪随机状态转移规则，将轮盘赌方式确定节点作为新的自适应计算方法，加快收敛速度进而弱化启发式信息对路径选择的影响；通过引入阻尼系数改进启发式信息函数。在MATLAB中进行模拟实验，得出最佳参数组合，利用基本和改进蚁群算法进行仿真实验，得出不同运动路径。结果表明：与基本蚁群算法相比，利用所提出的改进蚁群算法能够得到更短更平滑的运动路径，最短路径长度平均减少了14.3%，迭代次数平均减少了55.3%；结合打磨机器人刀具位置等特点，可以获得一条路径最短且平滑的规划曲线，满足打磨机器人实际应用需求。