高密度仓库中基于任务分配的多AGV无碰撞调度框架

《Swarm and Evolutionary Computation》：Multi-AGV collision-free scheduling framework with task allocation in high-density warehouses

多AGV调度框架在密集仓库中通过任务分配优化、路径规划增强和冲突优先级机制实现无冲突协同，遗传算法与热力图结合提升效率。

　　

杨志成|徐本连|乐书婷|周旭|卢明丽|丛金亮|史健|金志成

中国江苏省苏州市学府路99号，苏州科技大学

摘要

随着智能仓库系统的不断扩展和自动引导车辆（AGV）的广泛部署，在高密度布局下的大规模协调面临着日益严峻的挑战，包括频繁的AGV之间冲突、由拥堵引起的延迟以及呈指数级增长的路径规划复杂性。本文提出了一种基于优先级的多AGV无碰撞调度框架，该框架在高密度仓库环境中集成了任务分配功能。任务分配被构建为一个多旅行商问题（MTSP），其中考虑了AGV的负载状态和任务类型，并使用遗传算法（GA）求解以获得接近最优的分配方案。对于路径规划，改进的启发式A*算法结合了高速公路引导机制、方向约束、转弯惩罚以及基于热图的启发式方法，以提高路径质量并缓解拥堵。在路径生成后，设计了一种分层优先级冲突解决策略来消除AGV之间的冲突。在三种不同规模的仓库环境中进行的广泛实验验证了该框架的可扩展性和鲁棒性，证明了其在实现无碰撞协调的同时显著降低总体任务成本和计算时间方面的有效性。

引言

随着电子商务的普及和对高效及时订单履行需求的增加，现代仓库系统在可扩展性、协调性和响应性方面面临着前所未有的挑战[1]。高密度存储布局、易拥堵的通道以及不均匀的工作负载分布进一步加剧了运营效率低下问题，凸显了传统手动操作和基于静态规则的调度方法在大规模仓库环境中的局限性[2]。为了解决这些挑战，自动引导车辆（AGV）作为智能仓储的关键推动者应运而生，它们提供了灵活性、自主性和可扩展性。如今，AGV已被广泛应用于大规模存储和检索系统中[3]。例如，在亚马逊的Kiva系统中，协调的机器人-货架互动显著提高了空间利用率和处理效率[4]。在这种背景下，在多个AGV之间实现高效的任务分配和无碰撞路径规划成为智能仓库研究的核心挑战，因为它直接影响到系统的吞吐量和整体运营可靠性[5]。

尽管在多AGV系统方面取得了显著进展，但智能仓库中日益增长的规模和操作耦合性仍然对协调任务分配和路径规划提出了重大挑战[6]。任务分配负责将取货和送货任务高效地分配给AGV，而路径规划（通常表述为多AGV路径路由问题MAPR）则在共享环境中生成无碰撞的轨迹。作为NP难问题[7]，MAPR的计算复杂性随着AGV数量的增加而迅速增长，使得在密集环境中的决策变得复杂。此外，任务分配和路径规划是相互依赖的：调度影响路由的可行性和效率，而路由约束又限制了可完成的任务分配[8]。这种耦合性加剧了协调难度，凸显了需要集成框架来共同优化分配和路由，以确保可扩展性、无碰撞操作和整体系统效率。

关于AGV任务分配和调度的先前研究提供了宝贵的见解。基于禁忌搜索的启发式方法已被开发用于最小化制造调度中的总完成时间[9]。混合粒子群优化（PSO）模型已被应用于不确定性下的灵活作业车间调度[10]。最近，改进的遗传算法（GA）被用于智能存储系统中的多机器人任务分配，提高了整体调度效率[11]。然而，大多数现有研究侧重于算法优化或简化的任务-AGV匹配，忽略了AGV负载状态与货架可用性之间的动态对应关系，以及对于实际仓库操作至关重要的任务分配和路径规划的联合优化。

路径规划是智能仓库系统中的另一个关键组成部分，直接影响运输时间、AGV调度和整体运营效率[12]。现有方法通常被分类为全局或局部规划器[13]，实际策略往往结合两者以改进轨迹优化[14]。一种简化的地图区域采样RRT*方法被提出以提高全局搜索的效率[15]，但它假设环境是静态的，并未明确考虑多AGV交互或瞬态拥堵，这可能导致在密集仓库中产生冲突。一种基于行为的领导者-跟随者策略与改进的动态窗口方法（DWA）结合使用，用于编队导航[16]。尽管这种策略在反应式避障和编队控制方面有效，但它缺乏全局上下文和任务协调能力，因此可能会陷入局部最优行为，从而加剧多AGV交通中的拥堵。还探索了一种结合全局PB-RRT层和增强型安全DWA局部层的双层框架，用于动态障碍物避让[17]，但这些方案通常不整合任务分配、AGV负载状态或时空拥堵信息，限制了它们在密集、任务密集型操作中防止冲突和保持路径质量的能力。

总体而言，当前方法通常忽略了任务分配、路径规划、AGV负载状态和货架可用性之间的相互作用，缺乏明确的跨层交互机制，往往导致优化碎片化，即在任务或路径层面的改进无法转化为系统层面的效率提升。为了解决这些问题，我们开发了一种基于优先级的多AGV无碰撞调度框架，该框架紧密耦合了任务级语义分组、基于热图的道路规划和多决策层中的基于优先级的冲突解决。这些组件表现出强烈的跨层依赖性：任务分配决定了AGV流的空间分布，考虑拥堵的道路规划影响了交通瓶颈的形成，而优先级规则影响了多智能体协调过程中的冲突解决方式。任务分配被构建为一个多旅行商问题（MTSP），并通过考虑AGV负载状态和货架可用性的遗传算法求解，从而将任务语义直接嵌入到下游规划过程中。每个AGV随后使用改进的A*算法生成初始路径，其中时空热图捕捉了拥堵模式。在更高层次，分层优先级机制迭代解决AGV之间的冲突，通过高层冲突解决和低层路径重新规划之间的重复协调，所提出的框架生成了全局无冲突的联合路径集。通过明确区分负载状态和未负载状态，该框架利用了仓库布局的结构灵活性，同时保持了效率和可行性。本研究的主要贡献可以总结如下：

• •
  一种紧密耦合的多AGV无碰撞调度架构，它整合了任务级语义分组、考虑拥堵的道路规划和基于优先级的冲突解决，以提高高密度仓库环境中的可扩展性和鲁棒性。
• •
  一种基于开环MTSP的任务分配模型，该模型考虑了AGV负载状态和货架语义，以确保任务的可行性和空间一致性，并使用仅进行变异的遗传算法求解，以减少总行驶成本和下游冲突空间。
• •
  一种改进的A*路径规划器，它结合了高速公路约束、转弯和等待惩罚以及时空热图启发式方法，使得在密集操作场景中实现更平滑的轨迹和主动的拥堵避让。
• •
  一种嵌入在CBS框架中的多级优先级调度机制，它通过综合考虑任务紧急性、负载状态和路径唯一性来解决AGV之间的冲突，从而提高整体调度效率。

本文的其余部分组织如下。第2节回顾了多AGV系统中任务分配和路径规划的相关工作。第3节介绍了所提出方法的调度模型和数学表述。第4节对整个框架进行了全面描述。第5节报告并分析了实验结果，第6节以最后的评论和未来研究方向结束了本文。

部分摘录

任务分配

任务分配是多AGV协调的核心组成部分，它决定了如何在代理之间分配取货和送货任务，以满足运营约束，同时最大化仓库操作的吞吐量和鲁棒性[18]，[19]。多机器人任务分配（MRTA）的研究沿着四个主要范式发展：基于优化的方法、启发式/元启发式方法、基于市场的方法和基于学习的方法，每种方法都从不同角度解决了可扩展性和协调性问题

问题表述

仓库被表示为一个矩形网格，其中每个单元格对应于货架位置或AGV的可通行空间，分隔货架区域的通道形成了环境中的可导航路径，底部边界作为指定的装卸区域，如图1所示。装载的AGV在将货架运输到目的地时被限制在通道内行驶，而未装载的AGV则可以在所有路径上自由移动

方法论

我们提出了一种用于智能仓库环境中的多AGV协同调度的统一方法论，该方法论整合了任务分配和协调路径规划框架。任务分配被构建为一个MTSP，并使用考虑AGV和货架状态的遗传算法求解。路径规划使用改进的CBS框架进行，其中高层通过优先级规则解决冲突，低层生成可行轨迹

实验

在实际仓库场景中，环境规模和AGV数量都会显著影响系统性能。为了评估所提出方法的鲁棒性，我们在不同的仓库规模和AGV数量下进行了实验。当仓库规模固定时，增加AGV数量通常会由于AGV之间冲突加剧而降低运营效率。相反，当AGV数量固定时，扩大仓库规模会降低效率，因为

结论

在这项工作中，我们提出了一种统一的、基于优先级的多AGV无碰撞调度框架，该框架集成了任务分配功能，适用于高密度智能仓库环境。该框架整合了三个核心组件：（i）基于仅进行变异的遗传算法（MTGA）的开环MTSP任务分配策略；（ii）结合高速公路引导、转弯和等待惩罚以及时空热图启发式的改进A*路径规划器；以及（iii）多级

CRediT作者贡献声明

杨志成：撰写——原始草稿，验证，方法论。徐本连：撰写——审阅与编辑，资源管理，项目协调。乐书婷：撰写——审阅与编辑，监督。周旭：形式分析，概念化。卢明丽：监督。丛金亮：形式分析。史健：软件开发。金志成：软件开发。

利益冲突声明

作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。

致谢

本工作得到了国家自然科学基金（编号：62576238、U24A20263、62503348）和苏州市科技计划项目（编号：SYG202351）的支持。