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

刘永建，曾国辉，黄 勃，李晓斌

(1.上海工程技术大学 电子电气工程学院，上海 201620；2.上海应用技术大学 电气与电子工程学院，上海 200235)

移动机器人路径规划是当下研究的热点，在移动机器人路径规划的发展过程中，科学家提出了各种算法，如RRT算法[1]、模拟退火算法[2]、人工势场算法[3]、粒子群算法[4]、Dijkstra算法[5]、A*算法[6]和蚁群算法[7]等。

但是上述提及的各种算法，都存在各自的缺点。RRT算法在搜索过程中进行随机搜索，只要从起始点到目标点有连线，则立即生成一条路径，所以生成的路径既不能保证路径最优，又不能保证搜索时间最短。粒子群算法与模拟退火算法效果的优劣在于适应度函数的选择。Dijkstra算法，属于一种贪心算法，其只考虑当前节点到下一节点的距离，易陷入局部最优。算法在搜索期间进行全局搜索，搜索时间慢，而且搜索的方向有可能与目标点相背离，最终导致搜索失败。A*算法在Dijkstra算法的基础上，引入启发函数引导路径搜索的方向。但传统A*算法通过比较邻域的启发函数值F来逐步确定下一个路径栅格，当启发函数值存在多个最小值时，A*算法不能保证路径搜索获得最佳解决方案。

对于路径规划问题，国内外学者做了大量研究。在文献[8]中，提出了一种改进的遗传算法。该方法在初始种群生成过程中增加了偏移机制，并且将人工势场算法和偏移机制分别引入到交叉算子和变异算子中，提高了全局搜索的能力。文献[9]提出了最大最小蚂蚁思想，在一定程度上解决了因信息素增长过快导致的局部最优问题。文献[10]提出了一种改进的蚁群算法，在算法中基于狼群法则对信息素进行更新，避免陷入局部最优。

传统的蚁群算法[11]存在搜索速度慢且易陷入局部最优的缺点。本文对传统的蚁群算法进行改进，将A*算法[12]和蚁群算法相结合，在传统的A*算法的基础上，改进估价函数，增加了目标点对路径搜索的影响程度。然后，文中改进信息素挥发因子[13]，使信息素挥发因子动态变化。最后通过MATLAB仿真验证，结果表明改进的蚁群算法在最短路径上明显短于传统的蚁群算法，且在收敛速度上明显比传统的蚁群算法[14]快。仿真验证结果证明本文提出的改进算法是有效的。

1 建立栅格地图环境

栅格法(网格法)是机器人路径规划建立地图环境的常用方法，适用于各种算法的环境建模。本文采用栅格法对蚁群算法[15]的地图环境进行建模，建立大小为20×20的方格，坐标轴依次从左到右，从上到下标注。本研究将机器人的整个工作环境划分为20×20的大小。环境中若存在障碍物，将其对应的方格标注为黑色，不满一方格的按照一个完整的方格计算；白色的区域代表完全可通行区域。在(0.5,19.5)处设为起始点，在(19.5,0.5)处设为目标点。在网格环境中，机器人可以安全地搜索可行的最佳路径，同时避开障碍物，如图1所示。

2 传统的蚁群算法

蚁群算法是科学家从蚂蚁觅食的行为中得到的启发，它是由Marco Dorigo于1992年在他的博士论文中提出的。传统的蚁群算法主要模仿蚂蚁觅食的行为，蚂蚁通过释放信息素进行信息的传递。当然，并不是所有的蚂蚁都会循规蹈矩，有的蚂蚁会另辟蹊径，有可能会发现更短的路径。在蚁群算法中，针对这一现象，科学家引入信息素与启发函数对目标点的影响对路径进行选择。

蚂蚁k(k=1,2,3,…,m)根据移动过程中所有先前蚂蚁留下的信息素对下一节点进行选择。传统的蚁群算法根据状态转移规则选择下一个节点。在蚁群算法中，禁忌表tabuk(k=1,2,3,…,m)表示蚂蚁k当前正在传递的节点。当蚂蚁全部寻径完成时，清空禁忌表并继续下一次迭代。根据信息素和启发式信息的分布确定蚂蚁的状态转移概率。

状态转移概率公式

(1)

启发函数

(2)

其中，ηij(t)为启发函数，表示的是路径长短对节点的选择影响程度，在求解距离的方法中，典型的有欧式距离与曼哈顿距离。曼哈顿距离不能直接确定对角节点之间的距离，欧氏距离是两点之间的线性距离。本文选择欧式距离法。距离越大，启发函数的值越小，相反，距离越小，启发函数的值越大，则从当前节点选择下一节点的概率越大。

信息素浓度

Tij(t+n)=(1-ρ)·Tij(t)+ΔTij(t)

(3)

(4)

3 改进的蚁群算法

3.1 A*算法

A*算法是一种启发式搜索[16]算法，它是在Dijkstra算法的基础上，提出的一种新算法。Dijkstra算法是一种贪心算法[17]。A*算法在其基础上，引入一个启发函数，在保证最优路径的前提下，采用启发式搜索。A*算法通过估价函数确定搜索方向，使其朝着目标点前进，该启发式搜索的估价函数是

f(n)=g(n)+h(n)

(6)

其中，f(n)表示节点n的估价函数；g(n)表示从起点到当前节点的实际代价；h(n)表示当前节点到目标点的估计成本。本文使用欧式距离测量两点之间距离

(7)

其中，(x1,y1)、(x2,y2)分别表示两节点n1、n2的坐标。

本文将A*算法与蚁群算法相结合，在A*算法的基础上，将启发函数作如下改进

f(n)=mg(n)+(1-m)eh(n)h(n)

(8)

其中，m为[0,1]之间的常数，表示g(n)与h(n)对f(n)的影响程度；eh(n)增强了启发函数对估价函数的影响程度，增加了目标点对路径搜索的吸引力。

3.2 改进信息素挥发因子

在传统的蚁群算法中，信息素挥发因子[18]代表蚂蚁剩余信息量的挥发速度，通常为一固定常数。若在搜索时全程保持信息素的挥发速度为一恒量，则会降低全局搜索的效率。本文通过改进信息素挥发因子ρ，使ρ随时间服从泊松分布。ρ的变化情况如下：在路径搜索前期，路径的选择主要依靠信息素的指引，此时使信息素挥发因子的值为一较小值；在路径搜索中期，信息素量已积累到一定程度，为了提高全局搜索的能力，将信息素挥发因子的值取为一较大值；在路径搜索后期，路径的选择较单一，使信息素挥发因子的值降低，增加信息素的导向作用。信息素挥发因子ρ根据以下公式改进

(9)

称x服从参数为λ(λ>0)的泊松分布，并且根据实验获得λ的值，本文λ取值为10。k取NC的值，代表算法的迭代次数。

3.3 改进启发函数

在传统的蚁群算法中，启发因子η与当前节点到下一节点之间的距离成反比。不考虑目标点和当前节点的影响程度，容易陷入局部最优。本文将A*算法的思想融合到蚁群算法中，将两种算法相结合，可以提高收敛速度。改进的启发函数如下

(10)

其中，ηij代表启发函数；m为(0,1)的常数，m的取值根据实时环境确定。dij表示当前节点到下一节点的距离，die表示当前节点到目标点的距离，本文增加了目标点对节点选择的导向作用。

3.4 改进的算法具体步骤

步骤1环境建模。使用网格法构建二维静态地图模型。黑色代表障碍物信息，白色代表安全可通行区域，不满一格的障碍物按照一个网格计算，机器人可以自由地通过白色区域；

步骤2 初始化参数。例如迭代次数NC、信息素因子α和期望启发因子β等参数；

步骤3将所有蚂蚁置于起点并准备搜索；

步骤4结合轮盘赌法和状态转移概率公式对下一节点进行选择；

步骤5信息素更新。在蚂蚁k完成搜索后，根据改进的算法更新信息素；

步骤6重复步骤4和步骤5，直到蚂蚁到达终点；

步骤7将m只蚂蚁重置为起始点并清空禁忌表以进行下一次迭代；

步骤8判断NC是否达到设定值。如果NC达到设定值，则程序结束，否则转到步骤4。

4 仿真与实验

本文在MATLAB上进行仿真实验。硬件环境：Windows 10，CPU为Core(TM)i5-3230M、2.6 GHz，内存4 GB。通过建立二维栅格地图，地图模型为20×20个栅格。建立二维直角坐标系，横纵坐标的单位取值为1，最大值为20，机器人的起点为(0.5,19.5)，目标点为(19.5,0.5)。机器人按照改进的蚁群算法进行路径规划。

本文对传统的蚁群算法和改进的蚁群算法分别进行了仿真实验，如图2～图7所示。

图2是机器人运动轨迹，图2(a)和图2(b)分别为传统蚁群算法和改进蚁群算法的机器人运动轨迹。由图2可以看出，该地图模型相对简单，改进蚁群算法运动轨迹较传统蚁群算法短，而且传统的蚁群算法得到的运动轨迹较曲折。图3是机器人各代运动轨迹。

表1 算法比较

图4是算法收敛曲线，图4(a)和图4(b)分别是在传统蚁群算法和改进蚁群算法下的收敛曲线变化图。由图4可以看出，改进蚁群算法收敛速度更快，并且最短路径比传统蚁群算法短。从收敛曲线的变化趋势看，改进后的蚁群算法曲线变化幅度较小，说明改进后的蚁群算法收敛性较好。表1是传统蚁群算法和改进蚁群算法的比较。由表1可以看出，改进蚁群算法在最短路径上比传统蚁群算法短，由于地图环境相对简单，最短路径相差不大，但改进蚁群算法在迭代次数上明显少于传统蚁群算法，表明了改进算法的优越性。

上述仿真实验是在障碍物分布较简单的情况下得到的，而为了验证改进的算法对环境的强适应性，需要在复杂的障碍物环境中进行仿真实验。

图5是机器人运动轨迹，图5(a)和图5(b)分别是在传统蚁群算法和改进的蚁群算法下机器人的运动轨迹。由图5可以看出，在传统的蚁群算法中，机器人的运动轨迹明显比改进蚁群算法的运动轨迹冗长。在复杂环境条件下，改进蚁群算法具有良好的适应性。图6是机器人的各代运动轨迹。

图7是算法收敛曲线，图7(a)和图7(b)分别表示传统蚁群算法和改进蚁群算法的收敛曲线变化趋势。由图7可以看出，改进蚁群算法在最短路径长度上比传统蚁群算法短，而且改进蚁群算法在迭代次数上也具有很大的优势，表明改进蚁群算法具有良好的实时性，能够适应复杂的地图环境。表2是传统蚁群算法和改进蚁群算法的比较，可以看出在复杂的环境下，改进算法比传统蚁群算法有较大的优势，而且改进蚁群算法在最短路径上明显比传统蚁群算法短，表明了改进算法的强适应性。

由上述仿真显示，在相对简单的地图环境下，改进蚁群算法在最短路径上比传统蚁群算法短。由于地图环境相对简单，最短路径相差不大。但是改进蚁群算法在迭代次数上明显少于传统蚁群算法，验证了改进蚁群算法的可行性。在相对复杂的地图环境下，改进蚁群算法明显优于传统蚁群算法，改进蚁群算法在最短路径上明显短于传统蚁群算法，并且改进蚁群算法在收敛时间上明显快于传统蚁群算法。这些结果表明改进算法是有效的，并且能够适应不同复杂程度的环境。

5 结束语

传统蚁群算法的缺点是算法收敛缓慢且容易陷入局部最优。本文提出的改进蚁群算法相比较于传统蚁群算法，更能适应复杂的环境，在最短路径上明显小于传统蚁群算法，而且收敛速度快、搜索时间短、实时性较好，显示了改进后蚁群算法的有效性。