Particle Filters: How a Robot Figures Out Where It Is

The Belief Is a Cloud of Guesses

Localization asks a Bayesian question: given everything the robot has sensed and every command it has issued, what is the probability distribution over its pose xₜ = (x, y, θ)? That distribution is called the belief, bel(xₜ). A Kalman filter forces bel(xₜ) to be a Gaussian — one blob with a mean and covariance. A particle filter throws that constraint away and represents the belief with a set of N samples (particles), each a concrete pose xₜ⁽ⁱ⁾ carrying a scalar weight wₜ⁽ⁱ⁾.

The density of particles is the probability. Where the robot is likely to be, particles cluster thick; where it isn't, they're sparse or absent. Formally the swarm approximates the posterior as a sum of weighted Dirac deltas:

• bel(xₜ) ≈ Σᵢ wₜ⁽ⁱ⁾ · δ(xₜ − xₜ⁽ⁱ⁾), with weights normalized so Σ wₜ⁽ⁱ⁾ = 1.

This nonparametric form is the whole advantage: it can be bimodal, ring-shaped, or spread uniformly across a floor plan. When a robot boots up not knowing where it is (the global localization problem), you seed particles uniformly across the entire free space of the map — thousands scattered over a 2,000 m² warehouse — and let the data converge them.

The Recursive Bayes Filter, Made of Samples

Every particle filter is an implementation of the recursive Bayes filter, which updates belief in two alternating steps as each control uₜ and measurement zₜ arrive:

• Prediction (motion update): bel⁻(xₜ) = ∫ p(xₜ | xₜ₋₁, uₜ) · bel(xₜ₋₁) dxₜ₋₁ — push every hypothesis forward through the motion model.
• Correction (measurement update): bel(xₜ) = η · p(zₜ | xₜ) · bel⁻(xₜ) — reweight by how well the sensor reading matches each hypothesis; η is the normalizer.

The integral in the prediction step is intractable in closed form for a real nonlinear robot — that's precisely why sampling wins. The particle-filter cycle (the Sequential Importance Resampling, or SIR, algorithm) turns those two integrals into three concrete operations run every control-and-measurement tick, typically at 10–50 Hz:

• 1. Sample the motion: for each particle, draw a new pose xₜ⁽ⁱ⁾ ~ p(xₜ | xₜ₋₁⁽ⁱ⁾, uₜ). This is the proposal distribution.
• 2. Weight by the measurement: set wₜ⁽ⁱ⁾ = p(zₜ | xₜ⁽ⁱ⁾). Particles whose predicted sensor view matches reality get large weights; the rest get near-zero.
• 3. Resample: draw N new particles from the old set with probability proportional to weight. Good hypotheses breed copies; bad ones die. Reset all weights to 1/N.

Steps 1–2 are importance sampling: because we can't sample the true posterior directly, we sample an easy proposal (the motion) and correct the mismatch with weights (the likelihood). Step 3 is what keeps the filter from wasting all its particles on hopeless corners of the map.

The Two Models: Motion and Measurement

A particle filter is only as good as its two probabilistic models, and both encode real hardware noise.

The motion model p(xₜ | xₜ₋₁, uₜ) predicts where a particle goes given odometry. The standard odometry motion model decomposes each move into rotation δ_rot1, translation δ_trans, and rotation δ_rot2, then corrupts each with zero-mean noise whose variance scales with the motion itself:

• σ²_rot = α₁·δ_rot² + α₂·δ_trans², and σ²_trans = α₃·δ_trans² + α₄·(δ_rot1² + δ_rot2²).

The α₁…α₄ are calibrated noise coefficients — typical values α₁≈0.05 (rad²/rad²), α₃≈0.01 (m²/m²) for a decent differential-drive base. Wheel slip, uneven tile, and encoder quantization all live in these terms. Larger α spreads the particle cloud faster (more uncertainty), so it's a deliberate trade-off between robustness and precision.

The measurement model p(zₜ | xₜ) scores a hypothesis against reality. For a 2D LiDAR with, say, 360 beams, the likelihood field (beam endpoint) model is standard: for each beam, ray-cast from the hypothesized pose into the occupancy grid, compute the distance d from the beam's endpoint to the nearest map obstacle, and score it as a Gaussian:

• p(zₖ | xₜ) = z_hit · exp(−d²/2σ_hit²) + z_rand/z_max + z_max-range term.

With σ_hit ≈ 0.2 m (20 cm) and independent-beam assumption, the full-scan likelihood is the product over beams. A single well-aligned scan can drive the weight ratio between a good and bad particle to 10⁶:1, collapsing the cloud in one update.

Resampling, Degeneracy, and the Effective Sample Size

Without resampling, importance weights suffer degeneracy: after a few steps, one particle carries essentially all the weight (w≈1) and the other 999 carry ~0. The swarm becomes a single sample with expensive dead weight. The diagnostic is the effective sample size:

• N_eff = 1 / Σᵢ (wₜ⁽ⁱ⁾)². If all weights are equal, N_eff = N (healthy). If one dominates, N_eff → 1 (degenerate).

Best practice is adaptive resampling: only resample when N_eff drops below a threshold, commonly N/2. Resampling too often causes the opposite failure — particle impoverishment or sample degeneracy — where repeated cloning erases diversity and all particles converge to a few identical poses, so the filter can no longer recover if it's wrong.

The resampling method matters. Naive multinomial resampling adds O(N log N) sorting and extra variance. Production filters use low-variance (systematic) resampling: draw one random number r ∈ [0, 1/N), then step through the cumulative weight distribution at intervals of 1/N. It's O(N), touches every particle proportionally, and adds minimal Monte-Carlo noise — the reason it's the default in ROS's AMCL and virtually every SLAM back-end.

Sizing the Filter: How Many Particles?

Particle count N is the master dial: cost is O(N) per step (dominated by N ray-casts in the measurement update), while the RMS error of the estimate falls like ~1/√N (its variance like 1/N). Doubling accuracy costs 4× the particles. Real numbers frame the trade-off:

• Position tracking (robot already localized, small uncertainty): N = 200–500 is plenty; runs in <2 ms.
• Global localization (unknown start, whole map): N = 5,000–10,000 to seed the floor densely enough that some particle lands near the truth.
• Kidnapped-robot recovery: inject a fraction of random particles each step (or use Augmented MCL, which adds random samples when the average weight suddenly drops) so the filter can re-globalize.

The elegant fix is KLD-sampling (Adaptive MCL): choose N each step so the sample-based belief is within a bound ε of the true distribution with confidence 1−δ. It bins the state space and sets N from the chi-square statistic — N = (k−1)/2ε · (1 − 2/(9(k−1)) + √(2/(9(k−1)))·z₁₋δ)³, where k is the number of occupied bins. In practice this means N swells to thousands during global localization and shrinks to ~100 once the cloud collapses, cutting CPU by an order of magnitude on a converged robot. This is exactly what ROS's amcl node does, with defaults min_particles=100, max_particles=5000.

Where It Runs: Hardware, Maps, and the Stack

The canonical deployment is ROS AMCL / nav2 AMCL localizing a differential-drive base against a 2D occupancy grid (5 cm/cell) built by gmapping or Cartographer. Sensor stack: a planar LiDAR such as a SICK TiM or Slamtec RPLIDAR (0.25–1° angular resolution, 10–15 Hz, ±3 cm range noise) plus wheel-encoder odometry and often an IMU for the yaw rate. Particle count 500–2,000; the whole filter runs comfortably on a Raspberry Pi 4 or a mini-ITX in real time.

• Warehouse AGVs/AMRs (e.g., fleets doing 3 m/s aisle runs) rely on MCL against reflector or feature maps for ±2 cm docking repeatability.
• Self-driving cars historically used particle filters over LiDAR intensity or 3D point-cloud maps for lane-level pose; the DARPA Urban Challenge stack (Stanford's Junior) used a particle filter for exactly this.
• Planetary rovers use particle-filter variants for visual-odometry drift correction where no GPS exists.
• SLAM: FastSLAM factors the joint problem so each particle carries its own map — a Rao-Blackwellized particle filter, the backbone of gmapping.

The measurement update dominates runtime, so implementers precompute a likelihood field (a distance transform of the map, computed once) so each beam score is a single array lookup instead of a live ray-cast — turning the per-particle cost from hundreds of grid steps into O(beams) lookups.

Failure Modes and Best Practice

Particle filters fail in characteristic, diagnosable ways — every one traceable to sampling statistics or model mismatch:

• Particle deprivation: the true pose falls in a region with zero particles (common in high-dimensional state or after aggressive resampling), and no reweighting can recover it because there's nothing there to reweight. Fix: keep N adequate, inject random particles, don't over-resample.
• Overconfident sensor model: if σ_hit is set too tight, a single outlier beam (a person walking past the LiDAR) can drive a good particle's weight to zero and kill the correct hypothesis. Best practice mixes in a uniform/random component (z_rand) and a max-range term so no single beam can veto a pose.
• Symmetry / aliasing: in a corridor of identical bays, the belief legitimately stays multimodal; forcing convergence early causes commitment to the wrong mode. This is where MCL's multimodality is a feature, not a bug — let the doorway or a fiducial break the tie.
• Odometry underestimate: too-small α coefficients make the cloud tighter than the true error, so the truth escapes the swarm on a slippery floor. Calibrate α on real drive data.

Two rules of thumb that keep production filters healthy: (1) resample only on N_eff < N/2, never every step; (2) report the pose as the weighted mean of the largest particle cluster, not the global mean — averaging across a bimodal belief points the robot at the empty space between two valid hypotheses, a classic and dangerous artifact.

Particle filter (MCL) vs. Kalman/EKF for robot localization

Property	Particle Filter (MCL)	Extended Kalman Filter (EKF)
Belief representation	N weighted samples (nonparametric)	Single Gaussian: mean µ + covariance Σ
Multimodal belief	Yes — global/kidnapped-robot capable	No — collapses to one hypothesis
Nonlinear/non-Gaussian	Handles arbitrarily	Linearizes via Jacobians (error grows)
Cost per step	O(N) ≈ 1–10 ms for N=1,000	O(d³) in state dim d; tiny for d≈3
Failure mode	Particle deprivation / degeneracy	Divergence from bad linearization