Monte Carlo Localization uses randomized samples to represent a robot’s belief about its location in an environment and is notable for its accuracy, efficiency, and ease of use compared to previous approaches. MCL was first presented in 1999 at the International Conference on Robotics and Automation and was the first application of sample-based estimation in robotics, where it is now used across a wide range of application.
The new sample-based Monte Carlo Localization (MCL) is computationally efficient while retaining the ability to represent arbitrary distributions. The MCL applied the sample-based methods for approximating probability distributions employed by the number of samples is adapted on-line, thereby invoking the sample sets dynamic and necessary, which the grid-based approached that represented computationally cumbersome by 3D grids failed to achieve.
In mobile robot applications, the sensor-based location has been recognized as a key problem. Localization is a version of on-line spatial state estimation, where a mobile robot seeks to estimate its position in a global coordinate frame. The localization problem comes in two flavors: global localizaion and position tracking. The paper indicates that the global localization problem is difficult to solve because it involves a robot which is not told its initial position; the position tracking problem is the most-studied problem that a robot knows its initial position and only has to accommodate small errors as it moves.
The existing approaches to robot localization include Markov localization, Kalman Filtering, Particle Filtering, SLAM (Simultaneous localization and mapping), and Multi-robot localization.
- Markov Localization:
- Central idea: represent the robot’s belief by a probability distribution over possible positions, and use Bayes’ rule and convolution to update the belief whenever the robot senses or moves.
- Markov Assumption: the past and future data are independent if one knows the current state
- Kalman Filtering:
- Central idea: posing localization problem as a sensor fusion problem
- Assumption: Gaussian distribution function
- Particle Filtering (Monte-Carlo Localization)
- Central idea: the posterior belief by a set of N weighted, random samples or particles
- SLAM (Simultaneous Localization and Mapping)
- Multi-robot localization
In this paper, authors considered the limitation of Kalman filter-based techniques and Markov localization, including Topological Markov localization and Grid-based Markov localization, and then provided the sample-based density approximate Monte Carlo localization. These approaches have the following limitations:
The Kalman filter-based techniques are based on the assumption that uncertainty in the robot’s position can be represented by a unimodal Gaussian distribution. Kalman filter-based techniques have proven to be robust and accurate for keeping track of the robot’s position. However, this approach cannot deal with multi-modal densities typical in global localization. The other limitation is that the initial posture must be known with Gaussian uncertainty at most.
The Topological Markov localization methods uses increasingly richer schemes to represent uncertainty, moving beyond the Gaussian density assumption inherent in the vanilla Kalman filter, and is roughly distinguished by the type of discretization used for the representation of the state space. However, the coarse resolution of the state representation limits the accuracy of the position estimates.
The Grid-based Markov localization methods are powerful to deal with multi-modal and non-Gaussian densities. However, this approach suffers from excessive computational overhead and a priori commitment to the size and resolution of the state space. Moreover, the computational requirements have an effect on accuracy as well, as not all measurements can be processed in real-time and valuable information about the state is thereby discarded.