Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding Conference Paper uri icon

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. In Sharon et. al. (2011), we introduced a novel two-level search algorithm framework for this problem. The high-level searches a novel search tree called increasing cost tree (ICT). The low-level performs a goal test on each ICT node. The new framework, called ICT search (ICTS), showed to run faster than the previous state-of-the-art A* approach by up to three orders of magnitude in many cases. In this paper we focus on the low-level of ICTS which performs the goal test. We introduce a number of optional pruning techniques that can significantly speed up the goal test. We discuss these pruning techniques and provide supporting experimental results.

published proceedings

  • Proceedings of the International Symposium on Combinatorial Search

author list (cited authors)

  • Sharon, G., Stern, R., Goldenberg, M., & Felner, A.

citation count

  • 0

complete list of authors

  • Sharon, Guni||Stern, Roni||Goldenberg, Meir||Felner, Ariel

publication date

  • December 2011