Particle Filters

Imagine trying to track a submarine through murky water. You can hear pings — noisy echoes that tell you roughly how far away something is — but the ocean scrambles the signal. You cannot see the submarine. You don't know where it went between pings. Yet Navy sonar operators pin down its position with startling accuracy.

The algorithm behind that trick — and behind the self-locating phone in your pocket, the drones that fly through GPS-denied buildings, and the Mars rovers that navigate on their own — is called the particle filter (also known as Sequential Monte Carlo, or SMC).

The idea is disarmingly simple: instead of tracking a single best guess of where the target is, you maintain thousands of guesses at once — called particles — each representing one plausible position and velocity. Every time a new noisy sensor reading arrives, you ask each particle: "How well does this reading fit if I were here?" Particles that fit well get more copies in the next round; particles that fit poorly get dropped. The cloud of survivors is your running estimate of reality.

This predict-weight-resample loop, invented by Neil Gordon, David Salmond, and Adrian Smith in 1993, transformed state estimation. Kalman filters — the reigning approach since the Apollo missions — could only handle Gaussian noise and linear dynamics. Particle filters handle any distribution, any nonlinear motion model, any weird sensor. The cost is computation: you need enough particles to fill the plausible space, and that number can explode in high dimensions.

The canvas below shows a target dot moving on a random walk (blue). The particle cloud (small orange dots) starts scattered randomly across the canvas. Every frame the filter runs one full cycle: predict new positions, weight by closeness to the target's noisy sensor reading (the dashed circle), then resample — duplicating good particles and dropping bad ones.

<div class="controls">
  <label>{{lbl_particles}}: <span id="nLabel">300</span>
    <input type="range" id="nSlider" min="50" max="800" value="300" step="50">
  </label>
  <label>{{lbl_noise}}: <span id="noiseLabel">30</span>
    <input type="range" id="noiseSlider" min="5" max="80" value="30" step="5">
  </label>
  <div class="btns">
    <button id="pauseBtn" type="button">{{btn_pause}}</button>
    <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<canvas id="canvas" width="480" height="300"></canvas>
<div id="info" class="info">{{info_running}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem 1.2rem; align-items: center; margin-bottom: .5rem; font-size: .85rem; }
label { display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 90px; accent-color: #e07b39; }
.btns { display: flex; gap: .5rem; margin-left: auto; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #dde3e8; border-radius: 8px; max-width: 100%; }
.info { font-size: .82rem; color: #555; margin-top: .4rem; min-height: 1.3em; }

// Code not found

Notice how the cloud collapses around the target after a few seconds, then stretches to follow it as it wanders. Hit Pause to freeze a frame and inspect the spread; hit Reset to scatter the particles again from scratch. Crank up the noise slider to simulate a less accurate sensor and watch the cloud widen.

The key insight: no single particle is "the answer." The answer is the weighted average of the whole cloud — and the cloud's spread tells you how confident the algorithm is.

Particle filters are a solved tool in low dimensions and an open research frontier in high ones.

What is proven:

• Convergence: as the number of particles N → ∞, the particle distribution converges to the true posterior — a theorem proved by Pierre Del Moral in the late 1990s.
• Consistency: the estimated mean and variance approach the truth; error decreases roughly as 1/√N.
• Flexibility: no assumptions on the noise distribution or the dynamics model — the particles carry the distribution implicitly.

The hard part — the curse of dimensionality: To cover a d-dimensional state space with enough particles that at least one sits near the true state, you need roughly N ∝ εᵈ particles for precision ε. In a 3D navigation problem a few thousand particles suffice. In a 50-dimensional robot arm, you would need more particles than atoms in the observable universe. This is not a limitation of particle filters specifically — it is a fundamental barrier for any sample-based method.

Practical mitigations:

• Rao-Blackwellization: analytically marginalize out the linear-Gaussian part of the state, leaving only the nonlinear residual for particles. Used in FastSLAM.
• Auxiliary particle filters (Pitt & Shephard, 1999): look one step ahead when resampling to avoid wasting particles on bad predictions.
• Sequential importance resampling (SIR) tuning: choose the right resampling schedule — too often and you lose diversity (sample impoverishment); too rarely and weights degenerate.

Unlike Bayesian inference, which is generally intractable and only approximately solved, particle filters are exact in the limit — they just need a lot of samples to get there. The bottleneck is entirely computational, not theoretical.

Anywhere a system moves through an uncertain state space and receives noisy sensor data, a particle filter is a natural fit:

• Robot localization and SLAM: a robot scatters particles across a map; each particle carries a full hypothesis about the robot's pose. As it drives, particles that match laser-scan readings survive. This is how the Mars rovers Spirit and Opportunity navigated without GPS, and how warehouse robots map unknown floors in real time.
• Autonomous vehicles: fusing lidar, radar, camera, and IMU data to track every nearby car's position and velocity — even when one sensor goes dark — is a particle filter job. Tesla and Waymo both use variants under the hood.
• Computer vision: tracking a human face or hand through occlusions, changes in lighting, and rapid motion. The particle filter's ability to maintain multiple hypotheses prevents it from locking onto a ghost when the target briefly disappears.
• Weather and climate: ensemble weather models are particle filters at planetary scale — thousands of model runs ("particles") are weighted against real observations and resampled to produce the probabilistic forecast you see as "40% chance of rain."
• Finance: stochastic volatility models (e.g., Heston model) have a hidden state (instantaneous volatility) that cannot be observed. Particle filters estimate it from options prices in real time, helping traders price derivatives more accurately.
• Medical monitoring: tracking a patient's hidden physiological state (drug concentration, tumour dynamics) from sparse, noisy blood-test readings.

The common thread: a hidden state evolving over time, noisy partial observations, and a need for uncertainty quantification — not just a point estimate, but a full distribution. See also Bayesian inference and Kalman filter for the Gaussian-linear special case that particle filters generalize.

The particle filter encodes a profound shift in thinking: a distribution is more honest than a point estimate. Rather than pretending you know where the target is, you carry all plausible positions simultaneously and let the evidence sort them out. The predict-weight-resample loop is just Bayes' theorem unrolled through time, approximated by a finite swarm.

That swarm tracks submarines, guides rovers across Mars, keeps autonomous cars from drifting into oncoming lanes, and updates the probability cloud on your weather app. Every application shares the same three-step heartbeat — predict, weight, resample — repeated until the cloud converges on truth.

The catch is dimension. Add enough unknowns and no computer can field enough particles to cover the space. That boundary is where active research lives: smarter proposals, analytical marginalization, neural approximations. The particle filter is not the last word — but it was the first algorithm that made Bayesian tracking practical, and decades later it remains the workhorse of state estimation.