动态环境下蚁群算法的路径规划研究

胡国栋， 陈 波， 欧凤琴

（1.上海埃奇机器人技术有限公司， 上海 201615； 2.安徽工程大学机械工程学院， 安徽芜湖 241000；3.埃华路（芜湖）机器人工程有限公司， 安徽 芜湖 241000）

0 引言

按照机器人对周围环境的知晓程度， 移动机器人路径规划[1]大致可分为两种：环境信息完全已知的全局路径规划，环境信息部分未知或完全未知的局部路径规划。人工势场法[2]、粒子群算法[3]、遗传算法[4]以及蚁群算法[5]对于环境信息完全已知的全局路径规划都体现出较大的应用价值。 在常用的路径规划算法中蚁群算法较为成熟和高效， 蚁群算法是一种搜索寻优强启发算法， 蚁群算法在TSP 问题[6]、函数优化问题[7]和路径规划问题[8]中有着较好的表现， 尤其对于路径规划这类离散系统具有很强的适用性。 文献[9]中提出迭代自适应因子去调节信息素的更新强度加快收敛速度以及信息素衰减因子避免算法早熟；文献[10]通过提出两个新的启发式因子和一个伪随机系数重新定义状态转移函数提高搜索随机性， 并引入罚系数结合回退策略解决蚂蚁死锁问题， 但是频繁回退有可能减缓算法的运行速度。

本文采用栅格法模拟移动机器人的工作环境， 针对基本蚁群算法存在的固有缺陷，如易陷入局部最优、收敛速度慢，及死锁等问题，提出利用扩展树随机优化方法，创建虚拟路径和蚁群更新域信息素更新原则， 改进信息素的更新方式；提出局部子起点再规划策略，解决蚂蚁死锁问题；针对传统蚁群算法对动态环境适应度低的问题，引入不断刷新的滚动窗口以探测环境信息； 依据提出的避障策略，根据环境信息作出决策。

1 全局路径规划

传统蚁群算法中蚂蚁通过向着信息素浓度较高的路径移动来寻找最优路径， 这种正反馈机制可极大地加快收敛速度，但会导致蚁群多样性减小，全局搜索能力减弱， 如何权衡收敛速度和种群多样性是一个值得商榷的问题。 此外，在算法迭代早期，由于信息素矩阵中还没有优势路径出现，蚂蚁有着较大概率陷入死锁状态。针对这些问题，本文作出以下改进。

1.1 蚁群更新域信息素更新策略

在经典蚁群算法中， 信息素更新常采用在每一次迭代后对所有觅食成功蚂蚁搜索到的路径进行一次更新，种群多样性大但收敛速度慢；在最大最小蚂蚁系统中，每一次迭代后仅对全局最优蚂蚁进行更新， 虽然加快了算法收敛速度，但失去种群多样性，容易陷入局部最优，导致算法早熟。 本文提出介于两者之间的权衡信息素更新方式，限制每次允许更新的阈值，每一次迭代后仅对阈值范围内的蚂蚁搜索路径进行更新， 阈值范围表示为（Upperlimit，Lowerlimit）。

式中，Lbest是当前代为止全局最优路径长度；f 是表征更新域的系数，介于0～1 之间；Dg是全局规划起点到规划终点的欧式距离；n 为阶数，0-inf， 值越大越接近最大最小蚂蚁系统。

1.2 扩展树随机优化原则

蚁群算法作为一种强启发式算法， 信息素对单一蚂蚁行为的影响很大，信息素矩阵失衡，导致某条路径信息素强度过于优势， 由于正反馈机制导致蚂蚁大部分集中该条路径，导致算法早熟。 为了避免陷入局部最优，本文提出一种基于扩展树的优化路径方法， 藉由这种方法创建虚拟路径，这些路径仅用于更新信息素，不作为实际搜索出的路径， 旨在调节信息素矩阵避免信息素矩阵过早出现失衡。在每次迭代结束后选取待优化路径，优化后作为虚拟路径用于更新信息素， 待优化路径为每一次迭代中路径长度最大和最小的两条路径以及区别于最大最小的随机一条路径。 同时，避免出现拖慢算法程序，定义启动系数去控制算法的运行。

对于任一条待优化路径， 路径上的节点称为元扩展节点，向外扩展的节点称为扩展节点，扩展树优化步骤见图1。①初始化；②输入待优化路径，元扩展节点序号设为1；③元扩展节点位置向外扩展。 若扩展节点触碰边界或者障碍物则该方向停止扩展并且将该方向的值设为INF，停止扩展； 若扩展节点属于待优化路径且元扩展节点与扩展节点之间直线可达， 用元扩展节点与扩展节点之间直线路径代替待优化路径中元扩展节点与扩展节点之间路径，生成一条待选择路径， 将值设为路径长度，停止扩展；④元节点所有方向达到停止条件，选择值最小的待选择路径更新待优化路径；⑤元扩展节点序号自增，重复③和④， 直到元扩展节点序号达到最大，输出优化路径。

图1 扩展树随机优化流程图

1.3 信息素更新素规则

如前所述， 每次迭代结束可获得若干条觅食路径，t+1 时刻与t 时刻的关系见式（3）。

式中，τmax，τmin分别为预设的信息素最大值和最小值。

当环境信息较为复杂时，在蚁群算法早期，蚂蚁随机搜索寻优时极易死锁状态。针对死锁问题，文献[11]直接令处于死锁状态的蚂蚁死亡，不对其进行任何处理，这样当环境很复杂有很多蚂蚁陷入死锁状态时，迭代早期无或者仅有少量有效路径，信息素矩阵无或者仅有少量增益，造成下一次迭代，死锁率仍然很高，陷入恶性循环，因此该方法不利于蚂蚁寻优也不能解决复杂环境的死锁问题。

本文结合回退策略提出局部子起点再规划方法，来解决蚂蚁死锁问题。其中子起点的代价函数如式（5）所示。

S（N）=（η（N）μ）·（f（N）v）（5）式中，N—栅格节点；η—启发式信息矩阵；f—节点附近可行节点数的归一化系数矩阵；μ—表述启发式信息的重要程度；υ—表述归一化系数的重要程度。

对于任一只蚂蚁陷入死锁时， 将其走过的路径分为前部和后部， 其中前部是全局规划起点和上一次局部再规划起点之间的路径，后部是余下的除死锁点的路径。如图2 所示，局部子起点再规划步骤：①初始化参数；②蚂蚁按照状态转移概率选择下一节点； ③若蚂蚁在当前节点有可选下一节点，继续运行蚁群算法；④若蚂蚁在当前节点无可选下一节点。 若后部为空，采取回退策略，子起点不变，并从禁忌表中删除死锁节点；若后部非空，则根据价函数在后部中选择值最大的节点作为子起点， 将蚂蚁路径更新为全局规划起点和当前局部再规划起点之间的路径； ⑤蚂蚁选择下一节点。若仍然无可选节点，令当前蚂蚁死亡；若有可行节点，重复②、③和④，直到蚂蚁死亡或者到达目标点结束。

图2 解决蚂蚁死锁流程图

1.4 改进蚁群算法步骤

移动机器人路径规划步骤见图3。 ①初始化：初始化移动机器人的栅格环境信息并设置基本参数；②蚂蚁由起始点开始转移；③判断栅格环境是否可行。若下一栅格可行且未到达终止点，则按照转移规则继续前进，计算并保存路径长度，将蚂蚁每次到达的栅格节点从禁忌表中删除；若无可行下一栅格，执行蚂蚁死锁解决策略，直到到达目标点或者蚂蚁死亡；④扩展树随机优化；⑤按照式（3）和式（4）更新信息素；⑥判断是否达到算法最大迭代次数。 如果已达到，输出最优路径并退出；否则进入下一次循环。

图3 改进蚁群算法步骤

2 动态环境局部路径规划

滚动窗口算法基本思想是依靠机器人实时探测到的局部环境信息，以滚动的方式进行在线规划。滚动窗口随着机器人的移动不断行进而刷新，通过采集到的信息，预测是否会发生碰撞，若有可能发生碰撞，根据不同的局部信息采取相应的避障策略在窗口内重新规划路径， 否则按照规划好的路径行走。

2.1 局部避障策略

本节讨论滚动窗口中不同局部信息应采取的避障策略：①滚动窗口内不存在动态障碍物或者障碍物远离机器人，机器人沿着全局规划路径行进即可；②滚动窗口内存在动态障碍物时，轨迹规划周期内，机器人和障碍物均可视为匀速直线运动。 如图4 所示，为简单起见， 将障碍物适当膨化后，视为圆形。

图4 滚动窗口监测障碍物

根据余弦定理， 在一个采样周期（dt）内的移动距离可由式（6）表示。

式中，θ 是vobs与L1的夹角（锐角）。

根据d 的大小可分为以下几种情况：

（1）d＞robs+r+step。 动态障碍物在规划窗口外运动，不会发生碰撞；机器人沿着全局规划路径行走即可；

（2）robs+r＜d≤robs+r+step。 如图5 所示，动态障碍物运行在规划窗口内，可能发生侧碰。 此时可选择等待障碍物运行完再运动， 或者根据式（9）计算可行域，符合式（9）的所有ω 的集合即为可行域。

图5 机器人与障碍物可能发生侧碰

（3）0＜d≤robs+r。 如图6 所示，机器人处在动态障碍物的运行轨迹上， 可能发生正碰或者追尾； 此时可通过式（10）计算可行域，符合式（10）的所有ω 的集合即为可行域。

图6 机器人与障碍物可能发生正碰或者追尾

2.2 动态规划流程

图7 所示的滚动窗口规划流程：①初始化参数；②利用全局先验静态环境运行改进蚁群算法进行路径规划；③对滚动窗口里环境数据持续监测采集。 若无动态障碍物，按规划好的路径行走；若有动态障碍物，根据采集数据预测障碍物轨迹和即将可能发生的碰撞类型， 选择相应的策略；④根据选择的策略为机器人规划局部路径，使得机器人安全避开障碍物； ⑤刷新滚动窗口，重复步骤③和④，直到机器人到达目标点。

图7 滚动窗口规划流程图

3 仿真实验及分析

3.1 改进蚁群算法全局静态规划

为验证算法性能，在20×20 的栅格环境实施路径规划仿真实验， 移动机器人的起始点坐标为（0.5，19.5），目标点坐标为（19.5，0.5）。 通用参数如下：迭代次数k=200，蚂蚁数量m=50，信息素重要程度α=1，启发式重要程度β=7，信息素蒸发系数ρ=0.3。本文信息素上界设置为1，下界设置为0，μ=1，ν=7；对于文献[9]算法，信息素上界设置为120，下界设置为0，惩罚系数设置为0.85，随机系数设置为0.1。

多算法路径规划结果见图8 和图9， 结合表1 可以看出，本文改进蚁群算法相对另外两种算法，规划出最优路径的收敛迭代次数明显减少，路径的最优值也是最小的；见表2，多次均值试验表明，从最优值均值和最优率看，本文改进蚁群算法具有很强的稳定性，并且从一代死锁率看本文提出的局部子起点再规划策略相对另外两种算法可以明显降低迭代早期蚂蚁的死锁率，且优于另外两种算法。

图8 多算法路径规划路径结果比较

图9 多算法路径规划路径长度比较

表1 单次运行结果统计数据

对比各算法稳定性， 对三种算法分别独立运行100次，结果见表2。

表2 多次运行结果统计数据

3.2 改进蚁群算法局部动态路径规划

用20×20 栅格模拟移动机器人所处的运行环境， 设置起始点为（19.5，0.5），目标点坐标为（0.5，19.5），参数设置与前述静态环境下改进蚁群算法保持一致， 初始环境下使用改进蚁群算法规划出全局最优或者接近最优路径，见图10。

图10 改进蚁群算法全局路径规划结果

直线障碍物1、2 和3运行轨迹见图11，在t1 时刻， 障碍物1 运行到（13.5，4.5）点，滚动窗口内移动机器人检测到障碍物， 并预测出其速度大小及方向， 计算出预测航迹线， 机器人到航迹的距离触发侧碰避障策略； 在t2时刻， 障碍物2 运行到（10.5，14.5）点，滚动窗口内移动机器人检测到障碍物， 并预测出其速度大小及方向， 计算出预测航迹线， 机器人到航迹的距离触发正碰避障策略； 在t3时刻， 障碍物3 运行到（5.5，19.5）点，滚动窗口内移动机器人检测到障碍物，并预测出其速度大小及方向，计算出预测航迹线，机器人到航迹的距离触发追尾避障策略， 作出如图11 所示避障轨迹。

图11 动态环境下改进蚁群算法避障路径规划结果

4 结束语

本文针对传统蚁群算法在复杂环境中路径规划的缺陷，提出蚁群自适应更新域信息更新原则、随机扩展树优化原则、局部子起点规划以及滚动窗口的改进蚁群算法，用栅格图模拟移动机器人的运动环境。仿真分析表明，本文改进蚁群算法，能够在不损失程序运行时间的前提下，加快算法收敛速度， 能够改善陷入局部最优和迭代早期蚂蚁陷入死锁的情况；通过加入滚动窗口，为移动机器人规划出一条能实时避开环境中动态障碍物的最优或者近似最优无碰路径，更加适合移动机器人实际所处环境。