Cloud RRT*: sampling cloud based RRT*

Abstract

We present a novel biased sampling technique, Cloud RRT, for efficiently computing high-quality collisionfreepaths, while maintaining the asymptotic convergence to the optimal solution. Our method uses samplingcloud for allocating samples on promising regions. Our sampling cloud consists of a set of spheres containing aportion of the C-space. Especially, each sphere projects to a collision-free spherical region in the workspace. Weinitialize our sampling cloud by conducting a workspace analysis based on the generalized Voronoi graph. We thenupdate our sampling cloud to refine the current best solution, while maintaining the global sampling distributionfor exploring understudied other homotopy classes. We have applied our method to a 2D motion planning problemwith 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.