F-cardinal conflicts in conflict-based search

Eli Boyarski, Pierre Le Bodic, Daniel Harabor, Peter J. Stuckey, Ariel Felner

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

Abstract

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF) which features strong performance. In CBS, one conflict in a high-level node is resolved to generate two child nodes, until a node with no conflicts is found. Choosing the right conflict to resolve can greatly speed up the search. It is currently recommended to resolve cardinal conflicts first, resolving them yields two child nodes with a higher cost than the cost of their parent. However, since the recent addition of high-level heuristics to CBS, when resolving cardinal conflicts, the h-value of high-level child nodes often decreases by the same amount as their cost increases. This diminishes the effectiveness of the cardinal conflicts distinction. We propose an expanded categorization of conflicts into f-cardinal, g-cardinal, and non-cardinal. F-cardinal conflicts should be resolved first. Resolving f-cardinal conflicts generates child nodes with an increased f-value relative to their parent. We propose two methods for identifying f-cardinal conflicts. Finally, we demonstrate on standard benchmarks that choosing conflicts according to this expanded categorization increases the effectiveness of modern CBS.
Original languageEnglish
Title of host publicationProceedings of the Twelfth International Symposium on Combinatorial Search
EditorsDaniel Harabor, Mauro Vallati
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages123-124
Number of pages2
ISBN (Electronic)9781577358220
Publication statusPublished - 2020
EventInternational Symposium on Combinatorial Search 2020 - Vienna, Austria
Duration: 26 May 202028 May 2020
Conference number: 13th
https://aaai.org/ocs/index.php/SOCS/SOCS20/schedConf/presentations

Conference

ConferenceInternational Symposium on Combinatorial Search 2020
Abbreviated titleSoCS 2020
Country/TerritoryAustria
CityVienna
Period26/05/2028/05/20
Internet address

Cite this