Nested ECBS for Bounded-Suboptimal Multi-Agent Path Finding
Shao-Hung Chan, Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Graeme Gange, Liron Cohen and Sven Koenig.
IJCAI Workshop on Multi-Agent Path Finding (WoMAPF), 2020.
[bibtex] [pdf]
Abstract
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents on a map. Conflict-Based Search (CBS) is a powerful, complete, and optimal MAPF solver, while Enhanced CBS (ECBS) improves the efficiency of CBS by only guaranteeing a bounded-suboptimal solution. Both MAPF solvers suffer from the weakness of repeatedly resolving the same collisions between the same agents. Merging agents into meta-agents and planing their paths in the joint state space can be used to overcome this problem. However, a joint-state-space MAPF solver makes resolving collisions within meta-agents inefficient. In this paper, we therefore propose Nested ECBS (NECBS), a nested architecture based on ECBS, where collisions within meta-agents are resolved with ECBS. NECBS preserves the important properties of ECBS, namely its completeness and bounded-suboptimality. Empirically, NECBS has a higher success rate than ECBS and its state-of-the-art variants for a runtime limit of 5 minutes.