Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search
Conference Paper, Proceedings of 29th International Conference on Automated Planning and Scheduling (ICAPS '19), pp. 279 - 283, July, 2019
Abstract
Multi-Agent Path Finding (MAPF) is the planning problem of finding collision-free paths for a team of agents. We focus on Conflict-Based Search (CBS), a two-level tree-search state-of-the-art MAPF algorithm. The standard splitting strategy used by CBS is not disjoint, i.e., when it splits a problem into two subproblems, some solutions are shared by both subproblems, which can create duplication of search effort. In this paper, we demonstrate how to improve CBS with disjoint splitting and how to modify the low-level search of CBS to take maximal advantage of it. Experiments show that disjoint splitting increases the success rates and speeds of CBS and its variants by up to 2 orders of magnitude.
BibTeX
@conference{Li-2019-131431,author = {Jiaoyang Li and Daniel Harabor and Peter J. Stuckey and Hang Ma and Sven Koenig},
title = {Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search},
booktitle = {Proceedings of 29th International Conference on Automated Planning and Scheduling (ICAPS '19)},
year = {2019},
month = {July},
pages = {279 - 283},
}
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.