Multiple query probabilistic roadmap planning using single query planning primitives

We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner, which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.

Authors

• Kostas E. Bekris
• Brian Y. Chen
• Andrew M. Ladd
• Erion Plaku
• Lydia E. Kavraki

Keywords

• Robots
• Motion planning
• Sampling methods
• Space exploration
• Switches
• Interpolation
• Computer science
• Layout
• Data structures
• Orbital robotics
• Single Query
• Multiple Queries
• Query Plan
• Urban Planning
• Path Planning
• Planning Problem
• Refinement Technique
• Rapidly-exploring Random Tree
• Rigid Robots
• Straight Line
• Running Time
• Bounding Box
• Bisection
• Nearest Neighbor Search
• Collision Detection
• Preprocessing Phase