Iterative-deepening Conflict-Based Search

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

doi:10.24963/ijcai.2020/565

Iterative-deepening Conflict-Based Search

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

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

18 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Editors	Christian Bessiere
Place of Publication	Marina del Rey CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	4084-4090
Number of pages	7
ISBN (Electronic)	9780999241165
DOIs	https://doi.org/10.24963/ijcai.2020/565
Publication status	Published - 2020
Event	International Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020 - Yokohama, Japan Duration: 7 Jan 2021 → 15 Jan 2021 Conference number: 29th/17th https://www.ijcai.org/Proceedings/2020/ (Proceedings) https://ijcai20.org (Website)

Publication series

Name	IJCAI International Joint Conference on Artificial Intelligence
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Volume	2021-January
ISSN (Print)	1045-0823

Conference

Conference	International Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020
Abbreviated title	IJCAI-PRICAI 2020
Country/Territory	Japan
City	Yokohama
Period	7/01/21 → 15/01/21
Other	IJCAI-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	https://www.ijcai.org/Proceedings/2020/ (Proceedings) https://ijcai20.org (Website)

Keywords

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

Access to Document

10.24963/ijcai.2020/565

330802887-oaFinal published version, 330 KB

Cite this

Boyarski, E., Felner, A., Harabor, D., Stuckey, P. J., Cohen, L., Li, J., & Koenig, S. (2020). Iterative-deepening Conflict-Based Search. In C. Bessiere (Ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (pp. 4084-4090). (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2021-January). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.24963/ijcai.2020/565

Boyarski, Eli ; Felner, Ariel ; Harabor, Daniel et al. / Iterative-deepening Conflict-Based Search. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. editor / Christian Bessiere. Marina del Rey CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2020. pp. 4084-4090 (IJCAI International Joint Conference on Artificial Intelligence).

@inproceedings{33690a05a9544ddb8b5607227c08c4b7,

title = "Iterative-deepening Conflict-Based Search",

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.",

keywords = "Planning and Scheduling, Agent-based and Multi-agent Systems, Multi-agent Planning, Heuristic Search and Game Playing, Heuristic Search",

author = "Eli Boyarski and Ariel Felner and Daniel Harabor and Stuckey, {Peter J.} and Liron Cohen and Jiaoyang Li and Sven Koenig",

year = "2020",

doi = "10.24963/ijcai.2020/565",

language = "English",

series = "IJCAI International Joint Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

pages = "4084--4090",

editor = "Christian Bessiere",

booktitle = "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence",

address = "United States of America",

note = "International Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020, IJCAI-PRICAI 2020 ; Conference date: 07-01-2021 Through 15-01-2021",

url = "https://www.ijcai.org/Proceedings/2020/, https://ijcai20.org",

}

Boyarski, E, Felner, A, Harabor, D , Stuckey, PJ, Cohen, L, Li, J & Koenig, S 2020, Iterative-deepening Conflict-Based Search. in C Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI International Joint Conference on Artificial Intelligence, vol. 2021-January, Association for the Advancement of Artificial Intelligence (AAAI), Marina del Rey CA USA, pp. 4084-4090, International Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020, Yokohama, Japan, 7/01/21. https://doi.org/10.24963/ijcai.2020/565

Iterative-deepening Conflict-Based Search. / Boyarski, Eli; Felner, Ariel; Harabor, Daniel et al.
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. ed. / Christian Bessiere. Marina del Rey CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2020. p. 4084-4090 (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2021-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Iterative-deepening Conflict-Based Search

AU - Boyarski, Eli

AU - Felner, Ariel

AU - Harabor, Daniel

AU - Stuckey, Peter J.

AU - Cohen, Liron

AU - Li, Jiaoyang

AU - Koenig, Sven

N1 - Conference code: 29th/17th

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Planning and Scheduling

KW - Agent-based and Multi-agent Systems

KW - Multi-agent Planning

KW - Heuristic Search and Game Playing

KW - Heuristic Search

UR - http://www.scopus.com/inward/record.url?scp=85097352213&partnerID=8YFLogxK

U2 - 10.24963/ijcai.2020/565

DO - 10.24963/ijcai.2020/565

M3 - Conference Paper

AN - SCOPUS:85097352213

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 4084

EP - 4090

BT - Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

A2 - Bessiere, Christian

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Marina del Rey CA USA

T2 - International Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020

Y2 - 7 January 2021 through 15 January 2021

ER -

Boyarski E, Felner A, Harabor D , Stuckey PJ, Cohen L, Li J et al. Iterative-deepening Conflict-Based Search. In Bessiere C, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Marina del Rey CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2020. p. 4084-4090. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2020/565

Iterative-deepening Conflict-Based Search

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this