LaCAM: configuration-space MAPF search with PIBT and anytime refinement.
Fourth repository in the femi-mapf series. Builds on astar-grid, cbs-from-scratch and eecbs-benchmark.
CBS and EECBS both prove a lower bound and work upward. LaCAM does the opposite: it finds a solution almost immediately, then improves it if time allows. Same problem, opposite strategy.
The representation is what changes. CBS searches over constraint sets, keeping a full plan per agent at every node. LaCAM searches over configurations — a single tuple giving every agent's current cell — and the solution is a path through configuration space. A LaCAM node is a snapshot with no notion of the future: nothing to repair, nothing to propagate, nothing to prove.
The successor set of a configuration is astronomically large — five moves each across twenty agents is roughly 1014 — so LaCAM never materialises it. It asks PIBT for one plausible successor, commits, and descends. Only if that fails does it lazily generate another. That is what "lazy constraints addition" means.
Guaranteed: completeness. The low-level tree eventually enumerates every successor, so a solution will be found if one exists. Not guaranteed: anything about quality.
10×10 grids, 10% obstacles, 20 seeds per agent count, 5 s limit. All four solvers on identical instances, every plan checked by the same validator.
| solver | agents | success | median ms | cost vs optimal |
|---|---|---|---|---|
| CBS (optimal) | 8 | 20/20 | 11.1 | 1.000 |
| CBS (optimal) | 16 | 5/20 | 836.5 | 1.000 |
| CBS (optimal) | 20 | 1/20 | 460.7 | 1.000 |
| EECBS w=1.5 | 16 | 20/20 | 74.9 | 1.017 |
| EECBS w=1.5 | 20 | 20/20 | 197.3 | 1.025 |
| LaCAM | 16 | 20/20 | 10.5 | 1.248 |
| LaCAM | 20 | 20/20 | 12.3 | 1.713 |
| LaCAM* (anytime) | 20 | 20/20 | 1000 † | 1.680 |
† LaCAM* always consumes its full budget by design — it is not slower, it is still improving when the clock stops.
The whole series in one row. At 20 agents optimal CBS solves one instance in twenty; LaCAM solves all twenty, 16× faster than EECBS and 37× faster than CBS, at 71% worse cost.
Notice LaCAM's runtime barely moves with agent count — 4.7 ms at 8 agents to 12.3 ms at 20, while CBS spans 11 ms to timeout. Runtime tracks the length of the configuration path, not the branching factor, because the branching factor is never enumerated.
Where CBS and EECBS cannot go at all:
| map | agents | time to solution | validated |
|---|---|---|---|
| 32×32 | 50 | 250 ms | yes |
| 32×32 | 100 | 510 ms | yes |
| 64×64 | 200 | 4.2 s | yes |
This is the curve CBS and EECBS structurally cannot draw. Both are silent until they finish; LaCAM has an answer in milliseconds and spends the remaining budget improving it. For a system that must react to an anomaly mid-patrol, having some plan immediately is worth more than the best plan eventually.
Refinement helps only about a third of the time. Across 12 seeds at 12 agents with a 3 s budget: 33% improved at least once, median factor 1.24× when they did.
Worse, the rate is uneven and does not follow agent count in any tidy way:
| agents | improved | median factor |
|---|---|---|
| 8 | 1/12 | 1.051 |
| 12 | 3/12 | 1.250 |
| 14 | 3/12 | 1.068 |
| 16 | 2/12 | 1.013 |
| 20 | 4/12 | 1.021 |
My first run of this study used 6 seeds at 16 agents and reported 0% improvement. That was an unlucky sample, not a finding — at 16 agents only 2 in 12 improve, so 6 seeds can easily miss all of them. The published numbers use 12 seeds. Reporting the sample-size problem matters more than the result: the honest conclusion is that refinement is unreliable at this scale, and the implementation here (cost-based rewiring on revisited configurations) is the weakest form of it.
Okumura's LaCAM* achieves eventual optimality with a monotone refinement operator that this repository does not implement. What is here improves solutions sometimes; it does not converge.
LaCAM makes no optimality claim, so there is nothing to check against an optimal oracle. What must hold is legality and completeness, and both are tested against upstream code rather than anything written here.
Every plan is validated by cbs.validate — the same function that checks CBS and EECBS output. LaCAM configurations are transposed into per-agent paths and handed to it unchanged. 75 plans across the sweep, zero invalid.
Every configuration transition is checked at generation time. is_legal_transition verifies no shared cells, no moves off the graph, no moves into obstacles, and no head-on swaps. PIBT's backtracking can in rare corners leave two agents claiming one cell, so the generator's output is never trusted — a rejected configuration is a normal event, since completeness rests on the constraint tree rather than on PIBT succeeding.
Suboptimality is asserted, not assumed. A test requires LaCAM's first solution to be worse than optimal CBS on a majority of instances. If that ever started failing it would mean the instances had gone trivial, not that LaCAM had become optimal.
Both make a from-scratch LaCAM look plausible while failing, and neither produces an error message.
The low-level tree is a FIFO queue, not a stack. Popping from the back dives immediately to maximum constraint depth, pinning every agent at once. That over-constrains PIBT into failure and the search thrashes without escaping a local minimum. Popping from the front tries the empty constraint first — letting PIBT choose freely — then one-agent constraints, then two: a gradual tightening.
One instance went from timing out at 92,595 expansions to solving in 100 ms with 943. The bug was isolated by running PIBT alone, which got 11 of 12 agents home and stalled — correct PIBT behaviour, proving the generator was fine and the search was wrong.
Already-explored configurations must be re-pushed onto the stack. Skipping them leaves the search draining the current node's constraint tree, which is exponential in agent count. Re-pushing lets the depth-first search continue from the known configuration instead. The node's tree is finite and shrinks on every expansion, so this still terminates.
git clone https://github.com/femi-mapf/lacam-python.git
cd lacam-python
python -m venv .venv
source .venv/Scripts/activate # Git Bash on Windows
pip install -e ".[dev]"All three upstream repositories install automatically from GitHub and must be public.
# 200 agents on a 64x64 map
lacam solve --size 64 --agents 200 --seed 1
# Anytime refinement, showing each improvement as it lands
lacam solve --size 10 --agents 12 --seed 8 --anytime --time-limit 3
# Head to head against CBS and EECBS on one instance
lacam solve --size 10 --agents 16 --seed 2 --compare
# Reproduce the tables and figures above
lacam benchmark --size 10 --agents 8 12 16 20 --seeds 20
lacam anytime --size 10 --agents 12 --seeds 12 --budget 3Exit codes: 0 solved and valid, 1 no solution, 2 bad arguments, 3 validation failed.
from cbs import random_instance, validate
from lacam import lacam_star
instance = random_instance(size=32, num_agents=100, density=0.10, seed=1)
result = lacam_star(instance, time_limit_s=1.0)
print(result.summary())
# cost= 3165 makespan= 53 expanded= 53 improvements= 0 first= 510.1ms 1.000s
assert validate(instance, result.paths())
for seconds, cost in result.history:
print(f"{seconds * 1000:.0f}ms: {cost}")PIBT is greedy and myopic. Every agent walks down its own distance gradient and only negotiates on collision. When a high-priority agent wants an occupied cell it inherits its priority to the occupant and recurses, forcing it out; if the occupant is stuck, the recursion backtracks. That is the entire generator, and it explains both the speed and the poor first solutions.
Priorities are dynamic. An agent away from its goal gains priority every step; one that arrives resets to zero. Without this a settled agent blocks a corridor indefinitely.
Branching order matches PIBT's own ordering. The constraint tree exists to overrule PIBT, and it is most useful when it overrules the agent PIBT committed to first, since that is the decision everything downstream was built on.
Cost accounting matches cbs and eecbs exactly. Sum-of-costs, where a timestep is free for an agent only if it is at its goal both before and after the move. Sitting on the goal is free; leaving and returning is paid in full. This is what makes the comparison table valid rather than approximate.
pytest
ruff check src tests
mypy87 tests, 97.4% coverage. The build fails below 95%.
Highlights: solutions validated and conflict-free at 4, 8, 12 and 16 agents; LaCAM required to succeed where optimal CBS times out; first solutions asserted suboptimal; head-on swaps proven never to be generated; priority inheritance checked in a one-wide corridor where recursion is the only way through; anytime history asserted monotonically improving; and the anytime variant required never to return worse than the greedy one.
| repository | role | guarantee |
|---|---|---|
astar-grid |
single-agent A*, instrumentation, benchmark I/O | optimal |
cbs-from-scratch |
constraint tree, optimal baseline | optimal |
eecbs-benchmark |
focal search, EES | cost ≤ w × optimal |
lacam-python |
configuration-space DFS, PIBT | complete only |
inspection-mapf |
30-node pipeline benchmark, heterogeneous UAV battery | — |
Sturtevant's June framing was that the challenges of a particular problem determine which strategy is useful. Four solvers now sit on identical instances with the crossover points located: optimal CBS is fine to about 12 agents at this density and unusable past 16; EECBS buys back the whole failure region for 2.5% cost; LaCAM is an order of magnitude faster again and scales to 200 agents, at 20–70% cost.
The next repository applies this to the two-mode inspection problem, where the answer is plausibly both — a proven-optimal patrol schedule computed offline, and a LaCAM-class reactive replan when an anomaly appears mid-flight.
MIT. See LICENSE.