AAAI Publications, Workshops at the Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
A* Variants for Optimal Multi-Agent Pathfinding
Meir Goldenberg, Ariel Felner, Roni Stern, Guni Sharon, Jonathan Schaeffer

Last modified: 2012-07-15


Several variants of A* have been recently proposed for find-ing optimal solutions for the multi-agent pathfinding (MAPF)problem. However, these variants have not been deeply com-pared either quantitatively or qualitatively. In this paper weaim to fill this gap. In addition to obtaining a deeper under-standing of the existing algorithms, we describe in detail theapplication of the new enhanced partial-expansion techniqueto MAPF and show how pattern databases can be applied ontop of this technique.


Multi-agent pathfinding; partial-expansion; pattern databases

Full Text: PDF