Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph
- 1 February 2000
- journal article
- other
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 19 (2), 126-148
- https://doi.org/10.1177/02783640022066789
Abstract
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.Keywords
This publication has 6 references indexed in Scilit:
- Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi GraphThe International Journal of Robotics Research, 2000
- An opportunistic global path plannerAlgorithmica, 1993
- Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithmsPublished by Office of Scientific and Technical Information (OSTI) ,1993
- A robot exploration and mapping strategy based on a semantic hierarchy of spatial representationsRobotics and Autonomous Systems, 1991
- A 'retraction' method for learned navigation in unknown terrains for a circular robotIEEE Transactions on Robotics and Automation, 1991
- A robust layered control system for a mobile robotIEEE Journal on Robotics and Automation, 1986