王 玉, 沈丹峰, 李耀杰, 李靖宇

(西安工程大学 机电工程学院，陕西 西安 710048)

0 引 言

自动导引小车(automated guided vehicle，AGV)研究的主要问题之一，是基于已知信息规划环境中具有许多障碍的最优路径。即从起点到目的地点而不发生碰撞，并且以最快的速度和最短的路径到达。该研究中广泛使用的方法有势场法[1]、栅格法[2]、动态算法[3-5]、蚁群算法[6-8]、神经网络算法[9-10]等。势场法有助于下层的实时控制，结构简单但很容易陷入局部的优的死胡同，对全局的搜索不利；动态算法计算量大、收敛速度慢，效率低。目前，神经网络成为了比较流行的优化方法。该方法易于使用硬件实现，但可靠性和优化性能较差，并且难以解决局部最优解问题。尽管传统的蚁群算法收敛速度慢，也存在死锁的问题，但它易于并行实现、搜索效率高、鲁棒性强，可以广泛地用以各种复杂环境下的路径规划中。

目前，许多学者提出了不同的方式改善蚁群算法的弊端：NAZARAHARI等提出了遗传算法规划连续环境中多个机器人的路径，并改进了原有遗传算法的启发式功能，但是当触碰到障碍物时，仍然会出现死锁现象，效率低下[11]； ZHU等将人工势场法与蚁群算法相结合，引入诱发启发式因素，并动态调整了算法的状态转移规则，因而具有更高的全局搜索能力和更快的收敛进度[12]；OMRAN等改进连续蚁群优化问题，优化了开发和寻找蚁群的机制，收敛速度有所提高[13]；马军等提出了融合蚁群-A*算法的路径规划方法，虽然改进了启发式函数和信息素更新方式，但蚁群算法早期搜索效率低、收敛缓慢的问题仍然不能有效地解决[14]。

针对上述问题，本文提出一种融合跳点搜索(JPS)的新方式，并且从一开始即建立了2组蚁群，在起点和目的地的2个方向上同时执行路径搜索，从而减少了算法运行期间需要计算的节点数量，解决了蚂蚁在遇到“凹”型障碍物时撤退或死亡，或产生一些无效信息素误导搜索过程，从而加快了路径规划的收敛速度，降低AGV运行时间和能量损耗，显著提高了路径寻优的效率。

1 环境建模

图 1 AGV运行方向Fig.1 Direction of AGV movement

直角坐标与栅格序号的转换关系为

(1)

式中：Sx为栅格的序号；g为每行或每列的栅格个数；mod(Sx,g)为Sx/g的取余函数；ceil(Sx/g)为求取大于或者等于Sx/g的最小整数函数。可以得到AGV在当前栅格地图中的实际坐标。将地图信息存在二维矩阵M=(mij)中，其中：

(2)

为了验证改进的算法在不同规模复杂环境下路径规划的有效性与通用性，以及是否具有良好的全局搜索能力，采用栅格法构造了2个不同的仿真地图，如图2所示。

(a) 环境1栅格地图

(b) 环境2栅格地图图 2 栅格地图Fig.2 Grid map

图2中环境1和环境2分别为20×20和30×30的栅格地图，将S设置为AGV的起始点，E为目标点，在地图上，有一些障碍物呈现“凹”型状，障碍物的其他部分被设置成以近似随机分布的方式排列，没有规则和顺序。

2 融合JPS的蚁群算法

2.1 传统蚁群算法原理

蚂蚁寻找食物的过程中会释放一种称之为信息素的激素在走过的路径上，在一定范围内，后续的其他蚂蚁都能够感知到这种信息素。当经过的路径上有源源不断的蚂蚁时，信息素将继续在此路径上积聚，随后的蚂蚁选择同一路径的可能性将继续增加。该路径规划被视为是一组蚂蚁经过多次迭代寻找食物的过程，并最终将找到一条无碰撞且最优的路径[15-17]。

蚁群算法状态转移概率如下：

(3)

(4)

式中：dij为蚂蚁从栅格i到下一个栅格j的欧几里得距离；Ix、Iy分别为当前节点的横坐标与纵坐标。

整个循环过程中蚂蚁会不断地释放信息素，同时先前蚂蚁释放的信息素也会不断消失。循环完成后，需要对信息素实时更新，更新方式为

(5)

当路径上所有的信息素被更新后，表示此次路径已经搜索结束,蚁群已经准备好开始下一轮的路径搜索；当迭代达到设定的次数后，蚁群将从所寻找到的路径中选出一条最佳路径。

2.2 算法改进

使用传统蚁群算法尽管可以求解最优路径，但需要把蚂蚁全部放置在起始点，然后搜索到目标点，起始路径是大致相同的，缺乏全局的搜索能力，且均匀分配的信息素浓度会导致蚁群初期盲目搜索，一定程度上降低了算法的搜索效率。因此，本文在蚁群算法的基础上，融合了跳点搜索(JPS)算法，改进了蚁群算法的启发函数和信息素更新公式，并放置2组蚁群从起始点和目标点，同时执行双向搜索规划最优路径，使其进入“凹”型障碍物中自锁时可以进行局部规划，从而提高算法的搜索效率和速度。

2.2.1 启发函数的改进 在JPS算法的路径搜索中，丢弃了大量不需要计算的节点，并留下代表性节点，这些剩余的节点被称为跳点[18-20]。在过滤跳点时，首先展开所有的节点进行预处理，在当下节点周围找到8个相邻跳点并放置到open表中。再从周围的邻居节点集合中挑选出那些不需要计算的节点，将这些节点全部裁剪掉放置到close表中。然后展开这些点，当搜索到目标点时，连接所有跳点就是一条完整的全局路径。跳点搜索(JPS)寻优路径如图3所示。

图 3 JPS算法路径寻优Fig.3 Path optimization of JPS algorithm

如此改进，对open和close列表减少了大量的运算，很大程度上提高了寻优效率，并节省了大量的AGV路径规划时间。

JPS的评价函数表达式为

F(n)=G(n)+H(n)

(6)

式中：F(n)为要展开点的代价函数；G(n)为初始点到n节点的实际成本代价；H(n)为节点n至目标点的预算成本代价。

传统蚁群算法的启发函数在选择下一个栅格时,会导致蚂蚁更加倾向于选择方向为正的栅格，且没有考虑到最终栅格的位置。因此,使用曼哈顿距离作为双向搜索的预算代价函数。改进后的启发式函数为

(7)

式中：Hij为当前节点距离起始点或目标点的几何距离；Ix和Iy为当前节点的横坐标和纵坐标；Ex和Ey为目标点的横坐标和纵坐标；Sx和Sy为起始点的横坐标和纵坐标。

2组蚂蚁在它们各自的目标点上执行双向路径搜索，当它们找到一个公共的节点时，该节点内的信息素浓度就会加倍。找到的3个或更多的公共节点连接起来即产生一条新的路径，之后2组蚂蚁继续向各自的目标点移动。数学表达式为

HSE=|Ex-Sx|+|Ey-Sy|

(8)

式中：HSE表示2个目标点之间的距离。

2.2.2 信息素更新公式的改进 随着信息素在同一路径上的积累，传统的蚁群算法选择路径时，后续的蚂蚁将拥有大量的盲路径,导致在经过一定数量的迭代后，蚂蚁发现的是非最优路径。在当前情况下，寻找到的路径在实践中意义就不大了。每一轮路径搜索过后蚁群的信息素就会被更新，设定参数ρ以指示信息素的挥发程度，改进后的信息素更新式为

τij(t+1)=(1-ρ)τij(t)+2Δτij(t),0<ρ<1

(9)

(10)

式中：Δτij(t)为路径信息素增加量；HSE为路径长度；Q为信息素浓度增强因子。

2.3 改进算法流程图

将改进的算法用于AGV路径规划中，算法流程图如图4所示。

图 4 改进算法流程图Fig.4 Flow chart of improved algorithm

将参数初始化，设置初始信息素在节点间的浓度、信息启发系数α、期望启发系数β、信息素挥发系数ρ以及迭代次数N；使用栅格法创建指定大小的地图模型，并将障碍物存储在相应的网格中；将蚁群平均分为2组，分别放入起始点和目标点，使用JPS算法生成初始路径；根据式(5)更新对应路径的初始信息素含量，直到2组蚁群相遇有共同的节点并都到达目标点；用改进的公式更新上一代蚂蚁留下的信息素，当满足设定迭代次数时，结束算法，输出路径，并绘制出算法收敛曲线。

3 仿真实验与结果分析

为了验证改进后算法的有效性与通用性，选择运行环境Windows10和8 GB RAM内存的PC机，使用CPU为2.60 MHz的处理器，在MATLAB2019a软件上进行2组不同复杂环境下的仿真实验。设置算法的初始参数：2组蚂蚁的种群数量m=20,α=2,N=200,β=5,ρ=0.5,Q=2; 2种环境地图分别模拟100次。

3.1 环境1

在20×20的环境1栅格地图中进行仿真实验。本文算法的最优路径如图5(a)；传统蚁群算法的最优路径如图5(b)；传统算法与改进后的算法最小路径长度收敛曲线对比如图5(c)。对比搜索路径可以看出：传统蚁群算法缺乏前期目标点的路径规划，具有盲目性，导致后期的路径信息素积累过高，会出现不必要的拐点；而本文算法有效避免路径直角拐点的出现，降低了AGV的能量消耗，在路径上无多余曲折的拐点且更加平滑，收敛速度更快。

(a) 改进算法最优路径 (b) 传统算法最优路径 (c) 收敛曲线对比图 5 环境1中实验结果比较Fig.5 Comparison of experimental results in environment 1

3.2 环境2

在30×30的环境2栅格地图上进行模拟实验。图6(a)和图6(b)分别显示了使用改进算法与传统算法寻找到的最优路径，图6(c)为传统算法与改进后的算法最小路径长度收敛曲线的比较。在更为复杂栅格环境中设置了更多“凹”型障碍物，对传统算法来说，由于没有事先规划过路径，导致后期蚂蚁重复前期走过的路径，信息素积累过高，出现了大量多余的拐点，在实际搜索中增加了能量的损耗，见图6(b);改进后的算法避免了路径上信息素的过度积累，以找到最优路径为目标，规划出的路径依然比传统算法的更加平滑，并且转折点的数量也少了很多，见图6(a)；尽管改进算法的收敛曲线在刚开始会有波动，但收敛速度比传统的更快，迭代次数也远远小于传统算法的迭代次数，具有良好的全局搜索能力，见图6(c)。

(a) 改进算法最优路径 (b) 传统算法最优路径 (c) 收敛曲线对比图 6 环境2中实验结果比较Fig.6 Comparison of experimental results in environment 2

改进蚁群算法和传统蚁群算法在环境1与环境2的仿真实验结果对比，如表1所示。

表 1 仿真结果对比Tab.1 Comparison of simulation results

由表1可知，在20×20和30×30的栅格地图环境中，使用相同数量的蚂蚁种群和迭代次数，改进后的算法能获取更短的路径，具有更好的收敛速度，拐点数目更少，路径更为平滑。改进蚁群算法在搜索时间比传统蚁群算法减少了30%，迭代次数降低了33.3%，最小路径长度上缩短了4～5 m。对于实际的AGV来说，有效地降低了能量与时间的消耗。改进后的算法比传统蚁群算法在不同复杂的环境地图中均有较好的搜索效果。

4 结 语

针对现有的蚁群算法收敛缓慢，无法满足AGV的最优路径规划问题，本文在传统算法中融入跳点搜索算法，使待扩展点的数量大幅度的减少，降低了搜索盲目性和计算代价。在此基础上，将评估功能加入到启发式函数中，设置2组蚁群，分别从起始点和目标点执行双向搜索，并更新信息素方式，使蚁群的全局搜索能力有了很大程度上的提高。前期算法的收敛速度得以提高，避免出现陷入“凹”型障碍物中而直接输出路径，导致局部最优解的情况。Matlab的仿真结果证明，当环境变得相对复杂时，本文算法在寻找到最优路径的同时，计算路径花费的时间要比传统算法更少，具有更快的收敛速度，更少的拐点，路径优化能力更好。证明本文算法在不同的复杂环境中AGV路径规划算法的优越性与有效性。