一种基于改进蚁群算法的AGV小车三维路径规划研究

金 鑫 鑫

(亳州学院电子与信息工程系 安徽 亳州 236800)

0 引 言

智能仓储系统是指以信息化手段实现对仓库的实时监视和全面管理的信息系统，该系统能够实时掌握仓库容量、了解货物所存放位置、实现自主货物转移等[1-2]。在智能仓储系统中，货物转移快慢直接关系到其管理效率，通常执行货物转移作业的设备主要为AGV小车，如果要提高货物转移的速度，就需要对AGV小车的行驶路径进行规划[3]。

当前针对仓储系统中AGV小车的路径优化算法包括人工势场法、遗传算法、蚁群算法等。其中遗传算法虽然全局搜索能力强，但存在产生无效路径的问题；人工势场法在势场合力为零时会出现停滞状态，容易陷入局部最优；相比之下，蚁群算法具有正反馈、高稳健性和并行性的优点，已成功地用于智能仓储AGV小车的行驶路径规划等问题[4]。

蚁群算法最早是由Dorigo等学者提出的分布式智能仿生算法，该算法模拟了蚂蚁合作觅食行为的性质[5]。从算法原理上来看，蚁群算法主要存在搜索空间大、局部最优、搜索效率低、计算量大等问题。近年来，国内外众多专家学者致力于利用蚁群算法解决全局路径规划问题。文献[6]通过重新定义蚁群算法中的转移概率，对蚁群算法进行改进，从而加快了算法的寻优速度，但是其转移概率自适应调整能力较差。文献[7]为了避免蚁群在面对凹型障碍物时易陷入死锁状态的问题，通过采用广义信息素更新原则，代替传统蚁群算法的信息素更新，从而找到最优解，但是该算法易陷入局部最优。文献[8]提出了双层蚁群算法，大大提高了路径规划的效率，但双蚁群的信息素作用会相互干扰，影响寻优结果。文献[9]提出一种基于自适应调整信息素的改进蚁群算法，根据人工蚂蚁所获得解的情况，动态调整路径上的信息素，从而使得算法跳离局部最优解，但是该方法未能考虑较优路径重要路段上的信息素强度，使得算法搜索效率不高。

智能仓储系统中的AGV小车路径规划是当前研究的热点和难点。针对AGV路径规划，文献[10]在路径优化的方法中增加了对时间和能耗的考虑，实现了仓储系统货物转移作业中的能耗和效率之间的有效平衡。文献[11]通过利用交通规则和预约表解决仓储物流机器人集群在运行时发生的碰撞和死锁问题，并根据所设定的协同机制，减少机器人无任务的待机状态，平衡各机器人之间的工作量，最终实现在保证系统安全运行的基础上缩短系统运行时间的目的。文献[12]在仓储系统货物转移作业的工作中，为平衡行驶距离、行驶时间、作业载重等因素，建立了多因子的路径优化模型，并通过集成学习优化算法降低模型的复杂度，实现了仓储系统货物转移作业时间效率的优化。

从当前的研究现状来看，AGV路径规划的研究主要针对二维平面避障、二维路径优化等，但是不适用于货架式仓储系统中的三维折线路径规划[10]，且大多数路径规划算法运行效率低，容易陷入局部最优。鉴于此，本文提出了一种基于改进蚁群算法的AGV小车三维路径规划方法。首先，通过构建三维仓库模型来确定不同目标的三维坐标，并根据多个位置坐标建立AGV小车轨迹模型；其次，针对仓库AGV小车三维折线路径，利用改进的蚁群算法来实现路径优化问题；最后通过对比实验来验证基于改进后的蚁群算法的性能。

1 三维空间路径优化问题建模

1.1 立体仓库模型构建

在智能仓储系统中，AGV小车的作业模式主要有入库和出库作业[13]。在智能仓储系统中，单一的AGV小车作业往往需要在多个目标之间进行遍历工作且货物所存货架高度不一，因此需要对AGV小车的作业路径进行三维空间规划。在路径规划过程中不仅需要考虑二维平面内的最优路径，还需要注意小车在取货物时的垂直运动及变换不同货道时AGV小车的运动。鉴于此，本文建立立体仓库模型，确定多目标的三维坐标，并通过模拟现实货架和AGV小车来进行实验验证和操作。图1所示为立体仓库货架实物图，图2为立体仓库模型。模型将每排货架进行网格化划分，其坐标表示为(y,z)，货架的排数表示为坐标x。通过这种方式可以将整个货架式仓储系统表示为三维网格地图，这样货架的每一格均以三维坐标的形式表示出来，从而为AGV小车的路径规划提供保障。

图1 立体仓库货架实物图

图2 立体仓库模型

本文研究所使用的AGV小车并非单一两点式作业小车，而是可以在多个目标点之间遍历作业。智能仓储系统为货架式仓库，每个货架之间为货道，AGV小车在同一个货道上可以进行上下、前后运动，如果要到另一个货架上取货物，则需要先退出该货道，再进入到另一个货道。图3所示为实验AGV小车。

图3 实验AGV小车

当建立立体仓库模型，并确定不同目标的三维空间坐标后，AGV小车入库、出库作业就可以按照以下三个步骤进行：(1) AGV小车计算所有目标点与自身之间的距离，并选取其中最近的目标点作为本次作业的起始点，并运动至起始点。(2) AGV小车根据所有目标点的位置计算出本次作业的顺序，并按顺序依次到达下一目标点进行存取货。(3) AGV小车完成所有目标点的任务后回到起始点，即完成了本次作业，并等待下一次的作业指令。

通过上述分析可知，多目标点之间的顺序决定了AGV小车路径规划的效率，同时也直接影响了AGV小车的单次作业时间。

1.2 运行轨迹模型构建

在立体仓库模型中，AGV小车的运动主要包括水平和垂直两个方向，其中水平方向主要由小车驱动系统自主运行，垂直方向运动主要借助升降机来实现。假设小车为匀速运行，考虑其在启动及停止时的速度影响，取速度和时间均值，因此不会对路径优化产生影响。

为了便于对AGV小车路径进行规划，本文对AGV小车的运动轨迹进行分类，主要包括：

(1) 两个目标点位于同一个平面内，且X、Y、Z坐标中仅有一个坐标值不同，此时AGV小车在两目标点间的运动轨迹为直线；

(2) 两个目标点位于同一个平面，且X、Y、Z中有两个坐标值不同；

(3) 两个目标点位于不同平面，且X、Y、Z中坐标值均不相同。

根据上文分析，假设小车当前所在位置坐标为i=(x1,y1,z1)，目标位置坐标为j=(x2,y2,z2)，则如果AGV小车的运动符合第一种情况，那么其两点之间的位移如式(1)所示。

S=|y1-y2|或|z1-z2|

(1)

此时，若AVG小车需要在X轴方向上进行操作，那么其需要退出当前所在的货道，即运行到货道口，此时位移如式(2)所示。

S=2|y|+|x1-x2|

(2)

若AGV小车的运动符合第二种情况，此时虽然在同一个平面内但并非在同一条直线上，因此需要借助辅助点来实现AGV小车的运动。若AGV小车需要在X轴方向上进行操作，则AGV小车需要退出当前所在的货道，故两目标点之间的位移如式(3)所示。

S=|x1-x2|+|y1|+|y2|或 |x1-x2|+|z1-z2|+2|y|或 |y1|+|y2|+|z1-z2|

(3)

若AGV小车的运动符合第三种情况，此时两目标点不在同一个平面内，可以认为AGV小车需要进行跨平面运动。为实现两点之间的运动还需要借助三个辅点，如果需要在X轴方向上进行操作，则需要退出当前所在的货道，故两目标点之间的位移如式(4)所示。

S=|x1-x2|+|y1|+|y2|+|z1-z2|

(4)

2 改进蚁群算法三维路径优化

2.1 蚁群算法理论

蚁群算法是由Dorigo根据蚁群外出觅食的行为模拟总结出的一种寻找优化路径的概率性算法。蚂蚁在外出觅食时，将信息素释放在所经过的路径上，其他蚂蚁对信息素的浓度进行感知，如果信息素浓度较高，说明此路径目标点距离自己较近，其他蚂蚁沿着此路径行进的同时也会释放信息素，进而使得此路径上信息素浓度进一步增加，在正反馈机制的作用下，该路径上的信息素越来越多。通过不停迭代计算，最终可以得到两点之间的最短路径。式(5)所示为蚁群算法中蚂蚁选择下一目标点的概率。

(5)

式中：i、j分别表示两个目标点；α表示信息素因子，即信息素浓度的高低会对蚂蚁对此路径是否选择产生一定的影响；β表示启发式因子，即蚂蚁在路径选择时信息素所占的重要程度；τij表示i、j两点之间的信息素浓度；ηij(t)为启发函数，ηij(t)=1/dij，dij表示i、j两点之间的距离；tabuk为禁忌表。

当蚂蚁遍历完所有路径之后返回到初始位置时，实现了一次路径循环，之后再一次对信息素进行更新。此时每条路径上的信息素包括随着时间推移遗留下来的信息素及当前蚂蚁释放的信息素。因此信息素的迭代如式(6)所示。

(6)

根据上述对蚁群算法的原理分析，可知蚁群算法的优势包括：(1) 通过正反馈不断增加路径上的信息素，使得算法在计算的过程中形成收敛的搜索过程，最终得到最优路径。(2) 蚁群算法通过蚂蚁个体释放信息素来记录路径，每个蚂蚁个体都可以对周围环境进行改变，并可以对环境中的信息素进行感知。(3) 算法为分布式并发计算的过程，即每个蚂蚁的路径选择概率计算是并行的，可大大提高算法效率。(4) 通过信息素浓度进行启发式搜索，有利于找到全局最优路径，而不会陷入局部最优。

2.2 改进蚁群算法三维路径优化方法

在基本蚁群算法中，蚂蚁通常会被分配到各个点位，并且需要对所有的目标点进行遍历，不同目标点之间的顺序选择在很大程度上取决于转移概率，而转移概率又与每条路径的启发式因子和信息素浓度有关。

对于货架式立体仓库而言，要想实现AGV小车的路径规划，必须同时考虑到水平路径选择和垂直路线规划。目前，基本蚁群算法主要用于解决二维平面路径规划即平面两点之间的路径，而对于货架式立体仓库这种平行于各坐标轴的折线路径无法适用，因此需要对基本蚁群算法进行优化。

针对两目标点的三种位置关系，通过cenpt变量来辨别两目标点为何种位置关系，进而确定需要增加的辅助点的数量。图4所示为增加辅助点数量的部分MATLAB代码。

图4 增加辅助点数量的部分MATLAB代码

当cenpt=3,表示AGV小车在两点之间运动属于第三种情况，即两目标点的x、y、z坐标均不一样，需要增加三个辅助点a、b、c，此时三个点坐标分别为a=(x1,0,z1)，b=(x2,0,z1)，c=(x2,y2,z1)，两点之间由i到j所经过的点的顺序为i→a→b→c→j。当cenpt=2，表示小车在两点之间运动属于第二种情况，即两目标点有两个坐标值不同。此时可以分成两种情况，当x坐标相同则只需要增加一个辅助点a=(x,y2,z1)，由i到j所经过的点的顺序为i→a→j。当y坐标相同或者z坐标相同，那么小车需要退出货道，此时需要增加三个坐标点a=(x1,0,z)、b=(x2,0,z)、c=(x2,y2,z)，两点之间由i到j所经过的点的顺序为i→a→b→c→j。当cenpt=1，表示两个目标点只有一个坐标值不同，此时不需要增加辅助点，两点之间直接由i运动到j，即i→j。本文提出的改进蚁群算法三维空间路径优化方法，主要分为以下五个步骤：

步骤1假设算法中共有m个蚂蚁，同时把这些蚂蚁随机放置在三维空间的不同点上，设置Nc_max为本次计算的最大迭代次数，并初始化蚁群算法中的各个变量，β为启发因子，α为信息素因子，ρ为随着时间推移信息素的挥发系数，Q为信息素的增强系数。

步骤2对算法中的每个个体的初始信息素进行确定，并将蚂蚁随机分配到不同的起始点上，让其逐个选择路径，并将其经过的目标点放到禁忌表中。路径选择中，每个蚂蚁根据概率函数来判断应该选择哪个目标点作为下一点，如式(7)所示。

(7)

在所有蚂蚁都遍历完一次路径之后，会对各个蚂蚁的路径距离进行比较，并记录其中最短的路径，同时会记录所有蚂蚁行走路径的平均数。图5所示为实现最短路径选择的部分代码。

图5 选取最短路径的部分代码

步骤3将k值与m值进行比较，若k≥m，则说明k蚂蚁已经走完了所有目标点，此时进入步骤4，否则转入步骤2。

步骤4对全局中的信息素、信息素挥发系数、信息素增强系数进行更新，信息素的更新如式(8)所示。

(8)

图6 更新信息素部分代码

步骤5禁忌表清零。在达到最大迭代次数之后，将禁忌表清零，对每次迭代中所获得的最短路径进行比较，并最终得到最短路径和所有目标点的行进顺序，并输出最优路径结果。

图7所示为改进蚁群算法实现流程。

图7 改进蚁群算法实现流程

3 实验结果与讨论

为了验证改进蚁群算法的有效性，在Window 10操作系统下采用MATLAB 2013a对算法进行仿真实验，实验硬件环境：Intel(R)Core(TM) i5-3337U Duo CPU1.8 GHz/8 GB内存。首先，实验选取具有12列，每列4层，每层30个，共计1 440个仓位的仓库；其次，选取可以实现多目标点遍历作业的AGV小车，该小车需要满足在水平货道和垂直货架上运动。为了验证所提出算法的性能，将其与遗传算法、基本蚁群算法进行对比实验，实验中所设置的目标点数均相同。在本次实验中，若参数α值过大，则搜索路径的随机性会减弱，过小的话会陷入局部最优；β值过大容易选择局部最短路径，过小算法收敛速度太低。通过计算分析文中信息启发因子α和期望启发因子β的取值，分别取值为1.5和2。初期为了尽快找到最优解，信息素挥发系数ρ取0.1，算法后期根据实际情况对ρ值进行调整。另外，蚂蚁个数m取30，最大迭代次数NC_max为100。图8、图9分别为50个目标点和25个目标点情况下三种算法的收敛曲线。

图8 50个目标点收敛曲线

图9 25个目标点收敛曲线

由图8、图9比较可知，优化蚁群算法的迭代计算次数最少，反应时间较短。为了验证改进后的蚁群算法能够保证AGV小车在每列货架位置都能够正常运行且检测AGV小车最大化运行时间，故在每一列货架随机选取一个目标点。表1所示为随机生成的12个目标点坐标，其中X轴的取值区间为(1，12)，Y轴的取值区间为(1，30)，Z轴的取值区间为(1，4)。

表1 仿真实验的随机生成的目标点

图10所示为改进后蚁群算法计算出的平均距离和最短距离。可以看出随着迭代次数的增加，平均距离越来越小，由此表明增加迭代次数对于路径规划有一定作用。

图10 平均路径和最短路径

图11所示为本次实验中所得到的AGV小车最优路径轨迹，表2为实验中目标点的运行顺序。图11中实心圆为最优路径起始点，空心圆为目标点，菱形为辅助点。由此可知，本文设计的优化蚁群算法在货架式立体仓库的AGV小车多目标路径规划中有较好的应用效果，算法实现所需要的迭代次数较少，计算速度快，收敛性强，且能获得最短路径。

图11 优化路径轨迹

表2 仿真实验目标点运行顺序

4 结 语

本文研究了智能仓储系统中AGV小车多目标路径规划，利用蚁群算法将二维平面路径规划扩展到三维空间中，并引入禁忌表对基本蚁群算法进行改进，优化AGV小车行驶路径。通过实验得出以下结论：(1) 与其他算法相比，本文改进的蚁群算法所需迭代次数少、收敛性强，能够有效避免算法进入局部最优；(2) 改进后的蚁群算法在智能仓储系统AGV小车多目标路径规划中有较好的应用效果，能获得最短路径。