Particle filters with a robot in a hallway

TL;DR:

• A particle filter represents the robot's belief as many guesses (particles), each a possible position.

• After each sensor reading, particles that agree with it get higher weights, and resampling copies heavy particles and drops light ones.

• It can handle several guesses at once, which makes it suitable when the robot does not know where it started.

A robot wakes up somewhere in a long hallway. It knows the map: where the doors are. It has no idea which door it is next to. A single position estimate with an error bar is the wrong tool, because the robot could be at any of several places. What it needs is a way to hold many guesses, and let the evidence knock out the wrong ones.

The idea

A particle filter keeps a cloud of particles. Each particle is one hypothesis: "the robot is here". At the start, with no knowledge, the particles are spread over the whole corridor. Then the robot repeats a cycle:

1. Move. When the robot moves, move every particle by the same commanded amount, plus a little random noise, since motion is never exact.

2. Weigh. When the robot senses something, give every particle a weight that says how well that particle's position matches the reading. A particle in front of a door when the robot sees a door gets a high weight. One in front of a plain wall gets a low weight.

3. Resample. Draw a new set of particles from the old one, with the chance of choosing each particle proportional to its weight. Heavy particles are copied, light ones tend to vanish.

After several cycles the particles pile up near the true position.

Worked example: a robot seeing doors along a corridor

The corridor runs from 0 to 10 m. There are doors at positions 2 to 3 m, 5 to 6 m and 7 to 8 m. The robot has 10 particles, one in the middle of each metre: at 0.5, 1.5, 2.5, ... 9.5 m. All start with equal weight 0.1.

Step 1: the robot sees a door. The sensor model (example numbers): if a particle is in front of a door, the chance of seeing a door is 0.9, otherwise 0.1. Door-front particles are at 2.5, 5.5 and 7.5 m.

1. Raw weights: 0.1 × 0.9 = 0.09 for the three door particles, and 0.1 × 0.1 = 0.01 for the other seven.

2. Total: 3 × 0.09 + 7 × 0.01 = 0.27 + 0.07 = 0.34.

3. Normalized: each door particle 0.09 / 0.34 = 0.265, each other 0.01 / 0.34 = 0.029. Check: 3 × 0.265 + 7 × 0.029 = 0.794 + 0.206 = 1.000.

The belief now has three bumps, one at each door. Which one is the robot at? Still unknown.

Step 2: the robot drives forward 3 m and sees a door again. Every particle moves by 3 m: 2.5 to 5.5, 5.5 to 8.5, 7.5 to 10.5. The particle that would be at 10.5 m is off the end of the corridor and gets weight zero. The other particles move: 0.5 to 3.5, 1.5 to 4.5, 3.5 to 6.5, 4.5 to 7.5, 6.5 to 9.5. (Those from 8.5 and 9.5 also fall off the end.)

Now the survivors, with their weights from step 1:

The robot sees a door. Multiply each weight by 0.9 if the particle is at a door, and by 0.1 if not:

• 5.5 m: 0.265 × 0.9 = 0.238.

• 7.5 m: 0.029 × 0.9 = 0.026.

• 8.5 m: 0.265 × 0.1 = 0.026.

• The four others: 0.029 × 0.1 = 0.003 each, total 0.012.

Total: 0.238 + 0.026 + 0.026 + 0.012 = 0.302. Normalized: 5.5 m has 0.238 / 0.302 = 0.79, each of 7.5 and 8.5 has about 0.087, and the four others about 0.01 each.

The belief is now concentrated: the particle at 5.5 m, which started as the "2.5 m door" hypothesis, has about 79 of every 100 chances.

Resampling. Draw 10 new particles with these probabilities. On average about 8 of the 10 land at 5.5 m, about one each near 7.5 m and 8.5 m, and the others rarely. In a real filter, the new particles get a small random spread so they do not all stay at the same point.

So the robot has worked out that it was at the first door, 2.5 m, and is now at 5.5 m. No sensor ever told it so directly.

Where it goes wrong

• Too few particles. With only 10, the correct hypothesis may not exist at all. Real filters use hundreds to thousands, more for larger maps.

• Particle deprivation. After resampling, all particles may be copies of one or two. If that guess is wrong, there is nothing to recover with. Add some random particles, or resample only when needed.

• Overconfident sensor model. If you say a door reading is right 99 times in 100 and it fails once, the right particle gets weight near zero and the filter loses track.

• Symmetry. In a corridor with repeating identical doors, the robot cannot tell positions apart until it sees something that breaks the pattern.

• Cost. More particles mean more computation each cycle.

• No motion noise. Without it, particles stay on top of each other and cannot track small drifts.

Safety: While a robot is unsure where it is, move slowly or not at all, and let the particle spread tell you when it is safe: wait until the cloud is tight before driving fast or going near stairs or people. Keep an independent obstacle sensor and an emergency stop active, because the filter can be confidently wrong.

How real robots use it

Particle filters (often called Monte Carlo localization) are a standard way for wheeled robots to localize against a laser map. They handle the start-up problem and the kidnapped-robot problem better than a single Gaussian estimate. When the starting position is known and the noise is simple, the Kalman filter is cheaper. The broader idea of combining motion and landmarks is explained in localization: how a robot knows where it is.

Try it yourself

Draw the corridor on a strip of paper with the doors marked. Cut out 10 small tokens and place one per metre. Choose a sequence such as "door, move 3 m, door". Mark each token's weight. Move the tokens, and discard those that fall off the end. Multiply by 0.9 or 0.1. Then see which token ends with the most weight. Try the sequence "door, move 1 m, no door" and see how the answer changes.

Frequently asked questions

Why use many particles instead of one estimate?

Many particles can represent several possible positions at once, so the robot can start without knowing where it is, and let the sensor readings remove the wrong ones.

What does resampling do?

It replaces the set of particles with a new one, drawn in proportion to weight. That concentrates effort on likely positions and discards the unlikely ones.