基于混合蚁群算法的AGV路径规划*

孟冠军，陈信华，陶细佩，张 伟

(合肥工业大学机械工程学院，合肥 230009)

0 引言

路径规划是指在具有障碍物的环境中，移动物依照某一特定的性能指标(如空间距离、时间等)搜索一条从起始位置到目标位置的最优或次优路径[1]。自动导引运输车(Automated Guided Vehicle，AGV)路径规划主要包含两个核心问题：地图信息表达和搜索策略[2]。针对AGV路径规划问题，国内外学者进行了长期的深入研究，并相继提出了多种较为有效的方法，常用的地图信息表达方法有栅格法[3]、图论法[4]、可视图法[5]。搜索策略方面主要包括A*算法[6-7]、dijkstra算法[8]、蚁群算法(Ant Colony Optimization, ACO)[9-10]、粒子群算法[11]等较为常用。文献[10]采用一种改进蚁群算法，通过自适应的信息素更新机制，算法的全局搜索能力被提高，但算法的收敛速度却依然较慢。文献[11]提出了一种将粒子群算法与模拟退火算法、遗传算法相结合的方法，在一定程度上提高了算法的寻优能力，但算法操作复杂度也相应增加了。本文首先利用可视图法进行环境建模，而后采用改进蚁群算法进行路径搜索。针对蚁群算法搜索效率低的缺点，利用A*算法寻优速度快及蚁群算法易于与其它算法相结合的特点，采用A*算法与蚁群算法的混合蚁群算法。即先采用A*算法搜索出一条较优路径，以这条次优路径作为蚁群算法迭代搜索的初始路径，避免了蚁群算法在初期搜索的盲目性，大幅度提升蚁群算法的寻优能力。为了避免使用蚁群算法时陷入局部最优而导致算法停滞，本文对节点转移概率公式的启发函数加以改进，引入全局距离参数。同时为了提高算法收敛速度，本文提出一种面向对象的信息素更新规则，只对非最优路径上的信息素量进行削减。最后，通过实例分析，验证了本文提出的混合蚁群算法在AGV路径规划问题上的有效性。

1 环境建模

本文利用可视图法建立AGV车间路径规划的二维空间模型，环境模型如图1所示。

图1 环境模型图

图中S、T分别表示AGV的起始点和目标点，黑色区域表示障碍区域，不同障碍区域顶点之间的虚线即可视线如AB。可视图法将AGV视为一点，将障碍物多边形的各顶点进行链接，并保证这些链接线与障碍物均不相交，这样就形成了一张网络图，称为可视图[12]。搜索最优路径的问题便转化为在可视图的基础上利用搜索算法，寻找一条从起始点穿过可视图中部分可视线到达目标点的最短路径问题。由于搜索到的路径是穿过可视线的，即保证了这些路径均是无碰撞路径。

2 混合蚁群算法

2.1 算法原理

混合蚁群算法共包括两个阶段，是A*算法和蚁群算法的结合，运用两种算法的特点和优势来求解AGV最优运动路径。

第一阶段为A*算法，A*算法是一种启发式搜索算法，其适用于静态路网环境。它的根本思想是通过运用启发式搜索的方式来找寻恰当的启发函数，其计算和评估各个扩展节点的代价来选择代价值最优的结点并加以扩展，直到目标节点被找到为止。在路径搜索问题中，当前节点到目标点的代价值即路径长度的评估值就通过启发函数来计算获得。

第二阶段为改进蚁群算法，本文针对传统蚁群算法存在的缺陷与不足，做出若干改进。

2.1.1 节点转移规则

本文针对蚁群算法易陷入局部最优导致算法停滞现象的不足，采用新的节点转移规则，以增强算法的全局搜索能力，便于算法跳出局部最优。

在传统蚁群算法中，节点转移概率[13]由两节点连接路径上的信息素量τij和启发函数ηij共同决定，且一般令ηij=1/dij，这样启发函数仅由单一的距离参数dij来决定，而dij只能反映节点i周围的局部信息。在某些情况下，节点i与节点j的距离短，并不意味着节点j到目标点T的距离短。如图2所示，起始点S到目标点T有两条路径，路径L1上的第一个节点距S较远，路径L2上的第一个节点距S较近，如果按照传统蚁群算法的节点转移规则，最后搜索到的很可能是路径L2，但实际上L2的长度是大于L1的长度的。

图2 节点转移矢量图

(1)

其中，i、j为链接线上所有点的集合；α为信息素重要程度因子；β为启发函数重要程度因子；I为蚂蚁下一步选择节点的集合。

2.1.2 信息素更新规则

为了克服传统蚁群算法收敛速度慢的不足，本文引入一个常数μ，0<μ<1,其作用是减小目前非最优路径上的信息素增量。于是最优路径上的信息素增长优势得到加强，在保证算法全局搜索能力的情况下，加快了算法的收敛速度。新的信息素更新规则如式(2)所示：

(2)

(3)

其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；dij表示节点i与节点j之间的距离。

2.2 算法流程

综合上述描述得到混合蚁群算法，算法流程图如图3所示。

图3 算法流程图

首先采用可视图法建立AGV运动环境模型，并运用A*算法在环境模型中搜索出一条较优路径；然后将其作为改进蚁群算法的初始路径，同时根据新节点转移公式寻找蚁群运动节点，直至到达目标点；最后在迭代次数到达限定后输出算法求得的最优路径。

3 案例应用及分析

3.1 问题描述

将某车间AGV的工作环境作平面化处理，得到一个100 m×100 m的二维空间，该二维空间分布了一些障碍物，将这些障碍物进行区域划分，得到4个障碍区域，现需为AGV规划出一条从起始点S到目标点T避开障碍物且尽可能短的路径。S、T以及障碍区域的位置可通过测量得知。

3.2 仿真环境及环境模型

为了验证混合蚁群算法在AGV运动规划方面的优越性及有效性，采用MATLAB软件进行仿真。仿真环境：利用MATLAB R13a,在Intel(R) Core(TM) i5-3210M CPU @ 2.50GHZ、4.00GB内存、Window 7操作系统下进行仿真验算。建立适当的平面直角坐标系，测得S、T以及障碍区域顶点的坐标，利用可视图法，在MATLAB R13a上进行环境建模，如图4所示。

图4 环境模型图

图4中虚线L1，L2，……,L16为可视图链接线，链接线上的“*”为该链接线的中点，黑色区域即障碍区域。

3.3 A*算法规划较优路径

采用可视图法建立环境后，在MATLAB上运用A*算法搜索较优路径，为降低算法运算的复杂度，以可视图各链接线的中点作为A*算法路网中的扩展节点，图5为利用A*算法得到的搜索结果。

图5 环境模型图

图中粗虚线即搜索到的较优路径，该路径从起始点S出发，依次经过L1、L2、L3、L4、L9、L10、L14、L15的中点，最后到达目标点T，该路径总长度为107.4 m。

3.4 改进蚁群算法搜索最优路径

以A*算法得到的上述路径作为改进蚁群算法的初始路径，并进行最优路径搜索。同时针对原AGV路径规划问题，用同样的方法进行环境建模，再利用传统蚁群算法进行路径寻优。传统蚁群算法和混合蚁群算法求得的最优路径比较如图6所示。

图6 路径搜索结果对比图

为了便于分析将两种算法的迭代曲线求出并放在一起进行比较，如图7所示。

图7 算法迭代结果

图6和图7中细实线代表混合蚁群算法的结果，粗实线则代表传统蚁群算法的结果。

3.5 结果分析

将以上两种方法得到的路径规划结果的相关数据进行统计，具体见表1所列。

表1 算法结果对比

上述统计结果表明，本文提出的混合蚁群算法搜索到的最优路径比传统蚁群算法在路径长度上得到了明显改善，符合本文AGV路径规划问题的目标要求。并且经过改进后的蚁群算法在大约第98次循环迭代之后，就开始达到最优路径，而传统蚁群算法在大约第252次循环迭代之后，才开始趋于最优路径。即本文的混合蚁群算法不仅搜索的路径更优，在算法收敛速度方面也具有明显优势。为了更好的比较传统蚁群算法和混合蚁群算法的性能，将两种算法在同样的实验条件下运行5次，得到的结果见表2所列。

表2 算法结果对比

由表2数据可知，传统蚁群算法求取的最优路径长度稳定在95 m左右，相较之下混合蚁群算法求取的最优路径长度则在83 m左右。且混合蚁群算法所需的迭代次数要远远小于传统蚁群算法。此外由于本文提出的AGV路径规划问题没有对环境作限制，没有明确规定障碍物的位置，因而具有现实的普适意义，从而证明了本文混合蚁群算法在解决AGV路径规划问题方面的有效性。

4 结论

文章提出了一种基于混合蚁群算法的AGV路径规划研究方法。在传统蚁群算法的基础上，对算法中的节点转移概率公式以及信息素更新方式加以改进，并利用A*算法寻优速度快的优点将其与蚁群算法相结合，弥补了传统蚁群算法收敛速度慢且易陷入局部最优导致算法停滞的不足。基于此方法在MATLAB软件中对实际案例进行实验仿真，得出如下结论：混合蚁群算法可使AGV在运行过程中有效避开障碍物，并找寻出一条无碰优化路径；相较于传统蚁群算法，混合蚁群算法规划的路径长度和质量明显优于前者；通过算法迭代图和多次对比试验，表明混合蚁群算法具有较好的收敛性和较高的搜索效率等优点。