HPRM: a hierarchical PRM

Author

Collins, Anne D. ; Agarwal, Pankaj K. ; Harer, John L.

Author_Institution

Dept. of Math., Stanford Univ., LA, USA

Volume

3

fYear

2003

fDate

14-19 Sept. 2003

Firstpage

4433

Abstract

We introduce a hierarchical variant of the probabilistic roadmap method for motion planning. By recursively refining an initially sparse sampling in neighborhoods of the obstacle boundary, our algorithm generates a smaller roadmap that is more likely to find narrow passages than uniform sampling. We analyze the failure probability and computation time, relating them to path length, path clearance, roadmap size, recursion depth, and a local property of the free space. The approach is general, and can be tailored to any variety of robots. In particular, we describe algorithmic details for a planar articulated arm.

Keywords

computational geometry; path planning; probability; robots; sampling methods; computational geometry; free space property; hierarchical probabilistic roadmap method; motion planning; narrow passages; obstacle boundary; path clearance; path length; planar articulated arm; probability; recursion depth; sparse sampling; uniform sampling; Computer science; Mathematics; Motion measurement; Motion planning; Motion-planning; Orbital robotics; Path planning; Robots; Sampling methods; Time measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on

ISSN

1050-4729

Print_ISBN

0-7803-7736-2

Type

conf

DOI

10.1109/ROBOT.2003.1242287

Filename

1242287