ECBS with flex distribution for bounded-suboptimal Multi-Agent Path Finding

Shao Hung Chan, Jiaoyang Li, Graeme Gange, Daniel Harabor, Peter J. Stuckey, Sven Koenig

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

4 Citations (Scopus)

Abstract

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.

Original languageEnglish
Title of host publicationProceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS 2021)
EditorsHang Ma, Ivan Serina
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages159-161
Number of pages3
ISBN (Electronic)9781713834557, 9781577358701
Publication statusPublished - 2021
EventInternational Symposium on Combinatorial Search 2021 - Online, Guangzhou, China
Duration: 26 Jul 202130 Jul 2021
Conference number: 14th
https://ojs.aaai.org/index.php/SOCS (Proceedings)

Publication series

Name14th International Symposium on Combinatorial Search, SoCS 2021
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume1
ISSN (Electronic)12

Conference

ConferenceInternational Symposium on Combinatorial Search 2021
Abbreviated titleSoCS 2021
Country/TerritoryChina
CityGuangzhou
Period26/07/2130/07/21
Internet address

Cite this