Nature's Particle Filters

Regardless of how diligent we are occasionally we wake to find a swarm of fruit flies in our kitchen. The reality is that when this occurs we've probably slipped up and allowed a banana peel to rot in the garbage can a bit too long. This last occurred about a month ago and despite our efforts to eliminate them there are still a couple buzzing around. Rest assured if we leave something in the trash in the near future we'll have a flare up.
It dawned on me recently that these little buggers are basically nature's particle filter. Particle filters are a way of estimating belief about something that cannot or is not directly observed. In other words they estimate a probability density function of hidden variables. In this case the fruit flies estimate the existence of food in a given area. When there is food there are lots of fruit flies, when there isn't there isn't.

I first encountered the concept in my AI class. The example used, if I recall correctly, tried to estimate the weather outside from the perspective of an observer that can't go outside. Instead the observer bases their belief on whether others were carrying an umbrella. A bit contrived but illustrative none-the-less.

A more compelling use comes out of robotic localization research; the problem of determining ones location in an environment given a map and a sequence of sensor readings. Monte Carlo localization specifically employs particle filtering to accomplish this task. The process generally starts by distributing particles over the area(s) of the map where the robot is believed to be. It's not uncommon for the particles to be evenly distributed over the map which implies the initial position of the robot is completely unknown. From there the particles are repeatedly altered based on how the robot moves, odometric sensor input, and what it sees, input from IR sensors, ultrasonic sensors, laser range finders, and even vision systems to name a few.

Of course there are numerous uses of particle filters; they're generally applicable when performing simulation over an infinite space which makes them quite useful. I've only touched on a few examples here. I've had the inkling that gremlins can be cast as a particle filter. Thus far I have not succeeded in doing so but I'll let you know if I do.