Source-linked AI summary
LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding
Keisuke Okumura
TL;DR
MAPF requires collision-free paths for agents on graphs, and quick planning matters for real-time or massive-agent applications. LaCAM uses a two-level search that lazily generates configurations under location constraints. Across varied scenarios it is reported to solve difficult instances quickly, though some depth-first searches time out on particular configurations.
Problem
MAPF requires collision-free paths for agents, while real-time applications and instances with massive agent counts create a need for quick sub-optimal planning.
Source: §1 · p. 1Method
LaCAM searches configurations at a high level and constraints on agents' next locations at a low level, lazily generating successors to reduce search effort.
Source: §1 · p. 1Results
LaCAM outperforms several sub-optimal solvers in most benchmark scenarios and solved all 400-agent instances on a 32×32 grid with 20% obstacles at a median runtime of 1 s.
Source: §1 · p. 1, §4.3 · p. 6Takeaways & Limitations
LaCAM solved varied challenging and dense instances, and its scalability test reports solutions within 30 s even with 10,000 agents.
Source: §4.5 · p. 6, §6 · p. 7With its depth-first search, LaCAM can require significant search effort on certain configurations and reach a timeout.
Source: §4.4 · p. 6
Abstract
from arXiv · showhide
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.
1 Introduction
MAPF requires collision-free paths for agents on graphs, and real-time applications create demand for quick sub-optimal solvers. LaCAM pairs a two-level search with lazy successor generation and is reported to solve challenging instances quickly.
1 Introduction
- MAPF assigns collision-free graph paths to agents, and quick sub-optimal algorithms have practical value where real-time deadlines or massive instances make optimal solvers unsuitable.The paper states that even state-of-the-art optimal methods struggle with a few hundred agents in short timeframes.Source: §1 · p. 1
- On a 32×32 grid with 20% obstacles, LaCAM solved all 400-agent instances with a median runtime of 1 s, while baseline sub-optimal algorithms mostly failed within 30 s.The paper also reports that LaCAM handles large maps, massive agent counts, and dense situations.Source: §1 · p. 1
- LaCAM searches sequences of joint agent configurations at the high level and constraints on next locations at the low level, generating successors lazily to reduce search effort.The authors describe the structure as easily extensible and suggest it may apply beyond MAPF.Source: §1 · p. 1
2 Preliminaries
An MAPF instance specifies a graph, agents, and distinct start and goal locations. A solution gives each agent a path to its goal while avoiding conflicts, and the paper evaluates solution quality using sum-of-costs.
2 Preliminaries
- An MAPF instance consists of a graph, a set of agents, and distinct start and goal locations for each agent.The notation also defines a configuration as a tuple of locations for all agents.Source: §2 · pp. 1–2
- Agents may move to adjacent vertices or stay put, but paths must avoid both shared-vertex conflicts and swaps between agents.A set of paths is conflict-free when neither conflict occurs.Source: §2 · p. 1
- A MAPF solution is a set of conflict-free paths that takes every agent from its start to its goal, and solution quality is measured by sum-of-costs.Sum-of-costs sums each agent's earliest arrival timestep at which it remains at its goal.Source: §2 · p. 2
3 Algorithm
LaCAM couples a high-level search over configurations with a low-level search that incrementally builds constraints for generating successors. The algorithm is complete, while its implementation choices shape search progress and solution quality.
3.1 Concept
- The high-level search uses a stack in depth-first style and retains a selected node while its low-level tree is explored, discarding it once all connected configurations have been generated.A found goal yields a solution by backtracking through high-level nodes.Source: §3.1 · pp. 2–3
- At each high-level configuration, LaCAM incrementally expands a low-level constraint tree whose branches specify agents' next locations, then generates connected configurations satisfying those constraints.The low-level search uses breadth-first expansion, and each constraint-tree path assigns distinct agents.Source: §3.1 · p. 2, §3.2 · p. 3
3.2 Pseudocode
- The configuration generator returns a connected configuration consistent with the low-level constraints or ⊥ when generation fails, while an Explored table tracks previously seen configurations.At the bottom of the constraint tree, all agents are constrained, specifying exactly one configuration.Source: §3.2 · p. 3
- Theorem 1 guarantees that Algorithm 1 returns a solution for solvable MAPF instances and reports NO SOLUTION otherwise.The proof argues that the finite search examines all configurations reachable from the start.Source: §3.2 · p. 3
3.3 Implementation Details
- The implementation uses PIBT to generate promising successors and orders agents by start-goal distance initially, then by goal status and arrival time in later nodes.The paper says other MAPF methods can also supply successor-generation strategies.Source: §3.3 · pp. 3–4
- Low-level node insertion order affects search progress and is provisionally randomized, while reinserting a known high-level node can improve solution quality without losing completeness.The authors identify both low-level ordering and constraint design as areas for further investigation.Source: §3.3 · p. 4
4 Evaluation
The evaluation tests LaCAM across benchmark, adversarial, scalability, and design settings. It generally performs strongly on speed and success rate, while exposing sensitivity to narrow-corridor configurations and successor-generation choices.
4.2 Small Complicated Instances
- LaCAM solved all small complicated instances across random seeds, but its solution quality was worse than PP, EECBS, and LNS2.The authors attribute the quality compromise to LaCAM's short planning horizon.Source: §4.2 · p. 6
4.1 Experimental Setup
- In the MAPF benchmark, LaCAM was tested on twelve selected grids, using 25 random scenarios per grid, agent counts increased by 50 to each maximum, a 30 s limit, and five runs per setting.Runtime and cost were summarized by medians over solved instances within each solver, with minimum and maximum scores also shown.Source: §4.1 · p. 5, §4.3 · p. 6
4.3 MAPF Benchmark
- In most scenarios, LaCAM outperforms PP, OD, EECBS, and LNS2 in success rate and runtime; PIBT+ is its closest competitor.LaCAM's SOC scores are better than PIBT+'s, especially in dense situations. Figure 2 summarizes the MAPF benchmark across grids.Source: Figure 2 · p. 5, §4.3 · p. 6
4.4 Adversarial Instance
- LaCAM solved the adversarial narrow-corridor instances, but search effort increased dramatically as the number of agents rose.The authors explain that near-duplicate configurations can disrupt search progress; under the depth-first implementation, resolving such configurations can require substantial effort and lead to timeouts.Source: §4.4 · p. 6, Table 2 · p. 6
4.5 Scalability Test
- Only LaCAM solved all tested instances with up to 10,000 agents on warehouse-20-40-10-2-2, with runtime at most 30 s.OD was excluded because it ran out of memory.Source: §4.5 · p. 6, Figure 3 · p. 6
4.6 Design Choice of LaCAM
- On random-32-32-20, reinsert improved SOC, while GREEDY failed in most settings, showing that configuration-generator choice strongly affects search.The authors attribute LaCAM's strong benchmark performance to PIBT's successor generation at the high level.Source: §4.6 · p. 7, Figure 4 · p. 7
5 Related Work
LaCAM is classified as search-based, but its configuration generation can draw on methods outside that category. Its two-level search differs from common MAPF designs in where and how it represents constraints.
5 Related Work
- MAPF methods are grouped into search-based, compiling-based, prioritized-planning, and rule-based approaches; LaCAM is search-based, while its configuration generator need not be.The experiments use PIBT, which the paper categorizes as prioritized planning and rule-based.Source: §5 · p. 7
- Unlike popular two-level MAPF searches that place negative constraints at the high level, LaCAM handles constraints at the low level and uses positive constraints.The paper notes that a negative-constraint LaCAM is possible, but its low-level search space may be dramatically larger.Source: §5 · p. 7
- Unlike A* variants that generate successors without aggressive agent coordination, LaCAM coordinates high-level successors through another MAPF algorithm as a configuration generator.Its constraint-addition scheme is partly influenced by operator decomposition, which creates successors for one agent action at a time.Source: §5 · p. 7
6 Conclusion and Discussion
LaCAM is a complete, quick search-based MAPF algorithm that handles challenging, dense scenarios, including instances with 10,000 agents solved in tens of seconds.
6 Conclusion and Discussion
- 10,000-agent instances are solved in tens of seconds, while LaCAM also handles complicated, dense scenarios that state-of-the-art sub-optimal solvers cannot handle.Source: §6 · p. 7
- One initial high-level successor, followed by lazy alternatives, virtually suppresses branching; promising successors can reduce node generations beyond prior methods.Source: §6 · p. 7
- Breadth-first search can make LaCAM makespan-optimal, while asymptotic optimality is another direction the authors want to develop.Source: §6 · p. 7
- Further work should explore more effective low-level constraints and configuration generators, which the authors identify as areas for improvement.Source: §6 · p. 7