Publication

N. Sturtevant and M. Buro. Improving Collaborative Pathfinding using Map Abstraction. In Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE), pages 80-85, 2006.

Abstract: In this paper we combine recent pathfinding research on spatial abstractions, partial refinement, and space-time reservations to construct new collaborative pathfinding algorithms. We first present an enhanced version of WHCA* and then show how the ideas from WHCA* can be combined with PRA* to form CPRA*. These algorithms are shown to effectively plan trajectories for many objects simultaneously while avoiding collisions, as the original WHCA* does. These new algorithms are not only faster than WHCA* but also use less memory.

Download the paper in pdf.