智能仓储车间中多AGV路径优化算法研究

韩 强，何利力

（浙江理工大学 信息学院，杭州 310018）

0 引 言

近年来随着快消品制造业智能化及无人化的快速发展，在仓储和制造设施内的自动负载运输方式在提高生产效率的同时已然成为显著降低运营成本的实用手段，许多物流和制造过程都依赖于使用多个自动导引车（multi-AGV）系统。多AGV系统的任务是为系统中的每辆AGV（Automated Guided Vehicle）分配执行运输任务，对于每台AGV，给出了唯一的开始状态和唯一的目标状态，在AGV移动过程中不能发生碰撞的约束下，找到所有AGV从其开始状态到目标状态的路径。实现制造车间智能生产的关键是实现多AGV的路径轨迹最优或接近最优的无障碍路径。

从初始位置到目标位置检测并避开障碍物，实现物料的安全运输是AGV在无人仓库中的最重要功能。迄今为止，针对智能仓储车间中AGV路径求解较为常用的求解方法多以智能优化算法为主，如遗传算法、A算法、人工势场法、蚁群算法等。蚁群算法是通过模拟自然界蚂蚁觅食规律的概率型算法，相比于其他智能算法具有更强的鲁棒性和正反馈性，同时存在收敛速度慢，易陷入局部最优解等缺点，对此占伟等人改进启发因子给定初步引导方向减少算法收敛时间。李燕等人针对后期信息素浓度过高易陷入局部最优解问题提出了对信息素总量进行自适应调整的机制，大大降低了陷入局部最优解的概率。同时，人工势场法本身具有计算量小、反应速度快、路径无碰撞等优点，为此Liu等人利用人工势场法重新计算启发信息，提出改进的势场蚁群算法。王晓燕等人提出一种全局静态环境下移动AGV路径规划的改进势场蚁群算法，具有较高的全局搜索能力，但未解决原始人工势场法存在局部最优陷阱、目标不可达等问题。

针对智能仓储车间中多AGV路径规划问题，本文提出了一种改进人工势场蚁群融合算法。首先针对人工势场法改进斥力场函数，然后将人工势场法生成路径距离引入蚁群算法启发信息中，并改进蚁群算法信息素更新方式，提高算法的收敛速度和防止陷入局部最优解陷阱，最后针对多AGV路径规划加入冲突解决策略来解决AGV路径之间的冲突。仿真结果表明本文研究使改进人工势场蚁群融合算法在路径规划中耗时少，且能够针对多AGV规划出最优路径。

1 问题描述和环境建模

1.1 问题描述

在智能仓储车间内，为使多AGV运输系统完成运输任务，要求每台AGV从起点出发，避开静态障碍物，同时根据任务属性赋予的优先级信息，完成冲突路径的避让，最终到达目标位置完成运输任务。每台AGV所归划的行驶路径都应当是当前AGV从起点出发到达目标点的最优或次优路径（无碰撞、无冲突）。在进行多AGV路径规划则需考虑如下约束条件：

（1）仓库障碍物分布、可行路径已知。

（2）每台AGV的起点和目标点已知。

（3）所有AGV逐步进行路径规划直至到达目标点。

（4）AGV行驶过程中每一步都要考虑障碍物避撞和冲突路径的避让。

因此本文提出人工势场法蚁群混合算法，结合人工势场法收敛速度快和蚁群算法全局规划能力较强的优点，通过引入人工势场法先导路径到蚁群算法启发信息中，提高蚁群算法收敛速度，结合多AGV冲突避让策略确定了每台AGV从起点到目标点的最佳路径。

1.2 环境建模

AGV路径规划的首要条件是建立工作环境模型，通过标注环境信息产生AGV能理解的环境地图，使机器人可以在环境地图中模拟实际运输路径。常用的环境建模方法有拓扑图法、可视图法和栅格法等，其中栅格法具有易于实现、原理简单等优点，故本文中采用栅格法建立环境地图，地图中阴影部分代表障碍物，白色栅格为AGV可选栅格，如图1所示。

图1 栅格环境Fig.1 Grid environment

为栅格赋于序号的目的是方便表示路径，而在计算栅格之间距离时需使用坐标计算，两者之间的转换关系为：

其中，（x，y）表示序号为的坐标；表示取余函数；表示横坐标的最大值；表示横坐标的最小值；表示纵坐标的最大值；表示纵坐标的最小值。

本文在序号法下，若路径表示为｛X，，，，…，X，X｝，则表示从序号X为起点，行驶到目标点X路径经过序号为X的栅格，则全局路径长度函数为：

2 人工势场法蚁群融合算法

2.1 人工势场法优化

2.1.1 人工势场法原理

人工势场法是由Khatib提出的一种虚拟力法。该法的基本思想是将机器人在环境中的运动抽象成在人造引力场中的运动，其中目标点对于机器人产生“引力”，障碍物对于机器人产生“斥力”，最后通过合力来引导机器人的移动方向。研究可知，机器人所受引力大小与目标距离成正比，即目标距离越远时、引力越大，目标距离越近时、引力越小，到达目标位置时、引力为0；机器人所受斥力大小与障碍物距离成反比，障碍物距离越远时、斥力越小，障碍物距离越近时、斥力越大。

在二维空间中机器人当前位置为（，），目标位置为X（x，y），障碍物位置为X（x，y），则有合力势场函数为：

其中，U()为目标点对机器人的引力势场函数，具体计算公式为：

式（3）中，U()为机器人与障碍物之间的斥力势场函数，具体计算公式为：

机器人所受到的引力为引力势场函数的负梯度，其值可由如下公式计算得到：

机器人所受到的斥力为斥力势场函数的负梯度，其值可由如下公式计算得到：

当机器人处于障碍物的最大影响距离内时，机器人所受到的合力为：

传统人工势场法相比其他路径规划方法具有计算量小、反应速度较快及实时性较强的优点，但是仍存在一定的局限性，如目标不可达问题。

2.1.2 斥力场优化

传统人工势场法中，机器人在空间中运行时同时受到来自目标点的引力和来自障碍物的斥力作用。当目标点周围存在障碍物时，随着机器人越来越接近目标点，目标点对机器人的引力持续衰减，而周围障碍物对机器人的斥力则越来越大。此时人工势场法路径规划易陷入目标不可达问题。对此改进斥力场函数，引入斥力势场影响因子，针对目标点附近障碍物排斥力进行优化，改进后的斥力势场函数为：

式（10）中，F()为障碍物指向机器人的斥力分量，具体表示为：

式（10）中，F()为机器人指向目标点的引力分量，具体表示为：

2.2 融合蚁群算法优化和人工势场法

2.2.1 蚁群算法原理

蚁群算法（ACO）是一种用于优化路径寻找的概率型算法，最早由Marco Dorigo提出。蚁群算法模拟自然界中蚁群觅食的过程，其基本原理为：蚂蚁在环境中随机行走直至到达目标地点，此路径即为待优化问题的可行解，全部蚂蚁的行走路径即为待优化问题的解空间。其中，较短路径上释放的信息素较多，下次迭代时蚂蚁会倾向于选择信息素浓度更高的路径。随着迭代次数的增加，最终所有的蚂蚁都会在正反馈机制的作用下集中到最短路径上，此时的最短路径即为待优化问题的最优解。

在标准蚁群算法中，蚂蚁下一步所选节点的概率是根据可选路径上的信息素浓度和启发式信息决定。如在时刻，位于节点的蚂蚁选择下一节点的概率为：

其中，为信息素启发因子，τ t()为信息素浓度，当越大时，蚂蚁越倾向于选择信息素浓度高的节点；为启发式因子；η t()为启发式信息强度，η为节点到目标点的欧式距离的倒数，当越大时，蚂蚁越倾向于选择指向目标点的最短路径；表示下一步可选节点的集合。

当蚂蚁在路径上行走时会遗留信息素，同时一部分信息素会随时间挥发，每一次当代蚂蚁完成路径后，按照如下信息素更新公式对全局信息素进行更新：

2.2.2 人工势场法引入启发信息

在基本蚁群算法中，初始环境下蚁群信息素均匀分布，此时影响蚂蚁选择下一节点的主要因素为启发式信息。原始启发式信息的值为节点到目标点的欧式距离的倒数，此时蚁群算法寻路方式类似于贪婪算法，当位于特殊环境、如目标点周围存在较多障碍物时，蚁群算法初始路径容易陷入局部最优解，且由于蚁群算法的正反馈机制，易导致后续搜索局限在初始路径周围。

针对蚁群算法初始路径受启发式信息影响导致缺乏多样性和陷入局部最优解陷阱的问题，将人工势场算法规划的路径距离信息引入到蚁群算法启发信息中。同时为了避免蚁群算法后续迭代中受启发式信息影响导致后续路径缺少多样性，在启发信息中加入迭代次数N，随着迭代次数N的增大自适应减小启发式信息对蚂蚁下一节点选择的影响。改进后的启发式信息函数为：

其中，为最大迭代次数；N为当前迭代次数；d为可选节点到目标点的欧式距离；R为改进后的人工势场法计算出的节点到目标点的距离；为可选节点集合。

2.2.3 信息素更新

基本蚁群算法中信息素更新公式为本次迭代完成的对全局路径进行处理，但是并未对当前最优路径和当前最差路径做出区分，导致信息素浓度分布差异性不明显，同时影响迭代效率。为解决此问题，在信息素更新规则中引进狼群分配策略，即增强最优路径上信息素同时减少最差路径信息素，从而引导蚂蚁向最优路径靠拢，提高算法的收敛速度，改进后的全局信息素更新公式为：

2.3 AGV冲突解决策略

在多AGV路径规划问题中，能否在保证路径无冲突的情况下为每台AGV规划出各自的最优路径是问题的关键。以快消品制造车间为例，当同车间的AGV运输物料基本相同，即AGV速度保持一致的情况下，多AGV运行过程中可能会出现的冲突情况如图2所示。由图2可知，节点冲突表示当2台AGV在同一时间到达相同节点，此后驶向不同方向，2台AGV仅在驶过碰撞节点时发生冲突。相向冲突1、相向冲突2都表示2台AGV在到达相同节点后，对向行驶，此时2台AGV在重合路径上发生冲突。

图2 冲突类型Fig.2 Conflict type

为避免多AGV路径规划时发生上述冲突，根据冲突类型采取不同冲突解决策略，具体规则如下：

（1）停车等待。针对节点冲突情况，采用优先通行策略，即根据任务属性、剩余路径长度等因素为AGV赋予不同优先级。当2台AGV到达同一节点时，优先根据任务属性分配临时优先级，当任务属性无法区分时，分别计算2台AGV剩余路径长度，为剩余路径较短AGV赋予较高的临时优先级并优先通行，另一台临时停靠等待。通过冲突节点后清空临时优先级。

（2）重新寻路-临时避让。针对相向冲突的2种情况，除了重新寻路解决冲突问题外，还要考虑是否可以通过临时避让解决冲突。具体表现为：当AGV间出现相向冲突时，若优先级较低、AGV当前所在节点上存在其他可通行方向，且转向其他方向后等待另一AGV通过时间和原剩余路径长度行驶时间的和小于从当前节点重新规划的路径行驶时间，则优先采用临时避让策略；否则从当前节点重新规划到目标点的路径。重新寻路-临时避让流程如图3所示。

图3 重新寻路-临时避让流程图Fig.3 Repathing-temporary avoidance flow chart

3 算法仿真实验

3.1 路径规划实现流程

改进后的人工势场蚁群算法结合多AGV路径规划冲突解决策略，制定多AGV路径规划流程图，具体如图4所示。

图4 多AGV路径规划流程图Fig.4 Multi-AGV path planning flow chart

3.2 单机器人仿真实验

为了验证改进后的人工势场蚁群算法的可行性，通过Python3.9利用栅格法建立模拟环境，选取传统蚁群算法、文献［11］改进势场蚁群算法和本文改进后的人工势场蚁群算法进行比较。

实验环境及参数为：环境为20×20二维平面，路径栅格和障碍物栅格数量之比为6∶4，障碍物随机分配，最大迭代次数100，蚂蚁数量50，启发式信息影响因子1，信息素挥发系数04，信息素强度10。

传统蚁群算法、文献［11］算法、本文算法路径规划结果如图5所示。图5中，蓝色虚线为传统蚁群算法规划路径，紫色点虚线为文献［11］算法规划路径，红色实线为本文算法规划路径。

图5 传统蚁群算法、文献［11］算法、本文算法路径Fig.5 The path of traditional ant colony algorithm，the path of reference［11］algorithm and the algorithm path of this paper

传统蚁群算法、文献［11］算法、本文算法收敛结果对比如图6所示。由图6可以看出，在20×20随机栅格环境下，本文算法生成的最优路径相比于传统算法和文献［11］改进算法在路径长度、转弯次数上均有较好的表现。由图6还可以看出本文算法相比于其他2种算法的收敛速度更快。在20×20环境下3种算法仿真对比结果见表1。由表1可知，本文相比于传统算法最优路径长度减少14%，收敛于最优路径迭代次数减少51%，算法耗费时间减少25%，转弯次数减少45%。相比于文献［11］，最优路径长度减少8%，收敛于最优路径迭代次数减少19%，算法耗费时间减少12%，转弯次数减少33%，这是因为文献［11］未解决原始人工势场法易陷入目标不可达问题，导致机器人在障碍物较多环境中无法快速规划出合理路线。综上所述可知，本文算法相较于传统蚁群算法和文献［11］改进算法，均有较好的表现。

表1 20×20环境下3种算法仿真结果对比Tab.1 Comparison of simulation results of 3 algorithms under 20×20 environment

图6 传统蚁群算法、文献［11］算法、本文算法收敛比较Fig.6 Convergence comparison of traditional ant colony algorithm，reference［11］algorithm and the algorithm in this paper

3.3 多机器人仿真实验

为验证本文算法在实际仓储环境下能否实现多AGV路径冲突问题，通过Python3.9构建仓储布局栅格地图，其中为每台AGV设定行走占地范围，当2台AGV存在占地范围重叠时，即认为路径出现冲突。其中，未采用重新寻路-临时避让策略的多AGV行走路径规划如图7所示。

图7 多AGV路径冲突Fig.7 Multi-AGV path conflict

由图7可知，当系统未采用重新寻路-临时避让策略时，所有AGV选择各自最优路径执行运输任务，其中系统运行至第9步时，和在栅格出现节点冲突；和在栅格出现相向冲突。此时，系统的全局最优路径长度为117.799 m，运行时间为27.242 6 s。

图8 多AGV路径冲突解决Fig.8 Multi-AGV path conflict resolution

采用本文冲突解决策略后，系统全局最优路径长度为119.627 4 m，系统运行时间为28.071 1 s，相较于原始最优路径长度和运行时间仅分别增加1.5%和3%。通过不同仿真环境下的实验可知，本文提出的人工势场蚁群融合算法在不同环境下都可快速找到最优路径，实时规避动态障碍物，规划出全局最优路径，证明了本文提出的人工势场蚁群融合算法的可行性和有效性。

4 结束语

在快消品制造行业快速发展的背景下，针对智能仓储环境下多AGV路径优化的问题，本文通过对人工势场法斥力场函数、蚁群算法启发式、信息素更新算法及多AGV冲突解决策略等方面提出相应优化策略，提出人工势场蚁群融合算法，在以仓储车间的仿真环境下通过单AGV路径规划实验和多AGV路径冲突实验进行分析，验证了本文算法能够在优化路径长度、提高收敛速度的基础上完成多AGV路径冲突的解决。本文算法已经应用于某大型快消品制造企业在漯河某地的无人化制造车间的仓储物流设计中，不久将投入实际生产活动中。