The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

Sharon, Guni; Stern, Roni; Goldenberg, Mark; Felner, Ariel

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

The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

Guni Sharon, Roni Stern, Mark Goldenberg, Ariel Felner

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 662-666.

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

Abstract

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the previous state-of-the-art A*-based approach. Experimental results on various domains show the benefits and drawbacks of this approach. A speedup of up to 3 orders of magnitude was obtained in a number of cases.

Guni Sharon, Roni Stern, Mark Goldenberg, and Ariel Felner. 2011. The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 662–666. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-117

@inproceedings{ijcai2011p117,
  title     = {The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding},
  author    = {Sharon, Guni and Stern, Roni and Goldenberg, Mark and Felner, Ariel},
  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     = {662--666},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-117},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-117},
}

TY  - CPAPER
TI  - The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding
AU  - Sharon, Guni
AU  - Stern, Roni
AU  - Goldenberg, Mark
AU  - Felner, Ariel
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  - 662
EP  - 666
DO  - 10.5591/978-1-57735-516-8/IJCAI11-117
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-117
ER  -