Markov Localization: A Probabilistic
Framework for Mobile Robot Localization and Navigation
Institute of Computer Science III
University of Bonn, Germany
Interested in the complete thesis? Download the postscript version (5694 kb).
This dissertation explores fundamental issues in effective and safe
navigation of mobile indoor robots. In particular, we will look at the
problem of self-localization and aspects of collision avoidance during
the process of self-localization. A successful realization of this process
has to address several sub-problems.
Consider, for example, a man with a city map trying to find a particular
place in an unknown city. In order to use this city map, the man must first
determine his position within the city. To do so, he can look around and
compare his observations with the information represented in the map. Here,
such an observation can be for example a road sign or a landmark. In most
cases, a single observation is not enough to uniquely determine one's location.
This is mainly due to the fact that several places often look the same.
Thus, the problem of ambiguities is an inherent part of the problem
of localization. In order to disambiguate between the different possible
positions, one has to keep these possible locations in mind and collect
additional information at other locations in the environment. In many cases
it is sufficient to undirectedly move around until enough observations
have been made. This could be the case e.g. if the next street sign is
found. However, if the environment possesses only relatively few features
that enable one to unambiguously determine one's location, it can be much
more efficient to first determine directions in which to move in order
to actively disambiguate between the possible locations. For example,
the man in the foreign city could look for a church steeple in order to
uniquely determine his location. Additionally, the person often is confronted
with the following problem: Due to changes at some places, the city looks
different from the representation of the map. We call this the problem
of dynamic environments. Nevertheless, once the person knows where
he is, he still must keep track of his position as he moves on. In most
cases, the task of tracking can be efficiently achieved e.g. by
continuously comparing the observations with the places expected in the
city map. However, as soon as the person loses his position again, he has
to relocalize himself, which often requires similar steps to those
performed on arrival in the city.
This example shows that knowledge about one's position within one's
environment is a precondition for making use of a map. Autonomous indoor
mobile robots face the same problems as the person when performing their
tasks. Such tasks include, e.g., office delivery, surveillance, personal
assistance, entertainment, manipulation of objects, and so on. Effective
navigation is a basic precondition for successful mobile robot applications.
In order to make use of a map of the environment and to carry out navigation
plans, a successful application presupposes mobile robot localization.
Therefore, localization is one of the fundamental problems in mobile robotics.
Over the last few years, there has been a tremendous scientific interest
in algorithms for estimating a robot's location from sensor data. We are
particularly interested in methods that do not depend on any modification
of the environment such as the placement of active beacons. As can be seen
from the example, a successful system for autonomous mobile robot localization
should address the following aspects.
In this thesis we will introduce an approach to mobile robot
localization which addresses all these aspects of localization. Our
approach to position estimation is a fine-grained grid-based
implementation of Markov localization. The paradigm of Markov
localization is based on a general framework for state estimation and
applies probabilistic representations for the robot's location, the
outcome of actions, and the robot's observations. The basic principles
of our technique can be summarized as follows.
During the process of self-localization, ambiguous situations must be represented.
Ambiguities can be resolved by a sequence of observations at different
The map of the environment can be used to find actions helping to uniquely
determine the robot's location.
Once the location of the robot is uniquely determined, tracking this location
can be achieved more efficiently.
Due to possible changes in dynamic environments, the map does not always
match the environment.
Localization includes the ability to detect failures of the position estimation
and to relocalize the robot, when necessary.
All techniques introduced in this thesis will be extensively validated
on the robot RHINO. The experiments are conducted in two different
environments. One environment, a part of our computer science
department, is depicted in fig:intro-environmentsa. It includes all
features of typical office environments such as people walking by,
furniture that is moved around in the offices, and several places that
look the same to the robot's sensors such as e.g. symmetric
corridors. The other environment is a crowded museum, in which RHINO
served as an autonomous museum tour-guide robot for extended periods
of time (see fig:intro-environmentsb). This unstructured environment
stresses additional requirements for robust localization such as
accuracy and the ability to handle situations in which much of the
robot's sensory information is corrupted by the presence of
people. The experiments conducted in these two environments show that
our implementation of Markov localization in combination with the
extensions proposed in this thesis meets all requirements we have for
a technique for autonomous mobile robot localization.
By global localization we mean the ability to estimate the position of
a robot without knowledge of its initial
location and the ability to relocalize a robot if its
position is lost. In contrast with most existing position estimation
techniques, our implementation of Markov localization can represent
multi-modal probability distributions. Since Markov localization
estimates the location of the robot in the entire environment, it is
able to detect situations in which the position of the robot is
lost. Therefore, our technique meets all requirements for global
Most localization techniques rely on a static model of the
environment. Therefore, robust localization in dynamic environments requires the ability
to estimate the position of a robot even when a significant number of
the observations cannot be matched with the map. E.g. the appearance
of typical indoor environments may change significantly due to
furniture that is moved around, opened or closed doors, or people that
surround the robot. In order to reliably localize a mobile robot even
in such dynamic environments, our approach introduces a technique
which filters sensor data. These filters are designed to eliminate the
damaging effect of sensor data corrupted by unmodeled dynamics.
The efficiency especially of global localization can be improved by
actively disambiguating between different possible locations. Actively
controlling the actuators of a robot in order to localize it is
especially rewarding whenever the environment possesses relatively few
features that enable it to unambiguously determine its location. Key
open issues in active localization are ``where to move'' and ``where to look'' so as to best localize
the robot. In order to derive means for determining the best action
with respect to localization, we will introduce a decision-theoretic
extension of Markov localization. The guiding principle of our
approach is to control the actuators so as to minimize future expected
uncertainty. In our extension, uncertainty is measured by the entropy
of future position probability distributions. By choosing actions to
minimize the expected future uncertainty, our approach is capable of
actively localizing a mobile robot from scratch.
Active localization raises the problem of how to safely control a
robot especially during the process of active global
localization. Most existing approaches to safe navigation rely on a
purely sensor-based, reactive collision avoidance. In order to
overcome the limitations of this paradigm, we combined our method for
position estimation with such a reactive collision avoidance
technique. The resulting hybrid approach to collision avoidance
differs from previous approaches in that it considers the dynamics of the robot and avoids
collisions with invisible obstacles even if the robot is
uncertain about its position.
| Map of our department including
furniture (blue) not detectable by the robot's sensors.
|| RHINO as it gives a tour through the exhibition of the Deutsches Museum
My thesis is organized as follows. After the introduction, we will
introduce the basics of Markov localization and an implementation of
this general scheme. Then we will present the two indoor environments
in which all our techniques will be tested throughout the thesis. Our
extension for robust position estimation even in highly dynamic environments will be introduced in
Chapter 3. A further extension of Markov localization is introduced
in the following chapter. This enhancement significantly increases
the efficiency of position estimation by actively controlling the actuators of the
robot. After introducing our hybrid approach to collision avoidance in
Chapter 5, we will discuss the software architecture of the RHINO
system with an emphasis on the integration of localization into robot
control. Finally, we will conclude in Chapter 7.
Interested in the complete thesis? Download the postscript version (5694 kb).