Lazy Toggle PRM: A single-query approach to motion planning

Citations Over TimeTop 20% of 2013 papers

Abstract

Probabilistic RoadMaps (PRMs) are quite successful in solving complex and high-dimensional motion planning problems. While particularly suited for multiple-query scenarios and expansive spaces, they lack efficiency in both solving single-query scenarios and mapping narrow spaces. Two PRM variants separately tackle these gaps. Lazy PRM reduces the computational cost of roadmap construction for single-query scenarios by delaying roadmap validation until query time. Toggle PRM is well suited for mapping narrow spaces by mapping both C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">free and C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">obst , which gives certain theoretical benefits. However, fully validating the two resulting roadmaps can be costly. We present a strategy, Lazy Toggle PRM, for integrating these two approaches into a method which is both suited for narrow passages and efficient single-query calculations. This simultaneously addresses two challenges of PRMs. Like Lazy PRM, Lazy Toggle PRM delays validation of roadmaps until query time, but if no path is found, the algorithm augments the roadmap using the Toggle PRM methodology. We demonstrate the effectiveness of Lazy Toggle PRM in a wide range of scenarios, including those with narrow passages and high descriptive complexity (e.g., those described by many triangles), concluding that it is more effective than existing methods in solving difficult queries.

Related Papers

• → An Incremental Harmonic Function-based Probabilistic Roadmap Approach to Robot Path Planning(2006)20 cited
• → Path planning approach based on probabilistic roadmap for sensor based car-like robot in unknown environments(2005)11 cited
• An Obstacle-Based Probabilistic Roadmap Method For Path Planning(1996)
• Study on Path Planning for UAV Based on Probabilistic Roadmap Method(2006)
• Grid roadmap based real time path planning(2011)