AAAI Publications, Fourth Annual Symposium on Combinatorial Search

Font Size: 
Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding
Guni Sharon, Roni Tzvi Stern, Meir Goldenberg, Ariel Felner

Last modified: 2011-07-05

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.

Full Text: PDF