Particle Filter

A particle filter keeps its belief not as a tidy bell curve but as a swarm of guesses, each one a complete little robot insisting "I am right here." Most of them are wrong. The trick is that the world keeps voting, and bad guesses keep losing. Watch a swarm hunt for the truth below.

The robot lives in a known floor-plan of walls and rooms. Orange dots are particles, each a guess at the robot's pose, scattered across every room because the robot starts globally lost. The faint rays are the robot's real lidar scan: distances to the nearest walls. The accent ring is the filter's weighted-mean estimate; the white dot is the true pose, which the filter never sees. The status line above the map reports the cloud's spread, the effective particle count, and the live error.

Try this:

1. Watch the heartbeat. Use Step once to walk through the rhythm by hand and read the phase badge: PREDICT (every particle drives the same command, the cloud smears), UPDATE (each particle imagines its own scan and is weighted by how well it matches), RESAMPLE (the losers are culled, winners cloned).
2. Watch it un-lose itself. From the scattered start, drive a few steps. As the robot passes through a distinctive corner or threads a doorway, the cloud collapses from "could be anywhere" onto one tight cluster: the spread readout falls toward zero. A Kalman filter cannot start this lost.
3. Kidnap the robot. Tap Kidnap (reset). Particles re-scatter across the whole map (total amnesia) then re-converge within a handful of scans. This is the kidnapped-robot test that breaks a Kalman filter.
4. Catch the doubt. Early on, in a symmetric part of the building, the cloud holds two or more blobs at once: the scan looks the same from several rooms. The filter is honestly saying "I might be in any of these" and waits for one more wall to break the tie.
5. Starve it. Drop the count to 40 particles. Does the swarm still find you, or does it get unlucky and converge on a lie? Crank sensor σ up and the filter trusts each scan less, so it stays lost longer.

Belief as a crowd, not a curve

A Kalman filter describes your location with a mean and a covariance: one peak, perfectly symmetric, gloriously certain. That works right up until reality has two peaks. You wake up in a generic office building, see a hallway, and genuinely cannot tell floor 1 from floor 2. Asked to summarize that as a single bell curve, Kalman averages the two floors and confidently reports that you are hovering in the elevator shaft between them. 💥

The particle filter sidesteps the whole problem by never summarizing. It just keeps the crowd. One particle sits on floor 1, another on floor 2, hundreds more scattered as honest doubt. The shape of the cloud is the belief, and a cloud can be lumpy, lopsided, or split clean in two. This is what multimodal means, and it is the particle filter's superpower.

Predict, weigh, resample

The swarm lives by a three-beat rhythm, run a hundred times a second.

Predict. Every particle takes the robot's motion command and moves, plus a dash of random noise, because no two real robots slip identically. The cloud smears outward. Uncertainty grows.

Weigh. A sensor reading arrives. Each particle asks: if I were the true robot, how surprised would I be to see this? Particles whose imagined view matches reality get a fat weight; particles predicting a red door where there's a blank wall get almost nothing.

Resample. Now the brutal part. We draw a fresh thousand particles, picking each in proportion to its weight. Heavy particles get cloned many times over; the featherweights vanish. This is survival of the fittest in code: no particle is edited, only born or culled. The crowd quietly migrates toward wherever the evidence is strongest.

↘ Born on the bomb: the physics roots that predate robots by 50 years

Long before any robot rolled the dice, physicists were doing it to model atoms. In 1948 Enrico Fermi and Robert Richtmyer wrote a memo (its dry title: Note on census-taking in Monte Carlo calculations) describing how to follow a crowd of imaginary neutrons through a chain reaction, splitting the busy ones and killing off the rest. That birth-and-death bookkeeping is exactly resampling, decades early. In 1955 the husband-and-wife pair Marshall and Arianna Rosenbluth used the same trick to fold long polymer molecules, "pruning" hopeless chains and "enriching" promising ones. In 1984 Jack Hetherington reinvented it again to estimate the ground-state energy of quantum systems.

Each field thought it had a fresh idea. None of them called it a particle filter. That name only arrived in 1996, coined by the mathematician Pierre Del Moral, who also gave these methods their first rigorous proof of correctness. So the swarm in the demo above carries a strange pedigree: it was first imagined to design a weapon, reused to study plastics and quantum atoms, and only decades later pointed at a robot trying to find itself in a hallway.

The two thinkers whose ideas quietly run inside every beat of that loop lived more than a century apart and never met:

↘ The math: a delta-function crowd, weighted by Bayes

The filter represents the posterior belief over the state $x_t$ given all measurements $z_{1:t}$ as a weighted sum of point masses:

$$p(x_t \mid z_{1:t}) \approx \sum_{i=1}^{N} w_t^{(i)} \, \delta\!\left(x_t - x_t^{(i)}\right)$$

Each $x_t^{(i)}$ is one particle's hypothesized state and $w_t^{(i)}$ its weight. As $N \to \infty$ this approximation becomes exact: the swarm can mimic any distribution, no Gaussian assumption required.

Predict pushes each particle through the motion model with added process noise $Q$:

$$x_t^{(i)} = f\!\left(x_{t-1}^{(i)}, u_t\right) + \mathcal{N}(0, Q)$$

Weigh applies Bayes' rule, multiplying the prior weight by the measurement likelihood:

$$w_t^{(i)} \propto p\!\left(z_t \mid x_t^{(i)}\right) \cdot w_{t-1}^{(i)}$$

then normalize so the weights sum to one.

Resample draws a new generation, selecting particle $i$ with probability equal to its normalized weight:

$$P(\text{select } i) = w_t^{(i)}$$

That last step is what fights degeneracy. Without it, one particle eventually hoards all the weight and the other 999 become dead computation. Resampling spends the crowd where the probability mass actually is.

Where the swarm earns its keep

The cost is real: simulating a thousand robots is far heavier than propagating one Gaussian, and covering an entire building with enough particles is genuinely hard, which is why production systems use Adaptive Monte Carlo Localization (AMCL), spawning more particles when lost and fewer once confident. The payoff is worth it whenever the world is ambiguous, the noise is non-Gaussian, or the robot might be globally lost.

The same idea showed up in computer vision under a different banner. In the mid-1990s Michael Isard and Andrew Blake built a tracker they called condensation, short for conditional density propagation, that followed a wiggling hand or a dancer through a cluttered video frame. When the target ducked behind a chair, a single-peak tracker would lock onto the background and lose it for good. The condensation particles just kept several guesses alive and waited for the target to reappear. Robots localizing on a map and cameras tracking a moving shape turned out to be the same problem wearing different clothes.

So a Roomba feeling its way around your living room runs this exact algorithm. ROS, the de facto robot operating system, ships AMCL as its default localizer. Warehouse robots thread between QR-coded landmarks the same way. They all start every run a little bit lost, and they all find themselves the same way: by guessing wrong a thousand times at once and letting the world cross out the lies.

Key takeaways

• A particle filter holds belief as a swarm of guesses, not a single bell curve, so it can represent lumpy, multimodal "I might be in two places" uncertainty.
• The loop is predict, weigh, resample, and resampling is survival of the fittest: clone the likely particles, cull the unlikely ones.
• Unlike the Kalman filter it tracks several hypotheses at once, which lets it survive the kidnapped robot problem and solve global localization from scratch.
• The price is compute (a thousand simulated robots) tamed in practice by adaptive methods like AMCL.