Page 444 - Introduction to AI Robotics

11.8 Exploration
x_c = x_c/count 427
y_c = y_c/count

Once the centroid has been established, the robot can navigate either using
reactive move-to-goal and avoid-obstacle behaviors, plan a path and reac-
tively execute the path, or continuously replan and execute the path. Regard-
less, once the robot is at the frontier, the map is updated and new frontiers
may be discovered. These frontiers are then evaluated, a new one is chosen,
and the rest are stored.

11.8.2 Generalized Voronoi graph methods
Another method of deciding how to explore a space is to have the robot build
a reduced generalized Voronoi graph (GVG) as it moves through the world.
This method has been used extensively by Howie Choset. 35;34
To review Ch. 10, as the robot moves, it attempts to maintain a path that
places it equidistant from all objects it senses. Essentially, the robot tries to
move ahead but stay in the “middle” or at a tangent to surrounding objects.
This path is a GVG edge, the same as would be generated by decompos-
ing the space into a Voronoi graph. Generating and following the path is
straightforward to do with a behavior.
When the robot comes to a dead end or a gateway, there are multiple GVG
edges that the robot could follow. As shown in Fig. 11.23, dead ends produce
two GVG edges. But in this case, the robot can perceive that both of these
edges end at objects, so there is no reason to follow them. The robot can
then backtrack along the path it had been on, either to the start or to another
branch. If the robot encounters branches in the GVG edges, it can choose one
at random to follow.
Fig. 11.23 shows how the robot would explore the an area. For conve-
nience, the figure shows the entire GVG that would be drawn after the robot
had fully explored the area. The robot would begin by sensing the walls on
each side (without any recognition that it was in a hall). The sensed area is
shown in light gray. It would attempt to center itself between the walls while
moving perpendicular to the line of intersection. Eventually it reaches an in-
tersection. This creates two edges, neither of which appears to terminate at
an object. It arbitrarily chooses the left edge and saves the right. It does this
repeatedly, as seen in Fig. 11.23b. It continues up the hall until it comes to
the dead end. The robot then backtracks using the same edge behavior (stay
in the middle). It continues to favor exploring to the left until it comes to a