Conflict-Based Search, implemented from scratch and verified against an exhaustive optimal oracle.
Second repository in the femi-mapf series. Builds on astar-grid.
CBS is two searches stacked. The low level plans one agent at a time under a set of constraints. The high level searches the space of constraint sets, represented as a binary tree.
The root has no constraints, so every agent takes its own shortest path and ignores the others. That plan is almost always in conflict, but its cost is a lower bound on the optimum — no constraint can make a path shorter. The high level then repeatedly takes the cheapest node, finds a conflict in its plan, and splits it into two children, each forbidding one agent's half of that conflict.
Because the branching is exhaustive and no child is ever cheaper than its parent, expanding in cost order means the first conflict-free plan found is optimal.
That guarantee is the whole point, so this repository does not assume it. Every claim of optimality is checked against a brute-force search over the joint configuration space that shares no code with the solver.
All numbers from cbs benchmark. Nothing hand-copied.
| agents | solved | success | median ms | median CT nodes | median cost |
|---|---|---|---|---|---|
| 4 | 25/25 | 100% | 4.1 | 1 | 46 |
| 6 | 25/25 | 100% | 7.3 | 2 | 64 |
| 10 | 23/25 | 92% | 23.9 | 5 | 118 |
The median constraint tree is tiny — one to five nodes. At 15% density on a 16×16 grid there is enough room that agents mostly do not interact, and CBS confirms the root plan almost immediately.
The medians hide the real behaviour:
| agents | median CT | max CT | median LL calls | max LL calls | median ms | max ms |
|---|---|---|---|---|---|---|
| 4 | 1 | 4 | 4 | 10 | 4.1 | 31 |
| 6 | 2 | 67 | 8 | 138 | 7.1 | 221 |
| 10 | 5 | 754 | 18 | 1,516 | 24.4 | 2,415 |
At ten agents the median instance expands 5 constraint-tree nodes and the worst expands 754 — a 150× spread at identical agent count. Runtime spans 24 ms to 2.4 seconds. This is the single most important empirical fact about CBS: runtime is driven by the number of conflicts, not the number of agents.
| agents | solved | success | median ms | median CT nodes |
|---|---|---|---|---|
| 4 | 20/20 | 100% | 1.9 | 1 |
| 8 | 20/20 | 100% | 8.2 | 4 |
| 12 | 16/20 | 80% | 49.8 | 17 |
| 16 | 5/20 | 25% | 881.1 | 96 |
| 20 | 1/20 | 5% | 276.1 | 24 |
Squeeze the same agents into a smaller map and success collapses: 100% → 100% → 80% → 25% → 5%. Not a gentle degradation — a cliff.
The mechanism is visible in the last two rows. At 20 agents the median solved runtime (276 ms) is lower than at 16 agents (881 ms), and the median tree is smaller. That looks backwards until you realise what is being averaged: at 20 agents the only instance solved was an easy one. Everything with real congestion timed out. The statistic is conditioned on success, and success has become a biased sample.
This is why status distinguishes timeout from unsolvable rather than collapsing both into "failed". Reporting a timeout as unsolvability would silently corrupt every curve above.
Solution cost grows smoothly and predictably with agent count. Constraint-tree effort does not. Two instances with the same optimal cost can differ by three orders of magnitude in the work needed to prove that cost is optimal. Optimality, not path quality, is what CBS is paying for.
That is the motivation for everything that follows in this series. EECBS keeps the constraint tree but relaxes optimality to a bounded factor, buying back the tail. LaCAM abandons the tree entirely, finds a solution fast, then improves it. Sturtevant's framing — best-first methods that prove a lower bound and work up, versus depth-first methods that find a solution and iteratively improve it — is precisely the choice this data motivates.
Three independent layers, none of which trusts the solver.
1. An exhaustive optimal oracle. verify.optimal_sum_of_costs runs A* over the joint configuration space — all agents moving simultaneously, one monolithic search. It has no constraint tree, no constraints, and no low level. It shares nothing with CBS but the grid.
Checking CBS against another CBS variant would share the very logic most likely to be wrong. This shares none of it. It is exponential in agent count and useless in practice, which is exactly what a test oracle should be: obviously correct, and too slow to be tempting anywhere else.
Cross-validated on 150 instances (2–3 agents, 5×5 to 7×7 grids, 25 seeds each): zero mismatches.
2. An independent validator. verify.validate recomputes legal moves from the grid and checks that agents start and end correctly, never enter obstacles, never teleport, and never conflict. It is tested by feeding it plans deliberately broken in each possible way — a validator that accepted everything would make the suite vacuous.
3. Validation inside the benchmark. Every solution produced during a benchmark sweep is validated before being recorded. An illegal plan shows up as a failure, never as an inflated success rate.
These are the ones that make a from-scratch CBS look correct while being wrong. Each has a named test.
Missing edge constraints. Two agents swapping cells across one timestep never share a cell, so a vertex-only conflict check reports success. The plan has them passing through one another. On the corridor scenario a vertex-only solver returns cost 8; the true optimum is 11.
Forgetting that finished agents still occupy space. An agent that reaches its goal does not vanish — it parks there for the rest of the plan. Comparing paths only up to their own lengths hides exactly the conflicts hardest to spot by inspection: an agent sitting on its goal, blocking a corridor another agent needs later. position_at extends every path indefinitely at its final cell.
Ignoring goal-hold constraints in the low level. If a vertex constraint forbids agent a from its goal at time 7, then a may not settle there at time 5 either — it would be sitting on a banned cell two steps later. Miss this and the solver appears to work, then loops forever whenever one agent's goal lies on another's only route: the low level keeps returning a path that violates the constraint just added, so the same conflict is rediscovered and branched on without end. ConstraintTable.earliest_goal_arrival is the fix.
Requires Python 3.10+. Instructions for Git Bash on Windows.
git clone https://github.com/femi-mapf/cbs-from-scratch.git
cd cbs-from-scratch
python -m venv .venv
source .venv/Scripts/activate # Git Bash on Windows
pip install -e ".[dev]"astar-grid is pulled automatically from GitHub as a declared dependency. It is reused rather than reimplemented, which is what guarantees CBS, EECBS and LaCAM consume byte-identical instances — the thing that makes their head-to-head comparison honest rather than approximate.
# Solve one instance, validate the plan
cbs solve --size 16 --agents 6 --seed 3
# Print the full plan and cross-check optimality against the oracle
cbs solve --size 8 --agents 3 --seed 1 --paths --verify-optimal
# Load a movingai.com scenario
cbs solve --scen benchmarks/den312d.scen --map benchmarks/den312d.map --agents 8
# Reproduce every table and figure above
cbs benchmark --size 16 --agents 4 6 10 --seeds 25 --out examplesExit codes: 0 solved and valid, 1 no solution, 2 bad instance, 3 validation failed, 4 disagreed with the oracle.
from cbs import random_instance, cbs, validate, optimal_sum_of_costs
instance = random_instance(size=16, num_agents=6, density=0.15, seed=3)
result = cbs(instance, time_limit_s=30)
print(result.summary())
# cost= 64 makespan= 14 ct_expanded= 2 ll_calls= 8 0.007s
assert validate(instance, result.paths)
assert result.cost == optimal_sum_of_costs(instance) # small instances onlynotebooks/cbs_walkthrough.ipynb takes the corridor-swap instance apart step by step: the low level, conflict detection, branching, replanning, and the full search. Every cell executes; it is run in CI.
pip install -e ".[notebook]"
jupyter notebook notebooks/cbs_walkthrough.ipynbOnly the constrained agent is replanned. A constraint binds exactly one agent, so every other path in the parent node is still valid. Replanning all of them would be correct and would multiply the innermost loop by the agent count for nothing.
Distance tables are computed once per instance. The low-level heuristic is the exact obstacle-aware distance to goal, from astar-grid's Dijkstra. It ignores other agents and constraints, so it never overestimates, and being exact for the relaxed problem it is the strongest admissible heuristic available without solving the real one. Manhattan distance would also be admissible and is what most tutorial implementations use; it is far weaker on any map with obstacles, and CBS multiplies that weakness across every node in the tree.
Constraints are indexed, not scanned. ConstraintTable hashes on (cell, timestep) and (from, to, timestep) and filters to one agent up front. Scanning a list instead makes the low level quadratic in constraint count, in the innermost loop of the whole algorithm.
Ties break on conflict count. Among equal-cost nodes, the one with fewer remaining conflicts is expanded first. Any tie-break is correct; this one is closer to a solution.
Wait is generated before moving. Among equal-f states this biases toward yielding right of way rather than taking long detours.
The horizon is a stated limitation. CBS is complete only over an unbounded time horizon. Any finite bound makes the implementation incomplete in principle, and this one uses a generous instance-scaled cutoff. A solver that hits it reports timeout, never unsolvable, so the distinction is never silently lost.
pytest # full suite with coverage gate
pytest -vv --no-cov # fast and verbose
ruff check src tests # lint
mypy # strict type check136 tests, 98.6% coverage. The build fails below 95%.
Highlights: CBS versus the exhaustive oracle across agent counts and seeds; the corridor swap solved via the alcove; head-on pairs in a bare corridor terminating rather than looping; timeouts distinguished from unsolvability; every low-level plan audited against its own constraints under randomised constraint sets; the validator tested against deliberately broken plans; and determinism across repeated runs.
| repository | status | role |
|---|---|---|
astar-grid |
complete | single-agent A*, instrumentation, benchmark I/O |
cbs-from-scratch |
complete | constraint tree, vertex/edge conflicts, optimal baseline |
eecbs-benchmark |
next | focal search, bounded suboptimality at w ∈ {1.1, 1.5, 2.0} |
lacam-python |
planned | configuration-space DFS with PIBT, anytime refinement |
inspection-mapf |
planned | 30-node pipeline benchmark, heterogeneous UAV battery, two-mode inspection |
MIT. See LICENSE.