摘要
多自动导引车 (automated guided vehicle, AGV) 系统进行搬运作业时容易发生冲突、碰撞和死锁。为此，引入多值栅格和交通规则改进A*算法解决货架下方可通行场景下多AGV系统的轨迹规划问题。为提升系统搬运效率，通过增加货架召回机制、转弯代价和热度代价对规划路径进行优化，并采用二叉堆数据结构提高路径规划速度。利用Python搭建了可视化的四方向栅格无人仓模型，对改进A*算法和轨迹优化策略进行仿真验证。仿真结果表明，改进A*算法具有求解速度快、防死锁能力强的优点，可以快速完成该场论文拓展景下的多AGV系统的路径规划。
Abstract
The multiple AGV (automated guided vehicle) system is prone to conflict, collision and deadlock in the process of carrying. Therefore, the A* algorithm was improved by introducing multi-valued grid and traffic rules to solve the path planning problem for the multiple AGV system in scenarios where there was passable space beneath shelves. To improve handling efficiency of the multiple AGV system, the planned path was optimized by adding shelf recall mechanism, turning cost and heat cost. A binary heap data structure was also used to improve calculation speed of the path planning. The simulation results show that the improved A* algorithm has the advantages of fast solution and strong deadlock resistance, and can quickly complete the path planning of multi-AGV system in this scenario.
Keywords
传统物流仓库模式下，工作人员需要根据订单信息找到货物进行搬运，劳动力成本高且工作效率低。利用自动导引车（automated guided vehicle，AGV）自动取货实现“货到人”的模式可以提高订单处理效率、降低人力成本。目前大多数企业的智慧仓库通过通道堆垛机、穿梭车或基于移动式货架的AGV运输货物。本文构建的无人仓模型采用顶升式AGV作为搬运工具，装载货架时AGV移动到货架正下方，利用液压装置将整个货架托起，将其运送到站台进行拣选，拣选完成后再由AGV将货架运回原处并放下。该模式下无须在货架底部安装车轮，也无须机械臂将货物转移到AGV上，即可实现货物的搬运，适用范围广且成本低。
路径规划的研究当中，比较常用的有A*算法[1-5]、蚁群算法[6-7]、遗传算法[8-10]、强化学习[11-13]和快速扩展随机树[14-15]等。文献[16]提出的改进遗传算法适用于求解多自由度移动机器人在障碍物分布复杂场景下的最短路径。文献[17]提出的改进蚁群算法改善了多AGV系统路径规划收敛速度慢、容易陷入局部最优的缺点。文献[18]提出的改进深度强化学习算法通过引入先验规则和先验知识提高收敛速度，对移动和碰撞行为做出惩罚并训练出最优无碰撞路径。上述方法适用于障碍物分布复杂场景下对多自由度的少量AGV进行路径规划，当AGV数量增多时容易陷入局部最优解，训练速度慢。无人仓场景下货架分布规则，且有多台AGV同时进行搬运工作，上述方法的实用性不强。目前大多数无人仓路径规划的研究中，没有考虑到AGV空载时可以在货架下方通行的情况，而空载AGV在货架下方的通行可以极大地减少路径成本。针对顶升式AGV的无人仓协同路径规划提出了一种改进的A*算法，将货架下方区域纳入空载AGV的路径规划范围，具有计算量低、简单高效和仓库利用率高的优势，尤其是对多AGV系统中的冲突问题具有良好的处理能力。
A*算法作为一种经典且简单的启发式算法，是求解最短路径最有效的直接搜索方法，在栅格地图中容易应用且效果显著。文献[19]使用交通规则和预约表改进A*算法可以很好地解决多AGV的路径冲突问题，但交通规则下AGV可通行方向减少会使得最短路径加长。此方法适用于大量AGV协同运作下交通拥堵、绕路成本小于避障成本的情况，且简单的交通规则不能解决因货架下方通行产生的冲突和死锁问题。文献[20]引入时间窗改进的A*算法可以由其他AGV未来时间路径来判断可能发生的冲突并提前做出处理，可以不受交通规则的限制规划出无冲突路径，但该方法在AGV数量多且交通拥挤时计算量大，难以找到适用于过道狭窄仓库模型的多AGV系统路径规划方案。
为了解决在仓库中投入多台AGV时AGV之间存在的死锁和冲突问题，本文对AGV的任务类型进行分类，将栅格多值化存储位置和状态信息，基于多值化的栅格和交通规则约束，利用改进过的A*算法求解空载和负载AGV的全局路径，并用转弯代价和热度代价对路径进行优化。
1 算法设计
图1是智能仓库模型的简化示意图。AGV用蓝色的长方形表示，车身宽度略小于货架，实际物理模型为双轮差速小车，可进行原地转向和倒退，无法进行左右平移。车身高度小于货架底层离地高度，空载时可在货架下方通行。充电桩所在栅格用黄色表示，位于仓库两侧靠墙处，当AGV电量小于阈值时自动寻找空闲充电桩充电，充电时间由耗电量决定，耗电量简化为AGV的运行时间[21]。工作员用圆形表示，空闲时为绿色，拣选商品时切换为红色。站台包括等候区和工作区，工作人员面前的一个栅格区域为工作区，工作人员在处理货架商品时其余货架在等候区等待。货架区由货架及过道组成，为提高仓库的储货能力，过道宽度仅略大于一个货架的宽度，不能容纳两辆AGV并排行驶。送货架时AGV路径规划的终点不是工作区而是站台入口，之后按照固定路线排队前往工作区。文中用到的符号详见表1。
图1智能仓库模型
Fig.1Intelligent warehouse model
路径规划问题基于如下规定和假设：
1）AGV匀速行驶，单位栅格的通行时间和转弯时间恒定。
2）AGV只能在无障碍区域行驶，空载时可在货架下方行驶。
3）不考虑AGV在运行时出现故障以及意外障碍物的情况。
4）AGV完成订单后，若无下一个订单，则停在最后归还的货架下方。
5）货架搬离原地后带货架AGV仍不能从此处通过，以减少相向冲突。
6）任一时刻同一栅格上最多只能有一台AGV。
1.1 栅格地图构建
栅格地图中环境被分成一系列栅格，每一栅格的取值表示该栅格被占据的概率，取值介于0和1之间。无人仓环境下障碍物规则分布，适合构造栅格地图进行路径规划。为了对AGV在不同区域、不同任务下的路径规划做出详细的规定，表2给出了栅格值的含义。
表1符号含义
Tab.1 Meaning of symbol
表2栅格值含义
Tab.2 Meaning of grid value
栅格值取1和4、5和6的区分是为了保留栅格是否位于货架下的位置信息，避免带货架AGV在规划路径中通过货架下方。栅格值取2、7、8是为了强调站台的位置信息，禁止规划出的路径穿过站台。当AGV在一个栅格上停留时间超过停滞判定时间后判定为停滞，停滞的原因可以分为以下五类:
1）AGV间产生相向冲突;
2）交通拥堵，AGV等待时间过长;
3）AGV在货架下方进行取货或卸货工作;
4）没有接到新任务，AGV停留在货架下方;
5）AGV在充电桩处充电。
每个栅格的位置由坐标（x，y）表示，坐标系原点位于地图左上方，向右为X轴正方向，向下为Y轴正方向。
1.2 改进交通规则
交通规则的优势是通过限制每条通路的方向来解决最难处理的相向冲突问题。将交通规则扩展到栅格地图的货架区域后，得到每一行的交通规则Ryr和每一列的交通规则Rxc，可以解决AGV 在货架下方穿行的冲突问题，但会导致AGV 取完货架后无法离开的情况，如图2所示。
图2路径死锁1
Fig.2Path deadlock 1
图2中AGV的可通行方向只有向左和向上，而取到货架的AGV 无法穿过这两个方向上的货架，从而导致无法求得路径。
本文对交通规则进行更加详细的约束，按AGV运行的任务类型M不同分为取货架、送货架、还货架和充电，编码分别为M1，M2，M3和M4。取货架和充电为空载状态，在整个栅格地图上进行交通规则约束。送货架和还货架时只在过道进行交通规则约束，保证相邻的两条过道通行方向相反即可。由于货架区内的过道不允许两辆AGV并排行驶，在货架区的过道垂直方向上不对带货架AGV施加方向限制。然而这种约束下带货架AGV与空载AGV在货架处出现例如图3所示的相向冲突问题。
图3中带货架AGV 需要将货架送回到空载AGV所处栅格，而空载AGV向右行驶，产生相向冲突的双方必定存在空载AGV。考虑到空载AGV通行区域更广，规定产生相向冲突后由空载AGV重新进行路径规划避让带货架AGV。
图3路径死锁2
Fig.3Path deadlock 2
当AGV前往充电或充完电后取货架时，由于充电桩靠近墙壁，可通行方向减少会导致死锁问题，如图4所示，AGV 通行方向为向左和向下，而下边有AGV充电无法通行，左边是墙壁无法通行，无法重新规划路径。
图4路径死锁3
Fig.4Path deadlock 3
规定充电桩所在列的通行方向统一为驶离充电桩的方向，充电时在充电桩外的一列水平通行方向统一为驶向充电桩的方向。将方向用数字进行编码，上、左、下、右分别为1，2，3，4。确定的交通规则见表3。由AGV的类型和栅格的位置（x，y）可以确定通行方向。
表3交通规则表
Tab.3 Table of traffic rules
当订单信息较少时大部分AGV处于空闲状态，可能会出现路径死锁，如图5所示，空载AGV需要取到右边的货架，其可通行方向为向上和向左，而这两个方向上都有AGV 停滞，若多次规划路径失败后可以解除方向限制进行路径规划。
图5路径死锁4
Fig.5Path locked 4
新规划出来的路径与原路径对比如图6所示，虚线为交通规则下的最优路径，实线为无交通规则下的最优路径。在交通不拥堵的情况下可以通过解除空载AGV的方向限制以提高效率，遇到新的相向冲突则重新进行施加交通规则的路径规划。
1.3 基于交通规则的改进A*算法
A*算法是一种经典的启发式搜索算法，通过启发函数的引导，从起点向终点方向搜索直到找到终点，扩展方向一般分为四方向和八方向。由于考虑了空载AGV在货架下方穿行的情况，沿对角方向行驶会撞到货架腿，所以规定小车只能朝东南西北四个方向行驶。在路径规划时根据当前时刻的栅格地图和交通规则，在不考虑其他AGV位置的情况下为每台AGV规划出一条无碰撞最短全局路径。在实际跟踪该路径时，再由每个栅格的实际取值决定前进、停车或者重新规划路径。由两个列表open list和close list存储搜索过的节点，每个节点的估算代价为:
图6路径比较
Fig.6Path comparison
(1)
H使用不考虑障碍物的曼哈顿距离计算，计算公式为:
(2)
式中：xE，yE表示终点坐标；xC，yC表示当前节点横纵坐标。改进A*算法的运行步骤如下:
步骤1：清空open list和close list，将起点加入open list 中。
步骤2：选择open list中F值最小的节点作为当前节点C，将当前节点从open list中删除，加入close list 中。
步骤3：搜索与当前节点相邻的节点，要求扩展节点N不在close list中。由于空载AGV的通行区域广，绕路成本低，要求其路径规划结果能够解决相向冲突并且能绕开货架下方停留的AGV，扩展节点除了要满足交通规则，还不能是阻塞节点，在路径规划阶段不将移动AGV视为障碍物。若为空载小车i进行路径规划，节点可以作为扩展节点的要求为:
(3)
其中，D（x，y）表示小车i在坐标位置为（x，y）的栅格处的交通规则约束，VN表示扩展节点的栅格值，Nx、Ny表示扩展节点的横纵坐标。
若为带货架小车j进行路径规划，将货架所在栅格视为静态障碍物绕开，节点可以作为扩展节点的要求为:
(4)
由于带货架AGV可通行区域小、绕路成本高，在路径规划时假定当小车j到达阻塞节点时阻塞已经被解决，路径规划时不将阻塞节点视为障碍物。计算扩展节点的F，G和H，扩展节点的父节点为当前节点。
步骤4：若扩展节点已经存在于open list中，检验通过当前节点到达扩展节点是否更优，如果G更小则将该节点的父节点改为当前节点，更新F和G。若扩展节点不存在于open list中，则将扩展节点加入open list。
步骤5：不断重复步骤2~4，直到终点E出现在open list中，再通过节点的父节点由终点向前找到起点，得到一条从起点到终点的最短路径。
2 算法优化
通过交通规则的设计可以解决大部分的相向冲突，对于交叉冲突和追尾冲突可以采用栅格值判断的方法解决。当AGV 移动时将AGV车身所处的两个栅格根据其所处位置赋值为VC，VC∈{1，4，8}，赋值后其他AGV无法通过该栅格，从而保证AGV之间的安全距离。AGV移动一个栅格后判断路径中下一个节点n的栅格值Vn是否满足Vn∈{0，3，7}，若满足则继续行驶，不满足则等待让行或者重新规划路径。若AGV在站台外的某一栅格处等待让行时间超过预设时间，则将其车身所处的栅格判定为停滞，此时栅格值VC∈{5，6}。当AGV离开后将栅格值恢复，允许其他AGV经过此处。
使用A*算法寻找F值最小的节点时需要判断每一个节点的大小，open list中节点数量过多会影响程序运行速度，将open list 由无序表改为二叉堆结构的半有序表可以大大加快这一进程。二叉堆中父节点的F值小于等于其两个子节点的F值，根节点为F值最小的节点。路径规划时可以直接选择根节点作为当前节点，将根节点与堆的最后一个节点互换位置并将最后一个节点删除，然后从堆顶开始从上往下维护堆，如果节点的F值比子节点大则将该节点与子节点交换。将备选节点加入open list时直接插入堆的末尾并往根节点进行更新，如果插入节点的F值比父节点还小则将该节点与其父节点交换，直到父节点F值小于新插入的元素或到达根节点。
考虑到转弯时具有转弯时间，在G值的计算过程引入转弯代价来减少AGV的转弯次数。引入转弯代价前后的路线如图7和图8所示。
图7无转弯代价路线图
Fig.7Road map of no turning cost
图8引入转弯代价路线图
Fig.8Road map for introducing turning cost
红色和橙色路线分别代表两辆AGV的路线，实线部分是取货架的路线，虚线部分是送货架的路线。无转弯代价下取货架路线的总长度为26 m，转弯次数为8; 引入转弯代价后取货架路线总长度为26 m，转弯次数为3。两种情况下送货架路线基本一致。空载AGV通行区域广，可以在保证路径总长度不变的情况下大幅降低转弯次数，而带货架AGV的路线灵活度低，难以通过转弯代价进行优化。
站台接收到订单后按照订单信息寻找距离最近的可搬运货架，将正在送回原地的货架也认定为可搬运货架，且调用此种货架可以直接免去将其继续送回原处的代价，提高整个系统的工作效率。未被搬运的货架与站台的距离采用曼哈顿距离计算，正在送回的货架与站台的距离计算公式为:
(5)
通过执行历史订单的情况计算出每个栅格点上AGV的通行数量和停滞次数，可以近似求出该模型下的交通热度图，每个栅格热度值的计算公式为:
(6)
式中，Qpass和Qload用于表示可能发生的冲突，Qwait 和Qblock用于表示已经发生的冲突。将热度值变换为0~1的热度代价Tvalue，将每个栅格上的Tvalue引入A*算法的G 值的计算中，可以让AGV以增加路径长度为代价避开容易发生冲突的位置。
基于交通规则的改进A*算法的全局路径规划解决了同类型AGV的相向冲突问题，不同类型AGV相向冲突导致的阻塞问题由空载AGV路径重规划解决，重新规划出的路径可以有效避开当前发生阻塞的节点，有利于缓解交通压力。跟踪全局路径时基于前方栅格的栅格值判断是否有AGV存在，并将车身所处栅格进行赋值，从而解决AGV之间的交叉冲突和追尾冲突。因此本文所提出的方法可以解决多AGV系统的冲突和死锁问题，并且具有计算量小和结构简单的优势。路径规划的伪代码在算法1中给出。
在算法1中，GN、HN和FN分别表示扩展节点的G、H和F值，GC表示当前节点的G值，Nparent 和Cparent分别表示扩展节点的父节点和当前节点的父节点。AGV寻路行驶的伪代码如算法2所示。
本文主要研究了多AGV路径规划问题，并简化了无人仓系统的其他问题[22-23]。①简化了仓库最优布局问题：本文参照某企业建立的栅格地图模型具有一定的科学性和研究价值，将所有站台放置于仓库下方，按照货物所在货架在订单中出现的热度来决定其与站台的距离，所有充电桩分布在仓库左右两侧。② 简化了调度问题，在后台按照预先设定的货物拣选热度随机生成订单后依次分配给站台，由站台根据订单选择距离最近的可用货架，再由货架的位置将任务分配给距离最近的空闲AGV，这里的距离简化为无视障碍物的曼哈顿距离[23-27]。通过优化调度程序可以使AGV的订单分配更加智能，总体效率进一步提高，AGV在得到具体订单后的路径规划方法是一致的。AGV接到订单后进行路径规划，依次完成取货架、送货架和还货架的过程。
算法1 路径规划
Alg.1 Path planning
算法2 路径跟踪
Alg.2 Path tracing
3 实验结果
用python软件搭建出了一个100 m×50 m的仓库栅格地图，并用Tkinter画布进行可视化仿真，仿真界面如图9所示。
图9仿真界面
Fig.9Simulation interface
将货物由拣选热度分为六类，热度由高到低分别用红、橙、黄、绿、蓝、黑六种颜色表示，每种颜色的三种货物以十个货架为单位穿插排放; 仓库最上方空白处作为AGV的主要初始存放处，其余设置与图1相同。仿真所用的参数见表4。
表4仓库模型参数
Tab.4 Warehouse map parameters
在订单完全一致的前提下，增加热度代价前后的实验结果分别如图10和图11所示。图10和图11中颜色越亮的区域热度越大，交通拥堵程度越高。引入热度损失鼓励空载AGV从货架下方穿行并避开装卸货架频繁的区域，缓解货架区过道的交通压力，使AGV的路线分布更加均匀，充分利用仓库空间。
实验数据见表5，加入热度代价后经常发生相向冲突的地区通行代价最大，绕过该地区可以大幅度减少路径重新规划的次数。有热度代价与无热度代价相比会在增加转弯次数的前提下减小路径总长度。交叉冲突在每一行和每一列都有可能发生，绕路行驶不会产生太大作用。完成订单时间表明本文引入的热度损失可以小幅度缩短订单完成时间，大幅度减少相向冲突次数并使AGV路线分布更广。
图10无热度代价热度图
Fig.10No heat cost heat map
图11加入热度代价热度图
Fig.11Heat map with added heat cost
表5加入热度代价前后数据
Tab.5 Data before and after adding heat cost
表6给出了一些优化项对于完成订单时间和AGV运行总距离的影响，所有数据均是多次实验的平均值。由表6可以看出，召回机制可以减小AGV的运行总距离从而缩短完成订单时间，增加转向损失可以增大单位时间内AGV运行总距离从而加快订单完成，使用二叉堆结构可以加快路径规划速度从而缩短订单完成时间。
表6优化项选择及实验数据
Tab.6 Selection of optimization items and experimental data
4 结论
以贴近实际场景的智能仓库模型作为研究对象，针对多AGV系统的冲突、碰撞和死锁问题，提出通过引入多值栅格和交通规则改进的A*算法，解决了货架下方可通行的无人仓中多AGV系统的轨迹规划问题。通过增加转弯代价、热度代价、二叉堆和货架召回机制对算法进行优化，有效减小了AGV运行总距离、缩短了订单完成时间。仿真结果表明，所提方法对路径冲突的处理能力强，求解速度快，不易陷入死锁，能够实现该场景下多AGV系统的流畅运行。
