GPU-based dynamic search on adaptive resolution grids

Francisco M. Garcia, Mubbasir Kapadia, Norman I. BadlerICRA 2014 · OpenReview

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 (> 2048 m2) 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.
BibTeX
@inproceedings{garcia2014gpu,
  author = {Francisco M. Garcia and Mubbasir Kapadia and Norman I. Badler},
  title = {{GPU-based dynamic search on adaptive resolution grids}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2014},
  url = {https://openreview.net/forum?id=eEKkrcEoGo},
}

Loading related content...

Figure