使用改进蚁群算法的AGV路径规划研究

葛志远，肖本贤

（合肥工业大学电气与自动化工程学院，安徽 合肥 230009）

1 引言

近年来，伴随着仓储物流自动化快速发展以及劳动力成本的提高，货物的运输方式正在向系统化，智能化的方向发展。自动导引车（Automated Guided Vehicle，AGV）具有提高生产率和节约劳动成本等优点，因此AGV路径规划成为一项重要内容。

目前，针对AGV路径规划问题产生一些群智能优化算法，如神经网络算法[1]、遗传算法[2]、粒子群算法[3]等。蚁群算法[4]（ACO）具有并行性、正反馈性及良好的扩充性等优点，在解决路径规划[5]、TSP[6]等问题都有成功的应用。针对蚁群算法耗时长，容易陷入局部最优的缺点，文献[7]提出一种基于蚁群算法的带时间窗的启发式算法，提高了收敛速度。文献[8]利用遗传算法对蚁群算法参数的组合优化，但由于遗传算法计算量大，效果不明显。

在传统蚁群算法基础上，利用改进的蚁群算法对AGV路径规划进行了研究。

2 空间环境模型的建立

空间环境模型的建立是AGV路径规划的基础。栅格法[9]（grid method）具有简单高效、易于实现、表达不规则障碍物的能力等优点，所以采用栅格法建立AGV空间环境模型。

2.1 环境建模

利用栅格法将AGV所在的空间环境划分为一个M行N列的二维平面空间，如图1所示。栅格必须完全容纳AGV，并预留安全间距，定义障碍物所占用的栅格为障碍栅格（黑色），无障碍物的栅格为可行栅格（白色），单位长度为1cm且障碍物所占栅格不满一个栅格按一个考虑，通过直角坐标法对每个栅格进行标识，记为g（x，y）。将障碍栅格组成的集合用Qf表示，可行栅格组成的集合用Qt表示，则AGV路径规划就是在栅格图中寻找到一条无碰最优路径。

图1 AGV空间环境模型Fig.1 AGV Spatial Environment Model

2.2 AGV运动距离函数

在空间环境模型中，AGV所在的栅格中一般都有8个运动方向，以水平正方向为 0°基准，顺时针 45°，90°，135°；逆时针 45°，90°，135°，包含后退方向 180°，如图 2 所示。

图2 可移动方向示意图Fig.2 Movable Direction Schematic

通过栅格坐标 P（x，y）表示 AGV 所处位置，其中 x∈（1，2，…，N），y∈（1，2，…，M），P（x，y）∈Qt。AGV 在 t时刻从起始栅格位置Pt（xt，yt）到t+1时刻下一个栅格位置Pt+1（xt+1，yt+1）的运动距离为d（t），则总路径长度L为从源地址到目的地址行驶的所有节点路径距离之和，d（t）如下式所示。

3 传统蚁群算法的原理

蚁群算法中蚂蚁会根据信息素的强弱选择路径，并在自己走过的路径上遗留一定的信息素。设τij（t）表示t时刻在路径（i，j）连线上残留的信息素浓度，设初始时刻τij（t）=C（C为常数）。（t）表示为在t时刻蚂蚁k从地址i转移地址j的概率。

式中：ηij通常作为启发因子，取 ηij=1/dij；α—路径（i，j）上残留信息的相对重要性；β—启发因子的重要程度；allowedk—蚂蚁k还未遍历的地点集合。一次循环后，计算每一只蚂蚁所走过的路径长度Lk，并比较得出路径中最短路径Lmin。

随着时间的推移，各条路径上留下的信息素会逐渐减弱，当所有蚂蚁完成一次循环以后，根据式（5）调整各条路径上的信息量。

式中：ρ—信息素衰减的程度，ρ∈（0，1）；Δτij—信息素增量。

4 改进的蚁群算法

传统的蚁群算法存在耗时长，搜索效率低等缺点，给出以下几点改进。

4.1 蚁群算法概率公式的改进

传统蚁群算法中ηij与路径（i，j）的距离成反比，这样容易使蚂蚁陷入局部最优，故修改启发因子与当前地址到目标地址的欧式距离成反比，距离目标地址越近则概率越大，具体如式（5）所示。

式中：aroundk—当前地址i周围8个地址的集合，启发因子ηiT=1/diT—地址j到目标地址T的欧式距离，由式（5）可知，当蚂蚁寻找路径时会朝着离目标地址近的方向移动，提高了搜索效率，有利于蚂蚁寻找最优路径。

4.2 优胜劣汰机制

为加快蚁群算法的收敛速度，节省搜索时间，使搜索范围限定在优势路径中。每次循环后，差别更新最优路径与最差路径信息素，使蚂蚁的关注点较集中在优势路径，尽可能使蚂蚁在优势路径附近寻找最优路径，如式（6）～式（8）所示。

式中：c（r，s）—路径调整参数；Lbest_jT—最优路径中节点地址j到目标地址T的欧式距离；Lworst_jT—最差路径中地址j到目标地址T的欧式距离。

对于最优路径，前期距离较远，信息素增益低，有利于前期路径选择多样性，而后期距离目标越近，则信息素增益越大，越有利于提高搜索效率；同理，对于最差路径，前期路径信息素衰弱较少，防止路径信息素过少被忽略，后期路径距离越近，信息素衰减越多。因此，在最优与最差路径上的每一段路径上的信息素改变都不一样，扩大了最优与最差路径之间的差异。

4.3 全局信息量调整

蚁群每次循环后，只根据最优路径和最差路径进行信息素的更新，会在一定程度有利于加快收敛速度，但在算法初期，蚂蚁过早的集中在几条次优路径上，使可能的最优路径容易被忽略，不利于寻找到最优路径。因此，针对除最优路径与最差路径以外的路径，采取以下改进规则。

式中：n—在Lk上行走的蚂蚁总数；Lk—第k只蚂蚁在本次循环中的路径长度；ω—信息素扩大系数。由式（9）可知，若Lk与Lbest的差异越大，则该路径的信息素增益越低，只有与Lbest较为接近的保留下来。若算法前期出现次优路径，则与次优路径接近的路径也会较多，全局调整信息素调整的范围较广，保证了搜索空间范围，因此联合式（6）与式（9）使信息素集中表现在最优路径与次优路径中，提高了蚂蚁资源利用效率，有利于蚁群搜索出最优路径。

4.4 信息素浓度限制

经过上述蚁群算法的改进，提高了蚁群算法的收敛速度，但是为了防止部分路径上的信息素过多，降低了路径选择的多样性，导致蚁群算法出现早熟现象，所以引入最大最小蚂蚁系统对每条边上的信息素浓度进行限制，具体方法，如式（10）所示。

通过将信息素值限定在［τmin，τmax］之间，可以使得路径之间的信息素浓度之间差距限定在合理的范围内，从而解决了在不同路径上，由于信息素浓度差异过大从而导致蚁群算法最终出现次优的情况。

4.5 死锁策略

当AGV寻找最优路径时，可能会出现死锁现象[10]，使AGV在当前栅格中无法执行下一步动作，如图3所示。

图3 移动死锁问题示意图Fig.3 Mobile Deadlock Problem Diagram

针对上述出现的死锁现象，提出当AGV运动时无法找到除起始地址栅格以外的其他栅格地址时，可执行回归动作，返回到前一地址，并将该地址从可行栅格Qt中剔除，加入到障碍栅格Qf，使得后续蚂蚁避免在死锁地址消耗时间，有效解决死锁问题。

5 改进蚁群算法的路径规划步骤

综上所述，改进后具体步骤如下：

（1）初始化最大迭代次数Nmaxc，当前迭代次数Nc为0；设置在起始地址与终点地址。

（2）对蚂蚁k根据改进的蚁群算法概率公式移动至下一个地址。

（3）判断蚂蚁k是否陷入死锁状态，如果是，则进入回归策略，否则继续执行。

（4）当蚂蚁k完成路径搜索后，记录蚂蚁k到达目标地址时的路径长度Lk。

（5）循环（2）、（3）、（4），直到 m 只个蚂蚁都移动至目标地址。

图4 改进蚁群算法流程图Fig.4 Improved Ant Colony Algorithm Flow Chart

（6）通过 Lk（k=1，2，…，m）计算出最优路径 Lbest与最差路径Lworst，并根据改进的信息素更新方法更新路径轨迹信息素，并置Nc←Nc+1。

（7）对计算过的各个边的信息素浓度，利用最大最小蚂蚁系统公式进行判断与限制。

（8）若每个蚂蚁搜寻的最优路径相同，则直接跳出循环。

（9）若迭代次数Nc＜Nmaxc时，则跳转到（2）。当达到最大迭代次数Nmaxc时，则跳出循环，输出最短路径，程序结束。

6 仿真实验

利用MATLAB对基本蚁群算法和改进蚁群算法分别进行仿真，并比较它们的仿真结果。

各个参数设置分别为：α=1，β=4，m＝50，ρ=0.2，ω=10，Q=1000，Nmaxc=200，传统的蚁群算法和改进的蚁群算法最优路径长度与仿真结果分别，如图5、图6所示。并通过运行两种算法，对死锁问题以及最优解比例进行统计，结果如表1所示。

由图5～图6可知，改进的蚁群算法一开始的搜索效率优于传统的蚁群算法。在迭代次数上优势不大，但改进的蚁群算法搜寻的最优路径明显优于传统的蚁群算法，且改进的蚁群算法后期的收敛速度比传统的蚁群算法更快。

由表1可知，传统的蚁群算法容易出现死锁问题，而通过改进蚁群算法的死锁策略，可以有效的避免蚂蚁运动时陷入死锁状态，使改进的蚁群算法中蚂蚁最终全部达到最优解。

分析实验结果得出，传统的蚁群算法搜索效率较低，耗时长，且容易出现次优路径，通过改进的蚁群算法提升了搜索效率，缩短了搜索时间，提高了寻优的准确性，且有效的避免了死锁现象。

图5 传统蚁群算法最优路径图和仿真结果Fig.5 The Optimal Path Map and Simulation Results of Traditional Ant Colony Algorithm

图6 改进蚁群算法最优路径图和仿真结果Fig.6 Optimal Path Map and Simulation Results of Improved Ant Colony Algorithm

表1 传统蚁群算法与改进蚁群算法性能比较Tab.1 Comparison of System Ant Colony Algorithm and Improved Ant Colony Algorithm

7 总结

提出了利用改进的蚁群算法对AGV进行路径规划的方法。传统蚁群算法具有耗时长，算法的搜索效率较低，容易出现次优现象的缺点，提出将根据与目标地址的欧式距离作为启发因子，使蚂蚁具有目的性寻优，提高了搜索效率，并通过优胜劣汰机制调整最优路径与最差路径信息素浓度，给出了全局信息素调整方案及限制，有利于蚂蚁集中关注于最优路径和次优路径中，提升了路径的收敛速度，对多样性也有一定的保证，提高了搜索的准确性，同时也对死锁现象问题的处理，有效避免了AGV陷入死锁状态，仿真结果证明了方法的可行性和有效性。