Sampling-based Roadmap of Trees for Parallel Motion Planning
|Title||Sampling-based Roadmap of Trees for Parallel Motion Planning|
|Publication Type||Journal Article|
|Year of Publication||2005|
|Authors||Plaku, E, Bekris, KE, Chen, BY, Ladd, AM, Kavraki, LE|
|Journal||IEEE Transactions on Robotics|
|Date Published||August 2005|
This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampling-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.