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

李任江，滕智鹏

（长春工业大学 机电工程学院，吉林 长春 130012）

0 引言

自动引导小车AGV作为调节和联系离散型物流系统，被广泛运用于自动化立体仓库中，常用的路径规划方法有栅格法［1］、A＊算法［2］、Dijkstra算法［3］、遗传算法［4］、蚁 群 算 法［5］、粒 子 群 算 法［6］等。 在 这 些 方 法中，遗传算法有着较强的搜索能力，通过引入自适应的参数，能够找到全局最优解［7］，但是局部寻优能力差；粒子群算法参数少，能够快速收敛，但易于陷入局部最优解；蚁群算法具有很强的鲁棒性和适应性，但是还存在一些问题，如不具备自主避障能力、信息素的更新机制不完善等，有待进一步研究。

本文基于改进蚁群算法进行AGV路径规划，首先引入方向系数，并采用局部、全局结合的信息素更新方式，达到快速寻优的目的；其次引入安全距离判断策略，提高AGV运行路径的安全性。仿真结果表明，改进算法具有较好的避障能力，收敛速度快，能够运用于复杂运输环境。

1 构造AGV运行环境

为规划AGV运行路径，首先要建立能够使AGV识别的运行环境，通常情况下，AGV的运行环境为二维有界空间，为了便于研究，进行如下假设：①将行驶的AGV看作质点；②AGV行驶过程中主方向为x轴，且行驶速度v不变；③黑色方格为障碍物栅格；④每一条路径节点之间的连续不能穿过障碍物。

用M表示AGV的运动空间，建立笛卡尔坐标系xoy，以横向为坐标轴x，纵向为坐标轴y，原点位于M区域左下角，起点S位于原点，终点E位于M 区域右上角。x、y轴上的最大值分别为Xmax、Ymax，基于行驶速度v完成x、y对栅格的划分，每行的栅格数为Nx＝个栅格的序列号满足如下关系式：

其中：i为序列号；n为每一行栅格数；int为取整运算；mod为求余运算。

基于以上描述及设定，本文建立20×20的AGV运行环境，如图1所示。

2 传统蚁群算法

蚁群算法是一种模拟蚂蚁觅食的仿生算法，蚂蚁根据转移概率选择一条路径留下信息素，积累的信息素浓度越大，路径被选择的概率越大，蚂蚁会根据留下的信息素找到最优路径。根据传统蚁群算法设定，某时刻t蚂蚁k从节点i移动到节点j的概率为：

其中：pij（k）（t）为转移概率；τij（t）为t时刻节点i与节点j之间的信息素强度；α为信息素重要度因子；ηij（t）为节点i到节点j的期望启发函数，ηij（t）＝，dij为节点i到节点j的欧几里得距离；β为期望程度因子。

蚂蚁完成一次循环后更新每条路径上的信息素：

其中：τij（t＋1）为更新后节点i和j之间的信息素强度；ρ为信息素挥发系数；Δτij（t）为路径节点i到节点j上的信息素增加量，设初始时刻Δτij（0）＝0；m为蚁群的数量；Q为信息素加强系数；Lk为蚂蚁k所走过路径的总长度。

3 改进的蚁群算法

3.1 启发函数改进

传统蚁群算法中，由于初始时刻各条路径上的信息素含量较少，为了使路径规划初期AGV的路径选择具有一定的指向性，本文引入方向系数（即方向启发因子）μ来判断AGV运行过程中当前节点与下一节点的角度，避免角度过大而造成路径搜索时间的浪费。某时刻AGV运行引导原理如图2所示。

图1 AGV运行环境

图2 AGV运行引导原理

AGV连续经过节点i、j、a、b，当前 AGV运行路径为节点i到节点j，节点a和节点b为下一步的出发点和到达点，θ1、θ2分别为AGV处于节点a和节点j时与运动边界形成的角度。Δθ越小，AGV运行方向越靠近终点b，从而缩短运行距离。设ηij＊为改进后的期望启发函数，Δθ和ηij＊的计算公式如下：

其中：dij为i与j之间的距离；μ为方向启发因子，且μ＞0。

由式（7）可知，若角度过大则会使η＊ij的值减少，可以减少角度较大的栅格被选择的概率。结合式（7）和式（2）可得到改进后的蚁群算法转移概率计算公式：

3.2 信息素更新机制改进

传统蚁群算法对信息素的更新方式较为单一，当算法进入下一循环时并没有充分利用上一循环中最短路径上的信息素。本文采用的信息素更新方式如下：当蚂蚁进行一次循环时，对所到达的每个节点上的信息素根据式（4）进行局部更新；经过n个时刻蚂蚁完成一次循环后，对最优、最差路径上的信息素根据式（9）进行全局更新：

其中：Lgb为当前最优路径长度；Tu为当前最优路径上所有节点的集合；Lgw为当前最差路径长度；Tv为当前最差路径上所有节点的集合。

采用上述更新方式，可以使每个循环中的信息素充分利用，提高较好路径被选择的概率，从而提高算法的性能，避免陷入局部最优解。

3.3 路径安全距离判断策略

算法对AGV进行路径规划的过程中，会出现与障碍物边缘碰撞的路径，这样会影响AGV运行的安全性。本文在对AGV路径规划过程中引入安全距离，以提高AGV运行路径的安全性。图3为引入安全距离前、后的AGV运行路径，路径uv、ij分别为引入安全距离前、后的规划路径。

图3 引入路径安全距离

根据本文的设定，AGV运动方向为x轴，假设障碍物右上尖角点e的坐标为（x，y），取ce为250mm，点c的坐标为（x，y＋250）。某时刻AGV运行到点c，点c与障碍物尖角e以及路径终点j产生一个角度θ，由此可以计算出线段lde的长度，并将线段lde的长度称为安全距离：

其中：lce为线段ce的长度；θ为ce与cd的夹角，且θ∈（0，90°］。

路径规划过程中，AGV经过障碍物时路径节点的选择与点c一致，可以满足安全距离且安全距离∈（0，250］。若AGV经过障碍时主运动方向为y轴，则判断障碍物右下尖角与AGV的安全距离。

4 仿真实验及结果分析

在图1环境下，对传统蚁群算法和改进蚁群算法进行仿真实验，并对两种算法规划出的结果进行对比分析。仿真中各项参数的设定为：蚂蚁数量m＝50；信息素重要度因子α＝1；期望程度因子β＝8；信息素挥发系数ρ＝0.1；信息素加强系数Q＝15；最大迭代次数N＝100。图4为传统蚁群算法和改进后的蚁群算法的收敛曲线。从图4中可以看出，改进蚁群算法比传统蚁群算法更快达到收敛。

图5为传统蚁群算法、改进蚁群算法和改进蚁群算法引入安全距离（取安全距离为250mm）后进行路径规划的结果。通过比较图5（a）和图5（b）可以看出，改进蚁群算法得到的最优路径更短。再比较图5（b）和图5（c）可以看出，引入安全距离后AGV在靠近障碍物时会控制与障碍物的距离为设定的安全距离。传统蚁群算法在路径规划初始时刻路径的选择具有随机性，而改进后的蚁群算法在引入方向启发因子之后在路径选择上避免了平移的出现，同时也能够根据安全距离自主避碰。

对以上仿真得到的最优路径长度、平均收敛代数和平均收敛时间以及拐点数进行比较分析，见表1。由表1可以看出：引入方向启发因子和安全距离后，AGV的运动更具有指向性，产生的路径上的拐点数比传统蚁群算法更少，从而产生的路径长度更短且搜索耗时也明显减少；AGV会在障碍物附近判断当前安全距离同时保证路径最短，使直行路径变成拐角，所以路径长度也会有所增加，更符合实际情形。

图5 算法路径仿真结果

表1 算法性能对比

5 结语

本文提出一种适用于复杂运输环境下AGV路径规划的改进蚁群算法。采用栅格法建立运行地图，通过引入方向系数、安全距离判断策略和改进信息素更新机制，提高算法运行效率和收敛速度，避免陷入死锁，保证了AGV运输路径的安全性。实验结果表明，本文提出的算法比传统蚁群算法更快达到收敛，且规划的最优路径距离更短，引入安全距离之后AGV的运行路径与引入前相比更安全。