Particle filters and MCL

How do you filter with samples instead of parameters?

Every filter in this part of the series answers the same question — where is the robot? — and stores the belief in a different shape. The histogram filter keeps one probability per bin; the Kalman filter keeps a mean and a covariance. Both are parameterisations: a fixed, finite description of a belief usually far too rich to write down. The particle filter takes the other road, describing the distribution not with parameters but with samples drawn from it.

Formally, the belief after observations $z_{1:t}$ is approximated by a weighted set of points:

Each $x_t^{(i)}$ is a hypothesis and each weight $w_t^{(i)}$ says how plausible it is. Nothing assumes the belief is a bump, a bell, or even connected: two hypotheses on opposite sides of a landmark can both live in the cloud, which is exactly what a robot needs in a corridor it has never seen. The cost is that the approximation is random: a different cloud gives a different answer.

The recursion is unchanged: prediction pushes every particle through the motion model, correction reweights every particle by the measurement. Only the place the probabilities live has changed.

Sequential importance sampling in one picture

Scatter $N$ particles across the state space, drawn from a proposal that is easy to sample — here, a uniform draw over the corridor, because the robot has no idea where it is. Because the proposal is not the true prior, each particle enters with an importance weight that corrects the mismatch: high where the belief exceeds the proposal, low where it falls short.

Prediction propagates each particle through the motion model with independent noise, using the control the robot actually executed. Each particle carries its own perturbation, so the cloud spreads by exactly the process noise. Prediction never looks at the sensor.

Correction multiplies each weight by the measurement likelihood:

A particle where the range says the robot must be keeps its weight; one that could not have produced the reading is suppressed. After normalising, the estimate of position is the weighted mean of the cloud, and any other quantity is a weighted average in the same way. The cloud is the distribution; there is no separate formula to consult.

The trouble is in the formula. Every observation multiplies every weight by a number below one, and the particles that happen to be right are multiplied by larger numbers than those that happen to be wrong. After a few steps a handful carry almost all the weight while the rest carry almost none — weight degeneracy. They still cost time to carry, and contribute nothing. The measure of how many are actually working is the effective sample size, and the remedy is resampling.

Throw away the dead hypotheses, duplicate the live ones

Resampling rebuilds the cloud by drawing $N$ new particles from the old ones in proportion to weight, then resetting every weight to $1/N$. Heavy particles are likely to be duplicated, light ones to vanish. The belief is unchanged in expectation, but the representation is now efficient. The catch is that resampling adds variance and destroys diversity: it can copy a mediocre particle many times and never invent a better one.

Systematic resampling is the low-variance draw. A single uniform offset $u_0$ generates $N$ evenly spaced thresholds:

One random number decides the whole selection, so each particle's copy count differs from its expected count by at most one — far less noisy than independent draws, and a single ordered pass in $O(N)$.

The effective sample size, $\mathrm{ESS} = 1 / \sum_i \tilde w_i^2$, is the trigger. It is $N$ when all weights are equal and falls toward $1$ as one particle takes over — the number still genuinely contributing. Resample every step and you needlessly destroy diversity; never resample and the dead weight piles up. The compromise is to resample only when the ESS falls below a fraction of $N$, here $N/2$, the dashed line on the lower canvas.

The demo is a one-dimensional robot in a corridor with five landmarks at known positions. It follows a fixed control sequence — right, back, right again — measuring its range to one landmark at a time, cycling through them. The horizontal axis of the top canvas is the corridor and time runs upward: each faint row is the particle cloud at one instant, the solid magenta line is the true path and the dashed line the filter's estimate. Press Predict to move the robot and its particles, Update + resample to fold in the next reading, or Run to track automatically. Early on, one range leaves two mirror-image candidate positions and the next landmark rules one out: multimodal for a moment, then snapped to the truth.

Resampling does not manufacture information: a cloud that has thrown away the true state cannot resample its way back to it. What lets the cloud explore is the noise injected during prediction — too little and the particles are near-identical copies, enough and a resampling step has something new to choose from.

Too few hypotheses is not a smaller approximation; it is a different one

Drag the particle count to twenty and let the filter run. After a few resamples the readout's distinct particles collapses far below $N$: the same positions recur because systematic resampling copied them. This is particle deprivation. The cloud no longer samples the belief but a small set of duplicates, and any region none of them occupy is effectively declared impossible. With a thousand particles the corridor is covered densely enough that the truth is always represented; with twenty, one unlucky resample can delete it, and no later measurement brings it back.

The number needed is not fixed. It grows with the volume of the state space and, worst case, exponentially with its dimension — the curse of dimensionality that pushes high-dimensional problems toward parametric filters or optimisation. A few hundred particles is generous in one dimension; a full 3-D pose with heading, or SLAM, runs into thousands. Cost is linear in $N$ per step, which is why the filter is affordable and why accuracy saturates: past some count, more particles buy less than fixing the models.

The estimate is random too: a weighted mean of random samples jitters from run to run, and a different seed gives a different cloud. The RANSAC fitting guide makes the same trade: a small random subset is cheap and usually right, but the guarantee is probabilistic.

Confidently wrong, and unable to tell

So far the truth has always been somewhere in the cloud. Now break that. Press Kidnap robot: the robot is placed elsewhere along the corridor without the filter being told, as if a person carried it to another room. Prediction still applies the old control, so the cloud marches on from where it believed the robot was, and the estimate keeps moving smoothly while the true path jumps away.

The next measurement contains the information, but the filter cannot use it. Every particle is far from a position consistent with the reading, so every likelihood is tiny and the weights end up nearly equal. With nothing to distinguish them, resampling just re-copies the same wrong cloud. The effective sample size can even stay high — the subtlest lesson here: a high ESS means the weights are evenly spread, not that the belief is correct. The cloud is uniform and wrong. This is global localisation with a bad prior.

The cure is augmented MCL: each prediction, a small fraction of particles is replaced by fresh uniform draws. Turn on Random injections, kidnap the robot again, and watch: nothing happens for a while, then one injected particle lands near the truth, its weight spikes, the ESS plunges, a resample duplicates it, and the cloud snaps back. The cost is a few percent of particles spent on almost-certainly-wrong positions; the benefit is that the filter can never be permanently fooled.

The inheritance is clear. This is the Bayes filter with bins replaced by samples, and it degrades to a Kalman filter when the belief is one narrow Gaussian and the models are linear. Its advantage is that it assumes no shape at all; its price is that the representation is random and the particle count is itself a modelling decision.

The filter behind most robots that know where they are

Monte Carlo localisation became the default indoor method because it needs no linearisation, tolerates arbitrary belief shapes, and handles the global-localisation and kidnapped-robot cases a Kalman filter cannot. The same construction appears wherever a state is tracked under a nonlinear model with a non-Gaussian belief: radar target tracking, video object tracking, and sequence models that estimate latent state in time series. The moving parts are always the same — particles, weights, an effective sample size, and a decision about when to resample.

Further reading

Particle filtering is one of the few modern methods whose founding paper is still among the clearest introductions. Take away the picture of a cloud spread by motion, reweighted by measurement and thinned by resampling.

Thrun, Burgard and Fox is the standard robotics treatment and the source of the MCL and augmented-MCL algorithms here. Gordon, Salmond and Smith introduced the resampling step that made the method work; Fox and colleagues' MCL paper is the robotics origin story.

• Sebastian Thrun, Wolfram Burgard and Dieter Fox, Probabilistic Robotics, MIT Press, 2005 — Chapter 4 (nonparametric filters) and Chapter 8 (the particle filter and Monte Carlo localisation).
• N. J. Gordon, D. J. Salmond and A. F. M. Smith, "Novel approach to nonlinear/non-Gaussian Bayesian state estimation", IEE Proceedings F, 1993 — the bootstrap filter.
• Dieter Fox, Wolfram Burgard, Frank Dellaert and Sebastian Thrun, "Monte Carlo Localization: Efficient Position Estimation for Mobile Robots", AAAI 1999.
• M. S. Arulampalam, S. Maskell, N. Gordon and T. Clapp, "A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking", IEEE Transactions on Signal Processing, 2002.

Cheat sheet