Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph

Howie Choset, Sean Walker, Kunnayut Eiamsa-Ard and Joel Burdick
Journal Article, Carnegie Mellon University, The International Journal of Robotics Research, Vol. 19, No. 2, pp. 126 - 148, February, 2000

View Publication

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.


This paper prescribes an incremental procedure to construct roadmaps of unknown environments. Recall that a roadmap is a geometric structure that a robot uses to plan a path between two points in an environment. If the robot knows the roadmap, then it knows the environment. Likewise, if the robot constructs the roadmap, then it has effectively explored the environment. This paper focuses on the hierarchical generalized Voronoi graph (HGVG), detailed in the companion paper in this issue. The incremental construction procedure of the HGVG requires only local distance sensor measurements, and therefore the method can be used as a basis for sensor-based planning algorithms. Simulations and experiments using a mobile robot with ultrasonic sensors verify this approach.

author = {Howie Choset and Sean Walker and Kunnayut Eiamsa-Ard and Joel Burdick},
title = {Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph},
journal = {The International Journal of Robotics Research},
year = {2000},
month = {February},
volume = {19},
number = {2},
pages = {126 - 148},
} 2017-09-13T10:46:24-04:00