Abstract

This paper presents a GPU-based wave-front propagation technique for multi-agent path planning in extremely large, complex, dynamic environments. Our work proposes an adaptive subdivision of the environment with efficient indexing, update, and neighbor-finding operations on the GPU to address several known limitations in prior work. In particular, an adaptive environment representation reduces the device memory requirements by an order of magnitude which enables for the first time, GPU-based goal path planning in truly large-scale environments for hundreds of agents with different targets. We compare our approach to prior work that uses an uniform grid on several challenging navigation benchmarks and report significant memory savings, and up to a 1000X computational speedup.

Related Articles

GPU-based Dynamic Search on Adaptive Resolution Grids

Francisco Garcia, Mubbasir Kapadia, and Norman I. Badler

IEEE International Conference on Robotics and Automation, June 2014
Bibtex

Videos

Download here