Markov Localization: A Probabilistic Framework for Mobile Robot Localization and Navigation


Dieter Fox
Institute of Computer Science III
University of Bonn, Germany
 

Doctoral Thesis
December 1998


 


Interested in the complete thesis? Download the postscript version (5694 kb).



Introduction

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.
Global 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 localization.
Robust Localization:
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.
Active Localization:
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.
Safe Localization:
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.
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.
 
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 Bonn.

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).