A robot dropped into a long, symmetric hallway could honestly be in three places at once. No single bell curve can say that. The particle filter throws the bell curve away and lets a swarm of guesses carry the belief — then fuses every new measurement by survival of the fittest.
A robot wakes up somewhere in a long office corridor and has no idea where. The corridor is almost featureless — identical doors, identical fluorescent panels, identical carpet — except for three fire extinguishers spaced evenly down the hall. The robot's only sensor is a little camera that can spot a fire extinguisher and report "there is one about two meters to my right." That is the entire universe: a hallway, three identical landmarks, and a robot asking "where am I?"
It senses a fire extinguisher two meters to its right. Now — where is it? Honestly, it could be next to the first extinguisher, or the second, or the third. The measurement is perfectly consistent with all three. The robot's belief about its own position is not a single guess with some wiggle room; it is three separate clusters of possibility, one hugging each extinguisher, with empty space between them. The truth lives in one of those clusters, but the robot has no way yet to tell which.
This is the entire reason the particle filter exists. When the fused belief has several peaks — engineers call this multimodal, "many modes" (a mode is a peak) — a single Gaussian is the wrong container. You need a representation flexible enough to hold any shape: three peaks, a banana-shaped ridge, a lopsided blob, whatever the data implies. The particle filter's answer is radically simple: stop trying to describe the belief with a formula. Represent it with a cloud of sample guesses instead.
Make the failure concrete. Say the three extinguishers sit at positions 10 m, 30 m, and 50 m down the hall, and after the sensor reading the robot's honest belief is "I'm right next to one of them," i.e. three tight clusters centered at 10, 30, and 50. What single Gaussian best fits that belief? A Gaussian is forced to put its peak at the average of the clusters:
So the best-fit Gaussian peaks at 30 m — the middle extinguisher. That is at least a real possibility. But to cover the clusters at 10 and 50 as well, the Gaussian must spread its width all the way out, putting enormous probability on positions like 20 m and 40 m — the empty hallway between the extinguishers, where the robot provably is not. The Gaussian's single hump smears probability exactly where the truth cannot be, and starves the two outer clusters where the truth might actually live. A one-hump distribution forced onto a three-hump belief is wrong everywhere. No choice of mean and variance fixes it; the container is the wrong shape.
Watch the mismatch directly. Below, the gray curve is the robot's true (multimodal) belief after the sensor reading — three peaks. The orange curve is the best single Gaussian anyone can fit to it. Drag the Gaussian's width and try to make it match. You can't: narrow it and it ignores two peaks; widen it and it floods the empty hallway between them.
The gray filled curve is the robot's honest belief — three peaks, one per identical landmark. The orange curve is a single Gaussian (a Kalman-style belief) trying to fit it. Drag its width and slide its center. Notice you can never make orange hug all three peaks at once — it either misses peaks or piles probability on the empty gaps where the robot cannot be.
The grey belief has structure the orange curve can never copy. That structure — "here OR here OR here, never between" — is exactly the information the robot needs, and it is precisely what a Gaussian throws away. We need a belief that can be any shape.
Here is the whole trick the rest of this lesson unpacks. Instead of a formula, scatter a few hundred dots across the hallway, each dot a hypothesis — one concrete guess of where the robot might be. Each dot is a particle. Where the robot is likely to be, pack many dots; where it is unlikely, leave few. The density of dots — how crowded they are — is the probability. Three clusters of dots, one per extinguisher, with empty gaps between: that is a three-peaked belief, drawn not as a curve but as a swarm.
And because each particle is a complete hypothesis, the filter handles the hallway gracefully. Sense a fire extinguisher and the clusters near each extinguisher get reinforced while particles in the empty hallway get starved. Drive forward, and every dot drives forward too. After enough driving — say the robot reaches the end wall — only one cluster will still be consistent with everything seen, and the swarm collapses onto it. The robot figures out which extinguisher it was next to, not by clever formula, but by letting the wrong hypotheses die off. That is the particle filter, and it is the topic of this lesson.
This is still the same recursive Bayesian estimation you met in the Bayes filter (Lesson 4): a loop of predict (move the belief forward through the motion model) and update (fuse the new measurement). The particle filter is just the Bayes filter with a particular, brilliantly flexible way of storing the belief. The algorithm was introduced for tracking by Gordon, Salmond, and Smith in 1993 (the "bootstrap filter"), and is laid out beautifully in Thrun, Burgard & Fox's Probabilistic Robotics, chapter 4 — the two sources this lesson is built on.
We decided to throw away the formula and represent the belief with a swarm of guesses. Now let's make "particle" precise, because everything downstream is just operations on this one object. A particle is a single concrete hypothesis about the hidden state — for our robot, one guessed position. A particle set is a collection of N of them, written
where each particle i carries two things: a guessed state x⁽ⁱ⁾ (a position, say 23.4 m down the hall) and a weight w⁽ⁱ⁾ — a non-negative number saying "how much should we believe this particular hypothesis right now." High weight = a hypothesis the data supports; low weight = one the data is arguing against. We'll spend Chapter 3 entirely on where weights come from; for now just hold that each dot has a position and a believability score.
There are two ways a particle set expresses probability, and it helps to keep them straight:
The two are convertible — that's what Chapter 4 (resampling) is about: it turns weight back into density by duplicating heavy particles and deleting light ones. After resampling, all weights reset to equal and the density alone carries the belief again. For now, picture the belief as the swarm's shape, with each dot lightly shaded by its weight.
It can feel suspicious that a finite pile of dots could stand in for a continuous probability curve. The justification is Monte Carlo approximation: if you draw N samples from a distribution, then for any question you might ask (what's the mean? the probability the robot is past the 25 m mark?), the answer computed from the samples converges to the true answer as N grows. Concretely, to estimate the probability that the robot is in some region, you just count the fraction of particles in that region:
Let's do it by hand. Suppose N = 10 particles sit at positions 9, 10, 11, 10, 31, 29, 30, 49, 51, 50 (three little clusters around 10, 30, 50). What's the probability the robot is in the window [8, 12]? Count: positions 9, 10, 11, 10 fall inside — that's 4 particles. So:
And the probability it's near the middle extinguisher, window [28, 32]? Positions 31, 29, 30 — 3 particles → 3/10 = 0.3. And the empty hallway [18, 22]? Zero particles → probability ~0, exactly right: the robot can't be in the empty gap. The dots reproduced the three-peaked belief that defeated the Gaussian, with no formula at all — just counting. That counting is the belief.
A Gaussian commits to a shape (one symmetric hump) before seeing the data. Particles commit to nothing: they take whatever shape the data carves out of them. The price is that you need many dots to draw a fine curve (more on the cost in Chapter 8), and the dots are random, so the picture flickers a bit. But the payoff is total: a particle set can represent a belief with three peaks, a sharp corner, a long tail, or a banana — anything — because it never assumed a shape to begin with. This is why particle filters are the workhorse whenever the world refuses to be a bell curve.
python import numpy as np # a particle set = N positions + N weights. That's the whole belief. N = 10 x = np.array([9,10,11,10,31,29,30,49,51,50], dtype=float) w = np.ones(N) / N # start with equal belief in every hypothesis def prob_in(lo, hi): # probability the state is in [lo, hi] inside = (x >= lo) & (x <= hi) return w[inside].sum() # sum the WEIGHTS inside (= fraction, since equal) prob_in(8, 12) # -> 0.4 (4 of 10 particles near the first landmark) prob_in(18, 22) # -> 0.0 (empty hallway -- the robot cannot be here)
Notice we summed weights, not counts — with equal weights that's the same as a fraction, but it's the general rule: the probability of a region is the total weight of the particles in it. The belief is two arrays. The next three chapters are just three operations on those two arrays: move them (predict), reweight them (the fusion step), and resample them.
The belief is a swarm of dots. Now the robot moves, and the belief must move with it. This is the first step of the recursive loop — the predict step (also called the motion update or proposal) — and in a particle filter it is almost shockingly literal: take every single particle and drive it forward exactly as if it were the real robot.
If the robot's wheels report "I moved forward 5 meters," then each particle — each hypothesis "maybe the robot is here" — updates to "well then, now it's 5 meters past here." A hypothesis at 10 m becomes a hypothesis at 15 m; one at 30 m becomes 35 m. The whole swarm slides forward together. That's it: the predict step applies the motion model to each particle independently.
If we moved every particle by exactly 5 m, we'd be claiming the wheels are perfect. They aren't: wheels slip, the floor is uneven, "5 meters" is really "about 5 meters, give or take." The Bayes filter taught us that the predict step must grow the uncertainty — the belief should get a little fuzzier each time we move, because motion injects error. In a particle filter we model that fuzziness by adding a small random jitter (noise) to each particle's move. Particle i updates as:
where u is the commanded/odometry motion (the "move forward 5 m"), and ε⁽ⁱ⁾ is a fresh random nudge drawn independently for each particle from a zero-mean bell curve with spread σmotion (how unreliable the wheels are). Crucially, every particle gets its own nudge, so a swarm that started as a tight clump spreads into a slightly wider clump — the dots fan out exactly as much as the motion is uncertain.
Take five particles, each carrying a guessed position, and command a move of u = 5 meters with motion noise σmotion = 1 m. To do it by hand we'll use a concrete (made-up but plausible) noise draw for each particle. Watch each one move forward 5 and then get its private nudge:
| Particle i | before x⁽ⁱ⁾ | + u (5 m) | + noise ε⁽ⁱ⁾ | after x⁽ⁱ⁾ |
|---|---|---|---|---|
| 1 | 10.0 | 15.0 | +0.4 | 15.4 |
| 2 | 10.2 | 15.2 | −0.7 | 14.5 |
| 3 | 9.8 | 14.8 | +1.1 | 15.9 |
| 4 | 10.1 | 15.1 | −0.3 | 14.8 |
| 5 | 9.9 | 14.9 | +0.6 | 15.5 |
The clump started tightly packed around 10 (spread of about 0.4 m, from 9.8 to 10.2). After the move it's centered near 15 — correct, that's where 5 m forward lands — but now spread from 14.5 to 15.9, a width of about 1.4 m. The cloud both translated (by the motion) and widened (by the noise). The widening is the point: the robot is now less certain of its position than before it moved, and the swarm honestly shows it.
Two things to notice. First, weights are untouched by the predict step — moving a hypothesis doesn't change how believable it was; only a measurement does that (next chapter). Second, the predict step never looks at any sensor; it only uses the robot's own motion. It's the "best guess from physics alone, before we look out the window" step.
python import numpy as np def predict(x, u, sigma_motion): # move EVERY particle by u, plus an independent random nudge each noise = np.random.normal(0, sigma_motion, size=x.shape) return x + u + noise # the whole swarm slides forward AND fans out x = np.array([10.0,10.2,9.8,10.1,9.9]) x = predict(x, u=5.0, sigma_motion=1.0) # -> roughly [15.4, 14.5, 15.9, 14.8, 15.5]: centered ~15, but now WIDER
Play with it below. Set the move distance and the motion noise, then press Move repeatedly and watch the clump march across the hallway, fanning wider with every step. Crank the noise up and a few moves blow the cloud apart; set it to zero and the cloud translates rigidly (and lies about being certain).
A clump of particles starts near the left. Press Move to command a step of size u; every particle slides forward by u plus its own random nudge of spread σ. Watch the cloud both translate (by u) and widen (by σ). More motion noise → faster spreading.
Predict pushed the cloud forward and made it fuzzier. Now the robot looks — takes a measurement — and we must fold that new evidence in, sharpening the belief. This is the weight step, and it is the heart of the lesson, because weighting is the fusion step. Everything you learned about combining a prior with a measurement happens right here, particle by particle.
The mechanism is delightfully direct. We have a swarm of hypotheses (the prior, from predict). A measurement arrives — say the robot's range sensor reports "the wall is 8 m ahead." We ask of every single particle: "If the robot really were at your position, how likely is it that we'd have seen this exact measurement?" A particle whose position would naturally produce an 8 m reading gets a high score; a particle whose position would predict a 20 m reading gets a tiny score, because the data argues against it. That score is the particle's new weight.
To score a particle we need two ingredients. First, the measurement model h(x): what reading should we get if the robot were at position x? If the wall is at position 20 m and the sensor measures distance-to-wall, then a robot at x predicts a reading of h(x) = 20 − x. Second, the measurement noise: real sensors are imperfect, so the actual reading z scatters around h(x) with some spread σsense. The standard choice is a Gaussian likelihood — a particle's weight is how tall that bell curve is at the gap between what it predicted and what we actually saw:
Read it in plain words: let rⁱ = z − h(x⁽ⁱ⁾) be the residual (also called the innovation) — how far this particle's prediction missed the actual reading. The weight is large when the residual is near zero (the particle predicted what we saw) and shrinks fast as the residual grows. The σsense sets how forgiving we are: a precise sensor (small σ) punishes mismatches harshly; a sloppy sensor (large σ) is lenient. Note the residual is the same "z − h(x)" quantity that drives the Kalman filter's correction — the particle filter just uses it to score hypotheses instead of to nudge a mean.
Make it fully concrete. Five particles sit at positions after the predict step. The wall is at 20 m, the sensor measures distance-to-wall, so h(x) = 20 − x. The robot's actual reading is z = 8 m (so the truth is near 12 m). Sensor noise σsense = 1 m, so 2σ² = 2. Compute each residual r = z − h(x) = 8 − (20 − x) = x − 12, then the raw weight exp(−r²/2):
| i | x⁽ⁱ⁾ | h(x)=20−x | r = 8 − h(x) = x−12 | r² | raw w = exp(−r²/2) |
|---|---|---|---|---|---|
| 1 | 12 | 8 | 0 | 0 | exp(0) = 1.000 |
| 2 | 11 | 9 | −1 | 1 | exp(−0.5) = 0.607 |
| 3 | 13 | 7 | +1 | 1 | exp(−0.5) = 0.607 |
| 4 | 14 | 6 | +2 | 4 | exp(−2) = 0.135 |
| 5 | 9 | 11 | −3 | 9 | exp(−4.5) = 0.011 |
Particle 1, which predicted exactly the reading we got, scores a perfect 1.0. Particles 2 and 3, off by one meter, score 0.607. Particle 5, off by three meters, is almost annihilated at 0.011. The data has spoken: it loves the hypotheses near 12 m and despises the one at 9 m. That is the measurement getting fused in — not by moving anything, but by re-scoring every hypothesis.
Raw weights are only relative — the formula had a "∝" (proportional-to), because we dropped the constant in front of the exponential. To turn them into a proper probability distribution we normalize: divide each by the total. Sum the raw weights:
Then each normalized weight is raw / S:
| i | raw w | normalized w = raw / 2.360 |
|---|---|---|
| 1 | 1.000 | 1.000 / 2.360 = 0.424 |
| 2 | 0.607 | 0.607 / 2.360 = 0.257 |
| 3 | 0.607 | 0.607 / 2.360 = 0.257 |
| 4 | 0.135 | 0.135 / 2.360 = 0.057 |
| 5 | 0.011 | 0.011 / 2.360 = 0.005 |
Check: 0.424 + 0.257 + 0.257 + 0.057 + 0.005 = 1.000. ✓ Now the weights are a believability distribution over the five hypotheses. Particle 1 holds 42% of the belief; the badly-mismatched particle 5 holds half a percent. This re-weighted cloud is the fused posterior — the predict-step prior, sharpened by the measurement. We did Bayes' rule with arithmetic, no calculus.
python import numpy as np def weight(x, z, sigma_sense, wall=20.0): pred = wall - x # measurement model h(x): distance to wall r = z - pred # residual: how far each particle missed z w = np.exp(-(r**2) / (2 * sigma_sense**2)) # Gaussian likelihood = the fusion return w / w.sum() # NORMALIZE so weights sum to 1 x = np.array([12,11,13,14,9], dtype=float) w = weight(x, z=8.0, sigma_sense=1.0) # -> [0.424, 0.257, 0.257, 0.057, 0.005] (matches the hand table)
Below, place a measurement (a reading of distance-to-wall) and watch every particle get re-scored. Particles near the consistent position glow bright (high weight); particles far away fade (low weight). Drag the sensor-noise slider: a tight sensor makes the weighting brutally selective; a loose one barely distinguishes the particles. This re-scoring is the moment the measurement fuses into the belief.
Particles sit across the hallway. The robot reports a distance-to-wall reading (the dashed marker shows the implied position). Each particle's brightness = its weight: bright = "you predicted this reading well." Slide the measurement to move the evidence, and sensor noise to set how sharply mismatches are punished.
After weighting, our cloud has a problem hiding in plain sight. The belief is now carried by the weights (particle 1 holds 42%, particle 5 holds 0.5%) — but the positions haven't moved. Worse, if we just keep multiplying weights every step, a handful of particles will hoard nearly all the weight while hundreds sit around with near-zero weight, doing nothing but wasting computation. We need to convert the weight back into density — to make the positions reflect the belief again. That conversion is resampling, and the idea is brutal and biological: survival of the fittest.
Resampling builds a fresh set of N particles by drawing from the current set with probability proportional to weight. A heavy particle gets drawn many times — it spawns several copies. A light particle is almost never drawn — it dies out. After resampling, the new cloud has many particles where the heavy ones were (high density — high belief) and none where the light ones were (the wrong hypotheses are gone). Then we reset all weights to equal (1/N), because the belief now lives in the density again, not the weights.
The obvious resampling method: for each of the N new particles, spin a weighted roulette wheel (pick a random number, find which particle's weight-slice it lands in). This works, but it's slow (O(N log N) with a binary search) and, worse, it's noisy — N independent random spins can, by bad luck, over-sample some regions and miss others, adding random error to the belief. There is a far better method that's both faster and lower-noise, and it's the one everybody uses.
The trick (Thrun, Burgard & Fox call it low-variance sampling) is to use one random number, not N. Imagine laying all the weights end-to-end along a number line of total length 1 — each particle owns a segment as wide as its weight. Now drop a comb of N evenly-spaced teeth (spacing 1/N) onto that line, with the comb's starting offset chosen randomly in [0, 1/N). Each tooth lands in some particle's segment — that particle gets selected once per tooth that lands on it. Heavy particles own wide segments and catch several teeth; light particles own thin segments and may catch none.
Why this is better: the teeth are evenly spaced, so the selection is systematic — it can't accidentally clump or leave gaps the way N independent spins can. Only the single starting offset is random. The result has much lower variance (hence the name) and runs in O(N) with no sorting. One random draw, one linear sweep.
Take the five normalized weights from Chapter 3: [0.424, 0.257, 0.257, 0.057, 0.005] for particles at positions [12, 11, 13, 14, 9]. We want N = 5 new particles. The comb spacing is 1/N = 0.2. First lay out the cumulative weights — the right edge of each particle's segment:
| particle | position | weight | cumulative (segment ends at) |
|---|---|---|---|
| 1 | 12 | 0.424 | 0.424 |
| 2 | 11 | 0.257 | 0.681 |
| 3 | 13 | 0.257 | 0.938 |
| 4 | 14 | 0.057 | 0.995 |
| 5 | 9 | 0.005 | 1.000 |
Now pick a random start offset in [0, 0.2). Say we draw r₀ = 0.1. The five comb teeth are at r₀ + k·(0.2) for k = 0,1,2,3,4:
For each tooth, find the first particle whose cumulative edge is ≥ the tooth (i.e. which segment it lands in):
| tooth | which segment? | selected particle (position) |
|---|---|---|
| 0.1 | ≤ 0.424 → particle 1 | P1 (pos 12) |
| 0.3 | ≤ 0.424 → particle 1 | P1 (pos 12) |
| 0.5 | between 0.424 and 0.681 → particle 2 | P2 (pos 11) |
| 0.7 | between 0.681 and 0.938 → particle 3 | P3 (pos 13) |
| 0.9 | between 0.681 and 0.938 → particle 3 | P3 (pos 13) |
The new particle set is positions [12, 12, 11, 13, 13], all with equal weight 1/5 = 0.2. Read what happened: particle 1 (the heavy 42% one) got copied twice; particles 2 and 3 survived; the near-dead particles 4 (pos 14) and 5 (pos 9) were not selected at all — they're gone. The cloud has collapsed toward the high-belief region around 12 m, exactly where the measurement said the robot is. Survival of the fittest: heavy hypotheses reproduce, light ones go extinct.
python import numpy as np def low_variance_resample(x, w): N = len(x) positions = (np.arange(N) + np.random.uniform()) / N # the comb: one random offset, even teeth cumsum = np.cumsum(w) # segment edges along [0,1] cumsum[-1] = 1.0 # guard against float round-off new_x = np.zeros(N); i = 0 for j in range(N): # one linear sweep -> O(N) while positions[j] > cumsum[i]: i += 1 # find which segment tooth j fell in new_x[j] = x[i] # copy that particle return new_x, np.ones(N) / N # reset weights to equal: density carries belief now x = np.array([12,11,13,14,9], dtype=float) w = np.array([0.424,0.257,0.257,0.057,0.005]) x, w = low_variance_resample(x, w) # -> heavy particles duplicated, light ones dropped; weights all 1/N again
Below, set five (or more) weights and run the comb. The blue ticks are the comb teeth; watch which segment each lands in, and see the resampled cloud collapse onto the heavy particles. Re-run it: only the random offset changes, and the selected counts barely move — that stability is the "low variance."
Top bar: each particle owns a segment as wide as its weight. The comb drops N evenly-spaced teeth (one random offset). Each tooth selects the particle whose segment it lands in. Bottom: the resampled set — heavy particles duplicated, light ones gone. Press Resample to redraw the offset; press Skew weights to make one particle dominate.
One full loop is now complete: predict (Ch 2) moves the cloud and fuzzes it, weight (Ch 3) fuses the measurement by scoring each particle, resample (Ch 4) collapses onto the survivors. Repeat forever. But resampling has a dark side — do it too aggressively and the cloud collapses too far. That failure mode is the whole next chapter.
The predict-weight-resample loop has two opposite ways of going wrong, and a single number that diagnoses both. Understanding them is what separates a particle filter that works from one that silently lies. The disease is called degeneracy — the diversity of the swarm collapsing — and it comes in two flavors.
If you weight many times without resampling, the weights become wildly uneven: one particle ends up with weight 0.9999 and the other 999 hold a combined 0.0001. The belief is then carried by essentially one particle — you paid to simulate 1000 hypotheses but only one matters. Your "thousand-sample" estimate is really a one-sample estimate, with all the noise that implies. This is weight degeneracy: the weight piles onto a vanishing fraction of particles.
Resampling cures weight degeneracy — but overdo it and you get the opposite disease. Every resample duplicates heavy particles, and duplicates are identical copies, occupying the exact same point. With no new motion noise to spread them, repeated resampling makes the cloud collapse to a few distinct positions, then eventually to a single point — all N particles stacked on one spot. The filter becomes falsely, catastrophically certain. This is sample impoverishment (or particle impoverishment): diversity is lost not because the data demanded it, but as a side effect of resampling noise.
The effective sample size, written N₎ₐₐ, answers: "given how uneven my weights are, how many equally-weighted particles would carry the same amount of information?" If all N weights are equal, N₎ₐₐ = N (full diversity). If one particle holds all the weight, N₎ₐₐ = 1 (you effectively have one sample). The standard formula is one over the sum of squared weights:
where the weights are normalized (sum to 1). The intuition: squaring punishes unevenness. If weights are spread out, each is small and its square is tiny, so the sum is tiny and 1/sum is large (near N). If one weight is near 1, its square is near 1, the sum is near 1, and 1/sum ≈ 1.
Case A — perfectly even weights. Five particles, each w = 0.2. Sum of squares = 5 × (0.2)² = 5 × 0.04 = 0.20.
All five particles pulling their weight → N₎ₐₐ = 5 = N. Maximum diversity, healthy.
Case B — the Chapter-3 weights. w = [0.424, 0.257, 0.257, 0.057, 0.005]. Square each: 0.1798, 0.0660, 0.0660, 0.0032, 0.0000. Sum:
Out of 5 particles, only about 3.2 are really contributing — the two near-dead ones barely count. Still healthy-ish (3.2 of 5 is fine), but the number tells you the swarm is starting to concentrate.
Case C — one particle hogs everything. w = [0.97, 0.01, 0.01, 0.005, 0.005]. Squares: 0.9409, 0.0001, 0.0001, 0.000025, 0.000025. Sum ≈ 0.9412.
You have 5 particles but effectively 1. This is severe weight degeneracy — resample now, before the belief becomes a single noisy sample.
python import numpy as np def n_eff(w): return 1.0 / np.sum(w**2) # effective sample size (w normalized) n_eff(np.full(5, 0.2)) # -> 5.00 even weights, full diversity n_eff(np.array([.424,.257,.257,.057,.005])) # -> 3.17 concentrating n_eff(np.array([.97,.01,.01,.005,.005])) # -> 1.06 degenerate -- resample! # the gate, in the main loop: if n_eff(w) < N / 2: x, w = low_variance_resample(x, w) # resample only when degenerate
Below, drag the weight-skew slider from "even" to "one dominates" and watch N₎ₐₐ slide from N down toward 1. The dashed line is the N/2 resample threshold; cross below it and the readout flags "resample now." Feel how the squared-weight sum reacts to unevenness.
Bars are the particle weights. Drag skew from 0 (all equal) to 1 (one particle hogs everything) and watch Neff = 1/Σw² fall from N toward 1. The dashed line is the N/2 threshold: below it, the filter is degenerate and you should resample.
Every piece is on the table: particles as a sampled belief, predict, weight (the fusion step), resample, and the N₎ₐₐ meter that keeps it honest. Now we run them all at once on the canonical application — Monte Carlo Localization (MCL), a robot finding itself on a 2-D map using a cloud of particles. This is the algorithm inside countless real robots, and the payoff chapter of the lesson: no new theory, just every idea above made visible, interactive, and breakable.
A robot lives on a square map with a handful of landmarks (the orange beacons). It cannot see its own position; it can only measure its distance to each landmark (noisily) and command its own motion. The cloud of blue particles is its belief about where it is. Press Drive + Sense and watch the loop run: every step the cloud predicts (each particle drives like the robot, plus jitter), weights (each particle scored by how well its landmark-distances match the real reading), and resamples (the cloud collapses onto the survivors). Over a few steps the diffuse cloud snaps onto the true robot.
The green dot is the true robot (hidden from the filter). The blue dots are particles — the belief. Orange beacons are landmarks; the robot measures noisy distances to them. Press Drive + Sense to step the filter; the cloud predicts, weights, resamples, and collapses onto the truth. Sliders set the particle count and the sensor noise. Kidnap teleports the robot — watch the belief scatter and re-converge.
Run the loop a few times from a fresh scatter and the three steps announce themselves:
Don't just watch — falsify. Run this sequence and confirm each prediction with your own eyes:
The kidnap is the deepest moment: it stages Chapter 0's multimodal belief in real time. Right after the teleport, no particle is near the truth, so the filter must rely on the lucky few that get re-energized once the robot drives near them — or on injected random particles (a real MCL trick). Watch the belief temporarily hold two clusters — the dying old one and the growing new one — the exact two-peaked belief a single Gaussian could never represent. That is why this robot runs a particle filter and not a Kalman filter.
Every lesson in this series ends with the same four chapters — Use Cases, Practical Application, Debugging, Connections — because a method you can't point at in a shipped product is a method you don't yet own. So before any more theory, let's ground the particle filter in hardware running it right now.
The particle filter earns its keep wherever the belief refuses to be a single bell curve: multimodal localization, heavy-tailed sensor noise, nonlinear measurement models, and the global "where am I, with no prior" problem. Here are the headline deployments.
Robot-vacuum / AMCL localization. Open the navigation stack of almost any modern robot (and the open-source ROS ecosystem) and you'll find AMCL — Adaptive Monte Carlo Localization — the exact algorithm from Chapter 6. A robot vacuum or warehouse AMR holds a particle cloud over a pre-built map and matches its LiDAR scan against the map's walls to weight particles. The "adaptive" part is KLD-sampling: it uses many particles when the belief is spread across the whole map (just powered on, or kidnapped) and few once it's localized — spending computation only when uncertainty demands it.
Multi-target tracking. Tracking several objects (radar tracking aircraft, a camera tracking pedestrians, sonar tracking fish) is inherently multimodal: which blip is which target, and is that new blip a target or clutter? Particle filters handle the non-Gaussian, multi-hypothesis nature head-on — each cluster of particles can ride a different target, and the data association ambiguity lives naturally as multiple modes. The 1993 Gordon et al. bootstrap filter was born for exactly this radar-tracking problem.
Global localization & the kidnapped-robot problem. A Kalman filter must be initialized near the truth — it cannot start from "I could be anywhere." A particle filter can: scatter particles uniformly over the whole map and let the measurements winnow them. This makes it the default for global localization (find yourself from scratch) and recovery from kidnapping (someone moved you) — the very scenario the Chapter 6 sim staged.
FastSLAM and visual tracking. FastSLAM factors the SLAM problem so each particle carries its own map hypothesis — a landmark estimate per particle — letting the filter represent ambiguity about both the robot's path and the map. In computer vision, the CONDENSATION algorithm (Isard & Blake, 1998) used particle filters to track contours through clutter where Gaussian trackers lost lock. Anywhere the posterior is genuinely non-Gaussian, particles are the tool.
Notice why each chose a particle filter over a Kalman filter:
| Product / domain | What's fused | Why a particle filter (not KF) |
|---|---|---|
| Robot-vacuum / AMCL | LiDAR scan + odometry + map | multimodal belief in symmetric rooms; global localization from scratch |
| Radar / sonar multi-target | detections over time | data-association ambiguity is inherently multi-hypothesis |
| FastSLAM | landmarks + path | each particle = one map hypothesis; non-Gaussian joint belief |
| Visual contour tracking | image edges over frames | clutter creates multiple modes; Gaussian tracker loses lock |
| Financial / signal models | nonlinear state-space series | arbitrary, heavy-tailed, nonlinear likelihoods |
Three diagnostic questions reveal it:
If all three are "no" — a single mode, good initialization, mild nonlinearity, Gaussian noise — a Kalman/EKF/UKF is cheaper and you should prefer it. The particle filter is the tool for the hard, non-Gaussian cases; the next chapter makes that choice precise.
You know the loop; now we make the engineering decisions mechanical. This "now build it" chapter turns the theory into a small set of choices — how many particles, what measurement model, when to resample, and crucially, when a particle filter beats a Kalman filter at all — so you're never guessing on a real project.
Don't reach for particles reflexively — they're expensive. Walk this checklist; if you can answer "no" to all of it, use a Kalman-family filter instead.
The hardest knob. Too few and the cloud can't cover the belief — it under-samples the space, latches onto a wrong mode, or fails to recover from a kidnap. Too many and you waste compute. The brutal fact is that the number of particles needed to cover a region grows exponentially with the state dimension — the curse of dimensionality.
Feel it with numbers. Suppose you need about 10 particles per dimension to tile the space adequately:
| State dimension d | Particles to cover (~10ᵈ) | Verdict |
|---|---|---|
| 1 (position on a line) | 10 | trivial |
| 2 (x, y) | 100 | easy |
| 3 (x, y, θ) | 1,000 | fine — typical MCL |
| 6 (3-D pose) | 1,000,000 | painful |
| 10+ (pose + velocities + biases) | 10,000,000,000 | hopeless — don't |
This is why particle filters dominate low-dimensional localization (1–4 D) and are rarely used raw for high-dimensional state. The fix when you must go high-D is to factor the problem (FastSLAM samples only the trajectory and solves the rest analytically) or to fall back to a Gaussian filter for the easy dimensions. Rule of thumb: 500–1000 particles for 2-D/3-D MCL; if you're tempted to use 100,000, your state is too big for a vanilla particle filter.
The weight step is only as good as h(x), the model of "what reading should I get at this state." Two failure modes to engineer around:
From Chapter 5: don't resample every step (it causes impoverishment) and don't never resample (weight degeneracy). The standard recipe is the N₎ₐₐ gate — resample only when N₎ₐₐ < N/2 — plus a touch of "roughening" (extra motion jitter on duplicated particles) to keep diversity. This single rule resolves the whole push-pull from Chapter 5.
The task: an AMR must localize on a known 2-D floor map (state = x, y, heading θ — 3 dimensions) using a LiDAR scan, starting from anywhere. Walk the decisions.
The design reads as a sentence: "Adaptive (KLD) particle filter, ~1000→200 particles over the 3-D pose, likelihood-field LiDAR model with an outlier floor, resample on Neff<N/2 with 2% random injection." Every choice traces to one of the four decisions.
A particle filter rarely crashes; it fails by quietly producing a confident wrong answer. The bugs are subtle — a cloud that looks tight and healthy can be catastrophically wrong — and they hide until exactly the wrong moment (a kidnap, an outlier reading, a symmetric room). This recurring chapter catalogs the classic traps, the symptom each shows in the field, and the specific test that exposes it. The master diagnostic is one number you already know: N₎ₐₐ. Log it every step; most of these failures show up there first.
You weight many times without resampling (or resample too rarely), and the weight piles onto one or two particles. Your 1000-particle "belief" is really a one-particle estimate — jumpy, noisy, and falsely shaped by whichever particle happened to win.
The opposite disease. You resample too aggressively (e.g. every step), and because resampling duplicates heavy particles into identical copies, the cloud collapses to a few — eventually one — distinct positions. The filter becomes certain of a single point and can never represent uncertainty again; if that point is wrong, it can never recover.
The deepest particle-filter trap, straight out of Chapter 0. In a symmetric environment the belief is genuinely multimodal — several clusters, only one correct. With too few particles, or after an unlucky resample, all the particles end up in one cluster — and it's the wrong one. The filter is now tightly, confidently localized at a false position, and because no particle survives near the truth, no future measurement can pull it back.
| What N₎ₐₐ does | Distinct particles | Diagnosis |
|---|---|---|
| healthy: dips after weight, restored by resample | many, spread | working correctly |
| collapses toward 1, never recovers | still many positions | Trap 1: weight degeneracy — resample more |
| pinned at N (you resample every step) | collapsing toward 1 | Trap 2: impoverishment — resample less + roughen |
| healthy-looking, residuals small | one tight cluster | Trap 3: wrong mode — check against ground truth |
Two related, common bugs. Resampling noise: each resample injects a little randomness (which particle gets duplicated is partly luck), so resampling every step adds jitter to the estimate — the cure is the N₎ₐₐ gate and low-variance sampling. Over-sharp likelihood: if you set the sensor σ far too small, then after the weight step almost every particle has near-zero weight (only those matching the reading to the millimeter survive), N₎ₐₐ crashes to ~1 every single step, and a single outlier reading can annihilate the entire correct cloud.
| Check | How | Catches |
|---|---|---|
| Log N₎ₐₐ every step | 1/Σw²; watch dip-then-recover | Traps 1 & 4 (degeneracy, over-sharp likelihood) |
| Count distinct particles | how many unique positions remain? | Trap 2 (impoverishment) |
| Compare to ground truth | offset by a symmetry distance? | Trap 3 (wrong mode) |
| Kidnap test | teleport truth; does it recover? | too-few particles, no random injection |
| Inflate σ / add outlier floor | does N₎ₐₐ stop crashing? | Trap 4 (over-sharp likelihood) |
You can now represent a belief of any shape and fuse measurements into it by survival of the fittest. Before we point to what's next, here is everything in one place — the cheat-sheet to screenshot, the real sources, the cross-links, and the motto.
Screenshot this. It is the whole "which filter?" decision collapsed into a row:
| Filter | Belief shape | Cost | Best when |
|---|---|---|---|
| Kalman | one Gaussian, linear | tiny (closed form) | single mode, linear, Gaussian, good init |
| EKF / UKF | one Gaussian, nonlinear | small | single mode, mild–moderate nonlinearity |
| Particle | any shape (multimodal) | high (N samples, curse of dim.) | multimodal, global localization, non-Gaussian |
This was Lesson 10 of 22, the last of the classical estimation filters. We climbed the ladder of belief representations: Lesson 4 gave the general Bayes filter; Lesson 5 the Kalman filter (the Bayes filter when everything is linear and Gaussian); Lessons 6–9 the EKF/UKF (nonlinear, still Gaussian). The particle filter is the rung where we finally drop the Gaussian assumption entirely and represent belief by sampling. Next, Lesson 11 takes these filters into spatial fusion — occupancy grids and the mapping side of SLAM — where the particle filter you just learned reappears as the engine of Monte Carlo Localization and FastSLAM.
These go deeper on machinery we touched: