Parallel Evaluation of a Spatial Traversability Cost Function on GPU for Efficient Path Planning
Stephen Cossell, Jose Guivant
DOI: 10.4236/jilsa.2011.34022   PDF    HTML     6,926 Downloads   11,191 Views   Citations


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.

Share and Cite:

S. Cossell and J. Guivant, "Parallel Evaluation of a Spatial Traversability Cost Function on GPU for Efficient Path Planning," Journal of Intelligent Learning Systems and Applications, Vol. 3 No. 4, 2011, pp. 191-200. doi: 10.4236/jilsa.2011.34022.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] G. McComb and M. Predko, “Robot Builder’s Bonanza,” 3rd Editon, McGraw-Hill, Boston, 2006, pp. 654-656.
[2] 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.
[3] 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.
[4] 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
[5] D. Patterson, “The Trouble with Multicore,” IEEE Spectrum Magazine, Vol. 47, No. 7, July 2010.
[6] 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
[7] GPGPU, “GPGPU,” Accessed December 2010.
[8] nVidia Corporation, “GeForce GTX 480,” accessed December 2010.
[9] 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.
[10] G. R. Andrews, “Concurrent Programming: Principles and Practice,” The Benjamin/Cummings Publishing Company, 1991.
[11] 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.
[12] nVidia Corporation, “High Performance Computing—Supercomputing with Tesla GPUs,” accessed December 2010.
[13] M. Harris, “GPU Gems 2,” Addison-Wesley, April 2005.
[14] 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.
[15] 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
[16] J. Barraquand, B. Langlois and J.-C. Latombe, “Numerical Potential Field Techniques for Robot Path Planning,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 22, No. 2, March 1992, pp. 224-241. doi:10.1109/21.148426
[17] C. I. Connolly, J. B. Burns and R. Weiss, “Path Planning using Laplace’s Equation,” IEEE International Conference on Robotics and Automation, Cincinnati, May 1990, pp. 2102-2106.
[18] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269-271. doi:10.1007/BF01386390
[19] S.-H. Suh and K. G. Shin, “A Variational Dynamic Programming Approach to Robot-Path Planning with a Distance-Safety Criterion,” IEEE Journal of Robotics and Automation, Vol. 4, No. 3, June 1988, pp. 334-349. doi:10.1109/56.794
[20] J. Bruce, M. Veloso, “Real-Time Randomized Path Planning for Robot Navigation,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, December 2002, pp. 2383-2388.
[21] T. Furukawa, B. Lavis and H. F. Durrant-Whyte, “Parallel Grid-Based Recursive Bayesian Estimation using GPU for Real-Time Autonomous Navigation,” IEEE International Conference on Robotics and Automation, Anchorage, May 2010, pp. 316-321.
[22] R. Bellman, “The Theory of Dynamic Programming,” RAND Corporation, 1954.
[23] SGI, “OpenGL Shading Language,” Accessed February, 2011.
[24] nVidia Corporation, “CUDA Zone,” Accessed February, 2011.
[25] Advanced Micro Devices Inc, “ATI Stream Technology,” Accessed February 2011.
[26] Khronos Group, “OpenCL,” Accessed February 2011.
[27] M. Harris, “Mapping Computational Concepts to GPUs,” ACM SIGGRAPH, Los Angeles, July 2005.
[28] Mechatronics at UNSW, “UNSW Mechatronics YouTube Channel,” Accessed March 2011.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.