Particle Filter

A recursive estimation method that approximates a probability distribution over states using a large set of weighted random samples.

The particle filter is also called Sequential Monte Carlo; its classic starting point is the 1993 bootstrap filter proposed by Gordon and colleagues. It represents uncertainty using many “particles” — each one a hypothesis about the state, such as a robot’s pose — together with a weight for each particle, and repeats three steps at every timestep: move the particles forward using a motion model and add noise (prediction), re-score the particles against a sensor observation (update), and discard low-weight particles while duplicating high-weight ones (resampling). A Kalman filter can only represent a single-peaked Gaussian distribution, but a particle filter can handle nonlinear, non-Gaussian, and multi-modal situations — for instance, a robot that is unsure which of two similar-looking corridors it is in. The most well-known robotics application is Monte Carlo Localization, proposed in 1999, and its adaptive version, AMCL.

ExampleWhen a mobile robot starts up, it scatters particles across the whole map; after a few steps, particles that agree with the lidar scan survive, and the particle cloud gradually shrinks around the robot’s true location.

Also called

PF, Sequential Monte Carlo

Related

Kalman Filter · Extended Kalman Filter · Adaptive Monte Carlo Localization · State Estimation · Simultaneous Localization and Mapping · Importance Sampling

Sources

Particle filter - Wikipedia
Monte Carlo localization - Wikipedia
Nav2 nav2_amcl README