particle filter
In plain wordsA way to track something uncertain, such as a robot's location, by keeping thousands of random guesses, scoring each against what the sensors see, and copying the best ones.
A recursive Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating. that represents the probability distribution over a hidden state by a set of weighted samples (particles) and updates it as measurements arrive. Each cycle moves every particle through a stochastic motion model (predict), reweights it by the likelihood of the new measurement given that particle's state (update), and periodically resamples — duplicating high-weight particles and discarding low-weight ones — to prevent degeneracy, in which nearly all the weight collapses onto a few particles. Unlike the Kalman filterKalman filter, n.: A method that keeps a running best guess of something you cannot measure exactly, such as a vehicle's position, by blending predictions from a motion model with noisy sensor readings., it needs no linearity or Gaussian assumptions and can track multimodal beliefs, such as a robot that could be in either of two identical corridors. Its cost grows with the number of particles and becomes prohibitive in high-dimensional state spaces. In robotics, Monte Carlo localization uses particle filters to locate a robot on a known map and is a de facto standard; FastSLAM applies them to simultaneous localization and mappingsimultaneous localization and mapping, n.: How a robot, drone or headset builds a map of an unfamiliar place while at the same time working out where it is on that map, using its cameras or laser scanners.. They are also used in visual tracking, signal processing, econometrics and constrained sampling from language models.
After a few meters of corridor the particle cloud collapsed onto the robot's true position.
Origin
Neil Gordon, David Salmond and Adrian Smith's 'bootstrap filter' (IEE Proceedings F, April 1993) is the usual starting point; Pierre Del Moral coined 'particle filter' in 1996, and Jun Liu and Rong Chen introduced 'sequential Monte Carlo' in 1998. Michael Isard and Andrew Blake's 'condensation' tracker (1996) and Monte Carlo localization by Frank Dellaert, Dieter Fox, Wolfram Burgard and Sebastian Thrun (1999) brought the method to vision and robotics.
Usage note
The formula shows the weight update for particle i given measurement z; with resampling at every step it reduces to the bootstrap filter.
Related
- Kalman filterKalman filter, n.: A method that keeps a running best guess of something you cannot measure exactly, such as a vehicle's position, by blending predictions from a motion model with noisy sensor readings.
- Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating.
- simultaneous localization and mappingsimultaneous localization and mapping, n.: How a robot, drone or headset builds a map of an unfamiliar place while at the same time working out where it is on that map, using its cameras or laser scanners.
- sensor fusionsensor fusion, n.: Combining readings from several different sensors, such as cameras, radar, lidar, GPS and motion sensors, to get a more accurate and reliable picture than any one sensor gives alone.
- Bayesian inferenceBayesian inference, n.: Reasoning that treats unknowns as uncertain beliefs and updates them with evidence using Bayes' theorem. The result is not one answer but a range of answers, each with a probability.
- samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery.
- Kalman filterKalman filter, n.: A method that keeps a running best guess of something you cannot measure exactly, such as a vehicle's position, by blending predictions from a motion model with noisy sensor readings.
Sources
- Gordon, N. J., Salmond, D. J. & Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F 140(2), 107–113.
- Thrun, S., Burgard, W. & Fox, D. (2005). Probabilistic Robotics. MIT Press.
Mentioned in
Bayes' theoremBayes' theorem, n.: A formula for updating how much you believe something after seeing new evidence: weigh your earlier belief by how well that explanation predicts what you actually observed., Kalman filterKalman filter, n.: A method that keeps a running best guess of something you cannot measure exactly, such as a vehicle's position, by blending predictions from a motion model with noisy sensor readings., mobile robotmobile robot, n.: A robot that travels around by itself — on wheels, tracks, legs, propellers or thrusters — such as a robot vacuum, warehouse cart, delivery robot or planetary rover., sensor fusionsensor fusion, n.: Combining readings from several different sensors, such as cameras, radar, lidar, GPS and motion sensors, to get a more accurate and reliable picture than any one sensor gives alone., simultaneous localization and mappingsimultaneous localization and mapping, n.: How a robot, drone or headset builds a map of an unfamiliar place while at the same time working out where it is on that map, using its cameras or laser scanners., importance samplingimportance sampling, n.: A shortcut for estimating averages: draw samples from a convenient source, then reweight each one to correct for how much more or less likely it would be under the source you actually care about., Sebastian ThrunSebastian Thrun, prop. n.: A German-American roboticist who led the Stanford team that won the 2005 desert race for self-driving cars, started Google's self-driving car project, and founded the online-learning company Udacity.