Particle filters
The Bayes filter is a two-line recursion, but only two families of belief have closed forms: a grid of bins, and a Gaussian. Neither survives a corridor with two equally likely ends, a room with symmetric furniture, or a robot that has not been told where it started. A particle filter takes the third road. It represents the belief directly as a set of random samples — hypotheses about the state — each carrying a weight that says how well it explains the sensor readings. The prediction is a push through the motion model, the update is a multiplication by the likelihood, and a resampling step prunes the hypotheses that stopped making sense. That is the entire algorithm, and it handles the multimodal, curved, non-Gaussian beliefs the other filters cannot. This part builds it, breaks it on purpose so you can watch it deplete, and then fixes it.
The question
The Bayes filter, without the Gaussian
Every recursive filter in this act is the same statement wearing different clothes. Given the belief bel(xt-1) at the last step, a control ut and a measurement zt, the new belief is a prediction followed by a correction:
The integral is the hard part, and the history of probabilistic robotics is a history of dodging it. The histogram filter chops the state space into bins and turns the integral into a sum, which is honest but exponential in the number of dimensions. The Kalman filter assumes the belief is Gaussian and the dynamics are linear, which reduces the recursion to matrix arithmetic — and which fails the moment the belief grows a second lump. A robot that hears "the corridor has a wall ahead" does not believe in one wall; it believes in several walls at once, one for each place it might be, and a single Gaussian cannot hold several lumps at the same time.
So ask the question differently. We do not need a formula for the belief. We need to answer questions with it: where am I, how sure am I, which of these two corridors is it. Those are integrals against the belief — expectations — and expectations can be estimated by sampling. Instead of storing a density, store a cloud of points drawn from it. More points near a place means more belief there. The cloud is the distribution, up to sampling error, and the error shrinks like 1/√N no matter how many dimensions the state has.
That is the whole idea, and it is called a particle filter, a sequential Monte Carlo method, or in robotics simply Monte Carlo localization. The next sections make it precise: what a particle is, how the three steps of the loop treat it, and why a careless implementation quietly throws away the very diversity that made the method worth using.
Particles as samples
A cloud of hypotheses standing in for a density
A particle is a single guess at the state, drawn at random. If we draw N of them from a distribution, the fraction that land in any region is, up to noise, the probability of that region. That is the simplest possible estimator of a density: sample it and count. The prediction we wanted, the expectation of a function f, becomes a plain average,
and the average converges to the integral by the law of large numbers. Nothing here cares whether p is a bell, a banana, or three separate islands, and nothing here gets worse when the state has twenty dimensions instead of one. The price is that the estimate is random: reload the page and the cloud is different, so every number carries a sampling error of order 1/√N.
The demo below makes the exchange concrete. A cloud of samples is drawn from a distribution shaped like a bell, and drawn next to it is the density the cloud is standing in for. At small N the histogram is lumpy and the sample mean wanders; turn N up and the lumps soften, the mean settles, and the cloud starts to look like a photograph of the density. Reseeding shows that the underlying distribution never changed — only the draw did.
The ticks at the baseline are individual particles; the bars are their histogram; the bold pink curve is the true density they were drawn from.
Read the readout as evidence, not decoration. The error in the sample mean is a random variable — it shrinks like 1/√N on average but not monotonically. At N=10 a lucky cloud can beat an unlucky cloud of a hundred. This is exactly the behaviour that particle filters inherit, and it is why a filter with too few particles is not merely inaccurate; it is unreliable in a way that no amount of clever bookkeeping repairs.
Sample, weight, resample
The loop, one step at a time
Now put the cloud into the Bayes recursion. The belief at time t is represented by particles xt(i) with weights wt(i) that sum to one, and the claim we are making is
a sum of spikes, one per particle, each weighted. Prediction is the easy half: push every particle through the motion model, one independent random draw each,
Because the motion model is itself stochastic, the particles fan out: a tight cloud becomes a looser one, and that spread is the predicted uncertainty. No Jacobian, no linearisation, no Gaussian assumption — the model does the work.
Correction is where the measurement enters. Each particle is scored by how likely the observed reading would have been if that hypothesis were the truth, and the weight is multiplied by that likelihood:
This is importance sampling: we cannot draw from the posterior directly, so we draw from the motion model and reweight by how well each draw explains the data. Consequences follow immediately. A particle sitting where the robot actually is gets a large factor and grows; a particle in the wrong corridor gets a factor near zero and fades. The normalisation is nothing but the evidence p(zt), estimated for free.
Weighting alone has a fatal drift. After a few corrections the weights are wildly unequal, almost all of the belief mass sits on one or two lucky particles, and the rest contribute nothing. Resampling fixes the drift by redrawing the cloud from itself: particle i is copied with probability equal to its normalised weight, and every copy starts fresh with weight 1/N.
The effect is a kind of natural selection. Regions of high belief get more descendants; regions of low belief go extinct. After resampling the cloud is concentrated where the evidence points, and it is free to fan out again on the next prediction. Prediction, weighting and resampling — three lines of code each — are the whole of a particle filter. The library's Prob.filters.particleFilter exposes exactly these as predict, update and resample.
Particle depletion and the fixes
When a healthy cloud collapses to one guess
The failure mode is called particle depletion, and it is a consequence of weighted resampling in a peaked world. Give the filter a very sharp likelihood — a sensor so precise it effectively points at one place — and a small cloud. Most particles will be far from where the robot is, their weights will fall to nearly zero, and the normalisation will pile essentially all the mass onto the one particle that happened to land near the truth. Its descendants then fill the entire cloud: N particles, but one distinct hypothesis, repeated. The filter is now confident and wrong, and it has no way back, because nothing left in the cloud can generate the correct answer.
The number that detects this in real time is the effective sample size, the reciprocal of the sum of squared normalised weights:
If the weights are all equal the ESS is N; if one particle holds everything it is one. It is not the number of particles, but the number of particles that are actually doing work. A common rule is to resample only when the ESS falls below half of N, so the cloud keeps its diversity on easy steps and is pruned only when the weights have genuinely concentrated.
Two repairs matter. The first is low-variance resampling. Naive resampling draws N independent copies, which is unbiased but noisy — two descendants of the same likely particle, none of another — and that noise wastes diversity. Systematic resampling walks the cumulative weight once with evenly spaced offsets,
so a particle with weight m/N is copied almost exactly m times. The expected number of copies is unchanged, but the variance is dramatically smaller, and the cloud stays spread out instead of clumping.
The second repair is roughening, or regularisation: after resampling, add a little jitter to each particle, scaled to the spread of the cloud. Copies of one ancestor are nudged apart, so the cloud regains the diversity that resampling removed. The jitter must be small — too much and the filter ignores its own measurements. The point is to keep a living population, not to manufacture noise. In the localization demo below you can switch both repairs on and off and watch the ESS respond.
Monte Carlo localization
A robot lost in a room full of rectangles
Monte Carlo localization is the particle filter with the state set to the robot's pose. Here that is (x,y,θ) in a rectangular map, the motion model adds a noisy step to each particle, and the sensor is a fan of range beams: the robot reports how far it can see along five directions, and a particle is scored by how closely the walls it predicts match those readings. The map itself is the constraint. A particle in the wrong room predicts walls in the wrong places and dies at the next correction; a particle in the right pose keeps predicting the right distances and survives. Symmetry is the interesting case: two poses that see identical walls stay equally weighted until the robot moves and breaks the tie, which is exactly the multimodality a Gaussian filter cannot represent.
The canvas draws the obstacles as blocks, the true pose as a dark arrow, the sensor fan as faint pink rays, and every particle as a small arrow coloured and sized by its normalised weight. The bold ring is the weighted estimate, the belief's mean pose. Start it, press Predict a few times and watch the cloud smear; press Update and watch the arrows that point at the true pose brighten while the others fade. The readout tracks the ESS.
Press Predict to move the robot and spread the cloud, Update to weight each hypothesis by the range readings, and Resample to let the fittest breed. Set N small and sensor σ low, then press Update repeatedly without resampling to force depletion.
Now run the experiment the section promised. Drop N to ten or twenty, pull the sensor noise down to make the likelihood peaked, and press Update two or three times without resampling. The ESS collapses toward one, a single bright arrow survives, and the readout warns you. Press Resample and the whole cloud becomes copies of that arrow — depletion, made visible. Reset, then do it again with roughening on: the copies are nudged apart, a few recover weight on the next update, and the cloud stays alive. This is the practical face of the sampling-error trade-off from section two: with too few particles, the filter is not just noisier, it is brittle.
Where this shows up
Sampling wherever the integral refuses to close
Localization without a map of beliefs
A robot that wakes up not knowing where it is needs the multimodal belief a filter like this one carries. The motion model comes from odometry, and the correction from a laser or range fan like the one on the canvas. This is the standard answer to the global-localization problem.
SLAM and fastSLAM
In simultaneous localization and mapping the map is part of the state, and a particle can carry its own map. FastSLAM exploits that decomposition to sample trajectories and solve the map in closed form, which is why particle methods sit beside the factor-graph and bundle-adjustment view in the vision guide.
Monte Carlo, sequenced
The particle filter is Monte Carlo integration advanced one time step at a time: estimate an expectation by sampling, then recycle the samples instead of starting over. Importance sampling is the same weight-multiply-normalise move, applied every frame.
The non-Gaussian Kalman
Where the belief really is a single bell, the Kalman filter is cheaper and exact, and a particle filter with enough samples reproduces it. The two are not rivals: the Gaussian assumption buys speed, the cloud buys shapes, and the choice is a bet on the belief.
Cheat sheet
Every formula in one place
| Idea | Formula | Reading |
|---|---|---|
| Belief as spikes | $\mathrm{bel}(x_t)\approx\sum_i w_t^{(i)}\delta(x_t-x_t^{(i)})$ | A weighted cloud is the distribution. |
| Prediction | $x_t^{(i)}\sim p(x_t\mid x_{t-1}^{(i)},u_t)$ | Push each particle through the motion model. |
| Weight update | $w_t^{(i)}\propto p(z_t\mid x_t^{(i)})\,w_{t-1}^{(i)}$ | Importance sampling: score by the likelihood. |
| Normalised weight | $\tilde w^{(i)}=w^{(i)}/\sum_j w^{(j)}$ | The evidence is the normaliser. |
| Resampling | $\Pr(x^{(i)}\text{ copied})=\tilde w^{(i)},\ \text{then } w^{(i)}=1/N$ | Fitter particles breed; weak ones go extinct. |
| Low-variance resample | u_k=(u_0+k-1)/N | Evenly spaced draws stay spread out. |
| Effective sample size | $\mathrm{ESS}=1/\sum_i(\tilde w^{(i)})^2$ | How many particles are actually working. |
| Resample trigger | $\mathrm{ESS} < N/2$ | Prune only when the weights have concentrated. |
| Weighted estimate | $\hat x_t=\sum_i \tilde w_t^{(i)} x_t^{(i)}$ | The cloud's mean pose. |
| Roughening | $x^{(i)}\leftarrow x^{(i)}+\epsilon^{(i)},\ \epsilon\sim\text{small noise}$ | Jitter restores diversity after resampling. |
Further reading
Where to go deeper
- Sebastian Thrun, Wolfram Burgard and Dieter Fox, Probabilistic Robotics, 2005, chapter 4 — the sample, weight, resample loop and Monte Carlo localization, written for exactly the robot on the canvas.
- Arnaud Doucet, Nando de Freitas and Neil Gordon, eds., Sequential Monte Carlo Methods in Practice, 2001 — the reference treatment, including the low-variance resampling scheme.
- M. Sanjeev Arulampalam et al., "A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking", IEEE Trans. Signal Processing, 2002 — the standard tutorial, with the ESS derivation and resampling schemes side by side.
- Pierre Del Moral, Feynman–Kac Formulae: Genealogical and Interacting Particle Systems with Applications, 2004 — the convergence theory behind the cloud, for when you want the theorems.
- 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 paper that introduced the bootstrap filter.