If you’re a nerd like most of us here at Source Allies, you probably think robots are cool. One of the most important part of robotics is teaching the robot to find its location on a geographic map - a process known as “localization.” One such algorithm for solving this problem is known as Monte Carlo Localization. When talking about this algorithm, we typically use a a notion commonly referred to as “particles.” These particles generally can be thought of as virtual manifestations of the robot within some computer. They are postulations about the robot’s location, orientation, and certainty of this information on a geographic map. With that in mind, the Monte Carlo Localization algorithm in plain English is as follows:

1. Initialize set of particles (or beliefs about the robot's location.) Depending on what problem you're trying to solve, the set of particles can either be random or already localized.
2. Gather data about the physical environment by interacting (taking in sensor information, moving around)
3. Look at each particle in your set of particles and assign a weight to each based on how well that particle fits with the the data gathered in step 2. Basically, our certainty about whether a particle is actually representing the robot's location and orientation determines the "weight."
4. Create new set of particles by resampling from particles with greater weights. This is sort of a Darwinian, survival of the fittest, particles with higher weights repopulate the set for the next round.
5. Replace old set of particles with a new set and start again at step 2.

So that was a very basic, watered down version of the algorithm that omits many important statistical calculations, but hopefully it gets most of the main idea across.

In case there is any confusion, let’s walk through an example. Let’s say I am a robot. For obvious reasons, I was kidnapped by some ninjas. The ninjas then released somewhere in downtown Des Moines I have no idea where I am at first. Fortunately, I am a robot and have a perfect map of downtown Des Moines, so I initialize in my head a set of postulations about my position and orientation. These beliefs are completely random and distributed fairly evenly over all of downtown Des Moines and all have different random orientations.

First thing I do is open my eyes and look around, perhaps I’ll take a few steps in any direction and continue gathering visual information. I see a Smokey D’s. Then I look at all the particles in my set of particles and determine which of those particles also would see a Smokey D’s. I decide that those particles are better than all the other particles and assign them greater weights. Then I go through my set of particles again do some ninja-statistics that I learned while I was kidnapped to decide which particles can make it to round two and which cannot. What I’d end up with is two clusters of particles around the two points, appropriately titled “A” and “C.”

Then I’d go back to step 2, interact with my environment some more, find out that I’m actually indoors and that fits better with the particles around A - the Smokey D’s in the skywalks. Perhaps I’d repeat from step 2 a few more times and eventually weed out particles until I have a full set of particles that are all in a very similar spot around the Smokey D’s in the Skywalks. Then I know where I am and I’m a happy robot.