An Efficient Motion Planner Based on Random Sampling

An Efficient Motion Planner Based on Random Sampling

Abstract

In the first part of this lecture I will first give a general presentation of the Probabilistic Roadmap (PRM) approach to motion planning problems: motivation, algorithmic principles, and formal convergence results. This approach has proven an effective one to deal with problems involving many degrees of freedom and complex admissibility constraints (e.g., collision, visibility, stability, and kino-dynamic constraints). In the second part, I will describe in more detail a new, particularly efficient PRM planner that combines a single-query, bi-directional sampling strategy with a lazy collision-checking strategy that postpones collision-checking operations until they are absolutely needed. I will show a number of experimental results produced by this planner, including results with complex multi-robot systems. Finally, in the third part of the lecture, I will briefly present a number of applications of PRM planners, ranging from design for manucaturing, to surgical planning, to space robotics, to digital actors, to computational biology.