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

DOI:

https://doi.org/10.1609/icaps.v31i1.15984

Keywords:

Multi-agent And Distributed Planning, Continuous State And Action Spaces Based Planning

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.
ICAPS-21 Proceedings Cover

Downloads

Published

2021-05-17

How to Cite

Walker, T. T., Sturtevant, N. R., Felner, A., Zhang, H., Li, J., & Kumar, T. K. S. (2021). Conflict-Based Increasing Cost Search. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 385-395. https://doi.org/10.1609/icaps.v31i1.15984

Issue

Vol. 31 (2021): Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling

Section

Main Track