Particle Filter

A particle filter is fundamentally a Sequential Monte Carlo (SMC) method. It approximates complex probability distributions—specifically the posterior distribution of a system's state—using a set of random samples called particles. Unlike analytical methods, it uses this empirical, sample-based representation. Each particle is a hypothesis about the true state (e.g., a robot's position and velocity). The algorithm operates sequentially: it predicts new particle states using a process model, then updates their importance based on new sensor data via a sensor model.

This is the primary advantage over the Kalman Filter and its variants (EKF, UKF). Particle filters make no assumptions of linear system dynamics or Gaussian-distributed noise. They can represent arbitrary, multi-modal distributions (distributions with multiple peaks). This is critical in real-world robotics and tracking scenarios where:

• Sensor noise is not Gaussian (e.g., occasional large outliers).
• The system dynamics are highly nonlinear.
• The posterior belief can be multi-modal (e.g., a robot is equally likely to be in one of two rooms).

The core algorithmic loop involves two key steps:

• Importance Sampling (Weighting): After the prediction step, each particle receives a weight proportional to the likelihood of the latest sensor measurement given that particle's hypothesized state. Particles that align well with observations get high weights.
• Resampling: To avoid particle degeneracy (where most particles have negligible weight), the system resamples. Particles are probabilistically duplicated (based on their weight) or discarded. This focuses computational resources on the most promising state hypotheses. Resampling introduces its own challenges, like sample impoverishment if diversity is lost.

The state estimate is not a single mean and covariance. It is the entire cloud of weighted particles. The expected state (e.g., estimated position) is computed as the weighted average of all particles. Uncertainty is represented by the spread and distribution of the particles. This cloud can take on complex shapes that a simple Gaussian ellipse cannot, providing a richer understanding of estimation confidence, especially in ambiguous situations common in Simultaneous Localization and Mapping (SLAM).

The main drawback of particle filters is their computational cost, which scales poorly with the dimensionality of the state space. To maintain a good approximation of the posterior distribution in high-dimensional spaces (e.g., a 6D pose plus map features), an exponentially large number of particles is required. This curse of dimensionality makes standard particle filters impractical for very high-dimensional problems like full Graph-Based SLAM. Techniques like Rao-Blackwellized Particle Filters are used to mitigate this by analytically marginalizing out some state variables.

Particle filters are the workhorse for many real-world estimation problems:

• Robot Localization: Especially Monte Carlo Localization (MCL) for mobile robots using lidar/radar in known maps.
• Visual Object Tracking: Tracking objects in video where appearance changes and occlusion cause non-Gaussian behaviors.
• Sensor Fusion for Navigation: Fusing GPS, IMU, and odometry in non-linear dynamic models (e.g., aircraft, ground vehicles).
• Financial Time-Series Modeling: Estimating hidden states in complex, non-linear economic models. Their flexibility makes them ideal for prototyping and deploying robust estimators in dynamic, noisy environments.

The foundational probabilistic framework for all recursive state estimation. It provides the recursive equations for updating a belief state—the probability distribution over possible states—given new sensor measurements. The core steps are prediction (using a process model) and update (using a sensor model via Bayes' rule).

• Key Principle: Maintains a posterior distribution: bel(x_t) = P(x_t | z_1:t, u_1:t).
• Relation to Particle Filter: The particle filter is a non-parametric implementation of the Bayesian filter, approximating the posterior with samples instead of an analytic form.
• Other Implementations: The Kalman filter (for linear Gaussian systems) and the histogram filter (for discrete state spaces) are also specific Bayesian filters.

The optimal recursive estimator for linear dynamic systems with Gaussian noise. It represents the state belief as a single Gaussian distribution, characterized by a mean (the estimate) and a covariance matrix (the uncertainty).

• Core Assumption: Linear process and sensor models with additive white Gaussian noise.
• Comparison to Particle Filter: The KF is computationally efficient and provides an exact closed-form solution for linear Gaussian problems. The particle filter is used when these assumptions break down (nonlinearities, non-Gaussian noise).
• Ubiquitous Use Case: Foundational algorithm for GPS, inertial navigation, and countless control systems.

Two primary extensions of the Kalman filter designed to handle nonlinear systems while maintaining a Gaussian representation.

• Extended Kalman Filter (EKF): Linearizes the nonlinear process and sensor models around the current state estimate using a first-order Taylor expansion. This approximation can introduce significant error for highly nonlinear systems.
• Unscented Kalman Filter (UKF): Uses a deterministic sampling technique (the unscented transform) to propagate a set of carefully chosen "sigma points" through the true nonlinear functions. It often provides better accuracy and stability than the EKF without the computational cost of a particle filter.
• Trade-off: EKF/UKF are more efficient than particle filters for moderate nonlinearities but fail for multi-modal or heavily non-Gaussian distributions.

The core estimation problem in robotics: building a map of an unknown environment while simultaneously determining the robot's location within it. It is a high-dimensional, nonlinear state estimation problem where the state includes both the robot's pose and the positions of landmarks.

• Particle Filter in SLAM: The classic FastSLAM algorithm uses a Rao-Blackwellized particle filter. Each particle carries its own robot trajectory hypothesis and a set of independent EKFs for mapping landmarks conditioned on that trajectory.
• Modern Dominance: While particle filters were pivotal, modern SLAM often uses graph optimization techniques (e.g., pose-graph SLAM) for higher accuracy in post-processing, with filters used for real-time front-ends.

The system-level design patterns for combining data from multiple sensors. The choice of architecture dictates data flow, computational load, and robustness.

• Centralized Fusion: All raw sensor data is sent to a single node (e.g., a central computer) where a single state estimator (like a particle filter) processes it. This is theoretically optimal but requires high bandwidth and creates a single point of failure.
• Decentralized/Distributed Fusion: Each sensor node runs a local estimator. These nodes then share their local estimates (not raw data) to form a consensus. This is more robust and scalable but mathematically complex.
• Hierarchical Fusion: A hybrid approach with local and central fusion nodes. Particle filters can be deployed at any level in this hierarchy.

Critical supporting techniques that enable filters to function in real-world, messy environments.

• Robust Estimation (e.g., RANSAC): Methods to fit models to data contaminated by outliers. Used in sensor fusion to pre-process measurements before they enter the filter, rejecting spurious data.
• Data Association: The problem of determining which sensor measurement corresponds to which tracked object or landmark. This is a major challenge in multi-object tracking.
• Particle Filter Connection: In problems like tracking, each particle implicitly represents a hypothesis about data association. The filter's resampling step kills particles with poor association hypotheses.