Page 394 - Introduction to AI Robotics

377
11.1 Overview
spired much humorous discussion of the merits of the biological equivalent
of robot droppings and robots imitating animals that “mark” their territory
in the wild.) Other techniques attempted to match the raw sensor data to
an a priori map using interpretation trees or similar structures. One of the
many problems with these techniques is that the sensor data rarely comes in
a form amenable to matching against a map. Consider attempting to match
noisy sonar data to the layout of a room. In the end, the basic approach used
by most systems is to move a little, build up a small map, match the new map
to the last map, and merge it in, then merge the small map with the overall
map. The use of small, local maps for localization brings the process back
full circle to the need for good map-making methods.
Localization algorithms fall into two broad categories: iconic and feature-
based. Iconic algorithms appear to be the more popular in practice, in part
because they usually use an occupancy grid. Occupancy grids are a mech-
anism for fusing sensor data into a world model or map. Fusion is done
either following an algorithm provided by a formal theory of evidence, ei-
ther Bayesian or Dempster-Shafer, or by a popular quasi-evidential method
known as HIMM. Since occupancy grids fuse sensor data, the resulting map
does not contain as much sensor noise. Many Hybrid architectures also use
theoccupancy gridas a virtual sensor for obstacle avoidance.
The chapter first covers occupancy grids, which are also known as cer-
tainty and evidence grids. Since sonars are a popular range sensor for map-
ping and obstacle avoidance, the chapter next covers sonar sensor models
and the three methods for using sensor models to update a grid: Bayesian,
Dempster-Shafer, and HIMM. The Bayesian and Dempster-Shafer methods
can be used with any sensor, not just range from sonar. The comparison
of the three methods discusses practical considerations such as performance
and ease in tuning the method for a new environment. Iconic localization
is described next. It is useful for metric map building and generally uses
an occupancy grid-like structure. Feature-based localization, which is better
suited for topological map building, is discussed next. Feature-based meth-
ods have become popular with the advent of partially ordered Markov deci-
sion process (POMDP) methods to simplify reasoning about them; POMDPs
are outside the scope of this book but the basic localization strategy is pre-
sented. The chapter ends with a brief description of frontier and Voronoi
methods of using the data in an occupancy grid to direct exploration of an
unknown environment.