Sensor-based exploration: Incremental construction of the hierarchical generalized Voronoi graph

This paper prescribes an incremental procedure to construct roadmaps of unk nown environments. Recall that a roadmap is a geometric structure that a ro bot 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 co nstructs the roadmap, then it has effectively explored the environment. Thi s paper focuses on the hierarchical generalized Voronoi graph (HGVG), detai led in the companion paper in this issue. The incremental construction proc edure of the HGVG requires only local distance sensor measurements, and the refore the method can be used as a basis for sensor-based planning algorith ms. Simulations and experiments using a mobile robot with ultrasonic sensor s verify this approach.