融合栅格地图模型的改进AGV路径规划算法研究

顾文斌，陈泽宇，吴亚伟，苑明海

(1.河海大学 机电学院，江苏 常州 213022；2.常州工程职业技术学院，江苏 常州 213022)

0 引 言

自动引导小车(automated guided vehicle，AGV)最早出现于二十世纪五十年代，是一种智能化物料自动搬运设备，其特点在于自动化程度高、易于控制、节省劳动力、提高运输效率、占地空间小等，因此，AGV在众多生产制造物流行业中得到了广泛应用。在汽车制造行业中，物流领域自动化设备应用是大势所趋，使用AGV替代人力能够降低汽车制造企业的运输成本，提升服务质量[1]。对烟草、医药、食品和化工等行业而言，业内对搬运任务有清洁、无排放污染、安全等要求，AGV能够较好地胜任。在仓储业中，AGV使用程度更为广泛，因为AGV有较强自动化水平和较高柔性，在仓储物流行业中能够降低人力成本，提高运输效率[2]。在AGV的使用中，进行合理的路径规划对于降低企业运营成本，提高利润率有重大作用，因此AGV的路径规划问题十分值得研究。

为了计算得到全局最优路径，目前采用的方法主要有遗传算法[3-4]、粒子群算法[5-6]、快速扩展随机树寻路算法[7]和蚁群算法[8-9]。之后的研究主要针对这几种算法进行改进，文献[1]提出的改进遗传算法减少了最短路径的路程，文献[2]对传统遗传算法进行改进，提高了算法的收敛速度和效率。文献[5]提出的改进粒子群算法提高了在AGV在规避障碍时搜得解的精度。文献[7]提出的改进快速扩展随机树寻路算法使得在复杂环境下机器人的运行更加平稳，且在一定程度上缩短了路径长度。文献[8]提出的融合粒子群与蚁群算法提升了蚁群算法的整体性能。对于传统蚁群算法收敛性差，容易陷入局部最优，结果不稳定的缺点，则考虑在对蚂蚁和迭代质量的评估之后，对每一次寻路的信息素进行区别更新，有利于扩大算法前期的搜索范围，加强算法后期的收敛性，提高算法的稳定性。

以上文献所用方法是目前解决AGV路径规划问题中普遍认可的，较优的算法，但是传统算法存在容易进入局部最优解，收敛性较差和搜寻结果稳定性差的问题。基于此，该文提出了改进型蚁群算法，使用两次评估来合理区分蚁群，根据区分结果使用不同的信息素更新方式，以此实现提高算法解的多样性、收敛性和稳定性的目标。此外使用蜂巢栅格建立地图模型，使得模型更加实际可靠，能提高AGV小车行驶时的平稳性，并降低避险路径的长度。

1 环境模型建立

对于研究AGV的路径规划问题，建立其空间移动环境模型是基础，常用的方法有可视图法[10]、传统栅格法[11]和人工势场法[12]。栅格法(grid method)具有简单，易于表达和灵活等优点，所以采用栅格法建立AGV空间环境模型，并在传统的栅格基础上，模拟蜂巢建立起正六边形的栅格，对AGV行驶环境进行分割。

1.1 蜂巢栅格模型建立

图1 蜂巢型栅格

1.2 蜂巢型栅格和传统栅格的对比分析

图2 蜂巢栅格移动方向

图3 避险路径对比

图4 最短路径对比

综上，蜂巢栅格在行驶的平稳性和避险路径的长度方面都优于传统的正方形栅格，因此后文的改良蚁群算法将在蜂巢栅格的背景下进行求解。

2 基于动态分级制度的改进型蚁群算法

2.1 传统蚁群算法

在传统的蚁群算法中，蚂蚁会根据路径上的信息素浓度选择自己的路径，并且根据路径的质量留下新的信息素，每一次迭代后所有路径上的信息素都会消散一部分，使得路径寻找不会过早地进入局部最优。选择方法如下。

(1)

(2)

(3)

式中，ρ∈(0,1)，为信息素在一次迭代中的挥发系数；Δτij为信息素的增量；K为蚂蚁总数；Q为一常数。

2.2 选择机制的改进

在传统的蚁群算法中，路径启发因子ηij(t)是根据路径(i，j)所确定的，但是这样容易陷入局部最优解。为了获得全局优解，在改进的算法中使用ηij(t)=1/d(i,s)，其中d(i,s)为蚂蚁此时距离目标点的距离，同时将allowedk改为蚂蚁k相邻可选择的点，将栅格矩阵做邻接处理，蚂蚁k只能选择所得邻接矩阵中值不为0的点做下一目标点，以减少不必要的计算。

2.3 对蚁群进行评估分类

对于传统的蚁群算法，信息素的更新完全根据路径长度，也有学者研究了改良的信息素更新规则[13]来优化蚁群算法，但是在算法前期多样性和后期的收敛性方面还有待提高。针对这个问题，文中在考虑蚂蚁的动态分级[9]之上，考虑每一次迭代的质量，将每一次的迭代性质分为寻优和侦察，不同性质的迭代采用不同的信息素更新规则，以提高前期解的多样性和后期解的收敛性。

具体来说，受到人工蜂群算法[14]的启发，先将蚂蚁分为侦察蚁和寻优蚁。首先根据该蚂蚁在一次迭代中所搜索到的路径Lk与此次迭代中所搜索到的最短路径Lmin相比较，得到该蚂蚁的属性值，该值设置为：Tk=Lmin/Lk。之后设置属性值的阈值，记为T0。比较属性值和阈值来区分侦察蚁和寻优蚁，当Tk>T0时，说明该蚂蚁搜得结果与最优解相近，为寻优蚁，则该蚂蚁在更新信息素时，将更新的参数调整使得余留更多的信息素。反之当Tk≤T0时，说明该蚂蚁搜得路径与最短路径之间的差距较大，为侦察蚁，则该蚂蚁在更新信息素时，将参数调整使得余留更少的信息素。所以T0设置的值需要重点研究，如果T0太大容易导致更少的蚂蚁成为寻优蚁而导致算法最终不能很好地收敛，如果T0太小容易使更多的蚂蚁成为寻优蚁而导致蚁群容易陷入局部最优解。经过多次仿真，发现将T0设置为0.68时能得到很好的结果。

2.4 信息素更新规则

根据上文对蚁群的评估结果，将算法中的蚂蚁分为了四种情况，对于四种蚂蚁将采取不同的信息素更细规则。

首先对于寻优蚁和侦察蚁，两者在信息素更新时，满足以下关系：

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

(4)

(5)

(6)

式(5)、式(6)中，ω为蚂蚁质量系数，其中ω1>ω2>0，Q为一常数，Tk为蚂蚁的属性值，T0为蚂蚁属性值的阈值。在此更新规则下，寻优蚁的信息素余留要高于侦察蚁的信息素余留，这样在进行全局搜素时，确保了较优路径上有高浓度的信息素，但是ω1和ω2之间的差值不能过大，否则容易在算法初期就陷入局部最优。经过实验仿真，将ω1设置为5，ω2设置为3，能够有效防止陷入局部最优且最后收敛较好。

关于迭代质量，由于在算法初期，蚂蚁搜索范围大，路径长短参差不齐且相差较大，此时这一代蚂蚁的信息素更新策略采用式(7)。

τij(t+1)=(1-ρ)τij(t)+pm·Δτij,pm≤p0(7)

式中，pm为迭代的质量值；Δτij则根据上述内容先判断该蚂蚁是寻优蚁还是侦察蚁。

在这种机制下，算法初期过于发散的搜寻结果将不会留下过浓的信息素，而其中接近最优路径的蚂蚁则根据寻优蚁余留更多信息素的特点，将较优路径先行区分开来，到达算法后期，一次迭代中大部分蚂蚁都是接近最优路径后，则使用式(4)进行信息素更新，使结果收敛于最优路径。

综上所述，改进型蚁群算法信息素更新满足以下规则。

(8)

2.5 算法流程

将蜂巢栅格和改进的蚁群信息素更新规则融入传统蚁群算法，得到的基于蜂巢栅格的改良蚁群算法如下(见图5):

图5 改进蚁群算法流程

(1)全局初始化，将环境矩阵邻接化得到邻接矩阵，得到初始蚂蚁总数，迭代总数，起点终点位置。

(2)蚂蚁根据概率公式(1)对路径节点进行选择。

(3)判断蚂蚁是否到达终点，若是，记录此路径长度并对该蚂蚁的属性进行评估，当所有蚂蚁执行完此步，迭代数加1。若不是则重复步骤(2)。

(4)当所有蚂蚁完成步骤(3),对迭代质量进行评估。

(5)根据蚂蚁属性和迭代质量，对信息素进行区别更新。

(6)判断是否到达最大迭代数，若是，则输出最优路径，算法结束；若不是，则重复步骤(2)～(5)，直到算法结束。

3 仿真分析

使用MATLAB软件对传统蚁群算法和改进型蚁群算法进行仿真。前文已经论述了蜂巢栅格的优点，所以两种算法都在25×25的蜂巢栅格的背景下进行计算。各个参数设置为：α=1,β=7,ρ=0.3,Q=1蚂蚁数K=100，迭代数M=150。算法性能从算法的收敛性、路径多样性进行证明。

3.1 算法收敛性证明

图6为根据改进型蚁群算法所得出的最短路径图。图7为两种算法的最短路径长度的曲线收敛图。从图7的对比中可以看出，改进型算法在前期效果并非十分明显，因为要保证初期路径的多样性，而到了算法中后期，进行有针对地寻找最优路径时，改进型蚁群算法能体现出良好的收敛性。

图6 最优路径图

为了证明算法的稳定性，并和传统算法进行对比，将两种算法各运行10次并统计数据结果，如表1所示。

表1 算法结果对比

从表中可知，传统算法下搜得最短路径长度为36，而改进型算法下搜得最短路径为35，并且根据10次运算的平均值和标准差可以看出，传统的算法搜得最终结果差别较大，相比之下改进型蚁群算法出现此类问题的次数会少很多，根据收敛代数也可以看出，改进型蚁群算法由于信息素更新与传统蚁群有区别，所以算法后期收敛性更强。

3.2 路径多样性证明

为了证明改进型蚁群算法在路径多样性方面的优越性，和王槐彬等人提出的动态分级蚁群算法[15]进行了实验数据结果对比。

在同时采用蜂巢栅格的基础上，改进型蚁群算法和动态分级蚁群算法在路径多样性方面的对比如图8所示。实验设计150次迭代，在前半段迭代中，由于迭代质量不佳，蚂蚁残留的信息素浓度根据更新规则会相应减少，可以看到改进型蚁群算法的路径多样性要高于动态分级蚁群算法，达到避免进入局部最优的效果，证明了改进型蚁群算法在路径多样性方面的优越性。并且在算法后半段，迭代质量提升，蚂蚁逐渐向整体最优路径靠拢，根据信息素更新规则留下的信息素会增加使得蚁群准确地找到最优解。在图中可以看出，最后改进型蚁群算法能够使大部分蚂蚁都找到最优解，也证明了改进型蚁群算法的收敛性要优于动态分级蚁群算法。

图8 路径种类对比

从每一次迭代结果的路径长度标准差分析，如图9所示，动态分级蚁群算法整体上能实现算法前期避免进入局部最优，后期结果实现收敛，但是通过比较可以看出改进型蚁群算法在前期的发散程度和后期的收敛程度都要高于动态分级蚁群算法。如果考虑标准差到达一个阈值可以认为蚁群已经找到整体最优解，那么改进型蚁群算法相比于动态分级蚁群算法能够更快得到结果，解决算法效率低的问题，证明改进型蚁群算法整体上优于动态分级蚁群算法。

图9 路径长度标准差对比

4 结束语

对于AGV的路径规划问题，在传统的栅格模型上进行改变，使用转向角度小，避险路径和原路径比值小的蜂巢栅格对AGV行驶环境进行模型建立。在算法方面，由于传统蚁群算法效率低，根据蚂蚁和迭代的评估值对其进行信息素区别更新。在新的更新规则下，根据仿真结果可以得出，相比于传统算法，改进型算法在前期的路径多样性，后期的算法收敛性方面都更加优良，并且最终结果的准确性、稳定性也要优于传统的蚁群算法，证明了改进型蚁群算法整体优于传统蚁群算法。