Capturing the Connectivity of High-Dimensional Geometric Spaces by Parallelizable Random Sampling Techniques

: Applications such as robot programming, design for manufacturing, animation of digital actors, rationale drug design, and surgical planning, require computing paths in high-dimensional geometric spaces, a provably hard problem. Recently, a general path-planning approach based on a parallelizable random sampling scheme has emerged as an effective approach to solve this problem. In this approach, the path planner captures the connectivity of a space F by building a probabilistic roadmap, a network of simple paths connecting points picked at random in F . This paper combines results previously presented in separate papers. It describes a basic probabilistic roadmap planner that is easily parallelizable, and it analyzes the performance of this planner as a function of how well F satisfies geometric properties called ffl-goodness, expansiveness, and path clearance. While ffl-goodness allows us to study how well a probabilistic roadmap covers F , expansiveness and path clearance allow us t..