  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.
