Prerequisites

Why it matters in robotics

Particle filters estimate a robot's state when its belief about where it is has multiple competing possibilities or an irregular shape that simpler estimators break down on, representing that belief with a set of weighted samples instead of a single smooth distribution. This includes the hardest case, where the robot has no idea where it starts and has to work that out from scratch, by running a predict, update, and resample loop whose practical failure modes are losing track of the true possibilities or collapsing onto too few of them. Resampling strategy, how many effective samples remain informative, and total particle count trade compute against accuracy.

What to study

✓Representing belief as weighted samples vs. a parametric (Gaussian) distribution; sampling from the motion model and weighting by the measurement likelihood
✓The predict to update to resample loop and how it implements the recursive Bayes filter
✓Resampling: low-variance/systematic resampling, effective sample size (Neff), and avoiding sample impoverishment and particle deprivation
✓Monte Carlo Localization (MCL) and Adaptive MCL (KLD-sampling), including global localization and the kidnapped-robot problem

Where to study

Cheatsheet

Symbols used below

x_t^{[i]}

state hypothesis of particle

i

at time

t

w_t^{[i]}

importance weight of particle

i

N

number of particles

N_{eff}

effective sample size

p(z_t \mid x_t^{[i]})

measurement likelihood — how well particle

i

explains the observation

Predict → weight → resample

Predict: sample each particle forward through the motion model, $x_t^{[i]} \sim p(x_t \mid u_t, x_{t-1}^{[i]})$ .

Weight: score each particle by how well it explains the new measurement, $w_t^{[i]} = p(z_t \mid x_t^{[i]})$ .

Resample: draw $N$ new particles with replacement, probability proportional to $w_t^{[i]}$ , then reset weights uniformly. This is Monte Carlo integration standing in for the Bayes filter's exact predict/update integral.

Effective sample size

$N_{eff} = \dfrac{1}{\sum_i (w_t^{[i]})^2}$

Low $N_{eff}$ means weight is concentrated on a few particles — resample now. Resampling on every step is wasteful; resampling only when $N_{eff}$ drops below a threshold (e.g. $N/2$ ) avoids unnecessary variance.

Two failure modes

Sample impoverishment: repeated resampling collapses diversity — many particles become exact copies of a few ancestors, so the set can no longer represent the true spread of the belief.

Particle deprivation: no particle lands anywhere near the true state, so no amount of reweighting can recover it. More particles, better proposal distributions, or added process noise both mitigate this.

Low-variance (systematic) resampling

Instead of drawing $N$ independent samples from the weight distribution, low-variance resampling picks one random offset and then steps through the cumulative weight in fixed-size increments of $1/N$ .

Same proportional selection, far less sampling noise, and it runs in $O(N)$ instead of $O(N \log N)$ .

Monte Carlo Localization

MCL is a particle filter applied to global localization: particles start spread uniformly over the map (or over plausible poses) and concentrate as measurements arrive.

KLD-sampling (Adaptive MCL) varies $N$ on the fly — few particles once the belief is confident and tightly clustered, many while it's spread out or the robot is lost (the kidnapped-robot problem).

A Kalman filter carries a single Gaussian (unimodal); a particle filter represents the belief with weighted samples, so it can track multimodal / non-Gaussian distributions — at higher compute cost.

	Kalman filter	Particle filter
Belief shape	Unimodal Gaussian	Arbitrary, multimodal
Global / kidnapped-robot localization	Cannot represent — needs a unique starting guess	Natural fit — particles cover all hypotheses
Cost scaling	Polynomial in state dimension	Linear in particle count, but particle count needed grows with state dimension
Determinism	Deterministic given inputs	Stochastic — sampling and resampling noise

Resampling replaces weighted particles with equally-weighted copies drawn in proportion to their weight — concentrating samples where the posterior is high (but risking particle depletion).

Particle Filters

Prerequisites

Why it matters in robotics

What to study

Where to study

Cheatsheet

Application focus

Practice questions (5)