Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 38 ยท Localization and Mapping

Particle Filter and Monte Carlo Localization

Learn Monte Carlo localization with a particle filter: sample, move, weight, resample. Build a 2D range-landmark localizer in Python and tune it.

A Kalman filter keeps one bell curve. That fails when the robot is truly unsure between several places: a long hallway with identical doors, or a robot that has just been switched on somewhere in a building. The belief then has several peaks, and a single Gaussian cannot describe it.

A particle filter represents the belief with hundreds or thousands of random particles. Each particle is one hypothesis ("the robot is here, facing this way"). Where particles are dense, the robot is probably there. Used for localization it is called Monte Carlo Localization (MCL), and it is behind the amcl package in ROS navigation.

The four steps

Each cycle repeats:

  1. Move. Apply the commanded motion to every particle, adding random noise (different for each particle, which spreads the cloud).
  2. Weight. For each particle, ask: if the robot were here, how likely is the actual sensor reading? That probability is the particle's weight.
  3. Normalize. Scale the weights to sum to 1.
  4. Resample. Draw a new set of particles in proportion to their weights. Good hypotheses get copied, poor ones disappear.

Monte Carlo localization

Cloud of guesses Each particle is one possible pose.
Move with noise The cloud follows the robot and spreads.
Weight Score each guess against the sensor.
Resample Copy the good guesses, drop the bad.
1 / 2

A range-to-landmarks localizer

The robot lives in a 10 by 10 m room with three known landmarks. It can measure the distance to each, with Gaussian noise (standard deviation 0.5 m). It drives by commands (turn, forward). We start with particles spread everywhere (global localization).

The weight of a particle is the product over landmarks of a Gaussian likelihood: how close each particle's predicted distance is to the measured one.

Python Monte Carlo localization from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cloud starts spread over the whole room (about 2.9 m). Three range readings already pin the pose down, so within the first update the spread collapses to a few tenths of a meter and the error stays well below the 0.5 m sensor noise as the robot circles. n_eff, the effective sample size, tells you how many particles actually matter right now: it is tiny right after the first update (most guesses were wrong) and recovers after resampling.

Resampling details

Resampling is the delicate part:

  • Why do it? Without it, all weight ends up on one particle (degeneracy) and the rest are wasted computing.
  • Low-variance (systematic) resampling, used above, draws one random number and then steps evenly through the cumulative weights. It is faster and has less random error than drawing N independent samples.
  • When to do it? Many implementations resample only when n_eff falls below, say, half of N, which keeps diversity.
  • Particle deprivation. If the cloud collapses onto a wrong place and the real pose has no particles near it, the filter cannot recover. Remedies: add a few random particles each cycle (the idea behind augmented MCL for the kidnapped robot problem), or inflate the noise.
Python Why resampling matters: effective sample size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without resampling, the effective sample count collapses quickly. After resampling, high-weight particles are copied many times, so the number of unique parents is much smaller than N, but every particle again carries equal weight.

Choosing the number of particles

More particles give a better belief and cost more computation. A few hundred are fine when the robot is already localized in a small area; thousands may be needed for global localization in a large building. Adaptive MCL (KLD-sampling) changes the count on the fly: many particles while the robot is lost, few once the belief is tight.

Choice Effect
Too few particles Cloud collapses to a wrong place, cannot recover
Too many Accurate, but CPU time rises with N
Motion noise too small Cloud cannot follow slip or drift
Sensor noise too small Overconfident weights, early collapse

In ROS 2, the nav2_amcl node implements adaptive MCL with a 2D laser and an occupancy-grid map. You give it an initial pose estimate, or let it localize globally, and it publishes the map to odom transform. See ROS 2 concepts.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a particle in Monte Carlo localization represent?

    Each particle is a possible pose. The set of particles approximates the belief.
  2. 2. In the weighting step, a particle's weight reflects...

    Particles whose predicted measurements agree with the real ones get high weights.
  3. 3. Why is a particle filter better than a Kalman filter for global localization?

    A Gaussian has one peak. A cloud of particles can hold many clusters until evidence rules them out.
  4. 4. What is the purpose of adding a few random particles during localization?

    Random particles maintain diversity so the filter can re-localize if all current hypotheses become wrong.

Summary

  • A particle filter approximates the belief with weighted samples; Monte Carlo localization applies it to robot pose.
  • The loop is move (with noise), weight by the sensor model, normalize, resample.
  • Low-variance resampling and a check on effective sample size prevent degeneracy.
  • Add random particles and adapt the particle count to recover from being lost and save computation.
  • It handles non-linear models and multi-modal beliefs that Kalman filters cannot.

Next: Occupancy Grid Mapping