High-dimensional Planning on the GPU

Mark Henderson, Joseph T. Kider Jr., Maxim Likhachev, Alla Safonova
SIG Center for Computer Graphics, University of Pennsylvania
IEEE International Conference on Robotics and Automation (ICRA), 2010, p.2515-2522


   title={High-dimensional Planning on the GPU},

   author={Henderson, M. and Kider Jr, J.T. and Likhachev, M. and Safonova, A.},



Download Download (PDF)   View View   Source Source   



Optimal heuristic searches such as A* search are commonly used for low-dimensional planning such as 2D path finding. These algorithms however, typically do not scale well to high-dimensional planning problems such as motion planning for robotic arms, computing motion trajectories for non-holonomic robotic vehicles and motion synthesis for humanoid characters. A recently developed randomized version of A* search, called R* search, scales to higher-dimensional planning problems by trading off deterministic optimality guarantees of A* for probabilistic sub-optimality guarantees. In this paper, we show that in addition to its scalability, R* lends itself well to a parallel implementation. In particular, we demonstrate how R* can be implemented on GPU. On the theoretical side, the GPU version of R*, called R*GPU, preserves all the theoretical properties of R* including its probabilistic bounds on sub-optimality. On the experimental side, we show that R*GPU consistently produces lower cost solutions, scales better in terms of memory, and runs faster than R*. These results hold for both motion planning for 6DOF robot arm as well simple 2D path finding.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: