基于优化蚁群算法的AGV路径规划研究

张志军, 董学平, 甘 敏

(1.合肥工业大学 电气与自动化工程学院,安徽 合肥 230009; 2.福州大学 数学与计算机科学学院,福建 福州 350108)

0 引 言

自动导引车(automated guided vehicle,AGV)是一种无人驾驶的运输车辆。由于近几年我国仓储物流行业的迅速发展以及人力成本的提高,传统的仓储物流运输方式越来越不适应人们的需求[1]。AGV工作稳定可靠,可以大大提高工作效率,节省人力成本,将人们从某些危险的工作环境中解放出来,在仓储物流运输中扮演着越来越重要的角色,因此高效的AGV路径规划已经成为一个重要的研究课题。

对于AGV的路径规划问题,国内外学者做了大量的研究工作,提出了多种AGV路径规划方法,其中智能路径规划方法有遗传算法[2]、粒子群算法[3]、人工蜂群算法[4]以及蚁群算法[5]等。蚁群算法是意大利学者Dorigo受到自然界中真实蚂蚁群体的觅食行为启发而提出的一种元启发式算法[6],它具有良好的正反馈性、并行性以及较高的鲁棒性,具有全局搜索能力,在解决AGV路径规划问题上得到了广泛的应用[7-9]。文献[10]将蚁群下一步可达节点的范围扩大到整个地图空间,并且通过设置跳点,使搜索到的蚁群最短路径长度得到了优化,但该方法运行耗时比较长;文献[11]在精英蚁群算法的基础上引入了独狼搜索机制,采用独狼逃跑策略在蚂蚁视场内设定天敌,从而避免路径上的信息素趋于稳定,改善路径停滞问题,使最短路径解的质量得到了提升,但该算法的收敛速度还需要进一步改善;文献[12]针对复杂凹形障碍环境下的路径规划问题,提出了双蚁群完全交叉算法,将蚁群2的路径解和蚁群1的路径解相交,以优化蚁群1的路径解,从而得到高质量的路径,但该算法2个蚁群的迭代次数和迭代方式相同,内存占用比较大且耗时较长。

本文针对上述问题,提出了一种优化蚁群算法。首先,在基本蚁群算法中引入辅助蚁群,利用辅助蚁群的方向优势优化主蚁群初始信息素的分配,使主蚁群前期路径搜索更具有针对性,提高了搜索效率,且辅助蚁群和主蚁群的迭代次数和迭代方式有很大区别,因此优化蚁群算法占用内存较小且运行耗时较短。其次,伪随机状态转移策略的引入,增加了路径选择的多样性,避免了算法早熟。最后利用蚁群的当前最优解、主蚁群一代蚁群中的最优解、最差解对路径上信息素进行有区别地奖惩,提高路径搜索的质量。仿真结果表明,优化蚁群算法的收敛速度和最短路径质量均得到了提升。

1 环境建模

1.1 栅格环境

在对AGV的路径规划研究中,建立AGV的运动环境是一个很重要的步骤,常用的环境建模方法有可视图法、栅格法和拓扑法[13]。本文采用栅格法作为环境建模方法,将运动环境抽象为由m×n个网格单元组成的二维平面环境地图,使得AGV在该环境下的运动过程视作质点运动[14]。一个5×5的栅格环境如图1所示,以环境左下角为坐标原点,向上为Y轴正方向,向右为X轴正方向,建立平面直角坐标系,选择网格单元长度为1 cm。在栅格环境中,将环境中的障碍物在环境地图中用阴影栅格表示,不足1个栅格的按1个栅格计算,可行栅格用白色栅格表示。

将栅格环境按从左到右、从上到下的顺序标示每个栅格的序号,在m×m的栅格环境中,序号S与所在栅格的坐标(x,y)一一对应且对应关系为:

(1)

其中:mod为求余运算;ceil为向上取整运算。因此,AGV的行走路线可以用一系列序号数组的形式表示出来[15]。

图1 AGV栅格环境

AGV运动方向如图2所示,除边缘栅格外,每个栅格一般有左上、上、右上、左、右、左下、下、右下8个运动方向,分别将它们用1、2、3、4、5、6、7、8数字进行编号。

图2 AGV运动方向图

1.2 栅格环境处理

在栅格环境中,当一个可行栅格的上、下、左、右4个方向中至少有3个方向有障碍栅格存在时,就构成了一个凹形障碍物。本文针对此类凹形障碍物中的可行栅格做了优化处理,这是因为这类可行栅格不但会增加不必要的路径,而且还有可能导致蚂蚁在搜索路径的过程中无路可走而无法到达终点,即发生死锁现象,降低了蚁群路径搜索质量。栅格环境处理前后地图如图3所示。从图3a可以看出,由网格14到网格16处,经过网格9的长度比网格15的路径长度长;由网格24到网格36处,经过网格29的长度比网格30的路径长度长,而且在网格29处蚂蚁如果向网格28、27移动,那么会造成死锁。本文算法会检测可行栅格上、下、左、右4个方向栅格的可行状态,若出现3个及3个以上的栅格不可行时,则会把该栅格标记为障碍栅格,整个栅格持续重复检测标记,直到障碍栅格的数目不再增加为止,实现效果如图3b所示。

图3 栅格环境处理前后地图

2 基本蚁群算法

基本蚁群算法中,人工蚂蚁在寻找路径时,和真实蚂蚁相似,会根据路径上信息素的浓度选择运动方向,浓度越高,选择该运动方向的概率就越大。假设蚂蚁k在t时刻从节点i到节点j的路径上的信息素为τij(t),则从节点i到j的转移概率为:

(2)

其中:α反映了信息素在路径选择时的重要程度,α越大,蚂蚁就更倾向于选择高信息素浓度的节点;启发值ηij=1/djG,表示为从节点j到终点G的欧式距离的倒数;β反映了启发信息在路径选择时的重要性,β越大,蚂蚁就更倾向于选择距离终点较近的栅格节点;D为节点i可选的下一个可达节点的集合。

基本蚁群算法中,蚂蚁利用信息素寻找路径的同时,也会在路径上释放信息素,当一代蚂蚁中所有的蚂蚁都完成了路径搜寻,全局信息素更新方式为:

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

(3)

(4)

(5)

3 优化蚁群算法

3.1 优化信息素的初始分配

基本蚁群算法初始信息素的设置都是相同的量,会导致算法在初期搜索时具有一定的盲目性,增加了搜索路径的时间成本。本文中的优化蚁群算法提出了一种使用辅助蚁群来协助主蚁群进行初始信息素分配的方法。辅助蚁群利用其在搜索路径上的方向优势,这种方向优势可以让辅助蚁群较基本蚁群快速规划出可行的较优路径。辅助蚁群工作原理如图4所示，假设起点在序号为1的栅格处,记为B;终点在序号为25的栅格处,记为G,由于从B到G有一定的方向性,最优路径一般会出现在AGV由右、右下、下3个运动方向到达的节点组成的路径中。因此在辅助蚁群中,规定蚂蚁k在节点i处最多只有3个转移方向,即右、下和右下,从节点i到可转移节点j的转移概率为:

(6)

其中:jx、jy分别为节点j的横、纵坐标值;ix、iy分别为节点i的横、纵坐标值;D′为节点i在右、下、右下3个方向可达节点的集合。由(6)式可知,蚂蚁在右、下、右下方向的转移概率分别为1/4、1/4、1/2,因此辅助蚁群更偏向于往右下方向移动,有利于减少搜索路径长度。

图4 辅助蚁群工作原理

辅助蚁群的每一代蚂蚁中,只对找出该代中最短路径的蚂蚁的信息素进行更新,全局信息素更新方式为:

(7)

(8)

其中:n为一代中最优路径上的蚂蚁数;Lbest′为该代中的最优路径长度;路径(i,j)为该代最优路径。为避免某一路径较其他路径上的信息素浓度过高,造成主蚁群过早收敛,引入最大最小蚂蚁系统,利用下式对辅助蚁群迭代完成后的信息素进行限制，即

(9)

其中:τmax′、τmin′分别为设置的辅助蚁群信息素的最大值和最小值。

设置辅助蚁群的初始信息素,待蚁群迭代完成后,将辅助蚁群信息素传递给主蚁群,作为主蚁群的初始信息素。由于辅助蚁群每代最优路径上的信息素较其他路径多,能够引导主蚁群沿着这些路径移动,从而提高主蚁群前期搜索的路径质量;将辅助蚁群当前搜索到的最优路径传递给主蚁群,帮助主蚁群优化搜索策略。此外,辅助蚁群在类似于图1的环境中会找不到从起点到终点的通路,此时辅助蚁群路径上的初始信息素只会随着迭代而挥发,而没有信息素的增量。迭代结束后,辅助蚁群将挥发后的信息素传递给主蚁群,同时将当前最优路径长度设置为无穷大,此时主蚁群仍然能正常工作。

3.2 优化的状态转移策略

对于主蚁群,针对基本蚁群算法中蚂蚁从一个节点到下一个节点的状态转移为单独的轮盘赌方式,很容易造成蚂蚁较快集中到某一路径而导致搜索到的最优路径不为全局最优的情况,提出了一种伪随机状态转移策略为:

(10)

其中:j1为i节点处随机选择的下一个可达节点;j2为采用(2)式选择的下一节点;q为0～1之间的随机数;q0为伪随机转移策略选择的切换值,q0=1/(N+1),为自适应动态变量,随着迭代次数的增加而减少;N为优化蚁群算法主蚁群的迭代次数。前期q0能取到较大的值,增加搜索路径的多样性;后期q0较小,蚂蚁将会集中在信息素较多的路径上,加快收敛速度。

3.3 优化的信息素更新策略

本文采用全局信息素更新策略,即当一代蚂蚁中所有个体都完成了路径搜索后才更新路径信息素。

将辅助蚁群更新后的信息素和当前搜索到的最优路径传递给主蚁群,帮助主蚁群完成路径规划。主蚁群每代蚂蚁搜索完路径后,根据主蚁群一代蚂蚁中最差路径Lworst、一代蚂蚁中最优路径Lbest及当前主蚁群和辅助蚁群所找到的最优路径LbestALL,利用(3)式、(4)式、(11)式更新全局信息素,即

(11)

惩罚一代中的最差路径可以减少后代蚁群在该路径上的数目,对当前路径上的信息素进行有差别的奖励,使蚂蚁集中在较优路径附近,提高蚂蚁搜索路径解的质量,加快收敛速度。

在路径搜索过程中,可能会出现某代蚂蚁中出现了当前最优路径,但由于路径上的信息素比较低而在后代蚂蚁中丢失的现象,降低了找到全局最优解的概率。为了确保当前最优路径不会丢失,若Lbest和LbestALL在一代蚂蚁中不相等,即该代蚂蚁没有搜索到LbestALL所在路径时,在该代蚂蚁路径信息素更新完毕后,则根据(3)式、(12)式增加当前最优路径LbestALL的信息素为:

(12)

为了避免由于某一路径上信息素浓度过高导致算法的停滞,对路径上的信息素进行限制，即

(13)

其中:τmax为限制的信息素的最大值;τmin为限制的信息素的最小值。

3.4 优化蚁群算法的实现步骤

优化蚁群算法的路径寻优流程图如图5所示。

具体实现步骤如下:

(2) 栅格环境处理。当一个可行栅格的上、下、左、右4个方向中至少3个方向有障碍栅格存在,将该栅格标记为障碍栅格。

(3) 辅助蚁群利用其方向优势寻找路径,迭代完成后将当前最优路径和更新后的信息素传递给主蚁群作为初始信息素。

(4) 主蚂蚁k通过主蚁群状态转移策略选择移动到下一地址。

(5) 判断蚂蚁k是否陷入死锁,若陷入,则丢弃该只蚂蚁,并立刻启动下一蚂蚁,转步骤(4)。

(6) 判断蚂蚁k是否到达终点,若到达,则记录该路径并启动下一蚂蚁,转步骤(4)。

(7) 判断一代中m只蚂蚁是否都完成了路径搜索;若是,则对该代中的蚂蚁根据主蚁群信息素更新策略、更新信息素,迭代次数加1;否则转步骤(4)。

(8) 重复步骤(4)～步骤(7),直到达到主蚁群最大迭代次数。

(9) 输出最优路径,程序结束。

图5 优化蚁群算法路径寻优流程图

4 仿真实验及结果

对2种算法均进行20次独立实验,仿真后的统计数据见表1所列。

图6 文献[16]蚁群算法最优路径轨迹及仿真结果

图7 优化蚁群算法最优路径轨迹及仿真结果

表1 2种算法2次运行结果统计数据

从图6、图7可以看出,本文的优化蚁群算法和文献[16]蚁群算法的最优路径相同,但是由表1可知,本文算法20次仿真实验中的最优路径都为全局最优路径,而文献[16]算法有一定概率搜索到的最优路径为全局次优路径,同时本文算法达到最优路径的平均迭代次数相比文献[16]算法有了显著提高。

以上实验结果表明,相较于文献[16]算法,本文算法通过引入辅助蚁群,使主蚁群前期路径搜索时更具有针对性;通过引入伪随机状态转移策略,增加了搜索过程中路径的多样性;通过优化信息素更新策略,保证了路径解的质量,从而提高了蚁群算法的搜索效率,加快了蚁群算法的收敛速度,提升了最优路径解的质量,表明了本文算法的优越性。

5 结 论

在基本蚁群算法的基础上,本文提出了一种优化蚁群算法,对栅格环境做了优化处理,利用辅助蚁群设置主蚁群的初始信息素,减少前期主蚁群搜索路径的盲目性,并且对基本蚁群算法的状态转移策略以及信息素的更新策略做了相应优化。

MATLAB仿真结果表明,该优化蚁群算法提高了蚁群搜索效率,加快了收敛速度,提升了最优解的质量,表明该优化蚁群算法在AGV路径规划寻优问题上是行之有效的。