Page 232 - Introduction to Autonomous Mobile Robots

Mobile Robot Localization

Figure 5.20 217
Dervish exploring its environment.

5.6.2.2 Case study 1: Markov localization using a topological map
A straightforward application of Markov localization is possible when the robot’s environ-
ment representation already provides an appropriate decomposition. This is the case when
the environmental representation is purely topological.
Consider a contest in which each robot is to receive a topological description of the envi-
ronment. The description would include only the connectivity of hallways and rooms, with
no mention of geometric distance. In addition, this supplied map would be imperfect, con-
taining several false arcs (e.g., a closed door). Such was the case for the 1994 American
Association for Artificial Intelligence (AAAI) National Robot Contest, at which each
robot’s mission was to use the supplied map and its own sensors to navigate from a chosen
starting position to a target room.
Dervish, the winner of this contest, employed probabilistic Markov localization and
used a multiple-hypothesis belief state over a topological environmental representation. We
now describe Dervish as an example of a robot with a discrete, topological representation
and a probabilistic localization algorithm.
Dervish, shown in figure 5.20, includes a sonar arrangement custom-designed for the
1994 AAAI National Robot Contest. The environment in this contest consisted of a recti-