AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding
Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner

Last modified: 2011-06-28


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.

Full Text: PDF