自动导引车 (AGV) 是一种可以满足分拣操作要求的自动化智慧仓储设备, 将“人到货”分拣模式转变为“货到人”分拣模式[1]。路径规划问题是多AGV任务分配的核心和热点问题。目前, 国内外对动静态路径规划问题的研究很多。文献[2]总结并归纳了移动机器人的局部和全局路径规划方法。文献[3]研究了多AGV系统中的两阶段动态路径规划和调度问题。文献[4]对单一AGV和多AGV的路径优化问题进行了进一步的研究。文献[5]研究了不同调度规则下AGV系统的车辆行驶模型。文献[6]对动态路径自治分散式AGV系统的局部重新调度程序进行了实验研究。文献[7]研究了有AGV系统的调度和无碰撞路径问题的局部搜索和随机搜索。文献[8]提出了一种蚁群算法用于求解AGV作业的车间调度和无冲突路径集成模型。虽然关于搜索最短路径的问题有很多研究成果, 但从减少交通拥堵的角度来出发, 且这些研究并没有解决路径规划问题。

本文基于多个AGV的动态分拣操作模式, 采用网格方法描述智慧仓储环境。通过添加AGV彼此共享路径的惩罚值来改善A*算法的估计开销以减轻交通拥堵。然后结合改进的A*算法和无碰撞规划来完成无碰撞的路径规划。最后, 通过仿真实验将改进的A*算法的分类效率与其它算法的分类效率进行了比较。

环境建模是无碰撞路径规划的基础。本文利用网格方法[9]建立了AGV工作的智慧仓储空间环境模型。网格方法具有良好的可视性和简单的模型构建特点, 因此该方法的应用较为成熟。网格的大小和数量取决于AGV的大小和工作空间。网格在直角坐标系中进行定义, 网格的属性包括以下维度: (1) 每个网格的位置坐标信息 (xi, yi) 可以反馈给计算机; (2) 从左到右连续设置的每个网格的序列号可以代表AGV的驱动路径; (3) 网格类型包括货架网格, 分类架网格, 补给平台网格, 暂停区域网格, 充电桩网格和其它自由网格。

在智慧仓储环境模型中, 本文所设计的AGV工作过程如下:首先, AGV接收任务从指定的货架区域将货架运送到指定的分拣区域, 并且货架等待分拣。然后, 将已经分拣的货架运送到原始位置, 并且AGV被分配另一个任务。如果没有其它任务, AGV将返回暂停区域。并且AGV可以在4个方向行驶:正东、正西、正南和正北。

在本文中, 货架放置在所建立的智慧仓储网格节点的上方。如图1所示, 底层和地面之间的距离为75cm, AGV的高度为50cm。如果AGV需要运送货物, 则AGV上的托盘将提升, 由于货架底部的高度大于AGV的高度, 因此, AGV空载时可以穿过货架下方, 而AGV装载后则不能穿过货架下方。

A*算法可以有效的实时计算最短路径, 并在实际工程中得到广泛应用。在计算当前点与目标点之间距离时, 该算法考虑了包括实际代价和估计代价在内的两个因素[10]。实际代价是指AGV已采用的路径成本, 而估计代价是指AGV将采用的路径成本。一般代价估计函数表示如下:

图1 货架与AGV   下载原图

其中, g (n) 表示根据实际驾驶条件计算的实际代价 (从起点到当前点n) , h (n) 表示包括启发式信息的估计代价 (从当前点n到目标点) 。估计代价主要用于寻找搜索方向, 这对最终的搜索结果和效率有很大影响[11]。估计代价越接近实际代价, 收敛速度就越快。当估计代价小于实际代价时, 收敛速度将减慢, 但可以获得最优解。相反, 收敛速度将加快但可能无法获得最优解。因此, 估计代价是A*算法研究的重点和难点。

AGV在智慧仓储环境中的移动方向是正东, 正西, 正南和正北。因此, 在研究分拣路线时, 通常使用Manhattan距离[12]来计算估计代价h (n) 。根据当前点 (xn, yn) 和目标点 (xend, yend) 的估计代价函数如下:

如果将Manhattan距离用作估计代价, 则路径规划将限制在静态而非动态环境中的单个AGV, 并且将导致交通堵塞。为了缓解交通堵塞并提高计算效率, 本文在交叉路口再次规划AGV的路径并检测所有可行路径, 其中增加了AGV彼此共享路径的惩罚值。该惩罚值取决于与AGV的距离并且与距离成反比。最终, 估计代价函数选择为:

其中, a是距离目标点为1～4个网格且权重为α的AGV的数量, b是距离目标点为4～8个网格且权重为β的AGV的数量, 其它AGV的数量为c且权重为γ。本文规定α>β>γ, 这意味着距离越近, 惩罚值越大。通过提高估计代价实现动态路径规划并缓解交通拥堵, 最终代价估计函数如下:

当使用A*算法动态规划各AGV的路径时, 多AGV在实际操作中同时工作时不可避免的会发生碰撞, 本文给出了智慧仓储环境下的两种碰撞类型。

由追赶引起的碰撞如图2所示。为了解决这种碰撞, 本文不考虑AGV的优先级, 规定后面的AGV应该停止并等待前面的AGV通过, 然后再继续移动。

图2 追赶引起的碰撞   下载原图

交叉点中存在4种类型的碰撞如图3所示。为了解决交叉点中的这些碰撞, 本文规定优先级较低的AGV应该停止等待直到具有较高优先级的AGV通过, 然后再继续移动。

图3 交叉口的碰撞   下载原图

基于上述分析, 本文提出了基于改进A*算法和碰撞解决规则的多AGV无碰撞路径规划方法, 具体步骤如下:

步骤1:定义两个名为OPEN和CLOSE的表。OPEN表示将被明确搜索但不能确保它们在最短路径上的节点集。CLOSE表示已经搜索过的节点集, 在这些节点中可以找到从起始点到目标点的最短路径。

步骤2:选择节点Vs和Vend分别为起点和目标点, Vi表示其它点。然后将Vs放在表OPEN中, 并将表CLOSE初始化为空。

步骤3:选择使函数f (n) 最小的节点n, 然后将其添加到表CLOSE中。然后, 如果该点是目标点, 则结束搜索并获得最优解, 否则进行步骤4。如果表OPEN为空, 则表示无法找到路径并且结束算法。

步骤4:扩展搜索与Vj (j≠i) 相邻且没有障碍物的网格Vi并计算Vi的值, 然后重复步骤3。

如果AGV之间存在碰撞, 则由本文所提的碰撞解决规则处理。利用该方法可以重新规划AGVs的路径。因此, 在寻找无碰撞路径的前提下, 利用缓解交通拥挤的思想, 可以获得最大的效益。

在模拟实验中, 智慧仓储的长×宽为800m×400m, 划分为4m×4m网格。AGV的数量为80, 其大小为0.8m×0.8m。AGV速度为2m/s, 选择参数α、β和γ时, 应保证α>β>γ, 即距离越近, 惩罚值越大。本文将参数α、β和γ分别设为0.6、0.3和0.1。

本文利用C软件平台开发了多AGV分拣系统的仿真软件, 如图4所示。左边是菜单栏, 可以监视AGV的运动状态, 并调整AGV的速度和加速度。右方是通过网格方法建模的工作区域, 可以模拟真实的分拣环境。分拣效率指标显示在右上角。AGV的应用环境和所需的任务数量可以根据系统的需要自动设置。

图4 多AGV分拣系统仿真平台   下载原图

由于AGV均保持2m/s的速度运行, 所提出的碰撞解决方案中, 规定后面的AGV应该停止并等待前面的AGV通过, 然后再继续移动。因此避免了追赶引发的碰撞。在此只考虑交叉口的防碰撞。

在该平台只考虑交叉口的防碰撞分析, 对于两个AGV在既定的路径上运行时, 采用改进A*算法的多AGV防碰撞路径规划与文献[13]的蚁群算法防碰撞路径规划进行了比较, 如表1所示。

表1 蚁群算法与本文的改进A*算法的防碰撞时间对比     下载原表

由表1的交叉口防碰撞效率对比结果可以发现, 两种方法的模拟时间和停止等待时间均随交叉口防碰撞次数的增加而增加, 但基于改进的A*算法在时间上均随着防碰撞次数的增加呈现出较为线性的增长, 且模拟时间比蚁群算法快。而蚁群算法在模拟时间上呈现指数型增长, 这是由于改进A*算法的最终代价估计函数仅与距离目标点的AGV数量相关, 而蚁群算法的迭代次数与交叉口防碰撞次数相关, 且每次迭代均需从AGV的初始点重新进行计算, 加大了计算复杂度进而增加了模拟时间。同时, 本文方法在停止等待时间上略低于蚁群算法, 这是由于改进A*算法是以网格中的节点作为AGV的停止点, 而文献[13]的蚁群算法是以网格的边作为AGV的停止边, 所以在交叉口的防碰撞实验时, 本文中的AGV停止点距离交叉口更小, 再次启动运行时的等待时间更短。因此, 基于改进的A*算法可以有效缓解交通堵塞。

在该平台上, 对基于改进A*算法的多AGV路径规划分拣效率与传统A*算法进行了比较, 如表2所示。其中, ASP/s代表每秒平均分拣件。

表2 传统A*算法与改进A*算法之间的分拣效率对比     下载原表

由表2的分拣效率对比结果可以发现, 两种方法的分拣速度均随时间的推移而减小, 但基于改进的A*算法可以对更多的货物进行分拣, 且分拣速度比传统的A*算法快。这是因为在改进的算法中考虑了交通拥堵和防止碰撞。因此, 基于改进的A*算法不仅能满足分拣系统对稳定性的要求, 而且还可以提高分拣效率。

本文在采用网格方法构建的智慧仓储环境的基础上, 利用改进的A*算法和碰撞解决规则, 从缓解交通拥堵和避免碰撞的角度对AGV的路径进行了规划。仿真结果表明, 该方法可以提高多AGV的分拣效率, 缓解交通拥堵。在未来的研究中, 将根据不同的场景研究更有效的算法。