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

摘要

This paper prescribes an incremental procedure to construct roadmaps of unknown environments. Recall that a roadmap is a ge- ometric structure that a robot uses to plan a path berween two points in an environment. If the robot knows the rondmap, then it knows the environment. Likewise, if the robot constructs the roadmap, then it has effectively explored the emvironment. This paper focuses on the hierarchical generalized Voronoi graph (HGVG), detailed in the companion paper in this issue. The incremental construction proce- dure 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.