Multi-Agent Path Finding via Finite-Horizon Hierarchical Factorization

我们提出了一种用于大规模多智能体路径规划（MAPF）的新算法，该算法能够在动态环境中（例如自动化仓库）实现快速且可扩展的规划。我们的方法引入了有限时间窗分层分解框架，该框架以滚动时间窗的方式逐步进行规划。机器人首先并行计算各自的计划，然后根据时空冲突和可达性动态地组成小组。该框架考虑了冲突解决，并支持即时执行与并发规划，相比离线算法显著降低了响应时间。基准地图上的实验结果表明，我们的方法在保持高质量解决方案的同时，可将首次动作的时间减少多达60%，并在不同问题规模和规划时间窗范围内超越最先进的离线基线算法。

论文试图解决大规模多智能体路径规划（MAPF）问题，特别是在动态环境（如自动化仓库）中如何实现快速、可扩展的路径规划。这是一个经典问题，但针对动态环境和实时响应的需求提出了新的挑战。

论文提出了一种名为有限时间范围分层分解（finite-horizon hierarchical factorization）的新框架，采用滚动时域（receding-horizon）方式逐步规划。该方法通过让机器人首先并行计算个体计划，然后根据时空冲突和可达性动态分组来优化整体路径。相比传统的离线算法，这种方法显著减少了首次行动的时间，并支持即时执行与并发规划。

实验结果表明，该方法在基准地图上将首次行动时间减少了多达60%，同时保持了高质量的解决方案。实验涵盖了不同规模的问题和规划时间范围，验证了方法的鲁棒性和效率。此外，论文强调了其实时性能优势，适合动态场景中的应用。遗憾的是，摘要未提及代码是否开源，但其设计理念为未来研究提供了方向，例如探索更复杂的冲突解决策略或扩展到三维空间。

近期相关研究包括：1) Conflict-Based Search (CBS)，一种广泛使用的树搜索算法；2) Priority-Based Planning (PBP)，通过优先级分配减少冲突；3) Real-Time Dynamic Window Approach (DWA)，专注于移动机器人避障。其他值得关注的论文有《ECBS: An Efficient Bounded Suboptimal Search for Multi-Agent Path Finding》和《Learning Heuristics for CBS in MAPF》。这些工作主要集中在提高解的质量或降低计算复杂度，而本文则更关注动态环境中的实时性能。