Improving Collaborative Pathfinding Using Map Abstraction

Nathan Sturtevant and Michael Buro

In this paper we combine recent pathfinding research on spatial abstractions, partial refinement, and space-time reserva- tions 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.