Lazy CBS: implict Conflict-Based Search using Lazy Clause Generation

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

Abstract

Conflict-based Search (CBS) is a effective approach to optimal multi-agent path finding. However, performance of CBS approaches degrade rapidly in highly-contended graphs with many agents. One of the reasons this occurs is that CBS does not detect independent subproblems; i.e. it can re-solve the same conflicts between the same pairs of agents up to exponentially many times, each time along a different branch. Constraint programming approaches with nogood learning avoid this kind of duplication of effort by storing nogoods that record the reasons for conflicts. This can exponentially reduce search in constraint programming. In this work, we present Lazy CBS, a new approach to multi-agent pathfinding which replaces the high-level solver of CBS with a lazily constructed constraint programming model with nogoods. We use core-guided depth-first search to explore the space of conflicts and we detect along each branch reusable nogoods which help to quickly identify feasible solutions. Our experiments show that Lazy CBS can significantly improve on the state-of-the-art for optimal MAPF problems under the sumof-costs metric, especially in cases where there exists significant contention.
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)
Pages155-162
Number of pages8
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

Gange, G., Harabor, D., & Stuckey, P. J. (2019). Lazy CBS: implict Conflict-Based Search using Lazy Clause Generation. 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. 155-162). Association for the Advancement of Artificial Intelligence (AAAI). https://aaai.org/ojs/index.php/ICAPS/article/view/3471