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

徐宏宇,唐泽坤,叶长龙

(沈阳航空航天大学1.电子信息工程学院，2.机电工程学院，沈阳 110136)

科技发展带动机器人技术的进步，智能移动机器人已经成为众多学者的研究重点,仓储搬运机器人也随之进入人们视野。能够让机器人良好地解决其在不同工作环境下的路径规划问题十分关键。让机器人在有障碍物的环境中，规划出一条从起始点到目标点的连续的、无碰撞的最优或次最优路径[1]。对于解决路径规划问题的算法已经被学者提出，如A*算法[2-3]、人工势场法[4-5]等传统算法，以及近些年学者提出的仿生算法也应用在路径规划中，如遗传算法[6]、粒子群算法[7]、蚁群算法等。

意大利学者Marco Dorigo受到自然界中真实蚁群集体行为的启发，于1991年首次提出基于蚁群的新型优化算法[8]。由于蚁群算法是一种随机搜索寻优算法，具有信息正反馈机制，能够进行并行计算，并且鲁棒性强等特点，在机器人路径规划上的研究取得了很好的成果。如在文献[9]中将算法应用于机器人搜救,使得其在复杂的障碍环境中也能正确到达目标点。但传统蚁群算法也存在一些缺陷，如计算周期长、收敛速度慢、出现局部最小化等问题。针对算法这些缺陷许多学者进行了改进研究。文献[10]分析阐述了算法的主要参数对结果的影响，通过数据统计对比分析得到优化的算法参数组合；文献[11]采用蚂蚁回退策略来杜绝遇到U型障碍物时容易陷入死锁现象，导致蚁群算法停滞的问题；文献[12]通过引入最大、最小蚁群系统对更新的信息素浓度进行限制，解决了蚁群算法中因信息素差异过大而陷入“早熟”的问题；文献[13]将蚁群算法与遗传算法进行融合，将遗传算法的全局搜索能力和群算法的快速收敛互补，实现快速搜索。

本文提出一种蚁群算法的自适应启发式函数，引入自适应权重的目标点吸引评估，对寻优蚂蚁实行奖励提高信息素，以提高算法的收敛速度、全局搜索能力，并引入转向代价，以进一步缩短所寻路径并起到平滑处理的作用。针对死锁问题，通过A*算法随机对死锁蚂蚁进行辅助实现复活。通过MATLAB仿真与传统算法对比验证，得出改进算法在路径规划的准确性以及快速收敛能力。

1 环境模型建立

利用栅格法[14]将外部环境抽象离散化建立机器人二维运动环境模型，使复杂问题简单化，减少数据的计算量。

首先将室内环境抽象成二维平面，在静态二维地图中将地图按照一定步长分割，并将环境用黑白网格表示。黑色网格代表障碍物不可同行区域；白色网格则代表可通行区域，又称自由行驶区域。将不可行区域和自由行驶区域用一个二进制矩阵表示，矩阵中1代表障碍物，0代表自由栅格，由此在环境中建立一个可描述环境的路径规划地图如图1所示。

图1 栅格地图

以自身所在栅格为中心的8个节点任由机器人选择，如图2所示。

图2 机器人运动方向

左下角第一个栅格的序号为1，依次向右序号增加，则序号1的栅格坐标是(0.5,0.5)，序号5的栅格坐标是(4.5,0.5)，序号6的栅格坐标是(0.5,1.5)，依次类推，则栅格序号对应的节点坐标关系如公式(1)所示。

(1)

2 蚁群算法及改进

2.1 蚁群算法的基本原理

自然界的蚂蚁觅食过程中，能在其走过的路径上分泌一种化学物质称为信息素[15]。信息素会留在蚂蚁所经过的路线并保留一段时间，引导蚂蚁的运动方向，使蚂蚁倾向于朝着信息素浓度大的方向选择。同时一些蚂蚁会开辟新的道路，当寻找到更短的道路后，相同时间内较短路径上信息素含量高，逐渐吸引更多的蚂蚁到这条道路。如此重复，最后使得最短的道路被保留下来。

2.2 蚁群算法模型

(2)

蚂蚁完成一次循环后进行信息素的更新，各路径信息素根据下式进行调整

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

(3)

(4)

(5)

其中，ρ表示挥发系数，通常设置ρ<1来避免轨迹上的信息量无限累加；Δτij表示本次循环中节点i到节点j的信息素增量；Q是定值表示信息素总量；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。

2.3 蚁群算法的改进

针对基本蚁群算法的收敛速度慢、容易局部最优的缺点，本文提出几点改进：(1)转移概率中加入转弯代价；(2)节点的启发信息改进；(3)信息素更新方式的改进。

2.3.1 改进转移概率

机器人在运动过程中转弯会造成，因此要尽量避免机器人大量转弯，增强路径的平滑性，因此引入转弯代价评估，由蚂蚁在栅格中的运动方向可知，转角只能是0°、45°、90°和135°，因此加大转角的惩罚力度。转弯代价值如公式，转弯角度越小，被选中的概率越大，改进后的节点转移概率公式如下

(6)

(7)

2.3.2 启发函数的改进

在栅格地图中仅使用相邻栅格构造的启发函数差异较小，造成算法搜索效率低。因此利用A*算法中目标节点对待选节点的影响引入到启发函数，由此来加快蚁群算法的收敛速度，提高效率。通过利用到当前节点、转移节点、目标节点的欧氏距离来构造评价函数，改进后的算法启发函数见以下公式

(8)

(9)

其中，dij为节点i和节点j之间的欧氏距离，djE为节点j和终点E之间的欧氏距离。将转移节点与目标节点的关系添加到启发函数中，使得蚂蚁在运动过程中更具有方向性。ω权重值根据路径动态调整，可以让蚂蚁随着目标的接近方向感越强，提高算法的效率。

2.3.3 改进信息素分配机制

传统蚁群算法在信息素更新时是将所有路径的信息素进行更新，这样使得步长较长的路径上的信息素也得以更新，这就导致所有探索到的路径信息素含量差别较小，最优路线对后续蚂蚁吸引力弱，导致无法快速收敛。为了增加路径的吸引力，本文使用了信息素奖励机制，对本次迭代的最优路径和所有路径中最优路径进行奖励，增加其路径上的信息素量。改进的信息素分配方式如式(10)。

(10)

3 改进算法步骤

步骤1：栅格地图的构建，建立对应的描述矩阵用于存储障碍物情况。

步骤2：对种群数量M，迭代次数k,轨迹的重要性α，路径的能见度β，转折代价因子γ，信息素的挥发系数ρ，信息量Q以及起始点这些参数的初始化。

步骤3：将蚂蚁种群放置在起点。

步骤4：根据公式(7)选择下一节点，运用公式(6)记录转折代价同时记录拐点。

步骤5：更新运动节点禁忌表并判断蚂蚁是否运动至目标节点，如若蚂蚁无路可走判定该蚂蚁死亡并执行步骤6。

步骤6：随机选择是否进行操作，若未被选择，则此蚂蚁彻底死亡。若被选择，借助A*算法进行从死亡节点到目标点的局部路径规划，实现此蚂蚁的“伪存活”，并将局部路线与已经探索路线进行拼接融合。

步骤7：记录目前为止最短路径，同时记录本种群中最短路径，利用公式(5)和公式(10)对全局信息素进行更新。

步骤8：判断是否达到最大迭代次数，条件成立则输出最优路径，否则执行步骤(2)。

算法流程图如图3所示。

图3 算法流程图

4 算法仿真分析

为了验证本文改进蚁群算法性能，本文使用MATLAB2014a仿真软件,利用上文提到的栅格法构建环境模型，在相同环境下对两种算法进行大量仿真对比验证。

4.1 参数选择

蚁群算法的参数选择对算法实际应用效果有着重要影响，而参数的设置主要还是通过统计和经验值，而蚁群算法中重要的参数有蚂蚁数目M，轨迹的重要性启发因子α，路径的能见度因子β，以及挥发系数ρ，这些系数的不同组合直接影响着路径的最优效果。

蚂蚁数量的多少影响着算法的稳定性，但蚂蚁数目增加，算法的收敛速度降低影响到算法的运算效率，而蚂蚁数量过少又无法准确地寻找出最优路径。启发因子α过高会导致蚂蚁对路径上信息素更加敏感而忽略路径节点距离代价，启发因子β过高则导致蚂蚁只注重节点距离而忽略其他节点信息素的诱导，因此要设置好合理的α与β的比例关系。挥发系数ρ对算法的随机选择产生影响，ρ设置过大导致信息素损失过快，降低先前探索路径的吸引力。通过大量计算机仿真、组合、统计确定参数，选择参数如下：M=20，α=1，β=8，ρ=0.45。

4.2 仿真

此次仿真搭建了规模为20×20的两种不同的工作环境，在相同环境下将两种算法进行仿真对比。两种算法在不同环境下分别仿真20次，并对数据进行比对分析。

图4为在障碍物较为集中的环境地图下算法路径搜索结果和迭代效果，图5是障碍物相对复杂分散环境下的算法比较。改进的蚁群算法与传统蚁群算法分别由星型线和实线表示。通过仿真图的比较可以看出，改进的蚁群算法与传统蚁群算法比较，在不同的环境中改进算法均体现出良好的路径搜索能力。表1给出了两种算法在不同环境下分别运行20次的数据统计。两种算法均找出最短路径，但从多次算法的最优解次数来看，本文改进的蚁群算法具有良好的准确性、稳定性。从算法的迭代效果来看，算法在整体上呈现收敛趋势，在初期出现波动变化，在后期逐渐趋于稳定。传统蚁群算法收敛速度缓慢，而且在收敛中期还会出现小幅度的波动现象。而本文算法在初期路径探索后，快速稳定的收敛到最优值，并且改进的蚁群算法在转弯次数上少于传统算法，对路线进行了平滑处理。

图4 简单环境下实验效果与迭代收敛

图5 复杂环境下实验效果与迭代收敛

环境算法最优解最差解平均值平均拐点数平均迭代收敛数最优解次数环境1传统算法34.384838.799037.224412383改进算法34.384834.384834.384810920环境2传统算法30.384840.041638.524814496改进算法30.384830.384830.384811920

5 结论

文章中利用栅格法构建二维环境地图，为算法提供环境基础，研究分析传统算法的不足之处后通过改进自适应启发式函数，引入自适应权重的目标点吸引评估，使蚂蚁在路程前期有足够探索能力，离目标点越近方向感增强快速收敛。对寻得最优路径蚂蚁的奖励制度增加了最优路径的吸引力，达到快速收敛。设置运动方向引入转向代价，减小了运动过程中不必要的转弯，实现路径平滑，解决在搜索初期蚂蚁死锁问题，借助A*算法随机性的对死锁蚂蚁进行辅助实现“伪存活”的措施对传统算法进行改进优化。

利用MATLAB对算法进行仿真对比后可以看出，改进后的蚁群算法不仅提高算法的收敛速度、全局搜索能力，还进一步减少路径上不必要的转向，起到平滑处理的作用，具有足够的准确性和稳定性，实验结果良好。