Monte Carlo Localization (MCL)

MCL represents the robot's belief state not as a parametric Gaussian, but as a set of M discrete weighted particles. Each particle is a hypothesis of the robot's full pose (x, y, θ). The density of particles in a region of the state space directly corresponds to the posterior probability of the robot being there. This non-parametric representation allows MCL to represent multi-modal distributions, such as when a robot is symmetrically lost in a corridor and has two equally likely hypotheses.

MCL is a practical implementation of the Bayes filter with particle-based representation. It recursively estimates the belief state bel(x_t) by applying two alternating steps:

• Prediction Step (Motion Model): Particles are propagated forward using a probabilistic motion model p(x_t | u_t, x_{t-1}) that adds controlled noise to simulate actuator uncertainty.
• Update Step (Sensor Model): Each particle is re-weighted by the likelihood p(z_t | x_t) of observing the actual sensor reading given that particle's hypothetical pose. Particles with low likelihood are systematically eliminated in the subsequent resampling phase.

To combat particle degeneracy—where most particles drift to low-weight regions—MCL employs importance resampling. After the sensor update, a new set of M particles is drawn with replacement from the current set, where the probability of drawing a particle is proportional to its weight. This concentrates computational resources on high-probability regions of the state space. Common resampling algorithms include low-variance resampling (stochastic universal sampling), which minimizes the variance in the number of offspring per particle compared to naive roulette-wheel selection.

MCL's robustness derives from its ability to incorporate raw sensor data through a likelihood field model. Instead of extracting features, the model computes the probability of a laser range finder or sonar measurement given a particle's pose and a pre-computed map. For each beam endpoint, the likelihood is a function of the distance to the nearest obstacle in the map, typically modeled as a mixture of a Gaussian distribution (for correct measurements with noise) and a uniform distribution (for random noise and unexpected obstacles). This allows MCL to handle noisy, short-range sensors effectively.

Unlike extended Kalman filters that require a known initial pose, MCL can solve the global localization problem by initializing particles uniformly across the entire map. The algorithm naturally converges to the correct pose as sensor data arrives. This property also enables recovery from the kidnapped robot problem, where a well-localized robot is suddenly teleported to a new location. By injecting a small fraction of random particles at each iteration (augmented MCL), the algorithm maintains the ability to re-localize if the sensor likelihood drops catastrophically.

The time complexity of MCL is O(M) per iteration, scaling linearly with the number of particles. The constant factor is dominated by the sensor model evaluation, which requires ray-casting or nearest-neighbor lookups in the map for each particle's beam. In practice, implementations use k-d trees for efficient nearest-neighbor queries in the likelihood field. The number of particles M is typically tuned based on the map size and required accuracy, with common values ranging from 1,000 for simple indoor environments to 100,000 for large-scale outdoor localization.

Planning under uncertainty where the robot's state is represented as a probability distribution (the belief), not a single point estimate. Actions are chosen to reduce localization uncertainty while achieving goals.

• Dual Objective: Minimizes both path cost and state covariance.
• Active Localization: The planner deliberately seeks features to reduce ambiguity.
• Relation to MCL: MCL provides the belief state that belief space planners reason over.

A nonparametric Bayesian filter that represents a posterior distribution using a set of weighted random samples called particles. MCL is a specific application of particle filters to robot localization.

• Sequential Importance Resampling (SIR): The standard algorithm combining prediction, update, and resampling steps.
• Sample Impoverishment: A failure mode where particles collapse to a single hypothesis, mitigated by adding random noise.
• Computational Complexity: Scales linearly with the number of particles, making real-time performance achievable on embedded hardware.

A probabilistic model describing how a robot's state evolves given a control input. In MCL, the motion model propagates each particle forward during the prediction step.

• Odometry Model: Uses wheel encoder data with Gaussian noise to model translation and rotation uncertainty.
• Velocity Model: Propagates state based on commanded linear and angular velocities.
• Drift Accumulation: Open-loop motion prediction causes particle clouds to spread, requiring sensor corrections.

A probabilistic model that computes the likelihood of receiving a sensor measurement given a hypothesized robot state. This is the update step in MCL that reweights particles.

• Beam Model: Computes likelihood based on expected vs. actual range returns along individual LiDAR beams.
• Likelihood Field Model: Projects sensor endpoints onto a distance map for faster, smoother likelihood computation.
• Importance Weight: Each particle's weight is proportional to the probability of the actual observation given that particle's pose.

A localization failure scenario where a robot is teleported to an unknown location without being informed. MCL addresses this through global localization capabilities.

• Augmented MCL: Injects random particles uniformly across the map to recover from kidnapping.
• Sensor Reset: Detects sudden drops in average particle weight as a trigger for reinitialization.
• Multi-Hypothesis Tracking: Maintains distinct particle clusters representing competing location hypotheses until ambiguity resolves.