改进快速路径规划算法，让多智能体在毫秒内持续优化方案。
Anytime Single-Step MAPF Planning with Anytime PIBT
- 基于PIBT框架，实现可随时继续优化的单步路径规划。
- 毫秒级生成解，且随时间推移持续提升解的质量并收敛到最优。
- 适合需要快速响应且追求高质量解的多智能体系统应用。
PIBT 是一种流行的多智能体路径规划（MAPF）方法，被众多先进方法如 LaCAM、CS-PIBT 和 WPPL 所采用。其核心优势在于能以极快的速度求解单步路径规划，在不到一毫秒内为数百个智能体生成无碰撞解。然而，其主要缺陷是优先级策略过于激进，导致解质量较差；同时无法充分利用可用规划时间，仅返回首个找到的解。为此，本文提出 Anytime PIBT，该方法与 PIBT 一样快速生成单步解，但随后以“任意时”方式持续优化。理论上证明，只要有足够时间，Anytime PIBT 可收敛至最优解。实验表明，它可在毫秒级内显著提升单步解质量，甚至找到最优单步动作。但有趣的是，提升单步解质量对整体规划周期的成本影响有限。
原文摘要 · Abstract (English)
PIBT is a popular Multi-Agent Path Finding (MAPF) method at the core of many state-of-the-art MAPF methods including LaCAM, CS-PIBT, and WPPL. The main utility of PIBT is that it is a very fast and effective single-step MAPF solver and can return a collision-free single-step solution for hundreds of agents in less than a millisecond. However, the main drawback of PIBT is that it is extremely greedy in respect to its priorities and thus leads to poor solution quality. Additionally, PIBT cannot use all the planning time that might be available to it and returns the first solution it finds. We thus develop Anytime PIBT, which quickly finds a one-step solution identically to PIBT but then continuously improves the solution in an anytime manner. We prove that Anytime PIBT converges to the optimal solution given sufficient time. We experimentally validate that Anytime PIBT can rapidly improve single-step solution quality within milliseconds and even find the optimal single-step action. However, we interestingly find that improving the single-step solution quality does not have a significant effect on full-horizon solution costs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。