Bounded-suboptimal CBS with Explicit Estimation Search, benchmarked against optimal CBS.
Third repository in the femi-mapf series. Builds on astar-grid and cbs-from-scratch.
cbs-from-scratch established that optimal CBS collapses under congestion: on 10×10 grids at 10% obstacle density, success fell from 100% at 8 agents to 5% at 20. The cost of that failure is not path quality — it is the exponential price of proving a cost optimal.
EECBS asks what happens if you stop insisting on proof. Accept any solution within a factor w of optimal, and spend the search effort chasing conflict-free plans rather than certifying lower bounds.
The answer, measured here: at 20 agents, optimal CBS solves 1 instance in 20. EECBS at w = 1.5 solves 20 in 20, and pays 2.5% extra cost to do it.
All numbers from eecbs benchmark. 10×10 grids, 10% obstacles, 20 seeds per agent count, 5 s limit.
| solver | agents | success | median ms | median ratio | cost vs optimal |
|---|---|---|---|---|---|
| CBS (optimal) | 8 | 20/20 | 6.8 | 1.000 | 1.000 |
| CBS (optimal) | 12 | 16/20 | 37.7 | 1.000 | 1.000 |
| CBS (optimal) | 16 | 5/20 | 441.2 | 1.000 | 1.000 |
| CBS (optimal) | 20 | 1/20 | 246.7 | 1.000 | 1.000 |
| EECBS w=1.1 | 16 | 17/20 | 100.9 | 1.059 | 1.011 |
| EECBS w=1.1 | 20 | 15/20 | 493.6 | 1.085 | 1.016 |
| EECBS w=1.5 | 16 | 20/20 | 42.6 | 1.075 | 1.017 |
| EECBS w=1.5 | 20 | 20/20 | 124.0 | 1.142 | 1.025 |
| EECBS w=2.0 | 20 | 20/20 | 91.8 | 1.159 | 1.025 |
Read the last two columns together. Median ratio is cost divided by the solver's own proven lower bound — what EECBS can certify without knowing the optimum. Cost vs optimal is the real penalty, computed only over instances both solvers finished, so it compares like with like.
At 20 agents, w = 1.5 turns a 5% success rate into 100% for 2.5% extra cost. At 16 agents it is 25% → 100% for 1.7%.
| w | worst ratio observed | slack unused |
|---|---|---|
| 1.1 | 1.099 | 0.1% |
| 1.5 | 1.426 | 5% |
| 2.0 | 1.419 | 29% |
Permitting 2× degradation does not produce 2× worse paths. The worst instance across the whole sweep came in at 1.419, and the median at 1.159. w is a ceiling the search rarely approaches — it functions as permission to stop proving, not as a quality target.
Note that w = 2.0's worst case (1.419) is marginally better than w = 1.5's (1.426). Once the bound is loose enough to stop constraining the search, further loosening changes little; the two explore almost identically.
Both are reported because a benchmark that only publishes wins is not a benchmark.
The CG heuristic builds MDDs to identify cardinal conflicts and computes a minimum vertex cover over them, producing a provably admissible bonus to the lower bound. It works — the bound tightens — but it does not pay for itself here:
| w | heuristic | solved | median ms | median LB |
|---|---|---|---|---|
| 1.1 | CG | 15/15 | 78.1 | 103 |
| 1.1 | none | 14/15 | 53.1 | 100 |
| 1.5 | CG | 15/15 | 29.6 | 102 |
| 1.5 | none | 15/15 | 19.7 | 102 |
The bound genuinely sharpens (103 vs 100 at w = 1.1, which is a stronger guarantee for the same w), and it converts one timeout into a solve. But MDD construction is two breadth-first sweeps per agent per node, and on instances this small that dominates. It would be dishonest to report the heuristic as a speed-up.
It is on by default because the tighter bound is the more defensible artefact; --no-heuristic turns it off, and both settings are tested for bound compliance.
EECBS's node selection maintains three lists. Counting which one each expansion came from:
| w | FOCAL | OPEN | CLEANUP |
|---|---|---|---|
| 1.00 | 643 | 4 | 22 |
| 1.10 | 82 | 0 | 0 |
| 1.50 | 35 | 0 | 0 |
| 2.00 | 30 | 0 | 0 |
At w = 1.0 the machinery matters: FOCAL is restricted to lower-bound nodes, so OPEN and CLEANUP fire to advance the bound. Loosen the bound and FOCAL is always populated and always within it, so the other two never win — at w ≥ 1.1 on these instances, this behaves as ECBS with an explicit lower bound rather than as full EES.
That is not a defect; it is what the selection rule should do. But it means the "explicit estimation" contribution is not what produces the speed-up in the table above. The focal-search low level is.
The guarantee is cost <= w * optimal, and it is checked against the optimal solver from cbs-from-scratch — an independent implementation, not a self-consistency check.
Cross-validated across w ∈ {1.0, 1.1, 1.5, 2.0} × {3, 5} agents × 8 seeds — 64 instances, zero violations, with three separate properties asserted on each:
cost <= w * optimal_cost— the bound itself.lower_bound <= optimal_cost— admissibility of the reported bound. Without this the guarantee would be vacuous: a solver could inflate its own lower bound and satisfycost <= w * lbwhile badly exceedingw * optimal.- The plan validates under
cbs.validate— legal moves, no conflicts, correct endpoints.
Separately, w = 1.0 returns exactly the optimal cost on every instance tested (30 checked, zero mismatches). That is the property that says focal search degenerates correctly: at w = 1.0 FOCAL admits only lower-bound nodes and the algorithm is CBS.
The benchmark harness re-checks every run as it goes and refuses to report a sweep containing any invalid plan or any bound violation.
From Li, Ruml and Koenig (2021):
Implemented. Explicit Estimation Search node selection over three lists; bounded-suboptimal focal search at the low level with a conflict-avoidance tie-break; the CG heuristic via exact minimum vertex cover on the cardinal conflict graph, with MDDs built to classify cardinality.
Not implemented. The WDG heuristic, symmetry reasoning (rectangle, target, corridor), and bypassing. These are further speed-ups; their absence costs runtime, never correctness or the bound.
One deliberate weakening: only vertex conflicts are classified as cardinal. Edge conflicts can be cardinal too, but establishing that requires MDD edge sets rather than levels. Omitting them makes the heuristic weaker, never inadmissible — the safe direction.
git clone https://github.com/femi-mapf/eecbs-benchmark.git
cd eecbs-benchmark
python -m venv .venv
source .venv/Scripts/activate # Git Bash on Windows
pip install -e ".[dev]"astar-grid and cbs-from-scratch install automatically from GitHub. Both must be public.
# Solve at a bound and compare against optimal CBS on the same instance
eecbs solve --size 16 --agents 12 --seed 3 -w 1.5 --compare-optimal
# Turn the CG heuristic off
eecbs solve --size 16 --agents 12 -w 1.5 --no-heuristic
# Reproduce every table and figure above
eecbs benchmark --size 10 --agents 8 12 16 20 --bounds 1.1 1.5 2.0 --seeds 20Exit codes: 0 solved and within bound, 1 no solution, 2 bad arguments, 3 validation failed, 4 bound violated.
from cbs import random_instance, validate
from eecbs import eecbs
instance = random_instance(size=16, num_agents=12, density=0.15, seed=3)
result = eecbs(instance, suboptimality=1.5)
print(result.summary())
# cost= 152 lb= 141 ratio=1.078 (w=1.50) ct= 4 0.031s
assert validate(instance, result.paths)
assert result.ratio <= 1.5Focal search is where the speed-up comes from. OPEN is ordered by f and its minimum is a valid lower bound; FOCAL holds nodes with f <= w * f_min, ordered by how many conflicts the partial path already has. Expanding from FOCAL steers toward paths that get in everyone's way least, while the admission rule caps how much detour that steering may cost.
The lower bound is returned, not inferred. The low level reports the true optimal cost under its constraints alongside the path it chose. The high level sums those, and the guarantee is stated against that sum. A solver that reported the returned path's own cost as the bound would satisfy cost <= w * lb trivially and guarantee nothing.
Lower bounds never regress. A child inherits max(child.lb, parent.lb). Constraints only ever make paths longer, so a child's true bound cannot be below its parent's; taking the max recovers precision lost when one agent's replan happens to report a looser figure.
The MVC fallback stays admissible. Minimum vertex cover is NP-hard. If branch-and-bound exhausts its budget the code returns a matching size — a lower bound on the cover — rather than the truncated search value, which could overestimate and silently break the guarantee. Tested directly.
A finished agent still occupies space. Occupancy reserves each agent's goal cell from its arrival time onward, not merely for the length of its path. Same class of bug as in cbs-from-scratch, same fix.
pytest # full suite with coverage gate
ruff check src tests
mypy122 tests, 95.7% coverage. The build fails below 95%.
Highlights: the bound checked against true optimal CBS at four values of w; w = 1.0 proven to recover optimality; lower-bound admissibility asserted separately from the bound itself; minimum vertex cover checked exactly against brute-force enumeration on six graph topologies; the MVC budget fallback proven not to overestimate; MDD levels verified singleton in corridors and wide in open terrain; cardinal, semi-cardinal and non-cardinal conflicts each classified; and the harness's own violation detectors tested by feeding them sabotaged runs.
| repository | status | role |
|---|---|---|
astar-grid |
complete | single-agent A*, instrumentation, benchmark I/O |
cbs-from-scratch |
complete | constraint tree, optimal baseline |
eecbs-benchmark |
complete | focal search, bounded suboptimality, EES |
lacam-python |
next | configuration-space DFS with PIBT, anytime refinement |
inspection-mapf |
planned | 30-node pipeline benchmark, heterogeneous UAV battery, two-mode inspection |
The next repository takes the other branch of Sturtevant's framing. CBS and EECBS both prove a lower bound and work upward. LaCAM finds a solution immediately and improves it — a different answer to the same congestion problem, and the one better suited to reactive inspection.
MIT. See LICENSE.