Particle Filter

The core mechanism of a particle filter. It sequentially updates a set of weighted particles (samples) to approximate the posterior distribution p(x_t | z_{1:t}), where x_t is the state and z_{1:t} are all measurements up to time t.

• Particles: Each particle is a hypothesis of the system's state.
• Importance Weights: Each particle has a weight representing its likelihood given the latest sensor observation.
• Recursive Update: At each time step, particles are propagated through the motion model (prediction) and then re-weighted using the sensor model (update).

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

A critical step to combat particle degeneracy, where after a few iterations, all weight concentrates on a single particle, making the approximation useless.

• Process: Low-weight particles are discarded, and high-weight particles are duplicated. The new set of particles is then assigned uniform weights.
• Algorithms: Common methods include multinomial resampling, systematic resampling, and residual resampling.
• Trade-off: While essential, resampling introduces sample impoverishment, where diversity is lost if the particle cloud is too small. Adaptive strategies trigger resampling only when effective sample size falls below a threshold.

Particle filters make no parametric assumptions (e.g., Gaussian) about the shape of the underlying probability distribution. The distribution is represented entirely by the empirical set of samples.

• Flexibility: This enables tracking of arbitrary, complex distributions, including multi-modal distributions (multiple hypotheses, like a robot being in one of several rooms) and highly non-Gaussian noise.
• Curse of Dimensionality: The number of particles required for a good approximation grows exponentially with state dimension, making them computationally challenging for very high-dimensional states.
• Approximation Error: The error is governed by the number of particles, not by a fixed parametric form.

The filter's performance is fundamentally tied to the accuracy of its two probabilistic models:

• Process Model (Motion Model): p(x_t | x_{t-1}). Defines how the state evolves over time, incorporating control inputs and process noise. For a robot, this predicts its next pose based on wheel odometry.
• Measurement Model (Sensor Model): p(z_t | x_t). Defines the likelihood of receiving a sensor observation z_t given a hypothetical state x_t. This is used to compute particle weights.

These models can be highly nonlinear and are often the most domain-specific part of implementing a particle filter, such as using a LiDAR beam model or a camera projection model.

Particle filters address key limitations of the Kalman Filter (KF) and its nonlinear variant, the Extended Kalman Filter (EKF).

Particle filters are the preferred choice for problems like global robot localization (the 'kidnapped robot problem') where the initial belief is spread over the entire map.

Several algorithms build upon the basic Sequential Importance Resampling (SIR) filter to improve efficiency and accuracy.

• Rao-Blackwellized Particle Filter (RBPF): Marginalizes out analytically tractable parts of the state (e.g., map features in SLAM), using particles only for the remaining state (e.g., robot pose), drastically reducing dimensionality.
• Unscented Particle Filter (UPF): Uses an Unscented Kalman Filter to generate a better proposal distribution for each particle than the simple motion model, leading to more efficient sampling.
• Regularized Particle Filter: After resampling, particles are jittered using a kernel to restore diversity and mitigate sample impoverishment.
• Adaptive Particle Filters: Dynamically adjust the number of particles based on the estimated uncertainty or localization error.

The Kalman Filter is an optimal recursive algorithm for estimating the state of a linear dynamic system from a series of noisy measurements. It operates in a two-step cycle: prediction (forecasting the next state) and update (correcting the forecast with a new observation). Its key assumptions are linear dynamics and Gaussian noise, which make it computationally efficient but limited for highly nonlinear problems where particle filters excel. It is foundational to modern control and navigation systems.

The Extended Kalman Filter is the nonlinear extension of the standard Kalman filter. It handles nonlinear systems by linearizing the system dynamics and measurement models around the current state estimate using a first-order Taylor expansion (the Jacobian). While more versatile than the linear KF, the EKF's performance degrades with strong nonlinearities and its linearization can introduce significant errors. It is widely used in robotics for sensor fusion (e.g., GPS/IMU) but is often outperformed by particle filters in multimodal or highly non-Gaussian scenarios.

Sensor Fusion is the overarching process of combining data from multiple, often heterogeneous, sensors (e.g., LiDAR, camera, IMU, radar) to produce a more accurate, complete, and reliable estimate of the environment's state than is possible with any single sensor. Particle filters are a powerful probabilistic fusion framework, as each particle can incorporate measurements from different sensors via its weight update. This is critical for robust perception in autonomous vehicles and robots operating under diverse conditions.

SLAM is the core computational challenge of building a map of an unknown environment while simultaneously tracking the agent's location within it. Particle filters are directly applied in a major SLAM approach called FastSLAM, which uses a Rao-Blackwellized particle filter. In this method:

• Each particle carries its own trajectory hypothesis.
• For each particle, the map (e.g., landmark positions) is estimated analytically using smaller Kalman filters. This elegantly handles the data association problem and is robust in non-Gaussian, cluttered environments.

Particle filters are a specific class of Sequential Monte Carlo (SMC) methods. At their core, they rely on Monte Carlo integration, which uses random sampling to approximate complex integrals—in this case, the posterior probability distribution. Key principles include:

• Importance Sampling: Drawing samples from a proposal distribution and weighting them to approximate a target distribution.
• Resampling: Preventing particle degeneracy (where most weights become negligible) by discarding low-weight particles and duplicating high-weight ones. This statistical foundation makes them exceptionally flexible for problems where analytical solutions are intractable.

An Occupancy Grid is a probabilistic, discretized representation of an environment where each cell (voxel in 3D) stores the probability that it is occupied by an obstacle. Particle filters and occupancy grids are often used in tandem:

• The particle filter estimates the robot's pose (location and orientation).
• Given the estimated pose, sensor data (e.g., from LiDAR) is integrated into the occupancy grid to update the map. This decoupling allows for robust localization in dynamically changing maps and is a staple in robotic navigation stacks.