Korea Advanced Institute of Science and Technology (KAIST)
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.
The left figure shows a set of 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 a posterior state with a computed path between the initial position (shown in the red box) and the goal (the green box).