/Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph

Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph

Howie Choset and Joel Burdick
Journal Article, Carnegie Mellon University, The International Journal of Robotics Research, Vol. 19, No. 2, pp. 96 - 125, February, 2000

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


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 R3, but wherever possible, results are derived in Rm. 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.

BibTeX Reference
author = {Howie Choset and Joel Burdick},
title = {Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph},
journal = {The International Journal of Robotics Research},
year = {2000},
month = {February},
volume = {19},
number = {2},
pages = {96 - 125},