Research ArticleOpen AccessGoogle Scholar indexed
Parallel Evaluation of a Spatial Traversability Cost Function on GPU for Efficient Path Planning
- 1
- 2
Journal of Intelligent Learning Systems and Applications·Volume 03 (2011)·Pages 191–200·Published 29 November 2011·DOI10.4236/jilsa.2011.34022
Copy link · social · email
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.
KeywordsGPGPUDynamic ProgrammingConcurrent ProgrammingPath Planning
- G. McComb and M. Predko, “Robot Builder’s Bonanza,” 3rd Editon, McGraw-Hill, Boston, 2006, pp. 654-656.
- M. Whitty, S. Cossell, K. S. Dang, J. Guivant and J. Katupitiya, “Autonomous Navigation Using a Real-Time 3D Point Cloud,” Australasian Conference on Robotics and Automation, Brisbane, December 2010.
- A. Robledo, J. Guivant and S. Cossell, “Pseudo Priority Queues for Real-Time Performance on Dynamic Programming Processes Applied to Path Planning,” Australasian Conference on Robotics and Automation, Brisbane, December 2010.
- A. Elfes, “Using Occupancy Grids for Mobile Robot Perception and Navigation,” Computer, Vol. 22, No. 6, June 1989, pp. 46-57. doi:10.1109/2.30720
- D. Patterson, “The Trouble with Multicore,” IEEE Spectrum Magazine, Vol. 47, No. 7, July 2010.
- P. F. Gorder, “Multicore Processors for Science and Engineering,” Computing in Science and Engineering, Vol. 9, No. 2, April 2007, pp. 3-7. doi:10.1109/MCSE.2007.35
- GPGPU, “GPGPU,” Accessed December 2010. http://gpgpu.org/about
- nVidia Corporation, “GeForce GTX 480,” accessed December 2010. http://www.nvidia.com/object/product_geforce_gtx_480_us.html
- J. Fung and S. Mann, “Openvidia: Parallel GPU Computer Vision,” Proceedings of the 13th annual ACM International Conference on Multimedia, Singapore, November 2005, pp. 849-852.
- G. R. Andrews, “Concurrent Programming: Principles and Practice,” The Benjamin/Cummings Publishing Company, 1991.
- K. Fatahalian, J. Sugerman and P. Hanrahan, “Understanding the Efficiency of GPU Algorithms for Matrix-Matrix Multiplication,” Proceedings of the ACM SIGRAPH/EU- ROGRAHICS Conference on Graphics Hardware, Greno- ble, August 2004, pp. 133-137.
- nVidia Corporation, “High Performance Computing—Supercomputing with Tesla GPUs,” accessed December 2010. http://www.nvidia.com/object/tesla_computing_solutions.html
- M. Harris, “GPU Gems 2,” Addison-Wesley, April 2005.
- L. Magni, G. De Nicolao, L. Magnani and R. Scattolini, “A Stablizing Model-Based Predictive Control Algorithm for Nonlinear Systems,” Automatica, Vol. 37, No. 9, September 2001, pp. 1351-1362.
- Y. K. Hwang and N. Ahuja, “A Potential Field Approach to Path Planning,” IEEE Transactions on Robotics and Automation, Vol. 8, No. 1, May 1989, pp. 23-32. doi:10.1109/70.127236