Page 438 - Introduction to AI Robotics

421
11.7 Localization
be able to notice the change so that it can react accordingly. To allow this,
ARIEL has a map adaptation mechanism (the dashed lines in Fig. 11.19c).
After each localization, the Short-Term Map is integrated into the Long-
Term Map at the determined pose using Bayes’ rule. Changes in the envi-
ronment sensed by the robot and put into the Short-Term Perception Map
therefore make their way into the Long-Term Map, where they can be used
for improved localization (e.g. when a box shows up in a previously feature-
less hallway) and planning (e.g. planning a path to a goal via another route).
In this way, the robot maintains its ability to stay localized despite changes
in the environment while adding the ability to react to those changes.
Although continuous localization can be computationally intensive, the
fusion of sensor data over each element in the Short-Term Map would be
done for obstacle avoidance anyway. The added cost of the registration is
periodic and can be performed in parallel on a separate processor to reduce
its impact. The map adaptation mechanism has a small cost, as it reuses
the fused data in the Short-Term Map, rather than resensing and fusing the
individual sensor data into the Long-Term Map. Overall, the NRL algorithm
is able to localize at about a 1Hz rate on a Pentium II class processor.

11.7.2 Feature-based localization

Feature-based localization has two flavors. One flavor is similar to contin-
uous localization and mapping: the robot extracts a feature such as a wall,
opening, or corner, then tries to find the feature in the next sensor update.
The feature acts as a local, natural landmark. As noted earlier in Ch. 9, the
use of natural landmarks can be challenging for navigation in general, espe-
cially since a “good” set of features to extract may not be known in advance.
Trying to find and use natural landmarks for accurate localization is at least
doubly hard.
The second flavor is really an extension of topological navigation. The
robot localizes itself relative to topological features such as gateways. It may
not know how long a hallway is, but it knows what the end of the hallway
looks like and important information (e.g., the hallway terminates in a t-
junction and has 3 doors on the left and 3 on the right). Once the robot has
constructed a topological map, it can locate itself.
An interesting question that has been considered by many researchers is
what happens when a robot is given a topological map (such as in Fig. 11.21),
told it was at Position A, and was really at Position B? How would the ro-
bot ever notice it was misinformed, rather than assume its sensors were re-