基于变步长蚁群算法的移动机器人路径规划

赵高杰鲁守银袁鲁浩

(山东建筑大学 信息与电气工程学院，山东 济南 250101)

0 引言

机器人路径规划一直是机器人领域的关键技术之一，其是指移动机器人在特定环境中，找出一条连接起点与终点的最佳路径[1]。路径规划算法具有代表性的有A*(A-Star Search Method， A*)法[2]、快速扩展随机树(A Rapidly Exploring Random Tree，RRT)法[3]、人工势场法[4]、神经网络算法[5]等。除此之外，还有大量仿生算法，如粒子群算法[6]、遗传算法[7]、蚁群算法[8]等。其中，蚁群算法的应用最广泛，主要是因为其具有正反馈策略、寻优效果好等优点。

蚁群算法是根据蚂蚁搜寻食物行为设计提出的，已证明具有很多优点，但同时也具有稳定性不强、容易陷入局部收敛等不足。因此，在此基础之上，学者们设计了诸多不同的蚁群算法改进方案。2021年，SANGEETHA 等[9]引入了一种基于能量优化的蚁群算法，考虑到规划的路径与消耗的能量是一一对应的，改进了增益函数的信息素增强机制，减少了动态场景中路径规划过程消耗的总能量，从而起到路径优化的效果。然而，其本质仍为传统的蚁群算法，仅映射了问题，其收敛性和最优解情况仍有待提升。而MASOUMI 等[10]则考虑到地理信息系统中用户的需求，改进了蚁群算法目标函数，可适应不同优先级的多目标优化问题。这种方法有利于提升用户的体验性， 但其迭代次数仍较多。ABDULAKAREEM 等[11]则引入了基于概率路线图和三次样条插值的改进蚁群算法，分别采样目标点、构造路线图，随后使用蚁群算法优化，并使用三次样条插值进行平滑并降低路径长度从而获得最优路径，然而由于环节较多，因此计算量较大、搜索时间长。高茂源等[12]提出了一种基于环境改进的蚁群算法，其基于栅格环境选择机器人的步长，改进信息素挥发因子，使其尺寸分布服从高斯分布，从而加快了改进后蚁群算法的收敛效率，但对原始数据的分布具有较严格的要求，从而其应用场合较为有限。此外，徐玉琼等[13]为改进传统蚁群算法稳定性不足的问题，设计了一种自适应蚁群算法，能够依据算法中解的分布情况，动态地更新调节信息素；同时在多步长选择模型中选取最佳步长，提升算法全局搜索性能，但不足在于没有考虑移动机器人实际工作环境的高度因素。

综上所述，目前对改进蚁群算法的研究仍存在未触及蚁群算法内部环节和本质、应用场合受限、未考虑移动机器人实际工作环境等问题。针对上述问题，文章基于移动机器人实际的工作环境，提出了一种改进的变步长蚁群算法，主要设计了一种不定步长的选择模型，同时针对移动机器人实际运行时可能出现坡度大的环境，在启发函数中引入高度信息。另外，改进了算法中信息素更新模型，采用动态挥发系数，以提升算法寻优效率。

1 移动机器人路径规划的环境建模

机器人路径规划问题指的是在特定的约束下，搜寻出一条最佳路径，由式(1)表示为

式中f(p)为路径的目标函数；ps、po分别为起始点和目标点；Γ(ps，po)为起终点之间的路径节点集合。

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

机器人栅格环境模型如图1 所示，其中黑色区块为障碍物，白色区块为机器人可行走的区域。通过设定栅格图的栅格号从下至上、从左到右都分别递增。栅格地图规格为m行n列，栅格号和栅格粒径分别为N和1，每个栅格的中心点位置坐标(x，y)可由式(2)表示为

图1 栅格模型图

式中mod 为取余操作；int 为求整。

2 移动机器人路径规划蚁群算法改进

2.1 传统蚁群算法

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

个体在寻优迭代过程中的第t次，由节点i转移至节点j的概率计算公式由式(3)表示为

式中n为个体序号；i和j分别为当前节点和下一节点；s为所允许的转移起始节点；allowedi为所允许的点坐标集合；τ为信息素浓度；η为启发函数；α、β分别为信息素和启发式预期值；U为个体可搜寻栅格的集合。其中，节点i、j之间的距离d(i，j)由式(4)表示为

而在算法寻优时，环境中信息素更新公式由式(5)和(6)表示为

式中ρ为信息素挥发因子；Q为信息素强度；Ln为序号为n的个体走过的总路程；K为蚁群中个体总数；V为序号为n的个体走过栅格的集合。

2.2 基于传统蚁群算法的启发函数优化

传统蚁群算法中，启发函数只和路径长度有关，只能保证距离因素，无法适应真实工作环境中高度不定的情形。因此对启发函数进行改进，由式(7)表示为

式中v为高度因素，其多元函数形式由式(8)表示为

式中h为环境中栅格的高度矩阵；λ和σ为高度调节常数；hmin、hmax分别为相邻栅格中与当前栅格的最小、最大高度差，m；C为常数，C＝0.001，保证在最小、最大高度差相等时分母不为零。

2.3 基于传统蚁群算法的信息素更新机制改进

2.3.1 信息素增量

为更加真实地模拟机器人可能遇到的具有高度起伏的工作环境，加入了高度启发因素，因此对信息素增量公式做修正，由式(9)和(10)表示为

式中Zn(t)为路径的综合指标；Sn(t)为路径长度，m；Hn(t)为路径的转弯次数，路径的综合指标越低，说明路径越平直，路径的收敛性和优化程度越高。

2.3.2 挥发系数

传统蚁群算法中挥发系数自始至终都是维持不变的，无法适应实际环境。因此，为提升改进算法的全局性，提出一种自适应策略，在搜索前期增大ρ的值，加快收敛，而在后期减小其值，增强算法全局性。具体公式由式(11)表示为

式中a、b均为常数；ρmax、ρmin分别为挥发系数最大及最小值。

2.3.3 限定信息素范围

在蚁群算法的优化迭代过程中，设定路径上的信息素取值由式(12)表示为

通过范围限制，丰富了结果的多样性，从而可以提升算法的寻优效率。

2.4 基于传统蚁群算法的变步长选择策略改进

传统蚁群算法中采用的是单步移动的模式，且转移的方向只能为0°、±45°、±90°、±135°、180°共8个角度。在传统的单步长移动模式下，其路径距离更长，且转折次数也更多。因此，采用变步长移动机制，此时个体在进行移动时不再局限于单步长，且每一步的移动方向可以任意选择，从而减短路径距离，此两种步长模式对比图如图2 所示。

图2 两种步长模式对比图

变步长移动机制具体方案为:

先利用改进的蚁群算法搜寻出单步长模式下最佳路径，如图2 中的虚线所示，再次对此路径进行规划，即将当前栅格与下一栅格直接相连，判断路径是否遇到障碍物，若没有则接着寻找下一个栅格，直至碰撞障碍区域。此时形成的栅格节点连线为最优路径，如图2 中实线所示，可以看出变步长选择策略模式下路径距离更短且转折次数更少。

2.5 改进变步长蚁群算法流程

基于算法的相关分析，改进变步长蚁群算法相应的执行流程示意如图3 所示。

图3 算法流程图

其步骤主要为

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

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

(3)采用变步长移动策略，根据式(3)计算转移概率，得到下一节点坐标。而在本轮迭代结束后，则需要根据式(9)～(11)更新算法中的信息素；

(4)判断本次迭代是否结束，如果结束继续执行，否则需要重新计算下一节点坐标；

(5)判断算法是否超过迭代次数最大值，如果是，则输出最优路径，否则继续下轮迭代。

3 蚁群算法实验仿真及分析

为了验证所提出的变步长蚁群算法在机器人路径规划上的有效性，通过数学软件MATLAB 评价改进后蚁群算法在路径规划上的可行性和高效性，并与张晓莉等[14]使用的传统蚁群算法、WANG 等[15]提出的基于粒子群优化 (Particle Swarm Optimization， PSO)改进的蚁群算法进行对比。在仿真测试中，建立了二维栅格地图[16]，其中栅格环境模型的尺寸为30 m×30 m。实验中二维栅格地图的参数设置为:单位栅格长度为1 m、总长30 m，机器人起始坐标为(0.5，0.5)、终点为(29.5，29.5)。

在性能对比实验的算法参数中，设置个体数目(m值)为50，算法的迭代最大次数为50 次，信息素重要程度因子α、启发函数重要程度因子β、信息素增加强度系数Q和信息素挥发系数ρ分别设为1、3.2、1.1 和0.6，挥发系数的阈值ρmin和ρmax分别为0.01和0.8。选取hmax＝0.4 m、hmin＝0 m。高度调节因子选为λ ＝0.5、σ ＝0.5。除此之外，3 种算法所设定的其他参数都使用相同的参数设置。

对传统蚁群算法、PSO 优化蚁群算法以及改进蚁群算法在相同的二维栅格地图进行仿真测试，所得到的路径结果如图4 所示，其中的绿色部分表示栅格上的高度分布情况。而3 种算法在相同的二维栅格地图路径规划过程中的路径长度、转弯次数及综合指标对比结果如图5～7 所示。

图4 传统蚁群算法、PSO 优化蚁群算法和改进变步长蚁群算法在相同二维栅格地图路径结果图

图5 3 种算法在相同的二维栅格地图路径长度对比图

由图4～6 可知，传统蚁群算法及PSO 优化蚁群算法的移动机器人路径规划方法的避障能力不足，使得机器人移动过程中产生了一些冗余的路径，且需要多次迭代才可找出最优路径，迭代次数达到设定的最大迭代次数时，其最少转弯次数均＞10 次、最小路径长度为47 m。相对比之下，由于转弯方向的任意选择性，改进变步长蚁群算法规划所得出的路径的避障效果较好，路径较为平直，最优路径仅需要9 次转弯，最优路径长度为44 m，相比于其他二者减小了3 m。

图6 3 种算法在相同的二维栅格地图转弯次数对比图

若综合考虑算法的收敛性和效率，如图7 所示，可发现改进变步长蚁群算法的收敛效率相比于PSO优化蚁群算法提升了72%，比传统蚁群算法提升了84%。此外，改进变步长蚁群算法的综合指标相比于传统蚁群算法减少了33%，比PSO 优化蚁群算法减少了12%，也就是说其路径规划的效率和综合效果是最佳的。

图7 3 种算法在相同的二维栅格地图综合指标对比图

综合以上评价指标的实验结果可以看出，在蚁群算法基础上提出的基于变步长蚁群算法的移动机器人路径规划方法，在路径长度、转弯次数及综合效果等常用的路径规划评价指标方面，对比于传统的蚁群算法和PSO 优化蚁群算法的路径规划方法都具有更明显的优势。

4 结论

在传统蚁群算法基础上，提出了在移动机器人路径规划上应用的一种改进变步长的蚁群算法，并对比了传统蚁群算法及粒子群优化蚁群算法，经过分析得出以下结论:

(1)在蚁群的启发函数中增加了高度分布函数，表征机器人移动的高度起伏。仿真结果表明，改进变步长蚁群算法对高度函数具有稳定性，规划出的路径规避了高度起伏较大的区域，并保证了一定的平直性，其转弯次数仅为9 次，相对于传统蚁群算法及PSO 优化蚁群算法提升了约45%。

(2)改进变步长蚁群算法增加了长度和方向的选择特性，可提供根据环境不同而改变自身步长的搜索模式，总路径长度相比于其他二者算法减少了约5%。

(3)在收敛性和寻优效率方面，仿真结果表明改进变步长蚁群算法收敛所需的迭代次数仅需8 ～10 次，相比于其他二者减少了5～15 次，路径综合指标提升了约30%。