改进蚁群算法在机器人路径规划中的应用

李国涛 李丹 曹蒙

摘要：路径规划对移动机器人具有极其重要的意义，传统的蚁群算法存在收敛速度慢、容易陷入死锁以及容易陷入局部最优解等缺陷;本文采用栅格法进行地图空间建模，并且在蚁群算法中引入人工势场的概念，以此优化现有的蚁群算法;仿真结果显示该算法明显优于传统蚁群算法，可以让机器人在复杂环境中选择更好的前进路线。

关键词：蚁群算法;人工势场法;移动机器人;路径规划

0 引言

移动机器人是集环境感知、路径规划、动态决策和行为执行于一体的的复杂控制系统。其中路径规划是机器人研究领域的技术重点，经过几十年的发展，路径规划算法分为三大类：传统路径规划算法、启发式算法及智能仿生路径规划算法。其中传统路径规划算法包括可视图法、人工势场法、模拟退火法、模糊逻辑算法等;启发式算法具有很强的路径搜索能力，可以很好的在离散的路径拓扑结构中运用，常见的启发式搜索算法有A*算法、Dijkatra算法及Floyd算法;智能仿生算法是人们通过仿生学的研究，在一系列的自然现象中发现的算法，主要包括：蚁群算法、粒子群算法、遗传算法和神经网络算法。其中蚁群算法是人们受蚂蚁觅食的启发而产生的算法，蚂蚁在觅食的过程中会分泌一种信息素，并在其寻找食物的途中在道路上留下一定浓度的信息素，信息素会随时间挥发。在觅食的过程中，路程越短则蚂蚁遍历的次数越多，信息素浓度也就越高，蚂蚁将信息素浓度作为选择路径的依据，信息素浓度越高，路径被选择的概率越大，随着时间的推移，最短路径上的信息素浓度会越来越高，最终所有蚂蚁都会选择最短路径，从而达到路径规划的目的。蚁群算法本质上是一种并行算法，易于计算机实现，蚁群算法最早是作为一种解决组合优化问题的元启发式算法被提出，具有易与其他方法结合、鲁棒性较强等优点，但是传统蚁群算法同时存在搜索时间长、容易陷入局部最优、面对凹形障碍物容易陷入死锁等缺点。本文主要研究改进后的蚁群算法在机器人路径规划中的应用。

1 环境建模

设机器人运动环境为二维静止空间，由于栅格法地图表达规范、易于实现，所以对机器人运动空间进行栅格法建模。将机器人视为质点，占据一个栅格，同时如果静态障碍物只占据某栅格的一部分，则将其视为完全占据此栅格。机器人的运动方向共有8个运动方向，同时机器人可在匀速和静止两个运动状态中自由切换。运用栅格法进行环境建模的好處在于对于任何形式的障碍物都能很好的描述，而可视图法或自由空间法对于圆形障碍物无法建模，此外，运用一系列二值信息存储障碍物特征及位置，方便计算机的存储与更新，因此，选用栅格法进行环境建模具有显著的优势。

2 蚁群算法基本原理

2.1 传统蚁群算法

受蚂蚁觅食过程的启发，1991年首次提出了蚁群算法[10]。在人工蚁群算法中，设m为蚂蚁总数，蚂蚁从某个节点转移到另一个节点是由路径上的信息素决定的，在t时刻，蚂蚁k从节点i转移到节点j的状态转移概率  为：

所有蚂蚁完成一次觅食后，需要对信息素进行更新，随着时间的推移信息素会逐渐挥发，同时在蚂蚁经过的路段信息素量会增加，更新公式为：

2.2 改进蚁群算法

基本蚁群算法虽然能够规划出从起始点到目标点的路径，并有较强的鲁棒性，但依然存在很多不足，主要有容易过早停滞、搜索时间过长、效率较低等缺点。本文针对传统蚁群算法的先天不足，对基本蚁群算法做出以下几点改进，从而加快算法收敛速度，优化算法路径选择，提高算法性能，使算法更加适合移动机器人的实际使用。

（1）U形栅格优化

在蚁群算法中，蚂蚁很容易陷入U形障碍物并发生死锁，从而导致算法时间过长甚至停滞，刘徐迅等人提出了蚂蚁回退策略[11]，以此增加算法的鲁棒性。但是当U形障碍物过多时，蚂蚁需要反复回退、反复判断，因此增加了很多计算量，使搜索时间过长。本文采用填补的方式对U形障碍物进行填补，对于栅格中任意节点，如果与其相邻的上下左右四个方向中的三个方向都存在障碍物或禁忌栅格，则将该节点标记为禁忌栅格，不允许蚂蚁通过。同时，如果填补过后出现新的满足填补条件的栅格，则继续填补，直至栅格地图中所有满足条件的栅格都被填补。

障碍物，因与10号栅格相邻的三个方向的栅格同时存在障碍物，因此将10号栅格标记为禁忌栅格，对于6号栅格，因与其相邻的5号、7号栅格都存在障碍物，且10号栅格为禁忌栅格，因此将6号栅格也标记为禁忌栅格。

（2）人工势场法确定初始信息素

在基本蚁群算法中，初始信息素      ，即总是被设置为一个常数。地图上相同的信息素浓度导致蚂蚁在前期没有足够信息找到较优的路径，使算法在前期收敛速度过慢，因此设置合理的初始信息素对于提高算法初期的收敛速度具有重要作用，可以显著的提高算法初期收敛速度。本文提出一种基于人工势场法的设置初始信息素的方法，即在出发点设计斥力势函数，降低出发点的初始信息素浓度，在目的地设置引力势函数，提高目的地的初始信息素浓度。

式中ω为固定系数，di和dj分别为栅格节点到出发点和目标点的距离，为一阈值，保证所有栅格的初始信息素都不低于这个阈值，在一定程度上这也保证了算法避免过早陷入局部最优。

2.3 基于改进蚁群算法的路径规划

在蚁群算法中通过对U型栅格进行优化以及引入人工势场法确定初始信息素来提高蚁群算法的性能，把改进后的蚁群算法应用到移动机器人路径规划中，具体步骤如下。

（1）对环境采用栅格法建模，并且初始化机器人起始位置、方向等相关参数以及目标点的位置及相关参数。

（2）对栅格法地图中的U形障碍物进行填充，并且根据人工势场法设置出发点和目的地的信息素浓度。

（3）当一只蚂蚁到达终点时根据蚁群算法信息素浓度更新公式对其经过路段上的信息素浓度进行更新。