基于改进蚁群算法的机器人路径规划问题研究

牛龙辉，季野彪

（西安工程大学电子信息学院，西安710600）

1 引 言

在智能体的研究中，路径规划问题一直担任着重要角色，是一个涉及智能控制、材料工程、人工智能和信息处理等相关专业学科的复杂系统工程[1]。机器人规划路径时，需要以一定的标准评判。在已知起始点和目标点的障碍环境下，机器人需要进行从起始点到目标点最优路径的寻找，即解决机器人的路径规划问题。文献[2]提出了一种基于粒子群优化的路径规划算法，在障碍环境下对机器人进行导航。首先定义一个隶属函数来评价路径的风险程度，考虑风险度和路径距离这两个性能优点，对机器人进行有效的路径规划。文献[3]着重介绍和评价了模拟退火（SA）的人工势场方法，改进了人工势场法中易陷入局部最优值的缺陷。模拟退火作为一种有效的局部极小值逃逸技术，已被应用于局部和全局路径规划中。文献[3]针对移动机器人室内定位技术的特点，在结构化环境下开发了室内移动机器人路径规划系统，针对路径规划的不足，提出了一种改进的A*算法，能够计算具有拐点、旋转方向和最小旋转角度的移动机器人定位。移动机器人定位试验表明，改进算法不仅简化了路径规划，而且可以调整机器人在拐点的姿态，能够满足机器人自主运动的要求。采用改进后的蚁群算法对机器人路径规划进行研究，提高了路径规划的实现效率[4]。

蚁群算法在全局路径规划中有着极大优势，拥有着计算简便，具有良好鲁棒性且易与其他算法相结合的优点，在此，采用改进后的蚁群算法对机器人进行路径规划，有效降低路径长度。

2 环境建模

首先，在机器人路径规划前，要进行障碍环境的建模。此处采用栅格法进行建模，在建模前需满足以下假设条件：考虑机器人的工作环境为二维空间，不考虑高度的影响，且障碍物处于静止状态；已知机器人的起始点和目标点，并将机器人视为质点，忽略自身尺寸的影响[5]。

用黑白网格表示环境。黑色栅格代表障碍物，白色栅格代表可行区，矩阵中1 代表障碍物，0 代表自由栅格。建立的环境模型如图1 所示。

图1 栅格地图

以机器人所在栅格为中心，机器人行走的方向节点共8 个，蚂蚁对栅格的访问是以访问一个栅格的中心点为准，如图2 所示。

图2 机器人运动范围

图中左上角第一个栅格为序号1，向右序号逐次加一，序号1 的栅格坐标是(0.5,19.5)，序号7 的栅格坐标是(6.5,19.5)，以此类推序号400 的栅格坐标为(19.5,0.5)，也就是右下角栅格。

3 蚁群算法及改进

3.1 基本蚁群算法

蚁群系统（Ant System 或 Ant Colony System）是由意大利学者Dorigo、Maniezzo 等人于20 世纪 90年代首先提出的[6]。他们对蚂蚁觅食行为进行研究时，发现蚁群整体处于一种智能的行为中。蚂蚁在觅食过程中总是可以找到一条最短的路径进行食物的搬运。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会在短时间内找到信息素浓度较高的路径，并在下一次搬运食物时走信息素浓度较高的路径，同时依旧留下信息素，形成一种正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源[7]。

选择下一节点的具体实现公式为：

其中，S 代表按照AS 算法得到的下一节点的概率，allowedk表示当前节点的可选节点集合。τij表示i 点到j 点的信息素量，ηij则是对应点之间的启发式量，其中表示两点间的欧式距离[7]。两点间距离越大，启发式量则越小，蚂蚁在节点i 时选择节点j 的概率就会较小。α 为信息启发式因子，表示此路径的信息素对后续探索时蚂蚁选择此条路径的影响程度，α 越大，后续蚂蚁选择这条路径的概率越大，β为期望启发式因子，反映启发信息对蚂蚁路径选择的影响程度。每次迭代结束，路径信息素都要进行更新。全局更新公式为：

其中ρ 表示信息素挥发因子，τij表示i 与j 点之间的信息素浓度，Δτij表示i 与j 点之间的信息素增量，表示第k 只蚂蚁在i 与j 点之间的信息素增量的贡献量。经典AS 算法通过迭代对信息素进行更新来选取最优路径[8]。

3.2 改进蚁群算法

在ACS 算法迭代过程中，参数对算法性能有着直接或间接影响，其中信息素挥发度参数ρ 的取值会直接影响算法的收敛速度与全局搜索能力。信息素挥发系数ρ 过大，会导致算法多样性降低，易出现搜索提前停滞，但收敛速度加快。ρ 较小时，算法的收敛速度慢，但算法多样性提高，搜索能力加强。所以对ρ 的选择需要综合考虑算法的全局搜索能力和收敛速度。

根据上述分析，固定的ρ 值存在一定的弊端，因此，构造一个动态改变信息素挥发度参数ρ 的函数如下：

式中，自变量 n 为迭代次数，σ、μ 为常数。ρ 与迭代次数n 有关，其函数曲线单调递增。前期随着n 的增大，ρ 曲线平缓上升；中期随着 n 的继续增大，ρ 曲线急速上升；到后期ρ 曲线趋于平缓。在搜索路径前期，ρ 取较小值是为了保留最优路径的更多信息；在搜索的中后期，ρ 取较大值，是为了加快收敛速度。

4 仿真及分析

为验证本算法的有效性，在MATLAB 2014a 上进行仿真实验。利用上文提到的栅格法构建环境模型，在相同环境下比较本算法与ACS 算法的仿真结果，并对实验结果进行分析。

算法参数的设置如表1 所示。

表1 参数设置

障碍物条件下（设置起点S=49，终点G=369）的两种算法的路径规划结果及收敛曲线分别如图3、图4 所示。其中实直路线代表经典蚁群算法，点线路线代表改进的蚁群算法。

图3 路径规划图

图4 收敛曲线

从对图3 曲线的分析中可知，经典AS 算法在障碍环境中遇见障碍物会出现徘徊现象，无法逃离局部最优解，其多样性明显较差，而本算法在快速收敛的同时，可得到全局最优路径。实验表明本改进算法在环境障碍物条件下是可行且有效的。

从图4 收敛曲线可见，本算法所得路径长度明显较经典AS 算法短，收敛速度也不慢。综上分析，通过在障碍环境对算法进行实验，验证了改进算法较经典AS 算法具有更强的寻优能力，算法多样性明显提高，且具有良好的准确性与鲁棒性，在解的质量与收敛速度方面表现出更好的性能。

5 结束语

针对经典AS 算法在路径规划中寻优能力不足和算法多样性低等问题，引入自适应信息素挥发系数，以加强全局寻优能力，提高算法多样性。仿真实验表明，改进算法有效地解决了经典AS 算法寻优能力不足缺陷，提高算法多样性，并具有良好的准确性与鲁棒性。