Page 445 - Introduction to AI Robotics

428
Localization and Map Making
11
dead end in the lower left, then backtracks as shown in Fig. 11.24a. The robot
continues to explore and backtrack until the entire area is covered, as shown
in Fig. 11.24b.

11.9 Summary

Map-making converts a local, or robot-centered, set of sensor observations
into a global map, independent of robot position. One of the most common
data structures used to represent metric maps is the occupancy grid. An occu-
pancy grid is a two dimensional array regular grid which represents a fixed
area in an absolute coordinate system. Grids have a high resolution, on the
order of 5-10 cm per grid element.
Greater accuracy is obtained in occupancy grids by fusing together multi-
ple uncertain sensor readings. Sensor fusion requires a sensor model for trans-
lating a sensor reading into a representation of uncertainty, and an update
rule for combining the uncertainty for a pair of observations. Bayesian meth-
ods use a probabilistic sensor model, representing uncertainty as probabilities
and updating with Bayes’ rule. Dempster-Shafer methods use a possibilis-
tic sensor model with Shafer belief functions combined by Dempster’s rule.
HIMM uses an ad hoc sensor model and update rule. HIMM is less accurate
and harder to tune, but requires significantly less computation than tradi-
tional implementations of Bayesian or Dempster-Shafer methods. Because
of the improvement due to sensor fusion, occupancy grids are often used for
obstacle avoidance, serving as a virtual sensor for reactive behaviors.
Producing a global map based in a fixed coordinate system requires local-
ization. In general, the more often the robot is able to localize itself, the more
accurate the map. However, localization is often computationally expensive
so it may not be run at the same update rate as reactive behaviors. Raw sen-
sor data, especially odometry, is imperfect and confounds the localization
and map-making process. Most techniques concurrently map and localize.
The two categories of localization methods are iconic and feature-based.Of
the two, iconic methods are better suited for metric map-making and occu-
pancy grids. They fit raw observations into the map directly. An example
is creating a local short-term occupancy grid from sonar readings, then after
three moves, matching that grid to the long-term occupancy grid.
Feature-based methods perform less well for metric map-making, but work
satisfactorily for topological map-making. Feature-based methods match
current observations to the map by matching features rather than raw sen-