Page 436 - Introduction to AI Robotics

419
11.7 Localization
Once the score for all matches has been computed, the algorithm chooses
the pose with the best score. This (x;y; ) is declared the correct current
position of the robot on the global grid and is used to update the robot’s
odometry. The process then repeats.
A good example is the continuous localization component of the ARIEL
system 125 developed under the direction of Alan Schultz at the US Naval
Research Laboratory. ARIEL runs on Nomad 200 bases that have both sonar
and a structured light rangefinder for range detection, but can be used with
any type of sensor that returns range data that is fused into the occupancy
grids according to an appropriate sensor model.
The localization process is illustrated in Fig. 11.19c. The local occupancy
grid is called the Short-Term Perception Map, and it covers the area that
the robot can ideally sense; it is only about as large as the sensor coverage.
Fig. 11.19a shows an example of a short-term perception map generated by
the sonars in a large room. The grid is constructed by fusing range data with
a variant of the Bayesian combination method.
A second, global occupancy grid, the Long-Term Perception Map, repre-
sents the robot’s larger environment. It covers an area such as an entire room,
and is illustrated in Fig. 11.19b. In terms of updating, it serves as an a priori
map.
The robot’s odometry obtained from shaft encoders drifts with motion,
so the continuous localization process adapts the frequency of relocalization
with the distance traveled. More frequent localization reduces the amount
of motion between each attempt, which in turn reduces the odometric drift,
and fewer poses are needed to adequately cover the uncertainty in position,
which in turn decreases the computational effort.
As the robot moves, sensor data is obtained and fed into the Short-Term
Map. Every two feet (which corresponds to about 800 individual sensor read-
ings), the matching function estimates the possible choices k, and for each
pose compares the match between the mature Short-Term Map and the Long-
Term Map. The pose with the best fit is chosen, and the robot’s odometry is
updated.
Fig. 11.20 shows the results of using the ARIEL continuous localization and
mapping process to map a previously unknown environment (a 70-foot-long
hallway). ARIEL was able to reduce the errors in the final map (both the
dimensions of the hall and how well the maps lined up) by 75% compared
to maps generated by just shaft encoder localization.
But what if the environment is dynamic? After the Long-Term Map is
obtained, if a hallway is obstructed or a door is closed, the robot needs to