|
Abstract : |
Abstract: Applications such as robot programming, design for manufactur-ing, 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 e-goodness, expansiveness, and path clearance. While e-goodness allows us to study how well a probabilistic roadmap covers F, expansiveness and path clearance allow us to, |
