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

高茂源，王好臣

(山东理工大学 机械工程学院，山东 淄博 255000)

0 引 言

近年来人工智能领域快速发展，移动机器人路径规划[1]被广泛应用于自动驾驶、物流分拣运输等领域。移动机器人的路径规划在国内外得到广泛的研究，常用算法包括遗传算法、神经网络算法、A*算法等，各个优化方法有各自的优势，同时也并存在了明显的不足[2]。蚁群算法(ant colony algorithm)，被用于解决指派问题、旅行商问题以及车辆路由问题等[3,4]。其采用分布式并行计算机制，具有鲁棒性强，易于其他算法相结合等诸多优点，受到研究者们的广泛关注。但蚁群算法也有着收敛速度较慢，搜索效率低且时间长以及易陷入局部最优等不足之处，不利于高效率、高精度的求解优化问题。针对上述问题，本文提出了一种改进的蚁群算法，对算法的局部进行改进，达到提高搜索效率与寻优能力。

1 问题描述与环境建模

当移动机器人承担某项任务时，首先根据周边环境信息建立环境模型，通过自身算法对环境中的障碍物等进行定位、避障，从而获得最优路径。对移动机器人进行路径优化需要对机器人的运动空间进行数字建模处理，即运动空间与数学模型的转换，便于机器人识别与分析。本文机器人路径规划问题满足以下条件：1)机器人运动空间是二维有限空间，且空间中障碍物位置已知；2)障碍物随机分布在机器人运动空间中，且大小性状不发生变化，忽略其高度；3)不考虑机器人与机器人间和机器人与障碍物之间的碰撞；4)已知机器人起始位置与目标位置。最终经过路径规划实现移动机器人在所搭建的环境模型中寻找到最优路径。

栅格法建模方法简单，易于实现，是进行机器人路径规划中环境建模常用的方法[5,6]。机器人运动空间中用大小相同的栅格划分工作区域，将机器人理想化为一个质点，保证机器人的停留位置全部都在栅格的中心点。在二维运动空间中的栅格分为黑色栅格和白色栅格，其中白色栅格表示可行走栅格，用1表示；黑色栅格表示障碍物栅格，用0表示。将创建的二维空间进行等分，按照从左到右，从上到下的顺序，对每个栅格进行编号[7]。如图1为利用栅格法构造的环境模型。

图1 环境模型

各栅格点的坐标数学表达式为

(1)

式中b为栅格边长；mod为取余;MM为地图维度；ceil为朝正无穷大四舍五入；xi，yi为每个栅格的坐标位置。

2 传统蚁群算法

蚂蚁在寻找食物源时，会在走过的路径上释放一种信息素，并且能够感知其他蚂蚁所留下的信息素。其中信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短，反之，则越长。通常蚂蚁会以较大的概率优先选择信息素浓度较高的路径并释放一定量的信息素，以增强该条路径的信息素浓度，同时路径上的信息素浓度会随时间的推进而逐渐衰减，由此对蚂蚁路径的选择形成一个正反馈，最终，蚂蚁就能够找到一条从巢穴到食物源的最优路径，即距离最短[8]。图2为蚁群算法寻优原理图。

图2 蚁群算法寻优原理

传统蚁群算法的机器人路径规划执行步骤可描述为：利用栅格法搭建机器人环境模型，进行参数的初始化，蚂蚁根据在各个位置的信息素浓度(初始阶段信息素浓度为常数，即Tau=C)由当前节点i转移至下一节点j时，根据函数方程式(2)选择节点j的位置

(2)

式中τij(t)为栅格节点i,j之间的信息素浓度；ηij=1/dij为启发函数，表示蚂蚁由节点i行走至节点j的期望程度，dij为栅格节点i，j之间的距离；allowk为下一步待访问节点的集合；α为信息素重要程度因子；β为启发函数重要程度因子。

经过一定时刻后，当某一代所有数量的蚂蚁全部寻径结束后，根据方程式(3)～式(5)更新信息素浓度τ

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

(3)

(4)

(5)

3 改进的蚁群算法

3.1 启发函数

蚁群算法中启发函数ηij(t)=1/dij，表明蚂蚁从节点i行走至栅格j的期望程度与节点之间的距离相关联[9～11]。迭代次数过少，算法可能无法找到最优路径，而随着迭代次数的增多，算法耗时加大，导致收敛速度较慢。

3.2 初始化信息素浓度的改进

在算法初始化参数阶段，设定信息素浓度矩阵Tau时，虽将所有可能的路径设定为相同值，但蚁群算法的寻径是蚂蚁从起点出发行走至终点的过程，故可在起点与终点的路径以及周围将信息素浓度值设定比其他位置高，这样可以有利于增强最优路径对蚁群的吸引力，加快最优解的收敛速度。

3.3 信息素挥发因子ρ的改进

蚁群在其行走的路径上会留下信息素，信息素浓度并不会一直不变，而是会随着时间挥发。信息素挥发因子表示蚁群信息素的挥发速度。传统蚁群算法的信息素挥发速度在寻径过程中为常量。蚁群算法的挥发因子与收敛速度和全局搜索能力相关联，若挥发因子ρ的值过小时，蚂蚁会再次选择已走过的路径，陷入局部最优；反之，若ρ值过大，算法的全局搜索能力有所提升，但算法的迭代时间会大幅增加，导致收敛速度降低[12]。本文提出的改进信息素挥发因子与迭代次数相关联，使信息素挥发因子ρ随迭代次数k服从高斯分布。改进的信息素挥发因子ρ为

(6)

这里称k服从参数σ,μ的高斯分布，其中σ,μ,a可根据设定的迭代次数自适应调整；本文σ,μ取值分别为7.4，90；k表示算法的迭代次数。

这样蚂蚁在寻径时处于不同迭代次数时具有不同的信息素挥发因子ρ，使其根据迭代次数动态调整，将算法分为前、中、后期。在蚁群寻径的前期，即迭代次数处于[0,0.4k]时，信息素挥发因子为较小值并呈递增趋势，蚁群选择路径主要根据初始化的信息素浓度；随着迭代次数的增加，信息素挥发因子ρ逐渐增大，当迭代次数处于[0.4k,0.7k]区间时，各路径上信息素量达到一定程度，此时信息素挥发因子ρ为较大值，即各路径信息素挥发快，便于使蚁群开展全局搜索；当迭代次数处于[0.7k,k]时，信息素挥发因子ρ随迭代次数k递减，即在算法的后期，蚁群基本已寻找到最优路径，降低信息素挥发因子ρ加快最优路径的收敛速度。

4 仿真与分析

为验证优化算法的性能，在MATLAB上对改进蚁群算法的正确性和有效性进行测试，并比较利用传统蚁群算法和改进蚁群算法机器人进行路径规划的实际效果。利用栅格法建立二维栅格地图，环境模型为20×20的栅格。单位栅格长度为1，总长20，设置机器人为(0.5,19.5)，终点为(19.5,0.5)。实验过程中蚂蚁数目(m值)设定为60。设置仿真参数：迭代次数为200次，信息素重要程度因子α=1，启发函数重要程度因子β=6.8，信息素增加强度系数Q=1，传统蚁群算法信息素挥发系数ρ=0.5。改进蚁群算法ρ为上文自适应参数，传统蚁群与改进蚁群算法所设定的蚂蚁数目相同。本文对传统蚁群算法和改进蚁群算法分别进行多次仿真测试，测试结果如表1所示。

表1 传统蚁群算法和改进蚁群算法测试结果比较

从表1可以看出，改进蚁群算法较传统蚁群算法的收敛代数和最优距离都有所减少，改进蚁群算法收敛代数减少了135代，最优距离减少了2 m。

为更直观分析测试过程和仿真结果，将移动机器人寻优路径的收敛代数和所行走的轨迹进行可视化，如图3所示。

图3 移动机器人路径寻优结果

由图3(a1),(b1)可以看出，两种算法都能为移动机器人规划无障碍路径，从机器人路径轨迹图上看，传统蚁群算法寻优路径转弯次数多，运动轨迹曲折，而改进后的蚁群算法运动轨迹转弯次数少，轨迹较平滑。从收敛代数上看，传统蚁群算法收敛速度慢，且收敛性能不稳定，搜索效率低。而改进的传统蚁群算法明显提高了收敛速度，收敛性能更稳定，搜索效率更高，提高了全局寻优能力，说明改进后的蚁群算法在移动机器人寻优方面有着明显的优越性。

5 结束语

本文通过建立环境模型，分析传统蚁群算法的不足，并针对其不足在信息素启发函数、信息素初始值，信息素挥发因子方面对传统蚁群算法进行改进。通过MATLAB进行仿真，仿真结果表明：改进蚁群算法较传统蚁群算法在收敛速度，全局寻优，以及最优路径距离方面有明显的提升，证明了该算法的有效性和可行性。