Disjoint splitting for multi-agent path finding with conflict-based search

Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Ariel Felner, Hang Ma, Sven Koenig

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling
EditorsJ. Benton, Nir Lipovetzky, Eva Onaindia, David E. Smith, Siddharth Srivastava
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages279-283
Number of pages5
Volume29
Publication statusPublished - 5 Jul 2019
EventInternational Conference on Automated Planning and Scheduling 2019 - Berkeley, United States of America
Duration: 13 Jul 201915 Jul 2019
Conference number: 29th
https://icaps19.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2019
Abbreviated titleICAPS 2019
CountryUnited States of America
CityBerkeley
Period13/07/1915/07/19
Internet address

Cite this

Li, J., Harabor, D., Stuckey, P. J., Felner, A., Ma, H., & Koenig, S. (2019). Disjoint splitting for multi-agent path finding with conflict-based search. In J. Benton, N. Lipovetzky, E. Onaindia, D. E. Smith, & S. Srivastava (Eds.), Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (Vol. 29, pp. 279-283). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/3487