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

February 2021

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

Authors:

Jiaoyang Li, Wheeler Ruml, and Sven Koenig

Abstract:

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.
@conference{Li-2021-131397,
author = {Jiaoyang Li And Wheeler Ruml And Sven Koenig},
title = {EECBS: Bounded-Suboptimal Search for Multi-Agent Path Finding},
booktitle = {Proceedings of 35th AAAI Conference on Artificial Intelligence (AAAI '21)},
year = {2021},
month = {February},
pages = {12353 - 12362},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.