This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via HighWire Citing Articles via Web of Science (24) Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Choset, H. Articles by Burdick, J. Search for Related Content Social Bookmarking                         What's this?

Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph

Carnegie Mellon University, Scaife Hall, Pittsburgh, Pennsylvania 15213 USAchoset{at}cs.cmu.edu

Joel Burdick

California Institute of Technology, Mail Code 104-44, Pasadena, California 91125 USA

The hierarchical generalized Voronoi graph (HGVG) is a new roadmap developed for sensor-based exploration in unknown environments. This paper defines the HGVG structure: a robot can plan a path between two locations in its work space or configuration space by simply planning a path onto the HGVG, then along the HGVG, and finally from the HGVG to the goal. Since the bulk of the path planning occurs on the one-dimensional HGVG, motion planning in arbitrary dimensioned spaces is virtually reduced to a one-dimensional search problem. A bulk of this paper is dedicated to ensuring the HGVG is sufficient for motion planning by demonstrating the HGVG (with its links) is an arc-wise connected structure. All of the proofs in this paper that lead toward the connectivity result focus on a large subset of spaces in R³, but wherever possible, results are derived in R^m. In fact, under a strict set of conditions, the HGVG (the GVG by itself) is indeed connected, and hence sufficient for motion planning. The chief advantage of the HGVG is that it possesses an incremental construction procedure, described in a companion paper, that constructs the HGVG using only line-of-sight sensor data. Once the robot constructs the HGVG, it has effectively explored the environment, because it can then use the HGVG to plan a path between two arbitrary configurations.

Key Words: sensor-based exploration • skeletons • roadmap • Voronoi diagrams • motion planning

The International Journal of Robotics Research, Vol. 19, No. 2, 96-125 (2000)
DOI: 10.1177/02783640022066770


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?

This article has been cited by other articles:

				B. Barshan Directional Processing of Ultrasonic Arc Maps and its Comparison with Existing Techniques The International Journal of Robotics Research, August 1, 2007; 26(8): 797 - 820. [Abstract] [PDF]

				R. Geraerts and M. H. Overmars Creating High-quality Paths for Motion Planning The International Journal of Robotics Research, August 1, 2007; 26(8): 845 - 863. [Abstract] [PDF]

				J. Y. Lee and H. Choset Sensor-based Planning for a Rod-shaped Robot in Three Dimensions: Piecewise Retracts of R3 x S2 The International Journal of Robotics Research, May 1, 2005; 24(5): 343 - 383. [Abstract] [PDF]

				H. Choset and J. Burdick Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph The International Journal of Robotics Research, February 1, 2000; 19(2): 96 - 125. [Abstract] [PDF]