Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding

Proceedings of the International Symposium on Combinatorial Search, 4

Volume

Vol. 4 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search

Full Papers

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.

10.1609/socs.v2i1.18201