增加方向性信息素的改进蚁群路径规划算法

陈继清，莫荣现，谭成志，刘 旭，王志奎

（1.广西大学 机械工程学院，广西 南宁 530004；2.广西制造系统与先进制造技术重点实验室，广西 南宁 530004）

0 引言

移动机器人是集监测传感、动态决策、路径规划、行为控制和执行为一体的复杂智能控制系统。它的“智能”主要体现在机器人在运动过程中是否具有良好的环境交互能力，这一能力主要指路径规划能力。对路径规划的研究可以追溯到20 世纪60年代，经过几十年的研究和发展，大量优良的算法被提出，如A⁃star 算法、人工势场法、模糊控制算法等传统算法和蚁群算法、鱼群算法等仿生智能算法。其中，蚁群算法因为鲁棒性强、易与其他算法结合、能并行运算等优点被广泛用于解决移动机器人的路径规划问题。从20 世纪90年代提出至今，无数专家和学者对其进行改进，使蚁群算法成功应用在不同的行业。如文献[8]利用蚁群算法来优化生产车间的运输效率，有效地节约能源和降低生产成本；文献[9]提出一种作业路径生成算法和蚁群算法相结合的改进蚁群算法，并应用在无人机植保方面，有效缩短了无人机的搜索路径等。

然而，蚁群算法也有易受参数影响、收敛速度慢、易陷入局部最优解和前期路径有效性差等缺点。根据文献[10⁃11]和蚁群算法程序可知，蚁群算法在找到可行路径前，每个栅格的信息素浓度都相等，蚁群算法根据转移概率公式随机地选择可行栅格，这可能会出现蚁群算法搜寻远离目标点的方向，从而增加搜索时间和加大陷入局部最优解的概率。此外，文献[10]提出的蚁群算法前期的路径有效性差；文献[12⁃13]提及的蚁群算法的收敛速度慢和搜索时间长。为了解决这些问题，本文提出一种改进的蚁群算法。

1 改进蚁群算法描述

蚁群算法的改进包括两个部分：第一个部分是提出一种方向性信息素，该信息素与目标点方向的夹角有关，越靠近目标点方向信息素浓度越大，反之则越小。引入方向性信息素可以减少蚁群算法前期的盲目搜索，缩短搜索时间、减少转折点数量和蚁群算法陷入局部最优解的概率。第二个部分是提出一种针对方向性信息素的蒸发函数，该蒸发函数能减少前期方向性信息素浓度的蒸发，使蚁群算法更快速地搜索到可行路径，进而缩短搜索时间，减少迭代次数；而后期能加快方向性信息素浓度的蒸发，减少方向性信息素浓度对原有信息素浓度的影响。

1.1 方向性信息素

根据蚁群转移概率公式（1）可知，蚁群算法在没有信息素残留的初期，每个方向的概率是一样的，因而每只蚂蚁会随机选择搜索方向，这可能导致蚂蚁选择与目标点方向相反的路径进行搜索，增加了前期的搜索时间，可能使搜寻的路径长度陷入局部最优解。为了解决这个问题，本文提出一种方向性信息素。方向性信息素与偏离目标点方向的夹角有关，当偏离目标点方向的夹角在0°～180°时，夹角越小，方向性信息素的数值越大；当偏离目标点方向的夹角在180°～360°时，夹角越大，方向性信息素的数值越大。

本文将方向性信息素和蚁群算法原有的转移概率公式结合起来，通过方向性信息素浓度限制蚁群算法前期对偏离目标点方向的搜索，从而避免蚁群算法陷入局部最优解和减少搜索时间。带有方向性信息素的转移概率公式前期大概率会选择靠近目标点方向的路径，减少前期盲目搜索的时间。

为了设计出满足要求的方向性信息素函数，本文分两步：第一步是确定选取基本函数种类和确定递增递减关系，得出函数的大概轮廓；第二步是利用实验的方法将函数中特殊位置的坐标求出，然后利用插值的方法求出最终函数。

首先确定选取基本函数种类和递增、递减关系。方向性信息素函数与偏离目标点方向的夹角有关，因此选取三角函数cos和sin作为基本函数。其次，偏离目标点方向的夹角为0°～360°，且当偏离目标点方向的夹角在0°～180°时，夹角越小，方向性信息素的数值越大；当偏离目标点方向的夹角在180°～360°时，夹角越大，方向性信息素的数值越大。为了方便函数拟合，本文规定当偏离目标点方向的夹角为180°时，方向性信息素大小为0。由此可知，方向性信息素函数在0°～180°递减，在180°～360°递增，在夹角为180°时方向性信息素大小为0。第二步，做如下实验：分别在偏离目标点方向夹角为0°，45°和90°时加入等梯度的方向性信息素，求出0°，45°和90°的最优路径长度对应的方向性信息素；然后，利用函数拟合的方法求出方向性信息素的函数表达式。方向性信息素的取值范围为[0，1.6]，步长为0.1。蚁群算法的基本参数为：=1；=8；=1；=0.6；=200；=50。

方向性信息素的大小和算法最优路径的关系如图1 所示。

图1 三种夹角的方向性信息素与最优路径的关系

从图1 可以看出：偏离目标点方向夹角为0，加入方向性信息素的值为1.4 时，算法路径最短；同理，夹角为45°和90°，加入方向性信息素分别是1.2 和0.7 时，路径最短。

0°，45°和90°与360°，325°和270°是对称的，且当夹角为180°时的方向性信息素浓度为0。因此，可以通过上述求出的7 个点拟合出方向性信息素的函数。拟合结果如下：

式中为偏离目标点方向的夹角。拟合的函数图像如图2 所示。从图2 可以看出，方向性信息素函数是连续的，蚁群算法的搜索方向越靠近目标点方向，方向性信息素的数值越大。而由蚁群转移概率公式可知，蚁群算法在初期阶段向每个方向搜索的概率是一样的，如果加上方向性信息素，那么靠近目标点方向搜索的概率会变大，避免了前期蚁群算法其他非必要方向的搜索，可大大缩短搜索的时间；同时还可以避免路径长度陷入局部最优解，因为方向性信息素的限制使蚁群算法朝着目标点方向搜索的概率增大，而朝着目标点方向搜索的路径长度最优。最后，增加方向性信息素的蚁群算法还可以增加前期路径的有效性，因为前期蚁群算法是没有目标点方向的盲目搜索，所以搜索的方向是随机的，只有小部分路径能“幸运”地到达目标点，且路径长度不是最优。而增加方向性概率的蚁群算法开始就有目标点方向的指引，能到达目标点的概率增大且路径长度比蚁群算法要短，因而前期的路径有效性增加。

图2 方向性信息素函数图像

方向性信息素在前期可以减少蚁群算法的搜索时间，提高算法的效率。但方向性信息素不会随着迭代次数改变，而残留的信息素不断蒸发，导致残留信息素浓度比方向性信息素浓度小，最后使蚁群算法寻路失败或陷入局部最优解。为此，需要引入一种适合的蒸发函数。该蒸发函数前期需要减少方向性信息素的蒸发，使改进的蚁群算法能快速找到可行路径，避免局部最优解和缩短时间；而后期则加快方向性信息素的蒸发，避免方向性信息素的浓度影响新增的信息素浓度，从而影响蚁群算法最优路径的搜索。

1.2 针对方向性信息素的蒸发函数

为了发挥方向性信息素前期的作用，避免后期方向性信息素对新增信息素的影响，需要合适的蒸发函数来调节每次迭代后的方向性信息素浓度。本文列出蚁群算法的蒸发函数，通过分析该蒸发函数来确定方向性信息素的蒸发函数。蚁群算法的蒸发函数如下：

式中：是蒸发系数；是迭代次数；τ(0) 表示信息素的初始浓度，一般为8。

原始的蒸发函数不能满足方向性信息素前期减少蒸发而后期加快蒸发的要求，因此本文对原有的蒸发函数进行改进，假设方向性信息素蒸发函数的表达式如下：

式中：τ(0) 是方向性信息素的初始浓度；是待确定的系数。因为方向性信息素要在前期路径的选择中占主导作用，所以方向性信息素的初始浓度要比信息素的初始浓度高。其次，为了加快后期方向性信息素的蒸发，方向性信息素的蒸发函数要比蚁群蒸发函数更快递减。根据上述两个条件不难得出，τ( 0 )>τ( 0 )=8 且>1。

为了求出系数和方向性信息素的初始浓度τ( 0 )，本文设计如下实验：设置等梯度实验求出改进蚁群算法路径长度和迭代次数最优时的初始方向性信息素浓度τ( 0 )和系数。初始方向性信息素浓度τ( 0 )的取值范围为[8，10]，梯度步长为1；系数的取值范围为[1，2.5]，梯度步长为0.1。初始方向性信息素浓度为8，9，10 时，系数与路径长度、迭代次数的关系如图3图5 所示。

图3 初始浓度为8 时a 与路径长度和迭代次数的关系

由图3 可知，当初始浓度为8、系数为1.8 时，算法路径长度最短，为42.183 8，迭代次数为76 次；由图4 可知，初始浓度为9、系数为1.9 时，算法路径长度最短且迭代次数最优，分别为42.183 8 和51；由图5 可知，初始浓度为10、系数为1.2 时，算法路径长度最短且迭代次数最优，分别为42.183 8 和49。通过上述实验可知，当初始浓度取10，系数取1.2 时改进蚁群算法路径长度和迭代次数最优，所以方向性信息素的蒸发函数表达式如下：

图4 初始浓度为9 时a 与路径长度和迭代次数的关系

图5 初始浓度为10 时a 与路径长度和迭代次数的关系

式中，方向性信息素的初始浓度τ( 0 )为10，系数为1.2。

引入方向性信息素蒸发函数可以减少算法初期方向性信息素浓度的蒸发，使蚁群算法大概率向目标点方向搜索，减少非必要方向的搜索，从而减少搜索时间；而后期则加快方向性信息素浓度的蒸发，减少对残留信息素浓度的影响。

1.3 改进的蚁群算法转移概率公式

式中，为当前节点前进方向与目标节点的夹角。

由公式（6）可以看出，改进蚁群算法的转移概率公式由两部分组成，前面的部分是原有的转移概率公式，后面的部分是方向性信息素和对应的蒸发函数。原有的转移概率公式在开始阶段由于没有残留信息素，所以向每个方向搜索的概率相同，而方向性信息素越靠近目标点方向数值越大，所以前期蚁群算法的搜索方向由方向性信息素决定，且大概率向目标点方向搜索。而后期方向性信息素比残留信息素蒸发快，所以后期方向性信息素对蚁群算法搜索方向的影响变小，防止蚁群算法受方向性信息素的影响而无法收敛或陷入局部最优解。

图6 是改进蚁群算法的程序流程。首先初始化所有参数；然后开始循环迭代次数和蚂蚁个数，根据转移概率选择搜索节点并修改禁忌表；所有蚂蚁搜索完成便更新原始信息素和方向性信息素，再开始下一次迭代，直到迭代次数完成；最后输出最优解并结束程序。

图6 改进蚁群算法的程序流程

2 仿真分析与对比

为了验证改进蚁群算法的性能，将改进蚁群算法、原始蚁群算法和文献[10]算法进行仿真分析，仿真地图采用30×30 的随机栅格地图，障碍比为0.2，机器人的起点坐标为（0.5，29.5），终点坐标为（29.5，0.5）。三种蚁群算法的随机地图对比结果如图7 所示。

图7 30×30 障碍比为0.2 的随机地图对比

为了对比改进算法和原始算法、文献[10]算法的性能，本文列出路径长度、搜索时间、迭代次数的对比，如表1 所示。

表1 三种蚁群算法对比

从表1 可知，相比原始蚁群算法，改进算法所需的迭代次数更少，路径长度也更短。迭代次数变少是因为方向性信息素可以减少前期的盲目搜索，使蚁群算法能更快速地搜索到可行路径；路径长度变短是因为方向性信息素可以避免蚁群算法陷入局部最优解。文献[10]的算法在路径长度、搜索时间优于原始蚁群算法，但路径长度和搜索时间都比本文算法更长，因为该算法只规定了核心区域的信息素减少蒸发，蚁群算法会大概率在核心区域搜索，但没有指向目标点方向的信息素，无法保证蚁群算法以最短的路径向目标点方向搜索，所以路径长度更长、搜索时间也更久。

此外，图7b）中改进算法的收敛曲线比原始蚁群算法更快速地达到平滑，震荡幅度更小。由表1 可知，改进的蚁群算法性能要比原始的蚁群算法更好，路径长度缩短了3.15%，迭代次数减少了50.74%，搜索时间缩短了14.19%；相比文献[10]的算法，本文算法在路径长度上缩短了1.87%，在搜索时间上减少了6.79%，在迭代数上减少了45%，本文算法在搜索时间和路径长度上优于文献[10]的算法。

3 实验分析

本文用TurtleBot2 机器人来验证改进蚁群算法的性能。TurtleBot2 是一种开放式的机器人平台，最大的移动速度为0.7 m/s，最大的转向速度为180（°）/s。为了提高测试的精度，设定TurtleBot2 的线速度为0.2 m/s，角速度为30（°）/s。构建环境地图的传感器是RPLIDAR A1 激光雷达。实验场地选在实验楼楼梯口处，场地尺寸为6 m×5.5 m，用Rplidar A1 构建楼道2D 地图。改进的蚁群算法寻路结果和原始的蚁群算法寻路结果如图8 和图9 所示，选用的栅格尺寸为0.3 m×0.3 m。图8 中的黑色区域表示障碍物区域，粉紫色为可行区域，青蓝色为膨胀区域。机器人的起点和终点都相同，从图8 和图9 中可以看出，改进的蚁群算法路径更平滑，距离障碍物边界更远，减少发生碰撞的风险。为了更方便地比较改进蚁群算法的性能，本文将两种算法的寻路时间和路径长度进行对比，对比结果如表2 所示。

表2 两种算法寻路时间和路径长度的对比

从图8和图9可以看出，改进的蚁群算法可以用于机器人的路径规划，且相比传统的蚁群算法，改进的蚁群算法搜寻的路径更平滑，距离障碍物边界更远。从表2 可以看出，改进的蚁群算法在运行时间和路径长度上都优于原始的蚁群算法，在路径长度上缩短了4.27%，在运行时间上减少了4.53%。因此，本文认为改进的蚁群算法能用于机器人的路径规划，且比原始的蚁群算法更优。

图8 改进的蚁群算法寻路结果图

图9 原始的蚁群算法寻路结果图

4 结语

针对蚁群算法中存在搜索时间长、收敛速度慢和容易陷入局部最优解等问题，本文提出一种改进的蚁群算法。第一个改进的部分是引入方向性信息素，该信息素可以减少蚁群算法前期的盲目搜索，降低蚁群算法的搜索时间，避免蚁群算法陷入局部最优解。第二个部分是提出针对方向性信息素的蒸发函数，使改进的蚁群算法减少前期方向性信息素的蒸发，加快可行路径的搜索；而后期能加快方向性信息素的蒸发，使改进的蚁群算法更快收敛，避免方向性信息素对新增信息素的影响。仿真结果和机器人实验结果表明，改进的蚁群算法在路径长度、迭代次数和搜索时间上相比蚁群算法和文献[10]的算法有明显的提升。后续工作是将改进的蚁群算法和局部规划算法结合起来，使机器人能适应动态的实验环境。