Particle Filter

The core mechanism of a particle filter. It sequentially updates a set of weighted samples (particles) representing the posterior distribution.

• Particles: Each particle is a hypothesis for the system's full state (e.g., a robot's pose).
• Weights: Each particle has an importance weight representing its likelihood given the latest sensor observation.
• Process: At each time step, particles are propagated through the motion model (prediction), then re-weighted using the measurement model (update).

This allows the filter to track multi-modal distributions that a single Gaussian (like in a Kalman Filter) cannot represent.

A critical step to combat particle degeneracy, where all weight concentrates on a few particles, wasting compute on ineffective samples.

• Problem: Without intervention, variance of importance weights increases over time.
• Solution: Periodically resample particles, drawing a new set from the current weighted distribution.
• Effect: Low-weight particles are discarded, high-weight particles are duplicated. This focuses computational resources on the most probable state hypotheses.

Common algorithms include multinomial, stratified, and systematic resampling. Resampling introduces its own challenge: sample impoverishment, where diversity is lost if the distribution is too peaked.

Unlike parametric filters (e.g., Kalman Filter family), particle filters make no explicit parametric assumption (like Gaussianity) about the posterior distribution.

• They can represent arbitrarily complex shapes: skewed, multi-peaked, or non-Gaussian distributions.
• This is essential in robotics for handling global localization (the 'kidnapped robot' problem) or tracking multiple hypotheses when data association is ambiguous.
• The accuracy of the representation scales with the number of particles, offering a direct trade-off between computational cost and estimation fidelity.

Particle filters excel where traditional linear-Gaussian filters fail.

• Nonlinear Dynamics: The motion model can be any function, not requiring linearization that can introduce error (as in an EKF).
• Non-Gaussian Noise: Measurement and process noise models can be any distribution that can be sampled from.
• Example: A robot with a highly nonlinear wheel odometry model and a camera using a non-Gaussian feature matching likelihood function is a prime candidate for a particle filter.

The trade-off is computational intensity, as many samples are needed to adequately approximate complex distributions.

A key design choice influencing efficiency. The proposal distribution is used to generate new particle states during the prediction step.

• Optimal Proposal: Samples from the posterior given the new measurement. Often intractable to compute.
• Simple (Bootstrap) Proposal: Uses the system's motion model. Common but can be inefficient if the motion model is noisy compared to precise sensors.
• Improved Proposals: Advanced filters design smarter proposals that incorporate the latest measurement, leading particles to more likely regions and drastically improving sample efficiency.

Choosing a good proposal is central to building an effective particle filter.

The primary limitation of particle filters is their scaling with state-space dimension.

• Number of Particles: Required to maintain a good approximation grows exponentially with state dimension. This is the curse of dimensionality.
• Typical Use: In robotics, they are often applied to the pose estimation problem (3-6 DOF), not to full joint state+map estimation, where dimensionality is far too high.
• Mitigations: Techniques like Rao-Blackwellized Particle Filters (marginalizing out some states) or adaptive resampling are used to manage cost.

For high-dimensional SLAM, particle filters are typically used as a component within a larger architecture (e.g., FastSLAM).

Particle filters are the algorithm of choice for Monte Carlo Localization (MCL), the de facto standard for global robot localization. They excel where sensor noise or environmental ambiguity creates multi-modal belief distributions (e.g., a robot in a symmetric hallway).

• Key Mechanism: Maintains thousands of hypothetical poses (particles), each weighted by its likelihood given sensor observations.
• Real Example: The AMCL (Adaptive Monte Carlo Localization) algorithm in ROS uses a particle filter to localize a mobile robot within a pre-existing map, dynamically adjusting the number of particles based on localization certainty.

The FastSLAM family of algorithms decomposes the full SLAM problem using a particle filter to estimate the robot's path, with each particle carrying its own set of simple landmark estimators (often EKFs). This is particularly powerful for handling the data association problem—determining which landmark a new measurement corresponds to.

• Core Innovation: Each particle represents a potential history of data associations. Incorrect associations receive low weight and are pruned.
• Practical Impact: Enables robust mapping in feature-rich but ambiguous environments without perfect correspondence, a common challenge for purely optimization-based Graph SLAM.

Particle filters provide a flexible framework for fusing heterogeneous, noisy, and non-linear sensor streams. They can incorporate proprioceptive sensors (wheel encoders, IMUs) for the motion model and exteroceptive sensors (LiDAR, cameras, radar) for the measurement update.

• Advantage over EKF: No need to linearize complex motion or sensor models, allowing for more accurate representation of true system dynamics (e.g., wheel slippage, complex kinematics).
• Use Case: Estimating the full 3D state (position, orientation, velocity) of a drone using IMU data fused with sporadic GPS updates or visual features, where the system model is highly non-linear.

Many robotic systems, like legged robots, manipulators, or vehicles at the limits of handling, exhibit strongly non-linear dynamics. Particle filters can propagate complex motion models without approximation.

• Process: The prediction step simulates the motion model forward for each particle, capturing the spread of possible future states.
• Example: Predicting the state of a skidding car or a falling humanoid robot, where Gaussian assumptions fail and the distribution of possible outcomes is complex and multi-modal.

A critical, double-edged sword in particle filter operation. Resampling selectively replicates high-weight particles and discards low-weight ones to focus computational resources on likely hypotheses.

• Benefit: Prevents degeneracy, where all but one particle have negligible weight.
• Critical Challenge: Can lead to particle deprivation, where all particles collapse to a single incorrect hypothesis if the true state is not represented. This is a primary failure mode in highly ambiguous or perceptually aliased environments.
• Mitigation: Techniques like KLD-sampling adapt the number of particles, and adding a small amount of random noise (roughening) helps maintain diversity.

The primary limitation of particle filters is computational cost, scaling linearly with the number of particles and the state dimension. This has led to key engineering approximations:

• Rao-Blackwellized Particle Filters (RBPF): As used in FastSLAM, marginalizes out analytically tractable state variables (landmark positions) to drastically reduce the sampled dimension.
• Adaptive Particle Counts: Algorithms dynamically increase particles during global localization (kidnapped robot problem) and decrease them during precise tracking.
• Hardware Acceleration: Modern implementations often leverage GPU parallelization to evaluate and weight tens of thousands of particles in real-time.

A recursive algorithm that provides an optimal estimate for the state of a linear dynamic system under the assumption of Gaussian noise. It operates in two steps: a predict step (propagating the state forward using a motion model) and an update step (correcting the prediction with a new measurement).

• Core Assumption: The system's state and all uncertainties are represented by Gaussian distributions.
• Optimality: For linear systems with Gaussian noise, it produces the minimum mean-square error estimate.
• Limitation: Its performance degrades severely with highly nonlinear systems or non-Gaussian noise distributions, which is where particle filters become necessary.

The nonlinear extension of the Kalman Filter. It handles nonlinearities by linearizing the system's motion and measurement models around the current state estimate using a first-order Taylor expansion (the Jacobian).

• Mechanism: Propagates a Gaussian approximation of the state through the nonlinear functions.
• Application: Foundational for many early robotics and aerospace state estimation problems.
• Drawback: The linearization can introduce significant errors for highly nonlinear systems or with poor initial estimates, and it still assumes a unimodal Gaussian posterior, which fails for multi-hypothesis scenarios.

A broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. Particle filters are a specific instance known as Sequential Monte Carlo (SMC) methods.

• Principle: Use randomness to solve problems that might be deterministic in principle (e.g., integration, optimization).
• In Particle Filters: The set of particles is a Monte Carlo approximation of the posterior probability distribution. More particles lead to a more accurate approximation at the cost of increased computation.
• Strength: Can represent arbitrary, multi-modal distributions, unlike Gaussian-based filters.

The computational problem where an agent must build a map of an unknown environment while simultaneously tracking its location within that map. Particle filters provide a foundational solution framework, notably in the FastSLAM algorithm family.

• Particle Filter Role: Each particle carries its own hypothesis of the robot's trajectory and the associated map estimate. This elegantly handles the data association problem (matching observations to map features).
• Challenge: The number of particles needed can grow with map size, leading to computational constraints in large environments.
• Evolution: Modern SLAM often uses particle filters for global localization and loop closure hypothesis generation, while using graph-based optimization for precise map refinement.

A fundamental variance reduction technique used in Monte Carlo methods. It is the core mechanism by which particle filters update their belief from the prior to the posterior distribution after receiving a new measurement.

• Process: Particles are drawn from a proposal distribution (often the motion model). Their importance is then weighted by how well they explain the new sensor data.
• Weight Update: The weight for particle i is proportional to p(measurement | particle_state_i).
• Resampling: To avoid particle degeneracy (where most particles have negligible weight), a resampling step redistributes particles to regions of high probability, based on their weights.

A statistical approach to density estimation that does not assume the data follows a specific parametric form (e.g., a Gaussian). Particle filters are a nonparametric method for representing probability distributions.

• Contrast with Parametric: The Kalman Filter is parametric; it assumes the posterior is always a Gaussian, defined by a mean and covariance. A particle filter makes no such assumption.
• Representation: The distribution is represented implicitly by the set of samples (particles). The density at any point can be approximated by the local concentration of particles.
• Flexibility: This allows it to model complex, multi-modal, and skewed distributions common in real-world robotics scenarios like global localization or data association ambiguity.