Particulate Filter

Particle filtering is a probabilistic estimation method developed to work with nonlinear or multimodal probability distributions, particularly in the context of robotics and autonomous systems. Uncertainty regarding a system’s position, velocity, or other state variables is represented by a large number of samples (particles), and these particles are updated according to measurement and motion time models. Thus, reliable estimates can be obtained even in situations where Gaussian-based methods prove inadequate. Particle filtering provides an effective solution for autonomous systems operating in complex and uncertain dynamic environments.

Basic Principles of Particle Filtering

The fundamental principle underlying particle filtering is “Bayesian statistics,” which relies on updating the probability distribution of a system’s state using information from measurement and motion (process) models. The filtering cycle consists of two stages:

1. Prediction: The probability distribution of the system’s previous state is updated using the motion model and information such as “Dead Reckoning.” In this stage, particles are repositioned according to the predicted motion of the system.

2. Update: Measurement data (e.g., from lidar, GPS, or radar sensors) are used to compute how well each particle agrees with the actual measurement. Particles are weighted according to this agreement; low-probability particles are discarded while high-probability particles are duplicated (resampling).

The key feature of particle filtering is that it represents the probability distribution directly through particles rather than as a continuous function. This allows successful modeling of multimodal distributions or nonlinear systems.

Dead Reckoning

Dead reckoning is a method of estimating a body’s current position based on its previous position, orientation, and other motion information. While this approach provides reliable results in the short term, accumulated measurement errors can lead to significant deviations over time. Particle filtering is used to correct this error accumulation in dead reckoning by incorporating sensor measurements.

Particle Filter versus Gaussian Distribution and Kalman Filter

The Gaussian (Normal) distribution is a fundamental statistical model used in many engineering problems to represent noise. It has the following properties:

1. It is unimodal (has a single peak).

2. It is fully defined by its mean and covariance.

Because of these properties, the Kalman filter operates effectively only under Gaussian distributions and in linear systems. However, in real-world world systems:

1. Measurement and motion noise are often non-Gaussian.

2. Complex, multimodal probability distributions may arise.

In such cases, the particle filter can operate without assuming Gaussianity and provide accurate estimates regardless of the shape of the distribution.

How Particle Filtering Works

Particle filtering is an iterative algorithm used to estimate a system’s state and correct this estimate using sensor measurements. Its operation is a practical application of Bayes’ theorem and consists of the following fundamental steps:

1. Representation of the Probability Distribution

2. Prediction

3. Update

4. Resampling

5. Iteration and Convergence

Initialization: Representation of the Probability Distribution

The particle filter represents the state of a system (e.g., a robot’s position and orientation) as a probability distribution. Instead of using a continuous function, this distribution is approximated by a large number of samples (particles). Each particle represents a possible state of the system and its associated likelihood (weight).

1. If the initial state of the system is unknown, particles are randomly distributed across the entire state space.

2. If prior information is available (e.g., an approximate starting location of the robot), particles are distributed according to this information.

Representation of Randomly Generated Particles on a Map

Prediction

In the prediction stage, each particle is updated according to the system’s motion model. The motion model is an equation that describes how the system is expected to move. For example, a robot’s velocity and angular rate data are used to predict its new position.

Prediction process:

1. Each particle is propagated forward according to the motion model.

2. Random noise is added to account for uncertainty in the motion model.

3. The result is recorded as the predicted new states.

Robot’s Movement on the Map

Probabilistic Position Estimates of Particles in Initial State

Update of Particles with Added Noise According to the Motion Model

Update

In this stage, sensor measurements (e.g., from lidar or camera) are used to compute the likelihood that each particle represents the true state of the system. This likelihood is determined by the measurement model.

Probability Computation:

1. For each particle, a predicted measurement is computed using the measurement model.

2. The predicted measurement is compared with the actual measurement.

3. The particle’s weight is updated based on the magnitude of the difference.

Resampling

This step step improves filter efficiency by removing low-probability particles. Resampling is performed as follows:

1. Each particle’s weight is normalized so that the total weight equals one.

2. Particles are resampled according to their weights; particles with higher weights are copied more frequently.

3. As a result, particles become concentrated in high-probability regions.

Important Note: Resampling focuses the filter on high-probability areas but must be performed carefully to avoid loss of diversity.

Iteration and Convergence

The prediction and update steps are repeated with each new measurement and motion estimate. Over time, particles converge and become concentrated in regions that represent the true state of the system. This concentration enables the particle filter to produce increasingly accurate state estimates.

Example of Particle Distribution: Cleaning Robot

A cleaning robot can determine its position within an office building using particle filtering as follows:

1. Initialization: Since the robot’s initial position is unknown, particles are randomly distributed across the office building map.

2. Prediction: As the robot moves, particles are propagated forward using dead reckoning and the motion model.

3. Update: Distance measurements from the lidar sensor are compared with the map, and the compatibility of each particle is evaluated.

4. Resampling: Particles with higher probabilities are duplicated; those with low probabilities are discarded.

5. Result: Over time, particles concentrate around the robot’s true position, yielding an accurate estimate.

Advantages of Particle Filtering

1. It can operate without assuming a Gaussian (normal) distribution.

2. It can represent multimodal probability distributions.

3. It can be applied to both linear and nonlinear systems.

4. It delivers reliable results in dynamic and uncertain environments.

Limits of Particle Filtering

1. High computational cost (increases with the number of particles).

2. With too few particles, it may lose diversity and diverge to incorrect results.