Multiple query probabilistic roadmap planning using single query planning primitives

We propose the 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 al-gorithms, we obtain a multiple query planner which is significantly faster and more reliable than its compo-nent parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the per-formance differences are most notable in planning instances with several rigid non-convex robots in a scene with narrow passages. This planner is in the spirit of non-uniform sampling and refinement tech-niques used in earlier work on PRM.