Journal of Artificial Intelligence Research 11 (1999), pp. 391-427. Submitted 1/99; published 11/99.
© 1999 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Markov Localization for Mobile Robots
in Dynamic Environments

Dieter Fox
Computer Science Department and Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213-3891

Wolfram Burgard
Department of Computer Science
University of Freiburg
D-79110 Freiburg, Germany

Sebastian Thrun
Computer Science Department and Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213-3891

Abstract:

Localization, that is the estimation of a robot's location from sensor data, is a fundamental problem in mobile robotics. This papers presents a version of Markov localization which provides accurate position estimates and which is tailored towards dynamic environments. The key idea of Markov localization is to maintain a probability density over the space of all locations of a robot in its environment. Our approach represents this space metrically, using a fine-grained grid to approximate densities. It is able to globally localize the robot from scratch and to recover from localization failures. It is robust to approximate models of the environment (such as occupancy grid maps) and noisy sensors (such as ultrasound sensors). Our approach also includes a filtering technique which allows a mobile robot to reliably estimate its position even in densely populated environments in which crowds of people block the robot's sensors for extended periods of time. The method described here has been implemented and tested in several real-world applications of mobile robots, including the deployments of two mobile robots as interactive museum tour-guides.

• Introduction
• Markov Localization
  • The Basic Idea
  • Basic Notation
  • Recursive Localization
  • The Markov Localization Algorithm
  • Implementations of Markov Localization
• Metric Markov Localization for Dynamic Environments
  • The Action Model
  • The Perception Model for Proximity Sensors
  • Filtering Techniques for Dynamic Environments
    • The Entropy Filter
    • The Distance Filter
  • Grid-based Representation of the State Space
    • Pre-Computation of the Sensor Model
    • Selective Update
• Experimental Results
  • Long-term Experiments in Dynamic Environments
    • Datasets
    • Tracking the Robot's Position
    • Recovery from Extreme Localization Failures
  • Localization in Incomplete Maps
  • Localization in Occupancy Grid Maps Using Sonar
  • Precision and Performance
• Related Work
• Discussion
• References
• About this document ...