本文聚焦多智能体路径寻找（MAPF）问题，旨在为环境中多个智能体找到无碰撞路径，并最小化总路径成本（SOC）。文章重点介绍了领先的算法EECBS，该算法通过迭代选择路径集并引入约束来解决碰撞，以保证找到一个最优SOC在指定因子w范围内的次优解。为提升EECBS效率，研究提出了一种新的冲突解决机制——基于冲突的弹性分布，该机制将弹性分配与冲突数量成比例，并结合延迟估计提出延迟式弹性分布，以及一个融合两者的混合策略弹性分布。这些新机制被证明是完整且具有次优保证的，并在实验中展现出优于原有方法的性能。

⭐ MAPF问题的核心在于为多个智能体在共享环境中规划无碰撞路径，并以最小化所有智能体路径成本之和（SOC）为目标。路径成本通常定义为智能体从起点到终点的旅行时间。

⭐ EECBS是当前MAPF领域中解决有界次优问题（即SOC不超过最优值w倍）的领先算法。它通过维护路径集和SOC的下界LB，迭代地选择SOC不超过w·LB的路径集，并引入约束来解决碰撞。对于路径集中的每条路径，EECBS维护一个满足约束的最优路径下界。

⭐ 为了提高EECBS的效率，现有研究尝试通过弹性分布（flex distribution）来增加阈值。然而，过高的阈值可能导致SOC超出w·LB，迫使算法频繁切换路径集，降低效率。

⭐ 本文提出的冲突解决新机制包括：基于冲突的弹性分布（将弹性按冲突数比例分配）、延迟式弹性分布（估计满足约束所需的延迟）以及混合策略弹性分布（结合两者的分层框架）。这些机制旨在更有效地解决碰撞，提升算法性能。

⭐ 实验结果表明，引入本文提出的弹性分布机制的EECBS算法，相比于原始的贪婪弹性分布，能够更有效地解决MAPF问题，证明了其在完整性和有界次优性方面的优势。

arXiv:2507.17054v1 Announce Type: new Abstract: 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.