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
This classic 1999 paper from Fox, Burgard, and Thrun is a cornerstone of modern robotics, laying the groundwork for how robots navigate messy, unpredictable human spaces. Most early robot localization algorithms shared a fatal flaw: they assumed the world was static. They compared sensor readings against a fixed map, but if a crowd of people stood in front of the robot, the sensors would report "walls" where none existed. This led to the robot becoming "lost" or suffering from the "kidnapped robot problem"—the inability to recover its position after being moved or experiencing a major sensor error.
The challenge addressed by the authors was to create a system capable of global localization (finding itself from scratch), handling dynamic obstacles like people, and maintaining computational efficiency on the limited hardware of the era.
Probabilistic Framework and Methods
The paper utilizes Markov Localization, a probabilistic framework that maintains a "belief" (a probability distribution) over all possible robot poses $(x, y, \theta)$. Unlike Kalman Filters, which are unimodal and easily broken by incorrect readings, Markov Localization's grid allows the robot to represent multiple hypotheses simultaneously.
Key technical innovations include:
- Metric Grid-Based Representation: Using a fine-grained 3D grid allows the robot to represent multi-modal distributions. As shown in the figure above, the robot can maintain several "guesses" about its location until further sensor data resolves the ambiguity.
- The Distance Filter: A "common sense" filter for sensors. If a laser or sonar returns a distance significantly shorter than what the map predicts, the algorithm assumes it hit a transient obstacle (like a person) and ignores that specific reading.
- The Entropy Filter: This filter measures how much a sensor reading changes the robot's certainty. If a reading increases entropy (making the robot more confused), it is discarded as likely being corrupted by environmental dynamics.
- Selective Update: To maintain real-time performance, the robot only performs expensive calculations on grid cells where the probability is above a certain threshold, typically updating only ~5% of the state space once localized.
Real-World Deployment and Results
The researchers evaluated their approach using real-world data from two high-profile robot deployments: Rhino at the Deutsches Museum Bonn and Minerva at the Smithsonian National Museum of American History.
In these densely populated environments, the filtering techniques proved essential. Evaluation using over 100,000 laser scans revealed several key results:
- Robustness: In crowded environments, "plain" Markov localization failed ~26% of the time. With the new distance and entropy filters, the failure rate dropped to ~1%.
- Accuracy: The system achieved a positioning error of just 3.5cm to 10cm, depending on the grid resolution.
- Recovery: The robot could successfully re-localize after being "teleported" to a random location within an average of 235 seconds, even in a crowded room.
- Efficiency: Using selective updates and pre-computed look-up tables, the system ran in real-time on a 266MHz Pentium II.
Conclusion and Legacy
A major insight of this work is that in dynamic environments, it is often better to discard sensor data that doesn't fit the map than to try to incorporate it. By filtering out "short" readings, the robot focuses only on the static landmarks it actually recognizes.
While the primary limitation was the memory bottleneck of fixed grids, the authors correctly identified the path forward. They concluded by suggesting Monte Carlo Localization (MCL)—using "particles" instead of a fixed grid—as a way to achieve the same robustness with significantly less memory. This suggestion eventually led to the "Particle Filter" revolution that defines modern robotic navigation.
Summary updated