Abstract
S.-H. Chan, J. Li, D. Harabor, P. Stuckey, G. Gange, L. Cohen and S. Koenig. Nested ECBS for Bounded-Suboptimal Multi-Agent Path Finding. In IJCAI-20 Workshop on Multi-Agent Path Finding, 2020.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.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.