1. Sampling-based roadmap of trees for parallel motion planning
- Author
-
Plaku, Erion, Bekris, Kostas E., Chen, Brian Y., Ladd, Andrew M., and Kavraki, Lydia E.
- Subjects
Algorithm ,Algorithms -- Usage ,Robotics ,Road maps ,Probabilities - Abstract
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. Index Terms--Expansive space trees (EST), motion planning, parallel algorithms, probabilistic roadmap method (PRM), rapidly exploring random trees (RRT), roadmap, sampling-based planning, sampling-based roadmap of trees (SRT), tree.
- Published
- 2005