LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
LaCAM is a search-based multi-agent pathfinding algorithm capable of solving hundreds of agents quickly with high success rates.
Key Findings
Methodology
LaCAM employs a two-level search framework: the high-level explores sequences of configurations, while the low-level lazily generates minimal constraints for each configuration. The high-level uses depth-first search, expanding configurations step-by-step, and the low-level uses breadth-first search to produce minimal constraints guided by heuristics like PIBT. The approach incorporates lazy constraint addition, significantly reducing search space. By dynamically adjusting agent ordering and re-inserting high-level nodes, the method maintains completeness. Extensive experiments demonstrate LaCAM's ability to solve large-scale MAPF instances—up to 10,000 agents—in seconds, outperforming or matching state-of-the-art algorithms in success rate and solution quality.
Key Results
- In benchmark tests on 32×32 grids with 20% obstacles, LaCAM solved all 400-agent instances with a median runtime of 1 second, surpassing baseline methods like Silver and Standley. It also handled 10,000 agents within 30 seconds, showing excellent scalability. Across various scenarios, LaCAM achieved higher success rates and comparable or better solution costs (SOC) than EECBS, LNS2, and PIBT+, especially in dense environments with complex obstacles. The results highlight its efficiency and robustness in large, dense MAPF problems.
Significance
This work advances large-scale multi-robot path planning by addressing the computational bottleneck in real-time applications. The integration of lazy constraints and a hierarchical search reduces complexity, enabling rapid solutions in scenarios with hundreds or thousands of agents. Such capability is crucial for industrial automation, warehouse logistics, and swarm robotics, where fast, reliable path planning is essential. The approach bridges the gap between optimality and scalability, offering a practical solution for real-world multi-robot systems, and enriches the theoretical landscape of MAPF algorithms.
Technical Contribution
The main innovation lies in combining a two-level search with lazy constraint addition, ensuring completeness while greatly reducing search effort. The high-level depth-first search manages the configuration space efficiently, while the low-level breadth-first search generates minimal constraints guided by heuristics like PIBT. The adaptive agent ordering and node re-insertion strategies further improve search efficiency and solution quality. Theoretically, LaCAM guarantees finding a solution if one exists, and practically, it scales to thousands of agents, a feat rarely achieved by existing algorithms. This work introduces a new paradigm in hierarchical, lazy constraint-based MAPF solving.
Novelty
LaCAM is the first to integrate lazy constraint addition within a two-level hierarchical search for MAPF, enabling rapid solutions in large-scale scenarios. Unlike conflict-based methods such as CBS, it avoids explicit conflict detection by generating minimal constraints on demand. Its combination of depth-first high-level exploration with lazy low-level constraint generation represents a significant departure from traditional coupled or conflict-based approaches, offering both theoretical completeness and practical scalability.
Limitations
- In environments with narrow corridors or frequent swap conflicts, LaCAM's search effort increases dramatically, leading to potential timeouts. Its performance is sensitive to the environment topology, especially in dense, complex maps.
- The current configuration generator relies on heuristics like PIBT, which may produce suboptimal paths or cause instability in solution quality. Randomness in node re-insertion can also affect consistency.
- Handling extremely dense or dynamic environments remains challenging, as the search space can explode, and the lazy constraint approach may need further refinement to maintain efficiency and solution quality.
Future Work
Future research will focus on developing more intelligent configuration generators, possibly leveraging machine learning to predict promising paths. Extending LaCAM to dynamic environments with moving obstacles or changing goals is also a key direction. Incorporating multi-objective optimization, such as minimizing energy or time, and exploring distributed implementations for real-time multi-robot systems are promising avenues. Additionally, further theoretical analysis on the bounds of solution optimality and search complexity will deepen understanding and guide improvements.
AI Executive Summary
Multi-agent pathfinding (MAPF) is a fundamental challenge in robotics and automation, especially as the scale of robot swarms and logistics systems grows. Traditional algorithms like CBS and EECBS have achieved notable success in small to medium scenarios but struggle with real-time performance when hundreds or thousands of agents are involved. Addressing this gap, LaCAM introduces a hierarchical, search-based framework that combines a high-level depth-first exploration of configurations with a low-level lazy constraint generation guided by heuristics like PIBT.
The core innovation of LaCAM lies in its two-layer architecture: the high-level search manages the global configuration space, while the low-level lazily generates minimal constraints to refine each configuration. This approach drastically reduces the search effort by avoiding exhaustive conflict detection and leveraging the problem's structure. The algorithm guarantees completeness, ensuring that if a solution exists, it will be found.
Extensive experiments demonstrate LaCAM's remarkable scalability and efficiency. It successfully solves large instances with up to 10,000 agents within seconds, outperforming existing methods in success rate and solution quality, especially in dense and complex environments. The results highlight its potential for real-world applications such as warehouse automation, drone swarms, and autonomous vehicle coordination.
Despite its strengths, LaCAM faces limitations in environments with narrow passages or high swap conflicts, where search effort increases significantly. Its reliance on heuristic configuration generators like PIBT may also introduce suboptimal paths or instability. Future work aims to improve configuration generation, extend to dynamic environments, and incorporate multi-objective optimization.
Overall, LaCAM represents a significant step forward in large-scale, real-time multi-agent path planning, offering both theoretical guarantees and practical scalability. Its innovative combination of hierarchical search and lazy constraints opens new avenues for research and deployment in complex multi-robot systems, promising to transform how autonomous agents coordinate in crowded, dynamic spaces.
Deep Dive
Abstract
We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM). MAPF is a problem of finding collision-free paths for multiple agents on graphs and is the foundation of multi-robot coordination. LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more. At the low-level, it searches constraints about agents' locations. At the high-level, it searches a sequence of all agents' locations, following the constraints specified by the low-level. Our exhaustive experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios, regarding success rate, planning time, and solution quality of sum-of-costs.