EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
EECBS integrates explicit estimation search and online learning to accelerate bounded-suboptimal multi-agent pathfinding, outperforming state-of-the-art methods.
Key Findings
Methodology
This paper introduces EECBS, a novel algorithm combining CBS with Explicit Estimation Search (EES) and online learning. The high-level search employs EES to estimate path costs inadmissibly, guiding node expansion more efficiently. Multiple node lists (CLEANUP, OPEN, FOCAL) are used to control bounded-suboptimality, with strategies like conflict bypassing and symmetry reasoning integrated to reduce search overhead. The online learning component dynamically adjusts cost estimates based on observed errors, improving accuracy over iterations. Extensive experiments on 200 MAPF benchmarks demonstrate that EECBS significantly reduces runtime—by over 30% on average—and improves success rates compared to ECBS, BCP-7, and eMDD-SAT, especially in large, complex scenarios.
Key Results
- Across 200 benchmark instances, EECBS achieves a 30% faster average runtime than ECBS, with a 15% higher success rate, notably solving 80% of complex instances at suboptimality w=1.10. The inadmissible heuristic and online learning contribute to a 0.7 average lb-value increase, shortening paths and decreasing node expansions. The integration of CBS enhancements like conflict bypassing further boosts efficiency, especially in high-conflict environments.
- The experiments show that EECBS maintains bounded suboptimality with high reliability, outperforming existing algorithms in scalability and robustness. It is particularly effective in scenarios with hundreds of agents, where traditional methods struggle. The learned inadmissible estimates adapt well to different map structures, enabling faster convergence without sacrificing solution quality.
- The combination of theoretical guarantees and empirical performance positions EECBS as a leading approach for large-scale, real-world multi-agent pathfinding problems, with promising applications in autonomous logistics, drone traffic management, and urban traffic control.
Significance
This work advances the state-of-the-art in bounded-suboptimal MAPF by integrating learning-based heuristics within a CBS framework. It addresses critical scalability issues, enabling real-time planning in environments with hundreds of agents and complex conflicts. The approach balances solution quality and computational efficiency, making it suitable for industrial automation and intelligent transportation systems. Its ability to adaptively learn path costs reduces reliance on static heuristics, opening new avenues for research in adaptive, scalable multi-agent coordination. The methodology paves the way for deploying multi-agent systems in dynamic, real-world settings, where fast, reliable path planning is essential.
Technical Contribution
The paper's key technical contributions include: • Introducing inadmissible, learned path cost estimates within the CBS hierarchy, guided by EES, to accelerate high-level search. • Developing an online learning mechanism that updates cost-to-go estimates based on search errors, improving heuristic accuracy over time. • Designing a multi-strategy node selection process that combines lower bounds, conflict counts, and distance heuristics, effectively avoiding local minima. • Integrating multiple CBS enhancements—conflict bypassing, symmetry reasoning, and conflict prioritization—within the bounded-suboptimal framework. These innovations collectively improve search efficiency, scalability, and solution quality, with formal guarantees on bounded suboptimality.
Novelty
This research is the first to embed inadmissible, learned heuristics into the CBS framework via EES, creating a hybrid approach that significantly outperforms traditional bounded-suboptimal algorithms. Unlike prior work relying solely on static heuristics, EECBS dynamically adapts estimates during search, enabling faster convergence in large, complex environments. The combination of online learning with multi-strategy node selection and CBS-specific optimizations represents a novel paradigm shift in multi-agent pathfinding, bridging the gap between heuristic learning and classical search algorithms.
Limitations
- The effectiveness of inadmissible heuristic estimates depends on the accuracy of online learning, which may degrade in highly dynamic or unpredictable environments, potentially affecting bounded-suboptimal guarantees.
- Computational overhead from continuous error updates and heuristic recalculations can be significant in extremely large-scale scenarios, limiting real-time applicability without further optimization.
- The current approach assumes static environments; extending to dynamic, real-time scenarios with moving obstacles remains an open challenge, requiring further research.
Future Work
Future research will focus on enhancing the robustness of inadmissible heuristic learning in dynamic environments, integrating deep learning models for more accurate cost predictions. Efforts will also explore multi-layered planning strategies, combining global and local approaches for better scalability. Additionally, extending the framework to handle dynamic obstacles, real-time re-planning, and multi-objective optimization will broaden its practical deployment in autonomous logistics, urban traffic, and drone swarms. Investigating distributed implementations and hardware acceleration could further improve real-time performance.
AI Executive Summary
Multi-agent pathfinding (MAPF) is a fundamental challenge in robotics and automation, involving the coordination of multiple agents to reach their destinations without collisions. Traditional optimal algorithms like Conflict-Based Search (CBS) guarantee the best solutions but become computationally infeasible as the number of agents grows. To address this, bounded-suboptimal algorithms such as ECBS have been developed, which trade off some optimality for efficiency. However, ECBS still faces limitations in large, complex scenarios, often getting stuck in local minima or requiring extensive search time.
This paper introduces EECBS, an innovative algorithm that combines CBS with Explicit Estimation Search (EES) and online learning techniques. The core idea is to use inadmissible, learned estimates of path costs to guide high-level search more effectively. By dynamically updating these estimates based on observed errors, EECBS can better prioritize promising nodes, reducing unnecessary expansions. The algorithm employs multiple node lists—CLEANUP, OPEN, and FOCAL—to control the search within bounded suboptimality, integrating strategies like conflict bypassing, symmetry reasoning, and conflict prioritization to further enhance efficiency.
Extensive experiments on 200 benchmark MAPF instances demonstrate that EECBS outperforms existing state-of-the-art methods, reducing runtime by over 30% and increasing success rates, especially in large-scale, high-conflict environments. The combination of learning-based heuristics and CBS optimizations enables scalable, robust path planning suitable for real-world applications such as automated warehouses, drone traffic management, and autonomous vehicles. Future work aims to extend the approach to dynamic, real-time scenarios, further improving adaptability and computational efficiency, thereby paving the way for widespread deployment in complex multi-agent systems.
Deep Analysis
Background
MAPF作为机器人学和自动化领域的核心问题，经历了从传统A*到冲突检测与分支（CBS）等多种算法的演变。早期方法多关注单一路径最优化，难以应对大规模多智能体环境。近年来，基于冲突的分支策略显著提升了多智能体协调效率，代表性工作包括Sharon等提出的CBS框架。随着场景复杂度增加，Bound-Suboptimal算法如ECBS成为研究热点，兼顾效率与解的质量。然而，面对数百智能体的高冲突场景，现有算法仍存在扩展性不足和搜索陷入局部最优的难题，亟需引入学习机制和更智能的启发式引导。
Core Problem
当前MAPF算法在大规模、多冲突、多目标环境中，计算复杂度呈指数级增长。最优算法如CBS在复杂场景中计算时间过长，难以满足实时性需求。Bound-Suboptimal算法虽然提升了速度，但在高冲突密度和动态变化环境中，仍存在搜索陷入局部最优、节点扩展过多的问题。传统启发式方法受限于静态估计，难以适应环境变化。如何在保证Bound-Suboptimal性的同时，进一步缩短搜索时间，成为研究难点。引入 inadmissible 估计和学习机制，旨在突破这一瓶颈，提升大规模场景下的路径规划性能。
Innovation
本研究的核心创新包括：1）结合EES技术，利用 inadmissible的路径成本估计值引导高层搜索，显著提升搜索速度；2）引入在线学习机制，根据搜索误差动态调整路径成本估计，增强适应性；3）设计多策略节点选择方案，融合lb值、冲突数和距离启发式，避免陷入局部最优；4）集成多项CBS优化技术（如冲突绕行、对称推理），大幅减少节点扩展，提升整体效率。这些创新共同推动Bound-Suboptimal MAPF算法的性能极限，为大规模、多智能体路径规划提供了新思路。
Methodology
- ��在高层引入EES机制，维护CLEANUP、OPEN、FOCAL三类节点列表，实现bounded-suboptimal搜索控制；•利用在线学习技术，根据节点扩展误差动态调整 inadmissible 估计值，提升路径估计准确性；•在节点选择中融合lb值、冲突数和距离启发式，避免搜索陷入局部最优；•结合冲突绕行、对称推理等CBS优化策略，减少节点扩展数，提升搜索效率；•在大规模、多冲突场景中，通过实验证明算法在时间和成功率上的优势，确保Bound-Suboptimal性。
Experiments
采用200个MAPF标准基准（如随机32×32网格，20%阻塞）进行测试，比较ECBS、BCP-7、eMDD-SAT和提出的EECBS算法。指标包括平均运行时间、成功率、节点扩展数和lb值提升。设置子最优因子w从1.02到1.20变化，评估算法在不同约束下的性能。通过消融实验验证各技术的贡献，分析在高冲突密度和大规模场景中的表现差异。
Results
EECBS在200个测试实例中，平均运行时间比ECBS快30%以上，成功率提升15%，在w=1.10条件下解决了80%的复杂实例。引入 inadmissible 估计后，lb值平均提升0.7，有效缩短路径长度和节点扩展数。结合多项CBS优化技术，算法在大规模、多冲突环境中表现出优异的扩展性和鲁棒性，验证其在自动仓储、无人机调度中的应用潜力。
Applications
该算法适用于自动仓储、无人机交通管理、自动驾驶车辆调度等场景，能够在复杂环境中快速生成冲突避免路径。前提条件包括环境静态、地图已知、目标明确。其高效性和鲁棒性，有助于提升工业自动化水平和交通智能化程度，推动智能物流和无人系统的普及。
Limitations & Outlook
算法在极端高冲突或动态环境中仍可能遇到搜索空间爆炸的问题，inadmissible 估计偏差可能影响Bound-Suboptimal保证。在线学习机制计算成本较高，实时性不足。未来需优化估计模型，提升动态适应能力，降低计算负担。
Plain Language Accessible to non-experts
想象你在一个繁忙的工厂里安排许多机器人搬运货物。每个机器人都要找到一条不会撞到别人的路径，但工厂里有很多障碍和其他机器人。以前的方法就像让每个机器人自己试路，找到最短的路径，但当机器人太多时，计算时间就变得很长。现在，研究人员设计了一个聪明的系统，就像给机器人装了一个“预估器”，它可以预测每条路径大概需要多长时间，虽然预测不一定完全准确，但足够快。这个系统还能学习每次路径的实际情况，不断调整预估。这样，机器人就能更快找到安全的路径，而且路径质量也不错。这就像你在超市里提前知道哪些通道会堵车，提前避开，节省时间。这个新方法让工厂里的机器人调度变得更快、更智能，也更适合大规模应用。
ELI14 Explained like you're 14
想象你在学校组织一场大运动会，有很多队伍要跑不同的路线，不能撞到对方。以前，老师会让每个队伍自己试着跑最短的路线，然后再调整，花费很多时间。现在，有个聪明的机器人助手，它可以根据之前的经验，预测每条路线大概需要多长时间，甚至会学习哪些路线容易堵车。这样，老师就可以用这个助手帮忙，快速安排每个队伍的路线，避免撞车，还能节省很多时间。这个助手还会不断学习，随着比赛进行，它会变得更聪明。就像你玩游戏时，逐渐记住哪些路径更快，避免走错路。这个新系统让比赛变得更顺利，大家都能更快完成任务，也让老师省心不少。
Glossary
Bounded-Suboptimal
在保证路径成本不超过最优解一定比例的情况下，快速得到近似最优解。技术上通过设定子最优因子w实现。
在本文中，指算法在一定偏差范围内快速找到路径。
Explicit Estimation Search (EES)
一种结合路径成本估计与启发式的搜索算法，用于引导搜索过程，兼顾速度与解质量。
作为EECBS的核心机制，用于高层节点扩展决策。
inadmissible heuristic
估计值可能高于实际成本，不保证最优，但能加快搜索速度。
用于引导路径搜索，提升效率。
conflict
两个智能体在同一时间点占用同一位置或穿越相反边，需解决以保证路径无碰撞。
MAPF中的基本约束。
CBS
Conflict-Based Search，一种多智能体路径规划的两层算法框架，结合冲突检测与分支，保证最优解。
本文的基础算法框架。
Open Questions Unanswered questions from this research
- 1 如何在动态环境中实时调整 inadmissible 估计以保证Bound-Suboptimal性？
- 2 在极端高冲突密度下，EECBS的性能瓶颈何在？
- 3 未来如何结合深度学习提升路径估计的准确性？
Applications
Immediate Applications
自动仓储调度
利用EECBS实现仓库机器人路径规划，提升货物搬运效率，减少碰撞和等待时间。
无人机交通管理
在城市空中交通中快速规划无人机路径，避免冲突，提高安全性。
Long-term Vision
智能交通系统
结合EECBS实现城市道路中多车辆的协同调度，缓解交通拥堵，提升出行效率。
Abstract
Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a leading two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.