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

任学干,葛英飞

(南京工程学院机械工程学院, 江苏 南京 211167)

随着制造行业自动化生产水平的不断提高,越来越多的自动引导车(automated guided vehicle, AGV)投入到生产车间.AGV的使用在提高企业生产效率的同时节省了劳动成本.路径规划是解决AGV如何在复杂生产车间寻找一条从起点到目标点的较优运动路径的方法,使AGV在运动过程中能安全避开所有的障碍物,且行驶距离最短[1].

近年来,国内外的专家学者对AGV路径规划问题进行了广泛的研究,发展了多种路径规划方法.传统的路径规划方法主要有栅格法[2]、人工势场法[3]、滚动窗口法[4]等,但是随着研究的深入,传统路径规划方法因自身缺陷无法更好、更快地解决路径规划问题,因此提出更多的智能路径规划方法,如神经网络算法[5]、遗传算法[6]、粒子群算法[7]、蚁群算法[8]等.神经网络算法虽然有很好的学习能力和鲁棒性,但是泛化能力较差,对样本质量要求过高；遗传算法通过适应度函数进行有方向的自适应搜索,但存在收敛速度慢、易陷入局部最优的问题；粒子群算法适用于全局路径规划,但是易出现粒子早熟现象；蚁群算法由于具有搜索启发性、多个体并行计算、鲁棒性等特点,受到广泛的研究.

蚁群算法是受蚂蚁觅食行为启发,由Marco Dorigo提出的一种启发式的全局优化算法.该算法本质上是一个复杂的智能系统,具有较强的鲁棒性、优良的分布式计算、易与其他算法结合等优点[9].传统蚁群算法在寻优过程中过度依赖于信息素浓度,而在算法搜索初期路径上的初始信息素浓度相等,使得前期搜索盲目性大,导致寻优过程收敛速度缓慢,且算法存在易陷入局部最优.针对上述问题,很多研究者对蚁群算法进行了改进.文献[10]针对传统蚁群算法易陷入局部最优解问题提出一种基于双向搜索机制的改进蚁群算法,并引入奖惩因子改善全局搜索能力;文献[11]针对蚁群算法前期目标搜索盲目性导致收敛缓慢的问题,构建了一种新的数学模型,对初始信息素浓度进行预先的差异化设置,从而提高算法收敛速度;文献[12]对蚁群算法概率公式进行改进,提出一种优胜劣汰机制,提高算法的搜索效率及搜索的准确性,并改善了锁死问题;文献[13]提出一种蜂巢栅格模型与动态分级蚁群算法结合的路径规划方法,使移动机器人减小转弯角度和缩短避障路径;文献[14]提出一种粒子群算法和蚁群算法相融合的算法,通过粒子群算法最优解调整路径上的信息素分布,从而解决蚁群算法初始阶段的信息素缺乏问题,提高算法寻找最优解的能力.

蚁群算法在解决路径规划问题上具有易和其他算法融合、速度快、精度高等优点[15],但存在搜索初期盲目性高以及易陷入局部最优的问题.因此本文提出一种改进的势场蚁群算法,在蚁群算法中引入人工势场法,通过在启发函数中加入障碍物对AGV的斥力以及目标点对AGV的引力,解决传统蚁群算法搜索初期的盲目性,有效避免陷入局部最优,并对算法的路径选择策略进行优化,减少算法的搜索次数,提高搜索效率.

1 环境建模与路径选择优化

1.1 空间环境建模

本文中的AGV工作在二维环境中,采用常用的栅格法对环境地图进行创建,如图1所示,此后的路径规划均在此环境地图上进行.使用栅格法能将复杂的环境问题分解成简单问题,适合应用于静态环境的路径规划,且算法计算量小,便于实现[16].

图1 栅格环境模型

图1栅格环境模型共有20行和20列,其中白色栅格为AGV可行走栅格,黑色栅格为障碍物栅格,每个栅格的边长均为1.栅格序号从左到右、从上到下的顺序依次标注为1,2,…,400.第一个栅格设置为初始点,第400个栅格设置为终点即目标点.

1.2 路径选择策略优化

图2 AGV运动方向

假设AGV已经选择从点位1到点位2的路径,如图3(a)中实线所示,AGV在从点位2选择下一点位时,如果不存在障碍栅格时,有7个点位可以作为下一运动点位.如果下一运动点位选择为点位4或点位7,如图3(b)中虚线所示,最后得到的路径长度没有直接从点位1到点位4或点位7所寻得的路径短,因此可以提前排除点位4和点位7,即在点位2被选取时将点位4和点位7添加到禁忌表中.同样,如图3(c)所示,在假设前提下从点位2选择点位5或点位8也不符合最优路径选择,但为避免3、6、9点位均为障碍栅格,导致AGV无法继续进行目标搜索,所以采用将点位5和点位8加入到一个临时禁忌表中,当点位3、6、9均为障碍栅格时,将从临时禁忌表中进行点位选择.若AGV已经通过点位选择获取运动方向,在选择下一点位时,假设以逆时针为正、以水平向右为0°,可以将当前方向的-45°～45°作为优先选择点位,将当前方向的+90°和-90°点位加入到临时禁忌表中,而其他方位点位均加入到禁忌表中.

(a)

(b)

(c)

2 传统蚁群算法原理

传统蚁群算法中的蚂蚁根据路径上的信息素浓度进行路径的选择,蚂蚁在寻找食物的路径上会留下一定量的信息素,这些信息素可以被蚁群中的其他蚂蚁感知.蚂蚁一次在从起点到终点的路径上所留下的信息素是一定量的,所以长度更短的路径上的信息素浓度会更高,此后更多的蚂蚁会选择信息素浓度较高的路径,而被选择次数越多的路径上的信息素浓度会越高,蚁群通过这种正反馈机制寻找到一条到食物的最短路径.

(1)

当蚁群中的蚂蚁全部完成路径规划后(有些蚂蚁最终到达终点,而有些蚂蚁最终没能到达终点),对当前栅格地图上的信息素进行更新,公式为：

(2)

(3)

3 势场蚁群算法

传统蚁群算法中蚂蚁是通过路径上的信息素浓度和与终点的欧式距离作为启发信息进行路径选择的.在开始时路径上的信息素浓度设置相等,这使得蚂蚁的搜寻盲目性大、算法收敛慢,并且在没有障碍物作用条件下蚂蚁可能进入障碍环境、陷入锁死状态.因此本文引入人工势场算法,通过加入障碍物的斥力作用和终点的引力作用来提高算法搜素效率,帮助蚂蚁进行有效避障,解决锁死问题.

3.1 人工势场法

人工势场法的实质就是对机器人的运行环境人为建立一个抽象的势场[17],机器人在这个势场中受到障碍物的排斥力和目标点的吸引力共同作用,最终到达终点位置.人工势场的引力势场函数公式为：

(4)

式中:λ为引力势场系数；X与XE分别为AGV当前位置与终点位置；ρ(X,XE)为AGV当前位置与终点的欧式距离.

引力函数为引力势场函数的负梯度,公式为：

F1(X)=-grad(U1(X))=λρ(X-XE)

(5)

由引力函数可知,AGV在到达终点前所受引力始终指向终点位置,并且随着距离终点越大,引力越小,直至到达终点时引力变为0.

由障碍物产生的排斥力正好相反,距离障碍物越近,排斥力越大,因此人工势场法的斥力势场函数公式为：

(6)

式中:m1为大于零的斥力场系数常量;ρ(X,XO)为AGV与障碍物之间的欧式距离;ρO为障碍物对AGV的作用距离;当AGV与障碍物的距离超过障碍物作用距离ρO时,AGV不再受到斥力作用.

斥力函数公式为：

F2(X)=-grad(U2(X))=

(7)

式中,nOR为从障碍物指向AGV的单位矢量.

AGV受到的合力为F=F1+F2.

3.2 势场蚁群算法启发函数构造

在传统蚁群算法中,蚂蚁通过信息素浓度和距离启发函数进行路径选择,在人工势场中,蚂蚁通过所受势场合力进行路径规划,通过将人工势场法的势场力启发信息融合到蚁群算法的启发信息中,加快路径规划收敛速度.势场力启发信息公式为：

ηF(t)=aFcos θ

(8)

式中:α为大于1的常量;F为蚂蚁在势场中所受合力;θ为F与蚂蚁下一选取点位栅格方向的夹角.

在算法初期引入势场力启发信息加快路径搜索速度,但随着迭代次数增加需要限制势场力启发信息的影响,提高路径搜索全局最优性,因此引入势场力启发信息影响系数μ,计算公式为：

μ=(Nmax-N-1)/Nmax

(9)

式中：Nmax为最大迭代次数;N为当前迭代次数.

可以看到随着迭代次数增大,势场力启发信息影响系数μ越来越小.经过改进后的势场蚁群算法的综合启发信息计算公式为：

ηij(t)=μηF(t)/djE

(10)

在改进后的启发信息ηij(t)作用下,AGV可以有效避开障碍,解决初期搜索盲目性问题,加快算法收敛速度.

3.3 改进算法执行步骤

改进势场蚁群算法在路径规划问题上寻求最优解的步骤：

1) 建立栅格地图,确定起点和终点位置,初始化蚂蚁数m、信息素挥发因子ρ、信息素启发因子α、期望启发因子β、最大迭代次数Nmax、引力势场系数λ、斥力场系数常量m1、信息素总量Q以及常量a;

2) 将m只蚂蚁放在初始位置;

3) 蚂蚁通过公式(10)获取当前位置的启发信息,并通过公式(1)计算下一步可能访问栅格的概率;

4) 通过轮盘赌法使用步骤3)获取的概率信息选择下一个到达栅格位置,并将该栅格信息列入到禁忌表中;

5) 通过路径规划优化策略算法,将下一步不符合最短路径的栅格位置添加到临时禁忌表中;

6) 判断m只蚂蚁是否到达目标位置(或者陷入锁死状态),若是,计算每只蚂蚁搜索路径长度,找出当前搜索的最优路径,否则转向步骤3);

7) 按照式(2)和式(3)对路径上的信息浓度进行更新;

8) 判断是否到达最大迭代次数,如果到达,求出每次迭代过程中的最短路径长度,如果没到达,转向步骤3).

4 仿真试验

对传统的蚁群算法和改进后的势场蚁群算法在Matlab上进行仿真,并将两者的仿真结果进行比较.

算法中的各个参数分别设置为：α=1,β=2,m=50,ρ=0.2,Nmax=100,a=1.15,Q=10.通过软件仿真得到传统的蚁群算法和改进势场蚁群算法的路径规划结果分别如图4和图5所示,并将结果数据统计在表1中.

通过对比图4和图5的仿真结果可以发现传统蚁群算法在路径规划过程中收敛速度缓慢,通过30次迭代过程后才趋于收敛状态,但是改进的势场蚁群算法收敛速度很快,在迭代12次后就开始

(a) 传统蚁群算法路径规划图

(b) 传统蚁群算法收敛曲线

(a) 改进势场蚁群算法路径规划图

(b) 改进势场蚁群算法收敛曲线

表1 相同栅格地图下算法数据

趋于收敛.通过传统蚁群算法最终找到的最优路径长度为35.15,通过改进的势场蚁群算法最终得到的最优路径长度为33.42.

通过算法中设置的参数可以得到在使用传统蚁群算法100次的迭代过程中只有1 053次蚂蚁最终到达了终点,而其他蚂蚁均陷入了锁死状态;而使用改进势场蚁群算法则有4 664次蚂蚁成功到达终点,说明改进后的算法有效避免了蚂蚁在搜索过程中陷入锁死状态.

通过仿真图形和记录的相关数据可以看出,文中提出的改进算法能更快地在复杂的环境下搜索到最优路径,且改善了传统蚁群算法易陷入锁死的现象.

5 结语

本文对传统蚁群算法原理进行了分析,针对传统蚁群算法初期收敛速度慢且易陷入锁死等问题,引入了人工势场法,通过引入势场中的引力和斥力到蚁群算法的启发函数中,提高了算法的搜索效率,改善了锁死现象.另外对路径选择策略进行了分析与优化,通过设置临时禁忌表,可以提前排除一部分所需搜索的栅格点位,减少算法的计算量,从而加快算法的求解速度.仿真结果证实了改进算法的有效性和可实施性.