AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Conference on Automated Planning and Scheduling, 31 > Book One

Conflict-Based Increasing Cost Search

Authors

Thayne T. Walker

University of Denver, Department of Computer Science Lockheed Martin Corporation


Nathan R. Sturtevant

Department of Computing Science, Alberta Machine Intelligence Institute (Amii), University of Alberta, Canada


Ariel Felner

Ben-Gurion University, Be'er-Sheva, Israel


Han Zhang

University of Southern California, Los Angeles, USA


Jiaoyang Li

University of Southern California, Los Angeles, USA


T. K. Satish Kumar

University of Southern California, Los Angeles, USA


Proceedings:

Book One

Volume

Issue:

Proceedings of the International Conference on Automated Planning and Scheduling, 31

Track:

Main Track

Downloads:

Download PDF

Abstract:

Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains.

DOI:

10.1609/icaps.v31i1.15984


ICAPS

Proceedings of the International Conference on Automated Planning and Scheduling, 31