Sampling-based Roadmap of Trees for Parallel Motion Planning

TitleSampling-based Roadmap of Trees for Parallel Motion Planning
Publication TypeJournal Article
Year of Publication2005
AuthorsPlaku, E, Bekris, KE, Chen, BY, Ladd, AM, Kavraki, LE
JournalIEEE Transactions on Robotics
Volume21
Start Page597-608
Date PublishedAugust 2005
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.

URLhttp://www.cs.rutgers.edu/~kb572/pubs/sampling_based_roadmap_of_trees.pdf
Refereed DesignationRefereed