The Increasing Cost Tree Search for Optimal Multi-agent Pathfinding
Guni Sharon, Ron Zvi Stern, Meir Goldenberg and Ariel Felner
We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost is 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 increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the traditional A* search formalization. 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.