Published in

Springer, Lecture Notes in Computer Science, p. 330-340, 1998

DOI: 10.1007/3-540-64359-1_704

Kluwer, Combinatorial Optimization -Dordrecht-, p. 159-182, 1999

DOI: 10.1007/978-1-4613-3282-4_8

Links

Tools

Export citation

Search in Google Scholar

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

Journal article published in 1998 by David Hsu, Jean-Claude Latombe, Lydia E. Kavraki, Jean-Claude Latombel, Rajeev Motwani
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Red circle
Preprint: archiving forbidden
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

. Finding paths in high-dimensional gemetric spaces is a provably hard problem. Recently, a general randomized planning scheme has emerged as an e#ective approach to solve this problem. In this scheme, the planner samples the space at random and build a network of simple paths, called a probabilistic roadmap. This paper describes a basic probabilistic roadmap planner, which is easily parallelizable, and provides a formal analysis that explains its empirical success when the space satis- #es two geometric properties called #-goodness and expansiveness. 1 Introduction The path planing problem can be stated as follows: Given: # A geometric and kinematic model of a rigid or articulated object, called the robot, # A geometric model of the obstacles in the physical space where the robot operates, Find a path, i.e., a continuous sequence of collision-free con#gurations of the robot, connecting two arbitrary input con#gurations, called query con#gurations, whenever such a path...