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

王星宇，胡燕海，徐坚磊，陈海辉

（1.宁波大学 机械工程与力学学院，浙江 宁波 315211；2.宁波航工智能装备有限公司，浙江 宁波 315311）

0 引言

近年来,由于世界科学技术的蓬勃发展,机器人也逐渐走入中国大众的视野。路径规划是机器人控制中一个无法避免的问题。迄今为止，在机器人的路径规划问题上,已经有不少前辈做过难以计量的研究。常规的路径算法有Dijstra 算法[1]、A*算法[2]、人工势场法[3]等。随着机器人科技的蓬勃发展,传统的算法很难满足当前路径规划的需求,于是智能的仿生算法应运而生，如遗传算法[4]、粒子群算法[5]、蝙蝠算法[6]、蚁群算法[7]等。

蚁群算法可以利用全局搜索找到更优解,并具有很强的并行性,个体间也能够相互传递信息,并可以迅速收敛到解空间的某一子集,从而促进了对解空间的深入研究[8]。传统的蚁群算法由于其本身的原因，存在收敛速度不足、无法合理避开局部最优解的问题[9]。

为克服传统蚁群算法在路径规划上的不足，王晓燕等人[10]提出一种全静态环境下的改进蚁群算法，用人工势场求得的初始路径和下一个节点间距离构成距离启发式,并引入启发信息递减系数，避免了陷入局部最优解的情况；牛龙辉等人[11]构造了一种动态的信息素挥发系数，改变了算法在不同时期的搜索侧重点，加快了算法的收敛速度并且丰富了多样性；李理等人[12]提出了Ant Colony Algorithm with Multiple Inspired Factor(ACAM)算法，该算法提出一种新的距离启发函数、改进了信息素的更新方式,一定程度上解决了传统蚁群算法收敛速度以及路径平稳性方面的问题。

本文提出一种改进的蚁群算法，建立一种转角启发函数,使蚂蚁选择路径有更强的目的性;融合A*算法改进了距离启发函数,加入了距离的估算代价;并提出一种可根据迭代次数而改变的信息素挥发因子。

1 建立栅格地图及机器人移动方向

栅格法具有构建方便、表达清晰、测试性能好等优势,因此本文主要使用栅格法构建路径地图,如图1 所示。栅格法使用黑白二色来代表可以移动的路径以及障碍,矩阵中用1 来代表黑色即障碍,0 代表白色即可通行的路段。

图1 20×20 栅格地图

机器人的移动方法使用八叉树搜索策略,即机器人处于栅格地图中时,可以向其周围8 个方向进行运动,每次只能移动一个栅格。

2 蚁群算法及其改进

2.1 传统蚁群算法

蚁群算法是模拟蚂蚁在路面上移动的算法，蚂蚁在行走的路段上会释放一种包含已知信息的激素，这种激素在空气中会自行挥发，故较长路段所残留下的激素要少于较短路段。而激素残余量的多寡会影响下一只蚂蚁的选择，故多数蚂蚁会选择较短的路径。这种包含已知信息的激素称为信息素。

2.1.1 转移概率

蚂蚁从当前节点转移到下一节点的行为叫作状态转移，转移概率由距离启发式函数以及信息素的浓度共同确定。

转移概率如式（1）所示：

式中，α为信息素因子，α值的大小对蚂蚁的移动有着较大的影响；β为距离启发函数因子,反映两节点间的距离对蚂蚁移动的影响；τij(t)表示在t时刻蚂蚁从当前节点移动到下一节点的信息素浓度；ηij(t)为距离启发函数；dij为当前节点到下一节点的直线距离；allowedk为蚂蚁可选择的下一节点的集合。其中：

2.1.2 信息素更新策略

由于信息素具有挥发性，故每迭代一次，信息素都需要重新计算。

信息素更新公式如式(4)～式(6)所示：

式中，ρ为信息素挥发因子,通常取0<ρ<1；τij为当前节点移动到下一节信息素的增长程度，为 第k只蚂蚁对信息素增加所做出的贡献；m为自行设定的蚂蚁数目；Q为信息素系数；Lk为蚂蚁k爬行过程中的总距离。

2.2 改进蚁群算法

2.2.1 建立转角启发函数

蚂蚁在移动时，因栅格地图的限制，只能进行转角为0°、45°、90°、135°的移动，为了提高路径的选择性，建立一种转角启发函数,如式（7）、式（8）所示：

式中,ωij(t)为当前节点到下一节点转角启发因子,a为转角大小对蚂蚁选择路径的影响值。

2.2.2 改进距离启发函数

传统蚁群算法距离启发函数只考虑了接下来蚂蚁要走的两个节点间的距离，会导致蚂蚁无目标地移动。A*算法在路径规划方面能较好解决这个问题，A*算法计算路径的公式如式(9)所示：

式中，G为从起点到当前点的移动代价，H为从当前点到终点的估算成本。结合A*算法改进后的距离启发函数如式(10)所示：

式中，μ为平衡当前移动代价与估算成本的距离因子；σ为一常数,可根据需求改变；dje为下一节点到终点的估算成本,即直线距离。

2.2.3 改进信息素挥发因子

传统蚁群算法的信息素挥发因子ρ是固定的，若ρ过大，会导致蚂蚁重复搜索已经搜索过的区域，影响全局搜索能力；若ρ过小，又会导致收敛速度变慢。本文提出一种可根据迭代次数而改变的信息素挥发因子,如式(11)所示：

式中，K为最大迭代次数；γ为一常数，可根据迭代情况而改变。

2.2.4 改进蚁群算法步骤

(1)建立栅格地图、设置迭代次数、蚂蚁数量、信息素因子、启发函数因子、信息素挥发因子、信息素强度等初始参数。

(2)将所有蚂蚁置于起点开始寻路。

(3)蚂蚁根据转角启发式寻找下一步。

(4)更新节点和禁忌表。

(5)判断寻找的路线能不能够走到终点，若不能，则重新根据转角启发式寻找下一步；若能，则进入下一步。

(6)更新路径信息。

(7)根据迭代次数调整信息素挥发因子。

(8)判断是否达到最大迭代次数，若没有则返回步骤(3)；若达到最大迭代次数，则输出记录中的最优路径。

改进蚁群算法步骤流程图如图2 所示。

图2 改进蚁群算法步骤

3 仿真分析

为了验证改进蚁群算法的改善效果，将本文提出的算法与传统蚁群算法、ACAM 算法加以比较。使用MATLAB 在栅格总数为400 的方形栅格地图中进行对比试验。运行多次取其中最优解进行比较。实验设置两种不同的栅格地图，一种为常规的栅格地图，简称常规地图；另一种为包含U 形障碍的栅格地图，简称U 形地图。保持3 个算法的初始参数相同。初始参数如表1 所示。

表1 初始参数

其中，本文提出的自适应信息素挥发因子设为ρ0=0.9，ρmin=0.3。

3.1 常规地图运行结果

3 种算法在常规地图中运行结果如图3～图8 所示。

图3 传统蚁群算法常规路径

图4 传统蚁群算法常规迭代曲线

图5 ACAM 算法常规路径

图6 ACAM 算法常规迭代曲线

图7 本文改进蚁群算法常规路径

图8 本文改进蚁群算法常规迭代曲线

常规地图3 种算法仿真结果如表2 所示。

表2 3 种算法常规地图结果对比

从以上图表可知，在常规地图中，传统蚁群算法由于其距离启发函数的不足，容易陷入局部最优解，且收敛时间也较慢；ACAM 算法弥补了收敛速度不足的问题，提高了平稳性，对于防止陷入局部最优也有一定的作用；本文的改进蚁群算法在收敛速度以及避免局部最优解方面的表现比ACAM 算法更优。

3.2 U 形地图运行结果

为了验证3 种算法在特殊栅格地图中的表现，设置一种含有U 形陷阱的地图，简称U 形地图。

3 种算法在U 形地图中运行结果如图9～图14所示。

图9 传统蚁群算法U 形路径

图10 传统蚁群算法U 形迭代曲线

图11 ACAM 算法U 形路径

图12 ACAM 算法U 形迭代曲线

图13 本文改进蚁群算法U 形路径

图14 本文改进蚁群算法算法U 形迭代曲线

U 形地图3 种算法仿真结果如表3 所示。

表3 3 种算法U 形地图结果对比

从以上图表可知，传统蚁群算法在U 形地图中依然存在和常规地图中一样的缺点；与传统蚁群算法相比，ACAM 算法依然存在平稳性好、收敛速度快的优点；本文算法与ACAM 算法相比依然有收敛速度快、能减小陷入局部最优解概率的优势。

综合上述对比实验，可以发现本文所改进的蚁群算法在收敛速度以及避免陷入局部最优解方面有较好的表现。

4 结论

本文提出的改进蚁群算法，为了增加指定路径的选择性建立了一种转角启发函数，通过引入A*算法在距离估算上的优势，改进了原有的启发函数，并提出一种可根据迭代次数而改变的信息素挥发因子。仿真结果表明，该算法在机器人路径规划中可以起到加快收敛速度、避免陷入局部最优解的作用。