Page 374 - Introduction to AI Robotics

357
10.3 Cspace Representations

Figure 10.5 Graph from a generalized Voronoi graph (GVG). (Graph courtesy of
Howie Choset.)

complex. But more importantly, it uses artifacts of the map to determine the
polygon boundaries, rather than things which can be sensed. Unless the ro-
bot has accurate localization, how does it know it is halfway down a long,

featureless hall and should turn 30 ? The third major disadvantage is that
it is unclear how to update or repair the diagrams as the robot discovers
discrepancies between the a priori map and the real world.

10.3.2 Generalized Voronoi graphs

GENERALIZED Generalized Voronoi Graphs,or GVGs, are a popular mechanism for represent-
VORONOI GRAPHS ing Cspace and generating a graph. Unlike a meadow map, a GVG can be
constructed as the robot enters a new environment, thereby creating a topo-
logical map as shown by Howie Choset at CMU. 36
VORONOI EDGE The basic idea of a GVG is to generate a line, called a Voronoi edge, equidis-
tant from all points. As seen in Fig. 10.5, this line goes down the middle of
hallways and openings. The point where many Voronoi edges meet is known
as a Voronoi vertex. Notice the vertices often have a physical correspondence
to configurations that can be sensed in the environment. This makes it much
easier for a robot to follow a path generated from a GVG, since there is an
implicit local control strategy of staying equidistant from all obstacles.
If the robot follows the Voronoi edge, it will not collide with any modeled
obstacles, because it is staying “in the middle.” This obviates the need to
grow the obstacle boundaries. Edges serve as freeways or major thorough-