Cloud RRT*: Sampling Cloud based RRT*

by Donghyuk Kim, Junghwan Lee and Sung-Eui Yoon
KAIST Tech. Report (CS-TR-2013-383)
(Will be presented at ICRA2014)

The left figure show sampling spheres computed by our GVG-based initialization in a 2D example. Blue and black lines are obstacles and Voronoi edges, respectively. The right figure shows updated sampling spheres with a computed path between the initial position (shown in the red box) and the goal (the green box);


We present a novel biased sampling technique, Cloud RRT, for efficiently computing high-quality collision-free paths, while maintaining the asymptotic convergence to the optimal solution. Our method uses sampling cloud for allocating samples on promising regions. Our sampling cloud consists of a set of spheres containing a portion of the C-space. In particular, each sphere projects to a collision-free spherical region in the workspace. We initialize our sampling cloud by conducting a workspace analysis based on the generalized Voronoi graph. We then update our sampling cloud to refine the current best solution, while maintaining the global sampling distribution for exploring understudied other homotopy classes. We have applied our method to a 2D motion planning problem with kinematic constraints, i.e., the Dubins vehicle model, and compared it against the state-of-the-art methods. We achieve better performance, up to three times, over prior methods in a robust manner.


Technical report (PDF, 141KB)
ICRA2014 Presentation slides (PDF, 6,135KB)
Video (MP4, 4,893KB)

Donghyuk Kim, Junghwan Lee and Sung-Eui Yoon
KAIST Tech. Report, CS-TR-2013-383
September, 2013

Dept. of Computer Science
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com