| 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.