arXiv:2504.07841v1 宣布类型: 新颖 摘要: PIBT 是多智能体路径规划（MAPF）方法中的一个流行方法，也是诸如 LaCAM、CS-PIBT 和 WPPL 等许多最新 MAPF 方法的核心。PIBT 的主要优点在于它是一个非常快速且有效的单步 MAPF 解决器，并能在不到一毫秒的时间内为数百个智能体返回一个无碰撞的单步解决方案。然而，PIBT 的主要缺点是它在优先级方面非常贪婪，因此会导致解决方案质量较差。此外，PIBT 不能充分利用可用的所有规划时间，并且会尽快返回找到的第一个解决方案。因此，我们开发了 Anytime PIBT，它与 PIBT 一样快速找到一个单步解决方案，但随后会以随时可用的方式不断改进解决方案。我们证明，在充足的时间内，Anytime PIBT 会收敛到最优解。实验验证表明，Anytime PIBT 可在毫秒内迅速改进单步解决方案的质量，甚至找到最优的单步行动。然而，我们有趣地发现，改进单步解决方案的质量对全时间范围解决方案的成本几乎没有显著影响。