EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

Jiaoyang Li; Wheeler Ruml; Sven Koenig

Source-linked AI summary

EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

Jiaoyang Li, Wheeler Ruml, Sven Koenig

arXiv:2010.01367v2Oct 3, 2020cs.AIcs.MAcs.RO

TL;DR

MAPF requires collision-free, low-cost paths for many agents, while optimal search can be difficult to scale. The paper proposes EECBS, which combines online inadmissible cost estimation with Explicit Estimation Search, and adapts CBS improvements to it. With these improvements, EECBS significantly outperforms competing bounded-suboptimal algorithms and solves large instances with near-optimal guarantees.

Problem
Optimal MAPF search is NP-hard, while applications may require coordinating hundreds of agents with limited computational resources.
Method
EECBS uses online learning for potentially inadmissible solution-cost estimates and Explicit Estimation Search to select high-level CBS nodes, while adapting several CBS improvements.
Results
EECBS with the improvements significantly outperforms ECBS, BCP-7, and eMDD-SAT on bounded-suboptimal MAPF benchmarks.
Takeaways & Limitations
Within one minute, EECBS finds solutions provably at most 2% worse than optimal for large instances with up to 1,000 agents.
Takeaways & Limitations
The paper focuses on a MAPF variant with vertex and swapping conflicts, stay-at-target behavior, and sum-of-costs optimization.

Abstract

from arXiv · show

Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a leading two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.

1 Introduction

MAPF seeks collision-free, low-cost paths for teams of agents, but optimal solving is computationally difficult at application scale. EECBS addresses this need with inadmissible estimates and Explicit Estimation Search, and its improvements outperform competing bounded-suboptimal methods.

Motivation: MAPF finds collision-free paths for agents in known environments while minimizing the sum of travel times.The problem is motivated by applications including warehouse logistics, airport operations, UAV traffic management, valet parking, and video games.
Prior methods: CBS optimally solves MAPF using two-level search that independently plans paths and branches on collisions between agents.ECBS instead uses focal search to guarantee solution costs within a user-specified factor of optimal.
Motivation: Optimal MAPF solving is NP-hard, motivating bounded-suboptimal solutions that reduce search runtime for large teams under limited computational resources.The introduction specifically highlights coordination of hundreds of agents as an application requirement.
EECBS: EECBS uses online learning to estimate solution costs below high-level nodes and Explicit Estimation Search to select nodes for expansion.It is a bounded-suboptimal variant of CBS that replaces focal search at the high level.
Results: EECBS with adapted CBS improvements runs significantly faster than ECBS, BCP-7, and eMDD-SAT across MAPF instances.The paper reports that the combination of improvements performs best empirically.

2 Preliminaries

The preliminaries define MAPF and CBS, then describe CBS improvements and ECBS’s bounded-suboptimal focal-search framework. These components establish the search structures, heuristics, and mechanisms that EECBS later modifies.

MAPF: MAPF uses vertex and swapping conflicts, the stay-at-target assumption, and sum-of-costs optimization.Agents move or wait on a graph, remain at goals after completion, and require conflict-free paths.
Vanilla CBS: CBS searches a binary constraint tree whose nodes store agent constraints and corresponding paths.The root has no constraints and shortest paths; high-level expansion resolves conflicts by adding constraints and replanning with A*.
Vanilla CBS: CBS preserves completeness and optimality by exploring alternative conflict resolutions with best-first search at both levels.Each child prohibits one conflicting agent from using the vertex or edge at the relevant timestep.
CBS improvements: Bypassing conflicts replaces a node’s paths when equal cost and fewer conflicts are achieved, otherwise CBS splits the node normally.The technique often produces smaller constraint trees and decreases search effort.
CBS improvements: Conflict prioritization resolves cardinal conflicts before semi-cardinal and non-cardinal conflicts to improve the constraint-tree lower bound faster.Conflict cardinality is determined using agents’ Multi-Valued Decision Diagrams.
CBS improvements: Symmetry reasoning avoids repeatedly resolving conflicts caused by symmetric paths, while the WDG heuristic supplies an admissible high-level estimate.WDG can reduce constraint-tree size despite the overhead of graph construction and minimum vertex-cover computation.
ECBS: ECBS uses focal search with factor w at both levels, combining admissible cost bounds with secondary distance-to-go or conflict heuristics.Its high-level FOCAL contains nodes satisfying cost(N) ≤ w·lb(bestlb), while the low level minimizes conflicts among bounded-suboptimal paths.

3 Explicit Estimation CBS (EECBS)

EECBS replaces ECBS’s high-level focal search with Explicit Estimation Search and online-learned, potentially inadmissible cost estimates. On benchmark instances, EECBS improves runtime and success rate over ECBS, with larger gains at smaller suboptimality factors.

Explicit Estimation CBS (EECBS): EECBS replaces high-level focal search with EES and uses online learning to estimate each CT node’s potential solution cost without preprocessing.Its high-level estimate is ˆf(N) = cost(N) + ˆh(N), where ˆh(N) is learned from instance-specific search errors.
Limitations of ECBS: ECBS can inefficiently expand high-level nodes because its focal search considers distance-to-go while ignoring solution costs below selected nodes.This behavior can repeatedly pursue branches whose eventual solution costs exceed the suboptimality bound.
Limitations of ECBS: ECBS’s lower bound rarely increases because many CT nodes share similar costs, keeping CLEANUP nodes from being selected until FOCAL is nearly empty.When the optimum lies outside the initial suboptimality bound, this can hinder timely discovery of an acceptable solution.
Explicit Estimation CBS (EECBS): EECBS maintains CLEANUP, OPEN, and FOCAL lists and selects nodes using estimated cost, conflict-based distance-to-go, and the lower bound while preserving bounded suboptimality.It selects the best hc node when cost(besthc) ≤ w · lb(bestlb), otherwise the best estimated-cost or lower-bound node under the corresponding test.
Evaluation: EECBS has smaller runtime and larger success rate than ECBS, and its improvement increases as the suboptimality factor w decreases.The evaluation uses 200 MAPF instances, a one-minute time limit, and suboptimality factors from 1.02 to 1.20.
Explicit Estimation CBS (EECBS): EECBS’s learned heuristic is linear in the number of conflicts, so nodes with more conflicts can receive higher estimated potential cost increments.The heuristic is constructed from one-step errors for CT-node distance and cost functions.

4 Bringing CBS Improvements to EECBS

EECBS adapts several CBS improvements, including bypassing conflicts, conflict prioritization, symmetry reasoning, and an adaptive WDG heuristic, while preserving bounded suboptimality. Experiments report performance gains from these adaptations, with adaptive WDG reducing computation time while maintaining similar lower-bound improvements.

EECBS incorporates CBS improvements incrementally and evaluates each technique by adding it to the best EECBS version so far.
4.1 Bypassing Conflicts: Relaxed bypassing accepts more bypasses than standard CBS bypassing and improves EECBS performance across all tested w values and agent counts.The improvement generally increases as w increases.
4.2 Prioritizing Conflicts: EECBS prioritizes cardinal, semi-cardinal, non-cardinal, and unclassified conflicts in that order, applying classification selectively to limit MDD overhead.Conflict prioritization improves performance, and classification is used when CLEANUP selection or path-cost lower-bound conditions make it useful.
4.3 Symmetry Reasoning: EECBS applies rectangle symmetry reasoning only when both paths are provably shortest, while applying corridor and target symmetry reasoning to all conflicts.The symmetry reasoning technique significantly improves EECBS performance.
4.4 WDG Heuristic: The adapted WDG heuristic remains admissible because opt(N) + h_WDG(N) lower-bounds the minimum solution cost below CT node N.This lower bound supports sorting CLEANUP and computing the lower bound used by EECBS.
4.4 WDG Heuristic: Adaptive WDG obtains similar lower-bound improvements while spending less time computing the WDG heuristic than the standard approach.Adaptive WDG computes the expensive heuristic only for CLEANUP-selected CT nodes and the root, rather than for all CT nodes.

5 Empirical Evaluation

Across six maps and varied agent counts, EECBS+ significantly outperforms the compared bounded-suboptimal algorithms in runtime and success rate, while preserving solution quality relative to ECBS.

Overall comparison: For a given success rate, EECBS+ solves instances with up to twice the number of agents as ECBS on map den520d.
Effect of improvements: EECBS+ benefits more than ECBS from the four improvements, producing the strongest overall performance among the evaluated algorithms.Without the improvements, EECBS outperforms ECBS on some maps but is similar or slightly worse on others.
Solution quality: Across 1,081 jointly solved random-map instances, average solution costs are 1,967 for ECBS and 1,958 for EECBS+.The authors report that EECBS+ never fails to solve an instance solved by ECBS and does not sacrifice solution quality in this comparison.
Overall comparison: EECBS+ significantly outperforms ECBS, BCP-7, and eMDD-SAT on all six maps in runtime and success rate.The evaluation uses six maps, eight agent counts per map, 25 random instances per setting, and ten suboptimality factors.

6 Conclusion

The paper proposes EECBS, which combines online cost estimation with Explicit Estimation Search for high-level node selection, and extends it with four CBS improvements. The resulting system significantly outperforms state-of-the-art bounded-suboptimal MAPF algorithms and scales to large instances with near-optimal guarantees.

EECBS uses online learning to estimate solution costs below high-level nodes and EES to select nodes for expansion.
Adding conflict bypassing, conflict prioritization, symmetry reasoning, and the WDG heuristic further improves EECBS.
With these improvements, EECBS significantly outperforms ECBS, BCP-7, and eMDD-SAT.
Within one minute, EECBS finds solutions at most 2% worse than optimal for large instances with up to 1,000 agents.On the same map, state-of-the-art optimal algorithms handle at most 200 agents.