Particle Filtering

Unlike Kalman filters that assume a unimodal Gaussian posterior, particle filters make no parametric assumptions. The belief is represented as a discrete set of weighted particles:

• Each particle is a hypothesis of the true system state
• The density of particles in a region represents the probability mass
• Can model multimodal, skewed, and heavy-tailed distributions
• Complexity scales with the number of particles, not state dimensionality

This flexibility makes particle filters the default choice for global localization and kidnapped robot problems where multiple distinct hypotheses must be maintained simultaneously.

The core algorithmic loop that propagates and updates particles recursively:

1. Prediction Step: Each particle is propagated through the motion model p(x_t | x_{t-1}, u_t), simulating how the system evolves given control inputs
2. Update Step: Each particle receives an importance weight proportional to the measurement likelihood p(z_t | x_t) — how well it explains the current sensor observation
3. Normalization: Weights are normalized to sum to 1, forming a discrete approximation of the posterior

A critical vulnerability: after several iterations, weight degeneracy occurs where all probability mass concentrates on a single particle, wasting computational resources on negligible hypotheses.

Resampling is the mechanism that counters weight degeneracy by stochastically replicating high-weight particles and eliminating low-weight ones:

• Multinomial Resampling: Draws N independent samples from the categorical distribution defined by particle weights — simple but high variance
• Systematic Resampling: Uses a single random offset with uniform intervals for lower variance and better particle diversity preservation
• Residual Resampling: Combines deterministic replication of integer weight components with stochastic sampling of remainders
• Adaptive Resampling: Triggers resampling only when the effective sample size N_eff ≈ 1 / Σ w_i² drops below a threshold (typically N/2)

Resampling introduces particle impoverishment — the loss of diversity in low-probability regions — which must be balanced against the need to focus computation on likely states.

The choice of proposal distribution q(x_t | x_{t-1}, z_t) from which particles are drawn dramatically affects filter efficiency:

• Standard Proposal: Uses the motion model p(x_t | x_{t-1}, u_t) directly — simple but ignores current measurements, causing many particles to be wasted in low-likelihood regions
• Optimal Proposal: Incorporates the latest measurement p(x_t | x_{t-1}, u_t, z_t) — minimizes weight variance but is rarely tractable in closed form
• Auxiliary Particle Filter: Introduces an auxiliary variable to pre-weight particles before propagation, focusing sampling on particles likely to explain the next observation

A well-designed proposal reduces the number of particles required by orders of magnitude, directly impacting real-time performance on embedded hardware.

A hybrid architecture that decomposes the state space to reduce dimensionality and improve efficiency:

• Linear-Gaussian Subspace: Variables with linear dynamics and Gaussian noise are marginalized out and estimated analytically using embedded Kalman filters
• Nonlinear Subspace: The remaining nonlinear variables are estimated using particles
• Each particle now carries its own Kalman filter state (mean and covariance) for the linear variables

This factorization is the foundation of FastSLAM, where robot pose is estimated with particles and landmark positions are tracked with per-particle extended Kalman filters. The result: logarithmic complexity in the number of landmarks rather than quadratic.

Particle filters are asymptotically consistent — as the number of particles N → ∞, the empirical distribution converges to the true posterior:

• Law of Large Numbers: The particle approximation converges almost surely to the true expectation for any bounded function
• Central Limit Theorem: The approximation error is normally distributed with variance proportional to 1/N
• Sample Impoverishment Bound: Resampling introduces a finite-sample bias that diminishes as N increases

In practice, the required particle count grows exponentially with state dimension — the "curse of dimensionality" for Monte Carlo methods. Mitigation strategies include Rao-Blackwellization, better proposals, and annealed importance sampling for high-dimensional problems.

Particle filters are the gold standard for global localization and the kidnapped robot problem. By scattering thousands of particles across a known map and weighting them based on LiDAR scan correlation, the filter can resolve the vehicle's pose from complete ambiguity without requiring a precise initial estimate.

• Global Localization: Recovers pose without an initial guess
• Multi-Hypothesis Tracking: Maintains diverging position estimates in ambiguous tunnels or parking garages
• Sensor Resilience: Naturally handles the high noise and dynamic occlusion typical of urban driving

In aerospace and defense, particle filters solve the nonlinear measurement models inherent to radar systems. Unlike an Extended Kalman Filter, a particle filter can track a maneuvering aircraft through a high-G turn without divergence by representing the posterior density over position and velocity as a weighted cloud of samples.

• Maneuvering Target Tracking: Handles sudden velocity and heading changes
• Clutter Rejection: Distinguishes true targets from chaff and ground clutter
• Track-Before-Detect: Integrates raw sensor energy over time to find dim targets invisible in a single scan

Quantitative finance uses particle filters for stochastic volatility estimation. The filter tracks the unobservable, time-varying variance of an asset's return, a state that evolves with its own stochastic noise. The particle representation captures the heavy-tailed, non-Gaussian nature of market crashes far better than parametric Gaussian models.

• Regime Switching: Detects abrupt shifts from calm to turbulent market states
• Jump Diffusion Models: Accurately models sudden price discontinuities
• Options Pricing: Provides a more realistic underlying distribution for complex derivatives

During outbreaks, particle filters assimilate noisy daily case counts to estimate the unobserved effective reproduction number (Rt) and susceptible population. The filter's sequential nature allows it to update forecasts in real-time as new reports arrive, while its particle cloud naturally quantifies the uncertainty in intervention effectiveness.

• Real-Time Rt Estimation: Updates the transmission rate daily
• Intervention Analysis: Quantifies the probabilistic impact of lockdowns or vaccination
• Model Selection: Weights competing epidemiological models based on predictive likelihood

When a robotic arm grasps an object, the object's pose becomes uncertain due to slippage and occlusion. A particle filter maintains a belief state over the object's pose by fusing visual features, tactile sensor readings, and proprioceptive joint torques. This allows the robot to regrasp or reorient the object without dropping it.

• Tactile-Visual Fusion: Combines touch and sight for in-hand pose estimation
• Contact-Rich Dynamics: Models the discontinuous physics of making and breaking contact
• Occlusion Robustness: Tracks objects even when partially hidden by the gripper

In the cocktail party problem, particle filters track the spatial position of multiple moving speakers using a microphone array. Each particle represents a hypothesis about a speaker's azimuth and elevation. The filter weights particles based on beamforming energy, seamlessly handling crossing trajectories and periods of silence where a Kalman filter's Gaussian assumption would collapse.

• Crossing Speakers: Maintains distinct tracks when speakers walk past each other
• Reverberation Robustness: Handles multi-path echoes in enclosed rooms
• Variable Source Count: Adapts to speakers entering and leaving the scene