基于改进多步长蚁群算法的机器人路径规划

王明辉

(盐城工学院信息工程学院，江苏盐城 224051)

0 前言

路径规划一直是移动机器人领域的关键技术之一，指的是找出一条在特定环境中连接起点与终点的移动机器人最佳路径。路径规划问题上具有代表性的传统算法有A法、RRT法、人工势场法、神经网络算法等。除此之外，还有大量仿生算法例如粒子群算法、遗传算法、蚁群算法等。其中，蚁群算法的应用最广泛，主要是因为它具有正反馈策略、寻优效果好等优点。

蚁群算法最早是由DORIGO根据蚂蚁搜寻食物行为设计提出的。蚁群算法具有优势，但也存在稳定性差、易局部收敛等缺陷。因此国内外学者针对蚁群算法的缺陷，提出了许多不同的改进方案。文献[9]针对传统蚁群算法存在收敛性差、鲁棒性不足等缺点，采用了一种多步长蚁群算法，该模型可以根据周围情况自由选择步长，并寻找出一条最短路径，基于栅格环境选择机器人的步长，改进信息素更新公式，同时对信息素加以限制，防止算法过早收敛。文献[10]为改进基本蚁群算法鲁棒性不足的问题，设计了一种自适应蚁群算法，能够依据算法中解的分布情况，动态地更新调节信息素，同时在多步长选择模型中选取最佳步长，提升算法全局搜索性能，仿真表明改进的蚁群算法相可以更加准确且迅速地寻找出最短路径。

结合以上的研究成果及问题，本文作者基于移动机器人实际工作情景，提出一种改进的多步长蚁群算法。将移动机器人运行环境转化为栅格环境，设计一种多步长的选择模型，改善基本蚁群算法中单步移动模式的不足，从而缩短路径距离。同时，针对移动机器人实际运行时可能出现坡度大的工况，在启发函数中引入高度因素。另外，改进算法中信息素更新模型，采用动态挥发系数，以提升算法寻优效率。

1 移动机器人环境模型

移动机器人路径规划中常见的建模方法主要有栅格地图、MAKLINK图、拓扑图等。其中，栅格地图维护简易且构建简单，因此本文作者将栅格图作为移动机器人建模环境。栅格的粒径由移动机器人的规格决定，其大小必须可以容纳移动机器人自由运行且保持栅格边界与移动机器人有一定的安全距离。在栅格地图中黑色代表不可行空间，白色则代表自由通行区域。为保障移动机器人的工作安全，规定移动机器人工作时不能沿着障碍物边缘及顶点行走。另外，如果障碍物不足一个栅格时，将它膨胀为一个栅格。

机器人栅格环境模型如图1所示。假设栅格图中栅格号按从下至上、从左到右依次递增。栅格地图规格为行列，栅格号为，栅格粒径为1，则栅格中心坐标可表示为

图1 栅格模型

(1)

式中：、分别表示中心点的横、纵坐标；mod表示取余操作；int表示求整。

如果当前位置坐标为(,)，则栅格中障碍物及可行区域取值为

(2)

2 基本蚁群算法

蚁群算法是为模拟蚁群寻找食物的行动模式而设计的算法。蚁群在搜寻食物时会沿途分泌不等的信息素，而信息素的多少跟路径距离有关。其他蚂蚁则会根据路径上信息素的浓度作出相应决策，最终蚁群将逐步聚拢在最短路径上。

在第次迭代中，蚂蚁由节点转移至节点的概率为

(3)

式中:表示蚂蚁标号;、分别表示当前节点和下一节点；表示信息素浓度；表示启发函数；、分别表示信息素和启发式期望值；表示蚂蚁可转移节点的集合。其中：

,()=1(,)

(4)

式中：(,)表示节点与中心的距离。

在算法迭代过程中，信息素更新公式如下：

(5)

(6)

式中:为信息素挥发因子;为信息素强度；为蚂蚁走过的总路程；为蚂蚁总数；为蚂蚁走过节点的集合。

3 算法改进方向

3.1 改进启发函数

基本蚁群算法中，启发函数只和路径长度有关，只能保证距离因素，无法适应真实工作环境中高度不定的情形。因此对启发函数作以下改进：

(,)=1(,)+(,)

(7)

式中：表示高度因素，可表示为

(8)

式中:表示栅格高度矩阵;、指高度调节常数；max,、min,分别是相邻栅格中与当前栅格的最大高度差和最小高度差;0.001保证分式有意义。

3.2 改进信息素更新机制

3.2.1 信息素增量

为更加真实地模拟机器人可能遇到的具有高度起伏的工作环境，加入高度启发因素，因此对信息素增量公式进行如下修正：

(9)

()=()+()

(10)

式中:()为路径的综合指标;()为路径长度；()为高度均方差。

3.2.2 挥发系数

基本蚁群挥发系数从始至终都是维持不变的，无法适应实际环境。因此,为改进算法的全局性，提出一种自适应策略，在搜索前期增大，加快收敛，而在后期减小，增强算法全局性。具体公式如下：

(11)

式中:、都为常数；、分别为挥发系数最大、最小值。

3.3 多步长选择策略

基本蚁群算法中采用的是单步移动模式，且转移的方向只能为8个方向，如图2所示。在传统的单步长移动模式下路径距离更长，且转折次数也更多。因此,本文作者采用多步长移动机制，此时蚂蚁在移动时不再局限于单步长且方向可以任意选择，缩短了路径。具体方案：先利用改进的蚁群算法搜寻出单步长模式下最佳路径，如图3中的虚线所示，然后再次对此路径进行规划，即将当前栅格与下一栅格直接相连，判断路径上是否有障碍物，若没有则继续寻找下一个栅格，直至碰撞障碍区域。此时形成的栅格节点连线为最优路径，如图3中实线所示。可知，多步长选择策略模式下路径更短且转折次数更少。

图2 转移方向 图3 2种步长模式下最佳路径对比

3.4 改进多步长蚁群算法流程

改进多步长蚁群算法相应的执行流程如下：

(1)建立栅格地图环境，设置算法参数初始值；

(2)设置起始及目标位置，初始化信息素；

(3)采用多步长移动策略，根据公式(3)计算转移概率，得到下一节点坐标；

(4)此轮迭代结束后，根据公式(9)—(11)更新算法中的信息素；

(5)判断此次迭代是否结束，如果结束继续执行下一步骤，反之则返回步骤(3);

(6)判断算法是否达到迭代次数最大值，若是则输出最优路径，否则继续下轮迭代。

4 实例仿真及分析

4.1 15×15环境仿真

基于MATLAB R2016b平台进行仿真实验。仿真时算法主要参数设置：最大迭代数为80，常数=5、=1，期望因子、分别为1和8。机器人的栅格环境规格为15×15，机器人起始点设为(0.5,0.5)、终点为(14.5,14.5)。基本蚁群算法及改进多步长蚁群算法的移动机器人仿真路径分别如图4和图5所示，图中灰色越深表示环境高度越高。各指标对比结果如表1所示。

图4 基本蚁群算法仿真结果(15×15栅格)

图5 改进多步长蚁群算法仿真结果(15×15栅格)

表1 2种算法结果对比(15×15栅格)

由图4和图5可看出：在有坡度的环境中，基本蚁群算法路径长、转折次数多且无法避开高度高的区域，使得移动机器人自身消耗过大，不利于移动机器人实际工作；而改进后的算法采用了多步长策略，因此路径转折次数少且距离短，另外因为在目标函数中引入了高度因素，能够绕开高区域，规划出的路径也更平坦。由表1可知：改进多步长蚁群算法的收敛速度远高于基本蚁群算法，同时容易看出其各项指标均优于基本蚁群算法，因此在实际环境中更有利于移动机器人高效、安全地完成相应工作。

4.2 20×20环境仿真

为进一步验证文中算法的性能，在规格为20×20的栅格图中与文献[10]的改进方法进行仿真对比。各个参数设置与15×15的环境保持一致。基于文中算法的移动机器人仿真结果如图6所示，各指标数据如表2所示。

图6 改进多步长蚁群算法仿真结果(20×20栅格)

表2 2种算法结果对比(20×20栅格)

由表2可知:在更加复杂的环境中，采用文中算法的移动机器人搜索出的路径质量依旧较高，无论是路径长度、转折次数还是最大爬坡高度都优于文献[10]算法，且收敛效率更高，体现出了更强的环境适应能力。

5 结论

采用蚁群算法规划移动机器人路径时存在许多缺陷，因此本文作者设计了一种改进的多步长蚁群算法。一方面利用栅格地图对机器人工作环境栅格化，同时采用一种多步长的选择模型，使得移动机器人可根据环境自主选择移动方向，从而缩短路径、减少转折次数；另一方面，针对移动机器人实际运行时可能遭遇坡度变化大的环境，在启发函数中引入高度因素。同时，改进算法中信息素更新策略，采用动态挥发系数，以提升算法寻优效率。结果表明：所提算法具有更强的环境适应能力，效率更高，对移动机器人真实的运行有积极意义。