基于时空A*算法的多AGV无冲突路径规划

1 引言

快递业务量自 2010 年的不足 24 亿件, 迅速攀升到 2020 年的 833.6 亿件. 剧增的快递业务量对配送效率提出了更高的要求, 使得各大快递企业不断导入新的技术和手段. 为了实现高效快捷的包裹配送, 超过60% 的物流配送中心装备了分拣系统[1]. 采用自动导引车 (automated guided vehicle, AGV) 分拣的系统具有高度无人化、自动化、智能化等优势, 但多 AGV 分拣作为高度复杂的集成系统, 需要合理的集群调度方案和路径优化策略方能保证所有 AGV 得到高效利用, 并在尽可能短的时间内完成包裹的分拣. 多个 AGV 在分拣中心同时作业时, 需为每个 AGV 合理规划路径, 避免AGV 间发生冲突、死锁等情况, 保持整个分拣系统的正常运行.

多 AGV 路径规划旨在为每个 AGV 规划一条合适的路线, 以便在 AGV 运行空间内将物品从起点移动到目的地. 研究多 AGV 路径规划问题对于快递包裹分拣效率的提升具有积极的理论和应用意义. 业界对于多 AGV 路径规划的需求包括以下 3 个方面: (1) 随着包裹数量和土地成本的急剧升高, 仓储对于密集的多AGV 转运系统需求日益增强, 因而对于在此环境下保持多 AGV 系统高效运行的技术理论存在迫切需求;(2) 随着消费产业愈发成熟, 商品种类迅速增多, AGV面临的任务特点和任务要求也越发复杂. 除搬运到指定位置外, 还面临平稳、快速、大体积、超重搬运等多种搬运需求, 使得多 AGV 路径规划也面临新的挑战; (3) 随着 5G 高速通信和轻量化深度学习技术的出现, AGV 系统的搭建存在更多新的技术选择, 以远程检测和视觉导航为代表的新兴 AGV 技术使得多 AGV路径规划面临新的约束和场景. 本文聚焦多 AGV 路径规划在无碰撞要求下的算法改进, 瞄准上述所提的需求 (1).

针对多 AGV 路径规划, 其制定的线路须确保各台 AGV 不会发生碰撞和死锁等, 且需要实现最短行驶时间、最短距离长度或最少能量消耗等目标. 选择合适的路线对系统的性能有一定的影响, AGV 分拣单件包裹的时间越长, 在给定时间周期内可以处理的分拣任务就越少. 因此, 国内外学者对多 AGV 路径规划问题进行了大量的研究, 主要的解决方法有精确算法、启发式算法、人工智能和仿真模拟等[2]. 在精确算法方面, Langevin 等[3] 采用动态规划实现对两台 AGV 调度与无冲突路径规划相结合的优化问题求解. Desaulniers等[4] 提出了结合贪婪搜索、列生成和分支切割的精确算法, 可以解决最多 4 台 AGV 的情况. 但该算法存在一定的局限性, 其效率高度依赖于启发式算法的性能,如果搜索启发式方法不能找到可行解, 则不能找到最优解. 与精确算法相比, 启发式方法的优势在于求解速度快, 适合解决大规模问题. 对于 AGV 路径规划, A算法成为多数研究的首选方法, 譬如改进 A算法[5–7]、变步长双向 A算法[8]、时空冲突约束 A算法[9], 并且在诸多场景中得到了应用, 包括智能泊车[10]、自动驾驶[11] 等. 关于 A*算法的更多应用已由 Foead 等进行了总结[12]. 除此之外, 遗传算法[13]、人工蜂群算法[14]、迭代贪婪算法[15]、蚁群算法[16] 等元启发式算法也相继被用于解决 AGV 路径规划. 随着人工智能技术的日益成熟, 部分学者也将人工智能算法用于解决多 AGV 路径规划问题, 并取得了一定的效果[17]. Srivastava 等[18] 提出了基于智能体的框架来克服冲突和死锁等问题, 该框架通过整合路径生成、旅程时间计算、碰撞识别和死锁识别等不同活动来控制 AGV 的运行. 刘辉等[19]提出了多智能体独立强化学习算法, 用于同时优化多AGV 的任务调度和路径规划. 仿真模拟法可以更加直观地反应每个 AGV 的作业情况, Ashayeri 等[20] 介绍了交互式微型计算机自动物料搬运系统的 GPSS 仿真程序生成器. Um 等[21] 提出了基于多 AGV 的柔性制造系统仿真设计与分析方法. Kim 等[22] 提出了面向对象的仿真建模环境-AgvTalk, 为 AGV 系统的仿真提供灵活的建模能力.

现有多 AGV 路径规划研究大多是针对二维平面环境, 尽管存在时间窗模型等考虑时效约束的研究, 但是少有研究系统地从时空维度动态地解决路径规划问题. 即将基于时间的搜索与基于空间的搜索结合起来, 以实现算法计算时间开支最小与路径规划空间距离最短的均衡.

从这一角度出发, 本文首先根据物流分拣中心的场地特点选择合适的地图建模方法, 然后将时间维度导入 A算法, 将其改进为时空 A算法, 并将时空A*算法作为基于冲突搜索框架的下层规划器, 用于求解多 AGV 无冲突路径规划问题. 对上述两种算法的融合, 旨在优势互补为解决路径规划中的冲突问题提供新的求解思路. 最后, 通过仿真实验验证所提算法在不同冲突情况下的求解效果.

2 地图选择与单AGV路径规划

2.1 地图选择

生成 AGV 无冲突路径方案首先需要构建地图模型. 只有在 AGV 工作环境已知的情况下才能利用有效的路径规划算法为 AGV 找到合适的行驶路线, 而环境信息的描述正是通过建立地图模型实现的. 环境信息描述的准确性和复杂程度受到地图建模方式的影响,进而影响路径规划的决策效率和响应速度, 因此选择合适的地图建模方法是非常有必要的[23].

栅格地图法是将已知的工作环境划分为大小相同的固定栅格. 如图 1 所示, 栅格按照颜色的不同分为黑白两种, 黑色栅格表示障碍物, 白色栅格表示可通行区域. 若障碍物位置变化, 仅需调整栅格的占用情况. 栅格法构建地图时需要确定栅格尺寸, 栅格地图的精度与栅格尺寸密切相关, 尺寸越小精度越高. 若地图精度过高, 需要占用大量存储空间且计算时间过长, 但如果精度过低, 又会影响 AGV 移动和定位的准确性, 因此选择合适的栅格尺寸尤为重要. 一般来说, 以 AGV 车体的大小为基准设置栅格的尺寸, 即可满足地图的精度需求. 针对物流分拣中心布局规则、场地平坦、障碍物少等特征, 栅格地图法优势明显, 因此在后续的多 AGV路径规划算法研究中采用栅格地图法建立地图模型.

图片[1]-基于时空A*算法的多AGV无冲突路径规划 — 图 1 栅格地图法示意图

2.2 单台AGV路径规划

当分拣系统中仅有一台 AGV 工作时, 不存在路径冲突问题. 本文单 AGV 最优路径规划问题选用 A算法进行搜索. A算法利用评价函数在每次搜索时都对所有可扩展点进行评估, 从而找到每次搜索的最佳扩展点, 直至找到目标节点. 使用评价函数的好处在于可以避免搜索过多无用的点, 算法的搜索效率得以提高.评价函数如下: