TITLE:
Parallel Evaluation of a Spatial Traversability Cost Function on GPU for Efficient Path Planning
AUTHORS:
Stephen Cossell, Jose Guivant
KEYWORDS:
GPGPU, Dynamic Programming, Concurrent Programming, Path Planning
JOURNAL NAME:
Journal of Intelligent Learning Systems and Applications,
Vol.3 No.4,
November
29,
2011
ABSTRACT: A parallel version of the traditional grid based cost-to-go function generation algorithm used in robot path planning is introduced. The process takes advantage of the spatial layout of an occupancy grid by concurrently calculating the next wave front of grid cells usually evaluated sequentially in traditional dynamic programming algorithms. The algorithm offers an order of magnitude increase in run time for highly obstacle dense worst-case environments. Efficient path planning of real world agents can greatly increase their accuracy and responsiveness. The process and theoretical analysis are covered before the results of practical testing are discussed.