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

李燕 季建楠 沈葭栎 苏瑞

1 南京信息工程大学 自动化学院,南京,210044 2 南京信息工程大学滨江学院 物联网工程学院,无锡,214105

0 引言

随着移动机器人的飞速发展，路径规划问题成为移动机器人研究领域的基础与核心.移动机器人路径规划技术是机器人在复杂的环境中，从起点到终点之间无数条搜索路径里，智能地选择一条最优路径或者较优路径[1].传统的解决路径规划问题的算法主要包括广度优先搜索( BFS) 、深度优先搜索( DFS) 、Dijkstra 算法和A*的算法.近年来一些研究人员采用仿生智能优化算法解决路径规划问题，这些仿生智能优化算法主要包括蚁群算法、遗传算法、粒子群算法、免疫算法、模拟退火算法、DNA计算方法以及各算法之间的组合优化算法等[2-5].

蚁群算法是一种启发式的随机搜索算法，由意大利学者Maniezzo团队受蚂蚁觅食行为的启发，在1991年首次提出[6].蚁群算法模拟蚂蚁合作觅食行为，具有正反馈、高稳健性和并行性、易于与其他算法相结合等优点.但传统蚁群算法容易出现局部最优解、计算量大、收敛速度慢等问题[7].近年来国内外学者相继提出了一些改进的蚁群算法.2000年，Stutzle等[8]提出了最大最小蚂蚁系统( MMAS)，通过限制路径上信息素的上下限，在一定程度上避免了陷入局部最优解问题.2018年，张原艺等[9]提出一种改进的多步长蚁群算法，将蚁群每次迭代产生的最优路径作为引导径，利用路径引导搜索策略确定多步长的移动路径，提高了搜索范围的多样性.2018年，占伟等[10]提出改进启发因子的方法，给定一个初步的引导方向，最终大大增加了算法的时间有效性，减少了算法收敛的时间,保证了最短路径的搜索方向向着最短目标最优方向进行.2020年，陈劲峰等[11]提出了一种自适应信息素给予机制，提高了蚁群算法的收敛速度和路径全局优化能力.

针对现有蚁群算法的不足，本文提出了一种用于移动机器人路径规划的改进蚁群算法.首先用栅格法进行环境建模，然后通过优化信息素总量增强全局搜索能力，增加搜索的目的性，最后改善启发式函数来提高状态转移概率，以便快速地得到路径最优解.仿真结果表明改进的蚁群算法在性能指标上有显著提高.

1 环境建模

机器人环境建模的方法主要有栅格法、构型空间法、自由空间法

等几种.其中栅格法在机器人的环境建模上应用最多[12].栅格法主要任务是根据环境构建路径网格图，基本原理是将机器人的工作环境划分为许多微小的网格单元，每个网格的规格由机器人的步骤决定.网格由自由网格和障碍网格组成.白色的网格表示自由网格，黑色的网格表示障碍网格.图1是20×20的网格节点图，每行的节点数Nx=20和每列的节点数Ny=20.坐标原点定在栅格空间的左下方，定义x轴正方向为从左到右，y轴正方向为从下到上.第1个点的坐标为(0，19)，第2个点的坐标为(1，19)，以此类推.假设S={1,2,3,…,N}是一组节点的数量，第i个节点的坐标为(xi,yi)，从起始点坐标(0，0)开始到终点坐标(19，19)结束.机器人只能在白色的自由网格中移动，需要避开黑色的障碍网格.根据网格的位置，网格可以分为中间网格和边界网格.对于中间网格，机器人的下一个动作可选择8个方向.当机器人运动到边界网格时，它的运动方向需舍去无法到达的方向.

图1 20×20的节点图Fig.1 20×20 node graph

2 传统蚁群算法

蚁群算法是一种群体智能仿生启发式算法，它通过模拟蚂蚁觅食的行为来找到食物源与其蚁巢之间的最佳路径.蚂蚁在通过的路径上会释放信息素.通过这些信息素，蚂蚁可以彼此交流并最终找到一条起点到终点的最短路径.在搜索过程中蚂蚁会随机选择前进的运动方向，信息素在路径上遗留的越多，对信息素浓度大的路径选择的概率就越大，在寻找路径的过程中蚁群个体之间的协作形成了一种正反馈机制.

在寻找路径的过程中蚂蚁依据路径上的信息量和启发式信息计算转移概率：

(1)

τij(t+Δt)=(1-ρ)·τij(t)+Δτij(t),

(2)

(3)

(4)

(5)

3 改进的蚁群算法路径规划

3.1 优化信息素总量

对于传统的蚁群算法，完成一次完整路径搜索后所释放的信息素总量是一个定值.随着迭代次数的增加,后期路径上的信息素浓度易积累过高，导致蚂蚁一定程度上失去搜索优质解能力，信息素浓度在挥发因子的作用下降低，极可能增加陷入局部最优解的概率.本文提出了对信息素总量Q进行自适应调整的机制，随着迭代次数的增加Q逐步降低，大大降低陷入局部最优解的概率.方法如下：

(6)

其中Niter表示迭代次数，Nc,iter是当前的迭代数.

3.2 启发函数的改进

传统蚁群算法初始阶段在路径上没有遗留信息素，蚂蚁无法根据信息素浓度选择方向，搜索没有目的性，不能快速搜索到可行路径.针对这一问题，本文对迭代搜索的启发函数进行改进，采用当前节点到下一节点的距离与下一节点到目标节点距离之和的平方来优化启发函数，使得蚂蚁在搜索初期能够获得一个引导方向，增加目标节点对下一节点的影响，改进的启发函数如下：

(7)

(8)

其中djD表示节点j到目标点D的欧式距离.将传统的dij改为(dij+djD)2，增强了搜索的目的性，降低了陷入局部最优解的概率.

3.3 蚁群算法相关参数

蚁群算法中，参数的选取影响收敛速度和寻优结果，主要涉及的参数有蚂蚁数量、信息素挥发系数、启发因子α与期望启发因子β、迭代次数.具体分析如下：

1)蚂蚁数量.算法中蚁群数量是一个关键的参数，蚁群数量过大，搜索路径上的信息素会趋于相等，无法确定最优路径；蚁群数量过小，有可能出现早熟，不能获取全局最优路径.本文蚂蚁数量M设置为50.

2)信息素挥发系数.信息素反映蚂蚁搜索进程中积攒的信息量，指导蚁群搜索路径的方向.随着蚁群算法迭代的进行，节点上的信息素将逐渐挥发.信息素挥发系数ρ对蚁群算法的收敛速度和寻优能力都有着至关重要的影响.ρ增大信息素挥发加快，蚁群算法的随机性和搜索能力降低;ρ减小，全局搜索能力提高，但收敛速度也相应减慢.本文信息素挥发系数ρ设置为0.2.

3)启发因子α与期望启发因子β.启发因子α表示路径上的信息素浓度对整个蚁群的指导作用;期望启发因子β表示路径相关信息对蚁群的影响.α的大小决定蚂蚁选择之前路径的概率大小，β的大小决定了算法的搜索效率.本文启发因子α设置为0.9、期望启发因子β设置为4.

4) 最大迭代次数.迭代次数主要根据执行的收敛轨迹来调整，迭代次数过小，会导致算法未收敛就已结束，过大会造成资源浪费.本文迭代次数设置为200.

3.4 路径规划步骤

为了实现改进的路径规划算法，本文对算法整体流程进行了设计.路径规划流程如图2所示，具体步骤如下：

图2 路径规划流程Fig.2 Path planning

1)利用栅格法进行环境建模；

2)对最大的迭代数、蚂蚁个数,以及其他参数如α,β,ρ等进行初始化；

3)将所有蚂蚁放在起点处，计算启发信息；

4)根据状态转移概率方程确定要选择的路径；

5)蚁群遍历所有节点后根据信息素策略更新信息素；

6)保存每个循环中每只蚂蚁的路径和路径长度；

7)循环执行4)至6)直到获得最优解或者达到最大迭代数.

4 实验结果与分析

为了检测改进的蚁群算法在机器人寻找最优路径中的效率，本文实验通过pycharm在Windows 10的系统下进行了大量的仿真实验.通过20×20的栅格环境，0表示障碍节点，1表示自由节点，环境中的所有障碍的范围都可以由各章障碍节点组合形成.对传统蚁群算法[14]、文献[10]中改进的蚁群算法和本文改进的蚁群算法在相同的障碍环境下进行仿真比较.3种蚁群算法初始设置为蚂蚁的个数M=50,最大迭代数为200，α=0.9，β=4，ρ=0.2，Q=2.

图3a—3c分别为传统蚁群算法、文献[10]蚁群算法以及本文改进蚁群算法的最优路径搜寻图，可以发现图3a和3b都能够在起始点到目标节点之间找到一条最短的移动路径，但传统的蚁群算法在初始环境相同的情况下明显比文献[10]蚁群算法得到的可行路径长.图3b和图3c相比，图3c中的最优路径长度优于图3b中的最优路径长度.

图3 最优路径搜寻效果对比Fig.3 Optimal paths obtained by traditional ant colony (a),algorithm in Ref.[10] (b),and the improved ant colony algorithm (c)

图4a—4c分别为传统蚁群算法、文献[10]蚁群算法以及本文算法的收敛曲线.由图4a可以看出传统蚁群算法在复杂环境下收敛曲线波动较大，寻优能力极不理想，在大规模的环境中其缺点暴露得非常明显，在迭代第82次找到最优路径并逐渐趋于稳定.图4b显示文献[10]算法在迭代第69次找到最优路径，在迭代第69次后趋于稳定.本文算法收敛曲线(图4c)显示在迭代第59次找到最优路径，在此之后趋于稳定.

图4 收敛曲线Fig.4 Convergence comparison between traditional ant colony (a),algorithm in Ref.[10] (b),and the improved ant colony algorithm (c)

通过3个算法收敛曲线的对比，明显可以看出：传统蚁群算法收敛曲线波动较大、转折点过多；文献[10]中的蚁群算法和改进的蚁群算法在达到最大迭代数时虽都已收敛，但本文改进的蚁群算法收敛速度更快、更稳定，寻优的效果更好.3种算法多次仿真实验的数据对比结果如表1所示.

表1 仿真结果对比

从表1中的实验数据可以看出，本文改进的蚁群算法相对于传统算法和文献[10]中的算法最优路径长度缩短，收敛的速度也更迅速，且在各代路线的平均长度也优于其他两种算法.本文改进的蚁群算法从起点到终点规划轨迹有9个转折点，而传统的蚁群算法转折点有15 个，说明改进的算法具有更好的路径搜索效率.仿真结果表明本文改进的算法具有更好的路径规划效果.

5 结束语

本文利用栅格法的便捷性对环境进行建模，对每个栅格进行标记，应用改进的蚁群算法从初始栅格移动到目标栅格进行路径搜索，找到最优路径.本文主要创新在于：1)针对传统算法搜索的目的性弱、不能快速搜索到可行路径的问题，通过改进启发函数，增加蚁群搜索的目的性，降低陷入局部最优解的概率；2)本文提出了一种自适应变化信息素总量的方式，通过迭代次数的增加对信息素总量进行调整，提高全局搜索能力，使算法获得较快收敛速度.通过实验仿真验证了改进后的蚁群算法的优越性和有效性.