Iterative-deepening Conflict-Based Search

Eli Boyarski, Ariel Felner, Daniel Harabor, Peter J. Stuckey, Liron Cohen, Jiaoyang Li, Sven Koenig

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

Abstract

Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF). CBS variants typically compute MAPF solutions using some form of A* search. However, they often do so under strict time limits so as to avoid exhausting the available memory. In this paper, we present IDCBS, an iterative-deepening variant of CBS which can be executed without exhausting the memory and without strict time limits. IDCBS can be substantially faster than CBS due to incremental methods that it uses when processing CBS nodes.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
EditorsChristian Bessiere
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages4084-4090
Number of pages7
ISBN (Electronic)9780999241165
DOIs
Publication statusPublished - 2020
EventInternational Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020 - Yokohama, Japan
Duration: 7 Jan 202115 Jan 2021
Conference number: 29th/17th
https://www.ijcai.org/Proceedings/2020/ (Proceedings)
https://ijcai20.org (Website)

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume2021-January
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020
Abbreviated titleIJCAI-PRICAI 2020
CountryJapan
CityYokohama
Period7/01/2115/01/21
OtherIJCAI-PRICAI 2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence!IJCAI-PRICAI2020 will take place January 7-15, 2021 online in a virtual reality in Japanese Standard Time (JST) zone.
Internet address

Keywords

  • Planning and Scheduling
  • Agent-based and Multi-agent Systems
  • Multi-agent Planning
  • Heuristic Search and Game Playing
  • Heuristic Search

Cite this