High-dimensional Planning on the GPU

May 2010

High-dimensional Planning on the GPU

Authors:

Joseph T. Kider Jr., Mark Henderson, Maxim Likhachev, and Alla Safonova
Conference Paper
Proceedings of (ICRA) International Conference on Robotics and Automation

Abstract:

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 the 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 a 6DOF robot arm planar as well as 2D path finding.
@conference{Kider-2010-109656,
author = {Joseph T. Kider Jr. And Mark Henderson And Maxim Likhachev And Alla Safonova},
title = {High-dimensional Planning on the GPU},
booktitle = {Proceedings of (ICRA) International Conference on Robotics and Automation},
year = {2010},
month = {May},
pages = {2515 - 2522},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.