Complete Algorithms for Cooperative Pathfinding Problems

Standley, Trevor Scott; Korf, Richard E.

doi:10.5591/978-1-57735-516-8/IJCAI11-118

Complete Algorithms for Cooperative Pathfinding Problems

Trevor Scott Standley, Richard E. Korf

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 668-672.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-118

Abstract

Problems that require multiple agents to follow non-interfering paths from their current states to their respective goal states are called cooperative pathfinding problems. We present the first {complete algorithm for finding these paths that is sufficiently fast for real-time applications. Furthermore, our algorithm offers a trade-off between running time and solution quality. We then refine our algorithm into an anytime algorithm that first quickly finds a solution, and then uses any remaining time to incrementally improve that solution until it is optimal or the algorithm is terminated. We compare our algorithms to those in the literature and show that in addition to completeness, our algorithms offer improved solution quality as well as competitive running time.

Trevor Scott Standley, and Richard E. Korf. 2011. Complete Algorithms for Cooperative Pathfinding Problems. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 668–672. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-118

@inproceedings{ijcai2011p118,
  title     = {Complete Algorithms for Cooperative Pathfinding Problems},
  author    = {Standley, Trevor Scott and Korf, Richard E.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {668--672},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-118},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-118},
}

TY  - CPAPER
TI  - Complete Algorithms for Cooperative Pathfinding Problems
AU  - Standley, Trevor Scott
AU  - Korf, Richard E.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 668
EP  - 672
DO  - 10.5591/978-1-57735-516-8/IJCAI11-118
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-118
ER  -