arXiv:2507.17054cs.AI2025-07

改进多智能体路径规划的灵活分配机制,提升求解效率与稳定性。

New Mechanisms in Flex Distribution for Bounded Suboptimal Multi-Agent Path Finding

  • 按碰撞数量分配灵活性,动态调整约束阈值
  • 引入延迟估计,避免总成本超限导致路径切换
  • 组合策略在复杂场景中显著优于传统方法

多智能体路径规划(MAPF)旨在为共享环境中的每个智能体寻找无冲突路径,目标是最小化路径成本之和(SOC)。EECBS是当前领先的有界次优算法,其解的SOC不超过最优解的用户设定因子w。EECBS维护路径集和最优SOC下界LB,通过迭代选择满足SOC ≤ w·LB的路径集并引入约束解决冲突。每个路径维护一个满足约束的最优路径下界,通过寻找成本不超过其下界w倍的次优路径保证解的有界性。为加速,先前工作使用灵活分配提高阈值,但可能使总成本超过w·LB,迫使算法在不同路径集间切换,降低效率。本文提出基于冲突的灵活分配,按碰撞数分配灵活性;并估计约束所需延迟,提出基于延迟的灵活分配;进一步设计混合策略,在分层框架中结合两者。理论证明新机制保持完备性和有界次优性。实验表明,所提方法优于原始贪婪灵活分配。

原文摘要 · Abstract (English)

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths, one for each agent in a shared environment. Its objective is to minimize the sum of path costs (SOC), where the path cost of each agent is defined as the travel time from its start location to its target location. Explicit Estimation Conflict-Based Search (EECBS) is the leading algorithm for bounded-suboptimal MAPF, with the SOC of the solution being at most a user-specified factor $w$ away from optimal. EECBS maintains sets of paths and a lower bound $LB$ on the optimal SOC. Then, it iteratively selects a set of paths whose SOC is at most $w \cdot LB$ and introduces constraints to resolve collisions. For each path in a set, EECBS maintains a lower bound on its optimal path that satisfies constraints. By finding an individually bounded-suboptimal path with cost at most a threshold of $w$ times its lower bound, EECBS guarantees to find a bounded-suboptimal solution. To speed up EECBS, previous work uses flex distribution to increase the threshold. Though EECBS with flex distribution guarantees to find a bounded-suboptimal solution, increasing the thresholds may push the SOC beyond $w \cdot LB$, forcing EECBS to switch among different sets of paths instead of resolving collisions on a particular set of paths, and thus reducing efficiency. To address this issue, we propose Conflict-Based Flex Distribution that distributes flex in proportion to the number of collisions. We also estimate the delays needed to satisfy constraints and propose Delay-Based Flex Distribution. On top of that, we propose Mixed-Strategy Flex Distribution, combining both in a hierarchical framework. We prove that EECBS with our new flex distribution mechanisms is complete and bounded-suboptimal. Our experiments show that our approaches outperform the original (greedy) flex distribution.

多智能体路径规划优化算法分布式

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。