分阶段动态分组规划，让多机器人快速协同避障。
Multi-Agent Path Finding via Finite-Horizon Hierarchical Factorization
- 每步只规划一步，按时空冲突动态分组并行求解。
- 首次动作时间减少60%，且在各种规模下表现更优。
- 适合高动态场景如智能仓库，响应快、效率高。
我们提出一种新型大规模多智能体路径规划（MAPF）算法，适用于自动化仓库等动态环境，实现快速可扩展的规划。该方法引入有限时域分层因子化框架，以滚动时域方式逐步规划。机器人先并行计算个体路径，再根据时空冲突与可达性动态分组。该框架兼顾冲突消解、即时执行与并发规划，显著降低响应时间。在基准地图上的实验表明，本方法相比最先进的离线基线算法，首次动作时间最多缩短60%，且在不同问题规模和规划时域下始终提供高质量解。
原文摘要 · Abstract (English)
We present a novel algorithm for large-scale Multi-Agent Path Finding (MAPF) that enables fast, scalable planning in dynamic environments such as automated warehouses. Our approach introduces finite-horizon hierarchical factorization, a framework that plans one step at a time in a receding-horizon fashion. Robots first compute individual plans in parallel, and then dynamically group based on spatio-temporal conflicts and reachability. The framework accounts for conflict resolution, and for immediate execution and concurrent planning, significantly reducing response time compared to offline algorithms. Experimental results on benchmark maps demonstrate that our method achieves up to 60% reduction in time-to-first-action while consistently delivering high-quality solutions, outperforming state-of-the-art offline baselines across a range of problem sizes and planning horizons.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。