势场改进蚁群算法的移动机器人路径规划研究

2019-09-03李林喜李卫国任超群王利利

锋绘 2019年6期

李林喜李卫国任超群王利利

摘要：在复杂环境中工作的移动机器人，针对其避障及路径优化问题，对传统人工势场法和基本蚁群优化算法进行了分析研究，提出了改进的人工势场蚁群算法，并利用仿真实验进行了分析。结果表明，改进后的人工势场法能够得到最优的路径，提高了算法的收敛性，且速度快、过程稳定，可用于解决移动机器人路径规划问题。

关键词：移动机器人;路径规划;蚁群算法;人工势场

近年来，随着人工智能技术的发展，移动机器人作为当前机器人领域的一个重要分支，在工业制造、海洋探测、家庭服务、医疗护理、资源开发、巡检排险、航空航天和国防等诸多领域得到了成功的应用。

路径规划是移动机器人完成各种自主移动任务的关键环节之一，是机器人领域的一个重要研究课题。路径规划简单的理解，就是让机器人从初始位置到达目标位置，作出最优行走路径应遵循的某种性能指标（如距离，时间等）。目前，路径规划的求解方法主要有人工势场法和基于人工智能的启发式方法，如蚁群算法、遗传算法和粒子群等。蚁群算法是一种受到生物界蚁群觅食行为的启发式搜索算法，本文为校级科研项目，在项目开展过程中，对上述各种算法进行反复比对实验，最终提出一种移动机器人路径规划算法——势场改进的蚁群算法，并测试了其有效性和优越性。

1 建立足球机器人路径规划模型

移动机器人的路径规划模型如图1所示，起始点为当前移动机器人的位置，当机器人遇到障碍物时，在避开障碍物，避免发生碰撞的前提下，找到一条从起始位置到目标位置长度最优的路径。

2 基本蚁群算法的缺点

基本的蚁群算法具有其不足和局限性：相对于其他方法它的搜索时间更长;容易出现停滞（算法结束在不是最优解或次优解）;描述复杂问题的能力还不够强等等。对于复杂环境存在的缺陷之处主要在于：

（1）参数α、β的选择对算法的影响。

在蚁群算法中，信息素因子α反映的前面的蚂蚁所释放的信息素对后面蚂蚁寻找路径的影响程度，如果α过大则后面蚂蚁选择其路径的可能性过小，会导致搜索的随机性丧失太多，反之则容易过早陷入局部最优的问题;期望启发式因子β，是对于前期的信息对蚂蚁的指导程度，值的大小反映寻径过程中的预先确定因素的作用强度，过大会导致蚂蚁收敛速度加快，搜索随机性削弱，寻到局部最优的概率增大。由于α和β在通常情况下都是给的定值，它们的影响在从整个算法的执行过程中都是一直保持和开始一样的影响效果。在比较小的栅格规模下还可以满足算法需要，但如果到了规模很大的栅格环境时，蚂蚁能经过的位置点会成倍上涨，这时蚂蚁需要经过的位置点更多，开始给定的信息素因子可能已经蒸发了很多，不能保证蚂蚁走过栅格中的任何一个位置点都获得该点的信息素。当再经历数次迭代，能获得的信息素位置点越来越少，这时的蚁群算法不仅更有可能出现次优解，也更容易进入局部最优。

（2）存在不可逆栅格情况。

当在栅格模型下的障碍物，出现下图2（a）的情况时，蚂蚁可能会按照图上指出方向选择可行的自由栅格，结果就会进入无法继续行动的状态，如果在算法前期出现这种状态的蚂蚁增多，相当于m减小，会出现停滞状态。

解决的方法就是在已知全局信息的情况下将其中的自由栅格作障碍栅格处理如图2（b）所示。

3 基本蚁群算法的改进

本文针对参数α和β的给定值进行改进。在算法执行的开始阶段，对依靠信息素因子α的寻找路径的方式的依赖程度还比较低，到了算法后期对其的依赖程度增高;相反的，对于期望启发因子β，前期依赖程度较高，到算法后期主要依靠蚂蚁之间的信息素传递来寻找路径，对期望启发因子的需求降低。经上面的分析可知，我们在算法前期让β升高而让α降低，以解决前期更多位置点得不到足够信息素问题;同样道理，到算法后期，让启发值β降低而α升高，也就是后期让算法利用更具有优势的信息素的方式寻找最佳路径。通过上述分析，我们就是要设计一个规则让基本蚁群算法的参数α和β在算法运行过程中实行动态变化的形式，在随时间执行的过程中，α逐渐递增至最大值;而β则逐渐递减至最小。我们将这个过程用数学公式叙述如下式（1）和（2）：

在上两个式子中，m为临界迭代次数（即蚂蚁个数），NC为最大迭代次数。在本论文中取值分别为m=10;NC=100。

4 人工势场的改进蚁群算法

结合人工势场法在未知环境下局部搜索的优势和蚁群算法在全局路径规划中的特点，用联合启发因子来进一步提高机器人在路徑规划中的效率。

蚁群中一共有m只蚂蚁，当其中的蚂蚁k在第n位置Pn=r转移到下一步位置Pn+1=s的概率依据是由下面的式子决定的

当0≤q0≤1是一个常数，S是按照概率确定的下一个到达的位置，其概率分布是按照（2）式来确定的

其中τrsn与ηrsn分别为从Pn=r到Pn+1=s的路径所在边的信息素的浓度和启发期望信息;a与β代表信息素因子和启发期望因子的相对重要性;第k个蚂蚁到下步所能允许到达的位置用allowedkn集合表示，机器人只能倒退到来时的栅格Pn-1，则说明Pn位置是一个死路，这种情形在之后Pn这个位置将会作为障碍栅格处理，也就是上边的凹栅格的“凸”处理方式。

第k只蚂蚁在搜索路径的过程中，对走过的边的局部信息素更新遵照下式：

当0<ψ≤1为一个常数;τ0=mCnn为初始信息素的值;Cnn为相邻的启发规则产生的路径的长度。这个蒸发过程是为了避免对其它的蚂蚁的过于强的吸引力，以避免迭代过早的收敛，让蚂蚁对其他路径搜索的可能。当m只蚂蚁都已经走完，完成一次迭代后，对所有蚂蚁的路径进行比较从中找出最短路径，并对这条路径进行一次全局信息素更新，如下式：

当0<ρ≤1为控制信息素衰减速度的常数;其中Δτrs=1Lgb，Lgb为本次迭代所找到的全局最优路径。

上述将人工势场法和蚁群算法的改进分别作了详述。下面将两种算法融合到一起，让它们共同构成完整的规划过程，可得该势场改进蚁群算法的启发信息ηrs为：

从式中得出，当势场的合力，也就是机器人处于势场的局部稳定点处，这时若只在人工势场中，将陷在局部最优中。但在本算法中，由于蚁群算法的加入，在这时启发信息会为ηrsn=ηdn=1d2P，G，也就是说当某一位置合力Ftot=0时，ηd的启发信息会引导机器人跳出局部最优这个陷阱，继续进行全局最优路径的搜索。

以上介绍了人工势场法和蚁群算法的改进分别作了详述。下面就要介绍一下这两种算法如何融合到一起，让它们共同构成完整的规划过程。这里就要对启发信息ηrsn进行构造。

在路径搜寻过程中，蚂蚁寻找到下一个位置的启发性信息是由两个部分构成，其中之一是蚂蚁受环境中的势场的合力，形成让蚂蚁能沿着合力的方向接近目标的启发信息，这部分信息为

式子里，a是大于零的常数，θ为蚂蚁可行进的方向和势场的合力Ftot方向的夹角，如图3-4所示。这是可知蚂蚁会在这个合力的影响下向着与势场合力方向的夹角θ较小的边移动到下一个自由位置。该启发信息可以帮助机器人避碰，选择合适路径接近目标位置。

剩下的一部分就是由蚂蚁距目标所在位置距离提供的。定义这一部分的启发信息如下

再将两者综合在一起，便可得该势场改进蚁群算法的启发信息ηrs为：

从式子中我们可以了解到，当势场的合力，也就是机器人处于势场的局部稳定点处，这时若只在人工势场中，将陷在局部最优中。但在本算法中，由于蚁群算法的加入，在这时启发信息会为ηrsn=ηdn=1d2P，G，也就是说当某一位置合力Ftot=0时，ηd的启发信息会引导机器人跳出局部最优这个陷阱，继续进行全局最优路径的搜索。

5 仿真与实验分析

5.1 人工势场蚁群算法

如图3、图4为人工势场蚁群算法仿真图，在迭代30次后，算法趋于稳定，最优路径长度在33.9258，并且在最优路径上。但从图上可以看出，0-30次之间收敛曲线波动较大，表明在收敛上存在可以改进之处。

5.2 人工势场改进蚁群算法

如图5、图6所示，在迭代15次后，算法就趋于稳定，最优路径长度是33.9053，进一步提高了其收敛效率，而且收敛曲线也平滑了很多，收敛效果改进明显。

综上所述，人工势场法的改进蚁群算法，在收敛效率上有了明显的提高，搜索最优路径时间更快更加趋于合理。该算法克服了人工势场法遇到的局部最优和目标不可达等问题，而且提高了算法的收敛性。

6 算法验证

利用此算法，机器人在实际运行中的路径比较平滑，但机器人行进过程中，当挪动障碍物形成动态规划时，机器人在靠近障碍物时会出现震荡前进，但最后依然可以到达目的地。这也为以后的进一步研究提出了改进方向。

7 结语

本文針对基本蚁群算法和人工势场法存在的不足，整合两者的优点，提出了人工势场改进的蚁群算法，并通过仿真实验和真实室内环境下实验，均验证了其可行性。同时，也发现了对于动态规划的不足，有些地方还需要改进。

参考文献

[1]周明秀，程科，汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学， 2013，40（1）：314-316.