改进蚁群算法在AGV路径规划上的研究

岳春擂，黄 俊，邓乐乐

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)

0 引 言

近年来，随着物联网技术的发展，自动引导运输车(automated guided vehicle，AGV)被广泛应用于仓储物流[1]。AGV路径规划问题是指在障碍物环境已知的条件下，设计规划一条从特定位置出发，按照一定的要求，在确保路径安全情况下到达另一个特定位置的最优路径[2]。所述最优可以是时间最短、路径最短以及拐弯次数最少等[3]。路径规划算法包括A*算法[4]、Dijstra[5]算法、深度优先搜索(DFS)以及广度优先搜索(BFS)等。为了满足现代工业发展需求，学者们开始在将研究重心从传统算法转移到智能仿生算法，比如遗传算法[6]、粒子群算法[7]以及蚁群算法[8]。

蚁群算法(ACO)是由意大利学者Maro Dorigo最早提出的模仿蚁群觅食行为的智能仿生算法，该算法由于高鲁棒性、分布式、正反馈、易与其它算法结合等特点被广泛应用于路径规划中[9]。但该算法仍然存在搜索效率低、收敛速度慢、容易陷入局部最优等缺点。文献[10]将蚁群算法与D*算法结合，利用D*算法改进蚁群算法种的启发函数，同时使用先验路径进行预处理，减少算法处理时间，提高系统时效性。文献[11]采用多步长，增加算法灵活性并提高算法搜索效率，同时结合最大-最小蚂蚁思想，限制信息素浓度，避免算法陷入局部最优。文献[12]通过将遗传算法与蚁群算法相结合，利用遗传算法前期在搜索方面具有全面性和快速性，解决了蚁群算法前期由于缺乏信息素导致的盲目搜索问题，缩短了路径搜索时间。文献[13]引入双向蚁群，提高了算法全局搜索能力，同时结合A*算法改进了初始信息素分布，减小了算法初期搜索盲目性。文献[14]引入双种群蚁群，该算法有效避免了蚁群陷入局部最优，提升了算法的收敛速度。

1 基本蚁群算法

蚁群算法通过信息素完成最优路径的搜索，每只蚂蚁从巢穴出发搜寻通往目的地最优路径过程中，会遗留下信息素，信息素随着时间挥发，残留信息素为下一只蚂蚁提供寻路引导，通过整个蚁群的搜索，最优路径的信息素浓度远高于其它路径，最终得到最优路径[15]。

节点状态转移：蚁群初始种群规模大小为m， 第k只蚂蚁 (k=1,2…m) 从栅格i移动至栅格j的转移概率与两大因素有关。分别为栅格i和栅格j之间的信息素浓度以及两栅格间的距离启发式函数。如式(1)所示

(1)

(2)

dij表示栅格i和栅格j之间的欧式距离，距离启发式函数受栅格间距离的影响，如果栅格间距离越大，则距离启发式函数值越小，选择该栅格的可能性越小；反之，栅格间距离越小，则距离启发式函数值越大，选择该栅格的可能性越大。

信息素浓度更新：蚁群完成一轮迭代后，需要对栅格各段路径进行信息素浓度更新，便于为下一轮蚁群提供寻路引导，更新方式如下

τij(t+1)=(1-ρ)*τij(t)+Δτij(t)

(3)

(4)

(5)

其中，τij(t+1) 表示t+1时刻栅格i和栅格j路径上的信息素浓度。ρ表示信息素挥发系数， 1-ρ表示信息素残留程度，τij(t) 表示t+1时刻栅格i和栅格j路径上的信息素浓度， Δτij(t) 表示在本轮迭代过程中栅格i、j之间累积信息素总量。Q表示信息素强度系数,通常是一个常量，Lk表示第k只蚂蚁在本轮迭代中行走路径总长度。

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

根据上述分析中改进蚁群算法在路径规划应用中存在的不足，针对改进蚁群算法存在路径搜索效率低、收敛速度慢以及路径规划缺乏安全性等问题，本文在分析基本蚁群算法当前存在的问题基础上分别从算法前期、迭代中期以及算法后期3个部分对基本蚁群算法进行改进，确保在寻找全局最优路径基础上加快算法整体收敛速度。具体改进包括以下方面：①改进信息素浓度初始化，通过差异化初始信息素浓度，有效避免蚁群前期进行盲目搜索，减少算法迭代次数；②改进启发函数，综合衡量当前栅格i与待选栅格j之间的距离 (dij) 以及待选栅格j与目标栅格之间的距离 (djs)， 增强蚁群搜索方向性；③改进信息素重要程度，根据迭代次数设置不同信息素重要程度，增强算法前期搜索可能性同时加快后期搜索收敛性；对每个栅格周围的8个邻近栅格进行编号，有效减小AGV行进过程中碰壁情况发生，同时提前避免蚂蚁陷入“死角”，增强路径规划的安全性及加快算法收敛性。具体改进如下。

2.1 改进环境模型

二维平面地图建模的方法很多，包括拓扑法、可视图法以及自由空间法等[16]。本文考虑AGV工作环境多为室内且在障碍物已知的情况下，因此选用栅格法作为二维平面地图模型。栅格地图模型易于创建，维护简单且适应性强，通过简单修改即可改变模型环境。该模型中白色栅格表示可行区域，用数字0表示，黑色栅格表示静态障碍物，用数字1表示。

针对目前路径规划方法中AGV转弯安全性问题以及路径中存在“死角”现象，导致算法不能收敛到最优路径，本文提出了一种根据邻近栅格计算出“禁止栅格”的方法，如图1所示。

图1 栅格方向标号

如图1所示，当AGV行进至栅格i时，将栅格i的8个方向的邻近栅格从左上角开始按顺时针方向依次标记为数字1～8。

AGV在室内运动过程中，确保最优路径避免与静态障碍物发生碰撞，提高路径的安全性是AVG路径规划的考虑因素之一。如果栅格i的可选栅格中包含标号为奇数的栅格，例如图1中标号为7的栅格，此时判断与该路径方向(西南方向)垂直的两个邻近栅格(栅格6，8)是否为障碍物。若两个邻近栅格中其中一个为障碍物，则栅格7视为“禁止栅格”。通过该方法可减小AGV与障碍物发生碰撞的可能性。路径规划效果如图2所示。

图2 避碰效果

图2中正确行走路径远离障碍物边缘，减小了AGV与静态障碍物发生碰撞的可能性[16]，提高了AGV室内作业的安全性。

“死角”现象在算法迭代过程中时常发生，影响蚁群搜索效率以及算法最终结果。如图3所示，图中实线表示文献[16]最终路径规划效果，虚线表示基本蚁群算法最终路径规划效果。由图可知，基本蚁群算法以及改进算法均只考虑待选栅格与目标栅格之间的距离作为选路的标准，导致AGV行进至栅格i时，仍然将标号为3的栅格列入可选栅格队列，当AGV行进至栅格3时发现只能向栅格2或者栅格4行走。

图3 对比算法效果

针对算法迭代过程中出现“死角”现象问题，本文在邻近栅格的基础上再向外扩展一层栅格进行计算。如图4所示。

图4 防死角原理

栅格i的邻近栅格中，标号为3的栅格为可行栅格，且与该方向垂直的两邻近栅格(栅格2,4)均为可行栅格，因此栅格3满足路径安全性准则。但栅格3的邻近栅格中标号为2，4的栅格为障碍物，此时栅格i移动至栅格3，最终也会向左或者向下移动。因此，对于栅格i而言，栅格3称为“死角”。对比陷入“死角”现象的蚁群，本文算法通过提前将栅格3标记为“禁止栅格”，直接从栅格i行进至栅格2或栅格4，使得算法在计算量以及最优路径的转弯次数、路径长度方面都有所减少，在寻求全局最优路径的基础上加快了算法的收敛速度，同时节省了AGV的运行能耗。

2.2 改进信息素浓度初始化

蚁群算法在迭代初期，由于地图环境缺乏差异化初始信息素浓度，蚁群在寻路过程中缺乏引导因素，导致蚁群在算法前期盲目搜索，算法收敛速度变慢。因此，本文设计一种基于欧式距离的差异化信息素浓度初值，根据已知的地图环境模型并围绕起始点以及目标点生产的“次优路径”差异化分布初始信息素。如式(6)所示

(6)

式中：Tau(i,j) 表示可行栅格i与可行栅格j之间的信息素浓度。dsi表示出发栅格s到当前栅格i之间的欧式距离，dij表示当前栅格i到待选栅格j之间的欧式距离dje表示待选栅格j到终点栅格e的欧式距离，dse表示起始栅格到目标栅格之间的欧式距离， min(djm) 表示栅格j距离“次优路径”的最小欧式距离，dsm、dmn、dne、dme均表示“次优路径”上的两个栅格之间的欧式距离。σ表示差异化系数。σ越大，代表初始全局信息素浓度差异越大。

两点之间直线距离最短，但如果仅将起始栅格与终止栅格之间的连线作为“次优路径”，不考虑起始栅格与终止栅格之间的静态障碍物，直接对两栅格的连线进行信息素浓度初始化反而会误导蚁群进行搜素。如图5(a)所示，图中虚线为全局最优路径，实线为按照初始信息素寻路结果，由于初始化信息素时未考虑连线间静态障碍物影响，蚁群寻路至障碍物时需要继续沿障碍物进行随机搜索寻找最短路径，寻路效率低同时很难收敛到全局最优。本文首先确定出“次优路径”，然后根据欧式距离确定出栅格之间的初始信息素浓度，距离“次优路径”越短的栅格，初始信息素浓度越高，反之越低。确定“次优路径”的具体方法如下：首先确定起始栅格与终止栅格之间的连线，当栅格 (s,e) 的连线中有障碍物时，在障碍物处形成断点。若障碍物位于断点左边或右边，此时将沿障碍物向上、下分别进行搜索，记录障碍物数量，直至找到可行栅格。比较两个方向的障碍物数目，选择障碍物较少的方向的可行栅格作为下一个出发点；若障碍物位于断点上边或下边，此时将沿障碍物向左、向右分别进行搜索，记录障碍物数量，直至找到可行栅格。比较两个方向的障碍物数目，选择障碍物较少的方向的可行栅格作为下一个出发点，直至到达终止栅格，最终找到“次优路线”。如图5(a)的实线所示，栅格 (s,e) 的连线中存在障碍物，且障碍物位于断点右侧，因此沿障碍物上下搜索，发现向下的障碍物栅格数较少，因此将障碍物下方的可行栅格作为新的出发点继续搜索，最终形成图中虚线所示的“次优路径”；如图5(b)的虚线所示。栅格j为栅格i的待选栅格,选择栅格j距离“次优路线”最近的栅格m作为出发点。通过式(6)可以计算得出栅格 (i,j) 之间的初始信息素浓度。

图5 信息素初始化原理

如图5所示，当栅格i与栅格j越靠近“次优路线”时，栅格i与栅格j之间的初始化信息素浓度越高，蚁群在寻路过程中，会大概率朝该路径方向进行搜寻，提高蚁群寻路效率，加快算法收敛，减少算法迭代次数。

2.3 改进启发函数

在基本蚁群算法中，启发式函数仅由当前栅格i与待选栅格j之间的距离dij决定。但栅格之间的距离差值较小，蚁群仅通过栅格间距离dij很难从众多可选栅格中选出最优栅格。例如，当单位栅格宽度为1时，相邻栅格之间的最小距离为1，最大距离约为1.4；经过基本蚁群算法的距离启发函数计算后，最近相邻栅格与最远相邻栅格的启发函数值仅相差约0.3。距离启发函数对蚁群的寻路效果微弱，蚁群不能综合利用栅格间的信息素浓度和栅格间的距离。降低了蚁群算法的搜索效率以及最终的寻路效果。因此，本文改进一种启发式函数，该函数值由当前栅格i到待选栅格j之间的距离dij以及待选栅格j到目标栅格e之间的距离dje共同决定，如式(7)所示

(7)

为了避免由于栅格之间的距离差值过小导致启发式函数值对蚁群寻路过程中引导力弱问题，采用放大距离差值的方法增强待选栅格之间的“优劣性”

(8)

(9)

其中，φij表示栅格i与栅格j之间的距离放大函数，dje表示待选栅格j与目标栅格e之间的欧式距离，dij表示当前栅格i与待选栅格j之间的距离，dse表示出发栅格与目标栅格之间的欧式距离。ω与λ表示距离放大系数，可根据具体环境进行设置。Dmax，Dmin分别表示当前栅格与可选栅格之间距离的最大值和最小值，0.01为了保证分母不为0。系数q表示放大系数，其取值与待选栅格到目标栅格的距离有关。距离放大函数与当前栅格与待选栅格之间的距离dij以及待选栅格与目标栅格之间的距离dje有关，对于栅格i，在所有待选栅格中，当dij与dje均相对较小时，距离放大函数较大，蚁群选择栅格j的可能性越大。

启发式函数的最终计算如式(10)所示

(10)

为了便于启发式函数计算，建立每个栅格的邻近栅格距离矩阵Dn2×8， 如式(11)所示

(11)

式中：l表示单位栅格的宽度，G(i)表示栅格i的状态，其值为0表示可行栅格，为1表示静态障碍物，j表示待选栅格相对于栅格i的方向标号，i′,i″,i1,i2表示与斜线方向垂直的邻近栅格。具体如图6所示。

图6 栅格距离矩阵

2.4 改进信息素因子

信息素因子决定了蚂蚁在寻路过程中蚂蚁前往下一个栅格时，受信息素浓度影响的重要程度。算法迭代前期为了增强蚁群的全局搜索能力同时避免蚁群陷入局部最优或者“早熟”现象的发生，信息素因子设置较小，减少信息素对蚁群寻路的引导。随着迭代次数的增加，蚁群在寻路过程中在较优路径上累积的信息素增多，较差路径上的信息素较少，通过增大信息素因子，蚁群跟随信息素浓度较高的路径进行搜索，缩小了搜索范围，加快了算法的收敛速度。如式(12)所示

(12)

式中：NCmax表示最大迭代次数，NC表示当前迭代次数。为了避免算法后期由于信息素重要程度过大造成算法陷入局部最优，设定αmax为信息素重要程度的上界阈值。

3 实验与分析

3.1 实验准备

本文所有算法均通过MATLAB R2016b仿真实现。实验运行PC的操作系统为Windows10，处理器为Intel Core i5-9400F CPU，内存为16 GB。本文采用栅格法进行地图建模，地图规模分别为10×10、20×20以及30×30，为避免由于单次实验造成误差，分别对不同环境地图进行30次仿真实验，并对实验数据求取平均值。为增加地图真实性，将静态障碍物随机分布在地图栅格中。在栅格规模为20×20以及30×30,环境下分别对基本蚁群算法，文献[16]改进蚁群算法以及本文提出的改进蚁群算法进行性能分析，本文算法相关参数见表1。

表1 实验参数

3.2 算法性能对比

将基本蚁群算法、文献[16]的改进蚁群算法以及本文算法在地图规模为20×20的栅格上进行对比实验。仿真结果如图7和表2所示。

图7 20×20地图规模仿真结果

表2 20×20地图规模实验结果

图7(a)～图7(c)分别表示基本蚁群算法、文献[16]算法以及本文算法在栅格地图规模为20×20的最优规划路径。图7(d)、图7(e)中，虚线、实线、点画线分别表示基本蚁群算法、文献[16]算法以及本文算法路径长度和转弯次数，从图中可以看出，本文算法最优路径避免了“死角”现象发生，减少了路径长度和转弯次数。结合表2可以看出，本文算法在路径规划方面较文献[16]算法减少了10.8%，较基本蚁群算法减少了4.3%；在算法搜索效率(稳定迭代次数减少率)方面较文献[16]算法减少了30%，较基本蚁群算法减少了43.8%。本文算法在迭代稳定时间方面相较于文献[16]算法减少了54.2%，较基本蚁群算法减少了32.4%。

为进一步验证算法可靠性，增加地图环境复杂度，在地图规模为30×30的栅格地图上进行对比实验。仿真结果如图8和表3所示。

图8 30×30地图规模仿真结果

表3 30×30地图规模实验结果

结合表3，实验结果表明：本文最优路径长度在基本蚁群算法基础上减少了5.1%，在文献[16]算法基础上减少了5.6%，通过在算法前期设置信息素初值，蚁群算法搜索效率(稳定迭代次数减少率)在基本蚁群算法的基础上减少了65%，在文献[16]改进蚁群算法基础上减少了35.7%；本文算法在拐弯次数上稍逊于文献[16]算法，但相较于基本蚁群算法却减少了18.8%；本文算法在迭代稳定时间方面相较于文献[16]算法减少了66.5%，较基本蚁群算法减少了11.1%。结合两种不同大小规模的栅格地图仿真实验可以看出，本文算法在满足寻找全局最优路径的情况下，保持极快的收敛速度，且经过少数迭代次数后算法便趋近稳定；而另外两种算法在前期迭代过程中极其不稳定，收敛速度过慢。因此，在综合衡量最优路径各方面性能都较好时，本文算法优势明显。

3.3 特殊路径规划仿真

为了进一步验证本文算法在改进初始化信息浓度情况下能够搜索出全局最优路径，本文采用特殊的10×10规模大小的栅格地图进行实验对比分析。实验结果如图9所示。

图9 10×10地图规模仿真结果

图9(a)～图9(c)分别表示基本蚁群算法、文献[16]算法以及本文算法在栅格地图规模为10×10的最优规划路径。由上图分析可以看出，基本蚁群算法在迭代初期并未进行信息素浓度初始化，蚁群在算法前期进行随机搜索，且搜索过程中判定待选栅格的“优劣性”标准单一，因此未收敛到全局最优路径；文献[16]算法仅根据待选栅格距离障碍物的距离进行信息素初始化，距离障碍物远的栅格初始信息素浓度高，距离障碍物近的栅格初始信息素浓度低，并未充分根据目标栅格进行有方向性的设置信息素浓度，最终也难以收敛到全局最优路径；本文算法在初始化信息素浓度时，遇到障碍物就沿障碍物进行上下左右搜索，寻找下一个出发点，最终得到一条“次优路径”，并根据“次优路径”进行信息素浓度初始化。实验结果表明，本文算法收敛速度较快、稳定性较强，且能够收敛到全局最优。

3.4 改进启发式函数性能对比

为了进一步验证本文算法在改进启发式函数后能够快速搜索出全局最优路径，采用地图规模为20×20大小的栅格地图进行实验对比分析。为保证实验的有效性，对比算法为将本文算法的启发式函数替换为基本蚁群算法的启发式函数；为保证实验数据的可靠性，在相同实验环境下进行30次仿真实验，并对实验数据求取平均值。实验结果如图10和表4所示。

图10 改进启发式函数仿真结果

表4 改进启发式函数在20×20地图规模实验结果

图10(a)～图10(c)分别表示对比算法与本文算法在栅格地图规模为20×20的路径规划。由图10(a)可以看出，对比算法终止栅格对目标栅格的引导力弱，同时栅格间距离太小，导致蚁群难以寻找出全局最优路径。结合表4，实验结果表明：本文算法在路径长度方面较对比算法减少了13.5%，在迭代稳定次数以及迭代稳定时间分别减少了30.8%和27.7%。本文算法通过改进启发式函数，适当放大栅格间距离，同时结合当前栅格与待选栅格距离以及待选栅格与终止栅格距离，增强蚁群寻路效率的同时寻找全局最优路径。

4 结束语

改进蚁群算法在构建二维平面地图时初始化信息素浓度并改进启发式函数，提升了蚁群算法的整体性能。如提高算法收敛速度、寻找全局最优路径以及增强算法稳定性。通过为每个栅格引入“方向编号”,避免“死角”现象发生，同时引入“拐角”机制，合理加大了最优路径与障碍物之间的距离，提高了AGV行走路径的安全性和可靠性。通过引入动态信息素因子，避免算法前期发生“早熟”现象以及后期陷入局部最优。仿真实验和结果数据表明，本文算法可以在减少路径长度和拐弯次数之间获得最优比例，为AGV规划出安全、可靠的最优路径。与其它算法相比，本文算法在收敛性、稳定性以及寻找最短路径方面表现优异，得到了性能较好的蚁群算法。本文算法在考虑AGV行走路径的安全性基础上规划出全局最优路径，在提高算法收敛速度的同时增强了算法的稳定性。在今后的研究工作中，可结合粒子群算法进行参数优化，规划更加智能的路径，同时引入滑动窗口方法，使AGV在动态环境下，实现动态避障功能。