Conflict-Based Increasing Cost Search
Conference Paper, Proceedings of 31th International Conference on Automated Planning and Scheduling (ICAPS '21), Vol. 31, pp. 385 - 395, May, 2021
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.
BibTeX
@conference{Walker-2021-131396,author = {Thayne Walker and Nathan R. Sturtevant and Han Zhang and Jiaoyang Li and Ariel Felner and T. K. Satish Kumar},
title = {Conflict-Based Increasing Cost Search},
booktitle = {Proceedings of 31th International Conference on Automated Planning and Scheduling (ICAPS '21)},
year = {2021},
month = {May},
volume = {31},
pages = {385 - 395},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.