Page 442 - Introduction to AI Robotics

425
11.8 Exploration
readings will update the occupancy grid, reducing the amount and loca-
tion of unknown areas, and creating a new goal. Hughes and Murphy 105
showed that this move-to-unknown-area behavior was suitable for indoor
exploration and even localization. While the above behavior-oriented ap-
proaches are simple and easy to implement, they often are inefficient, espe-
cially when presented with two or more unexplored areas. Suppose a robot
has encountered a hallway intersection; how does it choose which area to
explore?
Two basic styles of exploration methods have emerged which rank unex-
plored areas and make rational choices: frontier-based and generalized Voronoi
graph methods. Both work well for indoor environments; it is less clear how
these work over large open spaces. Both use behaviors for navigation, but
are different in how they set the navigational goals. This section provides a
highly simplified overview of each method.

11.8.1 Frontier-based exploration

Frontier-based exploration was pioneered by Brian Yamauchi. 125 The ap-
proach assumes the robot is using a Bayesian occupancy grid (a Dempster-
Shafer grid can be used as well). As shown in Fig. 11.22, when a robot enters
a new area, there is a boundary between each area that has been sensed and
is open and the area that has not been sensed. (The boundary between occu-
pied areas and unknown areas are not interesting because the robot cannot
go through the occupied area to sense what is behind it.) There are two such
FRONTIER boundaries in Fig. 11.22; each of these lines form a frontier that should be
explored.
The choice of which frontier to be explored first can be made in a variety of
ways. A simple strategy is to explore the nearest frontier first. Another is to
explore the biggest frontier first. Since the world is unknown, the robot has
no way of knowing if upon reaching a big frontier it will discover a wall just
a meter away. This means that the robot might move across a room, briefly
explore one area, then return back to almost at its starting point, explore that
area, and then go to another place, and so on. In practice, this doesn’t happen
that often with indoor environments.
The size of the frontier can be measured by the number of edge cells. Every
cell in the occupancy grid that the boundary runs through is considered an
edge. If an edge “touches” an edge in one of its eight surrounding neighbors,
the edges are connected and form the line. In order to eliminate the effects of