Particle Filter

Unlike the Kalman Filter, which assumes a parametric (Gaussian) distribution, a particle filter uses a non-parametric representation. The posterior distribution is approximated by a set of discrete, weighted samples called particles. This allows it to model arbitrarily complex, multi-modal distributions (e.g., a robot's possible location split between two rooms), which is impossible for filters constrained to a single Gaussian.

The algorithm operates in a predict-update cycle using two key Monte Carlo steps:

• Importance Sampling: Each particle is propagated through the process model (prediction), then weighted based on the likelihood of the new sensor measurement (update).
• Resampling: To avoid particle degeneracy (where most particles have negligible weight), particles are stochastically replicated based on their weight. High-weight particles are multiplied, low-weight particles are discarded. This focuses computational resources on the most probable state regions.

This is the primary engineering motivation for using a particle filter. It makes no linearity assumptions and imposes no Gaussian noise requirements on the process or measurement models. It can directly use:

• Highly nonlinear motion models (e.g., skidding vehicles, agile drones).
• Non-Gaussian sensor noise (e.g., heavy-tailed distributions, bounded errors).
• Nonlinear measurement models (e.g., bearing-only sensors, landmark detection). This makes it a robust choice for complex, real-world robotic systems where linearization (as in an EKF) fails.

The primary computational limitation. The number of particles required to maintain a given approximation quality grows exponentially with the state space dimension. For a robot estimating its 2D (x,y) position, a few hundred particles may suffice. For a full 6D pose (x,y,z,roll,pitch,yaw) plus velocity, thousands are needed. For joint state and map estimation (as in FastSLAM), the requirement becomes prohibitive, leading to approximations like Rao-Blackwellized Particle Filters that partition the state.

All estimates are derived from the empirical distribution of particles. Key quantities are computed as sample statistics:

• State Estimate: Often the weighted mean of particle states, or the state of the highest-weight particle.
• Uncertainty: Estimated from the sample covariance of the particle cloud.
• Probabilities: The probability of an event (e.g., "robot is in Room A") is approximated by the sum of weights of particles satisfying the condition. This provides immense flexibility for querying the belief state.

This is the general probabilistic framework that underpins all sequential state estimators, including the particle filter. It recursively applies Bayes' theorem to estimate the posterior probability distribution of a system's state given a sequence of noisy observations.

• Core Equation: p(state | measurements) ∝ p(measurements | state) * p(state)
• The Kalman filter and particle filter are specific implementations of this framework, differing in how they represent and propagate the probability distribution.
• It formalizes the cycle of prediction (using a motion model) and update (using a measurement model).

The classical optimal solution for linear Gaussian systems. It represents the state's probability distribution as a single Gaussian, characterized by a mean and a covariance matrix.

• Key Assumption: Requires both the process model and measurement model to be linear, with noise that is additive and Gaussian.
• It is computationally efficient and provides an exact, closed-form solution under these constraints.
• The particle filter is often used when these linearity and Gaussianity assumptions break down, as in robotic perception with cluttered environments or multi-modal distributions.

A nonlinear estimator that improves upon the Extended Kalman Filter (EKF). Instead of linearizing models, it uses a deterministic sampling strategy called the unscented transform.

• It selects a minimal set of sigma points to capture the mean and covariance of the state distribution, propagates these points through the nonlinear functions, and then recomputes the mean and covariance.
• More accurate than the EKF for strong nonlinearities but, like the KF, still represents the posterior as a single Gaussian. It struggles with multi-modal distributions (e.g., a robot unsure if it's in Room A or Room B), where a particle filter's sample-based representation excels.

A broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The particle filter is a sequential Monte Carlo (SMC) method.

• The core idea is to approximate an intractable integral or distribution (like a complex Bayesian posterior) with a set of random samples (particles).
• Importance Sampling is a key technique used to weight particles based on how well they explain the observed data.
• Resampling is the critical step that mitigates particle degeneracy by discarding low-weight particles and duplicating high-weight ones, focusing computational resources on likely state hypotheses.

The canonical robotics problem where a mobile robot must build a map of an unknown environment while simultaneously tracking its location within it. Particle filters provide a direct solution known as FastSLAM.

• In FastSLAM, each particle carries its own pose hypothesis and an associated map (often a set of landmark estimates).
• This elegantly handles the data association problem (matching observations to map landmarks) on a per-particle basis.
• While graph-based optimization methods now dominate high-accuracy SLAM, particle filters remain relevant for their ability to represent multi-hypothesis tracking in ambiguous scenarios.

These describe the types of uncertainty that particle filters are uniquely suited to handle, in contrast to Kalman-family filters.

• Non-Gaussian: The probability distribution of the state is not a simple "bell curve." It could be skewed, heavy-tailed, or otherwise irregular. Sensor noise or motion models can cause this.
• Multi-Modal: The distribution has multiple distinct peaks, each representing a plausible state hypothesis. A classic example is global localization (the "kidnapped robot" problem), where the robot could be in one of several similar-looking corridors.
• A particle filter's sample-based representation can approximate these complex shapes arbitrarily well, given enough particles, whereas a Gaussian-based filter can only represent a single peak.