自适应避障蚁群算法的移动机器人路径规划

刘双双，詹京吴，黄宜庆*

(1.高端装备感知与智能控制教育部重点实验室，安徽 芜湖 241000；2.安徽省电气传动与控制重点实验室，安徽 芜湖 241000)

路径规划一直都是移动机器人领域的重点研究对象，在存在障碍物的环境里，机器人需要从中找到从起点到目标点的最短路径。机器人在行进中不能碰撞到障碍物，要求路径规划出的路线安全以避免碰撞，距离最短以降低机器人的能耗。

在机器人的路径规划方法里，传统方法有人工势场法、Dijkstra算法、A*算法等。随着移动机器人工作环境变得多样化，一些传统方法无法满足其在复杂环境中的运行要求，而智能算法的出现克服了传统方法的不足。目前，大多数移动机器人的路径规划采用智能算法，如蚁群算法、粒子群算法、人工鱼群算法等。其中，蚁群算法由于其算法收敛较快、算法的性能好和鲁棒性强等长处被普遍应用。

传统的蚁群算法搜索时间较长，收敛速度慢，并且容易出现算法停滞不前的问题，因此，许多科研工作者提出了改进的方法。如精英蚂蚁系统、最大-最小(MAX-MIN)蚁群系统、自适应蚁群算法。文献[10]在算法中建立了局部的信息素扩散模型，改进了启发函数以及信息素挥发因子，提高了算法的收敛速度。文献[11]用曼哈顿距离来替代欧式距离作为距离计算方法，引入了方向角启发因子，增大了选择当前节点和下一节点的方向向量与下一节点和终点的方向向量夹角小的路径的概率，提高了算法的效率。文献[12]将A*算法的估计函数结合到蚁群算法的启发因子里，并改进了信息素挥发因子，使得蚁群算法在收敛性和寻优路径上均有所提升。文献[13]在启发函数中加入当前节点与下一节点的距离，并用Laplace分布对信息素挥发因子进行了改进，防止算法陷入局部最优，并加快了收敛。文献[14]提出在算法前期加入避障策略，利用优质蚂蚁更新原则指导信息素的更新，并对得到的路径进行二次规划，使得到的路径更优，提高机器人的运行效率。

针对传统蚁群算法易陷入局部最优、收敛慢等不足，研究对传统的蚁群算法进行改进。首先，在状态转移概率公式中添加避障因子，减少蚂蚁搜索路径的过程中陷入死锁的数量，用曼哈顿距离替代欧式距离进行节点间的距离计算，减少在开平方之后取近似值而带来的误差影响，加快计算速度。然后，改进信息素挥发因子，使其从定值变为随迭代次数变化的动态值，并限定信息素的范围，避免算法停滞。经过仿真的结果对比，改进的蚁群算法收敛比传统的蚁群算法快，在复杂地图中也能进行高效合理的路径规划。

1 移动机器人环境建模

移动机器人的运行环境具有多样性和一定的复杂性，因此，若进行路径规划，环境模型的建立要符合实际环境情况。研究中的移动机器人在平面上运行，采用栅格法构建地图模型,在栅格地图中，机器人可自由通过的区域用白色栅格表示，障碍物用黑色栅格表示，机器人不可通过黑色栅格区域。机器人只被允许从当前所在的栅格移动到与该栅格相邻的8个栅格，规模为10*10的栅格地图如图1所示。由图1可知，起点和终点即为移动机器人的起点和终点，若机器人此时在栅格i，相邻的栅格共有8个，序号1～8标记。其中，2号栅格和3号栅格为障碍物，则移动机器人下一步可以到达的栅格只有1号以及4～8号，并且每个栅格仅可以通行一次。

图1 栅格地图

(1)

当所有蚂蚁完成一次路径搜索后，每条路径上的信息素量都要进行更新。更新的方式如式(2)所示：

τ

(

t

+1)=(1-

ρ

)·

τ

(

t

)+

Δτ

,

(2)

式中,

ρ

(0<

ρ

<1)是路径上的信息素挥发系数；1-

ρ

是信息素的持久系数；

Δτ

描述此次搜索过程里所有蚂蚁遗留在节点

i

到

j

的路线上的信息素量，即

(3)

(4)

其中，

Q

为常数，通常设为1;

L

表示第

k

只蚂蚁在此次路径搜索中行走路径的长度。

2 自适应避障(AOA)蚁群算法

研究在蚂蚁的状态转移概率以及信息素挥发因子上进行改进。为减少蚂蚁在前期搜索过程中向远离终点的方向前进的概率，只在以起始点和终止点为顶点的栅格地图区域设置初始信息素，其初始值为

τ

，用来减少蚂蚁盲目的搜索次数，提高收敛速度。

2.1 引入避障因子的状态转移概率

在蚁群的初期搜索过程中，信息素浓度和启发信息的值都较小，对蚂蚁选择下一步前进节点的引导作用很小。因此，蚂蚁搜索范围较大，搜索出的路径容易产生交叉现象，再加上禁忌表以及地图障碍物陷阱的影响，蚂蚁容易陷入死锁，无法到达终点。不仅如此，死锁蚂蚁遗留下的信息素信息会误导后面的蚂蚁也陷入死锁状态，严重影响算法的运行。

为避免上述情况的出现，根据人工势场法的原理加入障碍物斥力思想，提高蚂蚁避开障碍物陷阱的能力，蚂蚁将倾向于选择周围障碍物更少的节点。在状态转移公式里引入安全避障因子。该避障因子设为

χ

，其计算公式为：

(5)

式中，每个栅格节点有8个在蚂蚁移动步长范围内的相邻栅格，其中，

A

表示除去被禁忌表限制以及障碍栅格外的所有可行栅格。

经过改进的状态转移概率公式为：

(6)

式中，

ε

表示避障因子的相对重要程度，取值根据地图的复杂程度决定，是一可变参数，通常取值为一个小的正数。增加了避障函数后，蚁群算法的迭代速度加快，蚂蚁陷入死锁的数量大大减少。除此之外，对于启发因子

η

(

t

)，用曼哈顿距离替代欧式距离进行节点间的距离计算，减少计算开平方的时间，也减少在开方后取近似值的误差。启发因子

η

(

t

)计算公式为：

(7)

式中，

i

为蚂蚁当前所在的栅格；

j

为蚂蚁前进的下一栅格位置。

2.2 自适应信息素挥发因子

自然界中，在蚂蚁寻找路径并不停释放信息素的过程中，信息素也会以一定的速率挥发掉，该速率被称为信息素挥发因子。传统算法里，信息素挥发因子

ρ

的取值范围为(0,1),表示信息素的蒸发程度，它实际上反应的是蚁群中各个蚂蚁个体之间相互影响程度的强弱。当

ρ

过小时，蚂蚁更加倾向于选择之前行走的路径，这样会对算法进行全局搜索的能力造成影响，如果这条路径不是最优路径的话，就造成算法收敛在局部，只能得到次优路径。当

ρ

过大时，路径上残存的信息素量相对较低，虽然可以加强蚁群全局搜索路径的能力以及搜索的随机性，但是无用搜索的增多会影响算法的收敛速度。因此，

ρ

如果为定值，算法的适应性会较差。改进信息素挥发因子

ρ

，使其从定值变为随时间变化的动态值，根据算法的运行状况自适应地改变信息素的持久性系数，不但可以加速算法的收敛，还可以增大搜索到全局最优路线的概率。改进的信息素挥发因子计算公式为：

(8)

式中，

ρ

(

t

)的取值范围为(0,1)。令

t

=

k

为当前迭代次数，

σ

和

μ

为可变参数，根据地图的复杂程度和实验确定两者的取值，在当前迭代和设定的

μ

值相等时，信息素挥发因子取得最大值，

ρ

为一常数值，是用以保证信息素的挥发因子不会过小的最低值。

由于改进的信息素挥发因子的计算公式遵循高斯(Gaussian Distribution)分布的规律，那么在蚁群搜索可行路径的前期，挥发因子的值较小，有利于蚁群根据信息素的指引向较优的路径上靠拢；在搜索中期，信息素已经积累到一定的量，为防止算法陷入局部最优，提高全局搜索的能力，此时信息素挥发因子取得较大值；在蚁群搜索路径的后期，可选择的路径比较少，因此，为了加快收敛的速度，挥发因子取得一个较小值。

2.3 改进蚁群算法步骤

AOA蚁群算法具体步骤如下：

(1)使用栅格法对移动机器人运行的环境构建二维静态地图，在构建的栅格地图中，黑色栅格表示障碍物，白色栅格表示机器人可通行的节点，机器人不可以在障碍栅格上运行，但可以在白色栅格自由行进；

(2)设置初始化参数，将以起点与终点为顶点的初始信息素设置为一较小值，设置最大迭代次数

NC

、蚂蚁数量

M

、信息素启发式因子

α

以及期望启发因子

β

等基本参数；(3)将所有蚂蚁放置在起点，并将每只蚂蚁的禁忌表

tabu

的第一个元素设置为起点，准备开始搜索路径；

(4)每只蚂蚁个体根据轮盘赌法以及加入避障因子的状态转移式(6)对将要行进的下一节点进行选择；

(5)更改禁忌表，当蚂蚁行进到新的节点后，将上一个节点加入该蚂蚁的个体禁忌表里；

(6)更新信息素，在蚂蚁

m

完成搜索后，根据AOA蚁群算法进行信息素的更新，其中，信息素挥发因子的值根据式(8)进行计算；(7)重复步骤(4)～(6)，直到蚂蚁

m

完成搜索，到达终点；

(8)迭代次数加一，清空每只蚂蚁的禁忌表以进行下一次的迭代搜索；

(9)判断迭代次数是否等于事先设定的

NC

，如果相等，则程序结束，输出结果，否则转到步骤(3)。

3 仿真和实验

研究算法的仿真平台为MATLAB。计算机配置为：Windows 10，处理器为Inter(R) Core(TM) i5-7200U CPU @ 2.50 GHz 2.71 GHz，内存4 GB。使用栅格法建立规模为20*20三种障碍物不同分布的环境，初始化参数设置为：蚂蚁数量50，信息素因子为1，启发信息因子为8，传统蚁群算法的信息素挥发因子取值为0.4，AOA蚁群算法中的避障因子的指数部分以及信息素挥发因子

ρ

大小则根据调试经验确定。

研究设计了三种栅格地图，地图的规模都是20*20，但是障碍物的数目和分布情况都不相同，代表机器人的三种运行环境。基于这三种地图对蚁群的传统算法和研究的AOA蚁群算法进行了仿真实验，并进行对比。三种栅格环境分别命名为栅格环境A、栅格环境B、栅格环境C，相应的轨迹图和迭代图如图2所示。从图2可知，传统的蚁群算法和改进的蚁群算法都可在该种障碍物分布的20*20栅格地图中得到较为合理的路径规划结果。若在算法运行过程中，所找到的路径在某次迭代后保持不变，则将该次迭代数称为初次收敛迭代次数，即之后的所有蚂蚁都会沿着该次迭代得到的路径行走，不会再探索其他的可行路径。算法收敛曲线对比如图3所示。对图3中得到的两种算法的收敛曲线进行比较，结果如表1所示。

图2 机器人运动轨迹对比

图3 算法收敛曲线对比

表1 三种栅格地图下的算法比较

由图1和图2可以得出，传统的蚁群算法存在着以下两个问题。其一是无法找到全局最优路径，算法最终输出的路径是次优路径，并且初次收敛的迭代次数较大。其二是算法经过若干次迭代找到了全局最优路径，但是由于次优路径上的信息素量高于最优路径，所以算法最终收敛于次优路径长度。由表1可得，在三种不同的栅格环境中，AOA蚁群算法最终收敛得到的最小路径长度比传统蚁群算法得到的最小路径长度更短，并且在初次收敛迭代次数上，改进的蚁群算法明显少于传统的蚁群算法，这两点显示出改进的蚁群算法更具优越性。

为进一步验证改进算法的可靠性，设置同文献[16]相同的栅格地图进行对比实验，AOA蚁群算法运行结果如图4所示。与文献[16]的算法对比如表2所示。由表2可知，所找到的路径均为最优路径，但是，研究算法的初次迭代收敛次数明显降低，即AOA蚁群算法具有更快的搜索最优路径的能力和更好的收敛速度。

图4 AOA蚁群算法运行结果

表2 与文献[16]的算法对比

由实验可知，在规模为20*20的三种障碍物分布不同的栅格地图的仿真结果以及与改进算法的对比实验均表明，研究设计的AOA蚁群算法在机器人路径规划方面更具优越性。

4 结论

针对传统的蚁群算法容易陷入局部最优和收敛速度慢的不足对算法进行了改进。在蚂蚁的状态转移概率计算公式中添加了避障因子，减少了蚂蚁的死锁数量，加快了蚂蚁搜索路径的速度。对于固定的信息素挥发因子可能使算法陷入局部最优或者收敛速度慢的不足，给出了基于高斯分布的改进信息素挥发因子，使信息素挥发因子从固定值变为随时间变化的自适应值，使得算法得到的路径更优，大大加快了算法的收敛速度。对比两种算法的仿真结果，AOA蚁群算法在最短路径的寻找以及收敛速度上都比传统的蚁群算法更好。下一步将尝试改变蚂蚁的步长，进一步减小路径的长度，使得路径更加平滑，并尝试将得到的仿真结果应用到现实生活中，实时实现移动机器人的路径规划与避障。