Abstract: This paper presents a new algorithm for mobile robot localization, called Monte Carlo Localization (MCL). MCL is a version of Markov localization, a family of probabilistic approaches that have recently been applied with great practical success. However, previous approaches were either computationally cumbersome (such as grid-based approaches that represent the state space by high-resolution 3D grids), or had to resort to extremely coarse-grained resolutions. Our approach is computationally efficient while retaining the ability to represent (almost) arbitrary distributions. MCL applies sampling-based methods for approximating probability distributions, in a way that places computation "where needed." The number of samples is adapted on-line, thereby invoking large sample sets only when necessary. Empirical results illustrate that MCL yields improved accuracy while requiring an order of magnitude less computation when compared to previous approaches. It is also much easier to implement.
Introduction
In the field of robotics, localization—the process of determining a robot's coordinates relative to a map—is a fundamental challenge. This problem manifests in two primary forms: position tracking, where a robot compensates for small odometry errors from a known starting point, and global localization, where a robot must determine its position from scratch without any prior knowledge. The latter is significantly more difficult, particularly when faced with the "hijacked robot problem," where a robot is moved to a new location without notification.
Prior to the introduction of Monte Carlo Localization (MCL) by Fox et al. in 1999, researchers primarily relied on Kalman Filters or Grid-based Markov Localization. While Kalman Filters are computationally efficient, they are restricted to unimodal Gaussian distributions, making them unsuitable for global localization. Conversely, grid-based methods can represent complex, multi-modal distributions but are computationally expensive, often requiring massive amounts of memory and processing power to maintain high-resolution maps.
The Monte Carlo Localization Algorithm
MCL overcomes these limitations by using a particle-filter-based approach. Instead of calculating probabilities for every possible coordinate in a grid, MCL represents the robot’s "belief" (its probability distribution over possible locations) using a set of $N$ weighted samples, or particles. Each particle represents a hypothesis of where the robot might be.
The algorithm operates through two recursive phases:
- Prediction (Motion Model): As the robot moves, each particle is shifted according to the robot's motion commands. Random noise is added to each particle to account for real-world factors like wheel slippage and mechanical drift.
- Correction (Sensor Model): When the robot receives sensor data (e.g., from sonar or laser rangefinders), each particle is assigned a weight based on the likelihood of seeing that specific data from the particle's hypothesized location. Particles that match the sensor data well are more likely to be sampled in the next iteration.
A key innovation of MCL is Adaptive Sample Set Sizes. The algorithm dynamically adjusts the number of particles based on the robot's confidence. During global localization, a large number of particles are used to cover the map. Once the robot converges on a likely location, the particle count is reduced to save computational resources.
Key Insights and Multi-modality
One of the most significant advantages of MCL is its ability to handle multi-modal distributions. In environments with symmetrical features, such as identical hallways, a robot may reasonably believe it is in one of several locations. While a Kalman Filter would be forced to choose a single (potentially incorrect) mean, MCL maintains clusters of particles at each likely location until further sensor data disambiguates the position.
To prevent the robot from becoming permanently lost if all particles converge on an incorrect location (the hijacked robot problem), the authors introduced the injection of random samples. This ensures that the robot continues to "explore" the state space, allowing it to recover if its current tracking hypothesis fails.
Empirical Results and Performance
The authors validated MCL using real-world data from robots in diverse settings, including office buildings and the Smithsonian Museum of Natural History. In the Smithsonian tests, the robot "Minerva" had to localize while moving at high speeds through dense crowds.
The results demonstrated that MCL is remarkably efficient:
- Computation: MCL required an order of magnitude less memory (a few megabytes compared to over 100MB for grid methods) and was significantly faster, processing sensor scans in under 3 seconds compared to up to 120 seconds for high-resolution grids.
- Robustness: MCL successfully maintained tracking over a 700-meter trajectory in a crowded museum, a task where previous grid-based methods failed due to the computational overhead of processing high-frequency sensor data.
- Accuracy: The algorithm maintained a tracking error of less than 1 meter, even when subjected to artificial "teleportation" errors designed to test its recovery capabilities.
Conclusion
Monte Carlo Localization represented a paradigm shift in mobile robotics. By focusing computation "where it is needed" through sampling, it provided a solution that was more accurate, more robust, and significantly more efficient than previous state-of-the-art methods. Its conceptual simplicity and ease of implementation have made it a cornerstone of modern robotic navigation and a precursor to advanced techniques in Simultaneous Localization and Mapping (SLAM).
Summary updated