K. E. Bekris, B. Y. Chen, A. M. Ladd, E. Plaku, and L. E. Kavraki, “Multiple Query Probabilistic Roadmap Planning Using Single Query Planning Primitives,” in 2003 IEEE/RJS International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, 2003, pp. 656–661.
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 BIRRT 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 BIRRT techniques and obtains the advantages of both. We observed that the performance 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 techniques used in earlier work on PRM.
Publisher: http://dx.doi.org/10.1109/IROS.2003.1250704
PDF preprint: http://kavrakilab.org/publications/bekris-chen2003multiple-query-probabilistic.pdf