you can't tell where you are because you're wearing a blindfold.

You know your house pretty well so you could probably walk around

and bump into some walls and you'd be able to figure out where you were.

But imagine that you're also wearing oven mitts and a blow up sumo wrestling costume.

basically you've become a robot. You

can't see, you can't move, and all of your sensors

are really terrible. The robot actually has an advantage, though,

because it can simulate multiple copies of itself.

This is called a particle filter. Particle filters are basically just

finding a robot using lots and lots of robots.

Here's a map. The black areas are obstacles and the lighter areas are

spaces where the robot can drive around. The robot knows what this map looks like,

but it doesn't know where it is on the map.

But, of course, you're an all-knowing deity so you know where the robot is on

the map. You're just way too busy to tell the robot.

What the robot can do is place many many many simulations of

itself on the map. You can imagine that if there were

enough robots, at least one robot would end up in the same position as the real robot.

When the real robot moves it has the simulated robots move in exactly the

same way, just with a little bit of error.

The robot is actually really really terrible, and when you tell the robot to

move straight forward, it won't. It'll turn as it drives,

it won't go quite far enough, or it a little bit

too far. This could be because the floor is slippery,

or maybe the wheels don't drive at the same speed.

In other words, the robot might end up in the right place or it could end up

here, or here, or here, or any of these places.

This graph can tell you how to make your robot do things totally wrong.

In this case, the location of the robot is along the bottom and the likelihood

that the robot is at that location is on the side. This curve is called a

Gaussian curve after a guy named Gauss, but it's also called a bell curve.

When the robot moves it's most likely to end up where it's supposed to be but it's

also very likely to end up near where it's supposed to be.

It's unlikely to end up far from where it's supposed to be, but

it could be there. In fact, the robot could wind up anywhere.

The robot sensors are also really terrible.

The sensors tell you how far away the next wall is. If that wall is, say,

30 inches away, the sensors will tell you that the wall

is 29 inches away, or sometimes it will tell you that the wall is 20 inches away.

In the simulations, each of these robots actually has nine different sensors and

all of them are terrible. So you can now move lots of robots really badly

and you can read lots of sensors really badly.

How does this help you find which simulated robot is closest to the real

robot's position? This step is called redistribution.

I'll show you an example. Here's a simulated robot whose sensor

reads 12 inches. The real sensor on the real robot reads

24 inches. You have to find out: if the real robot

were at the simulated robot's position, what is the probability that it would

return the real sensor's reading? This probability can be found using the

bell curve. Just set the center of the curve at the

simulated sensor's reading, or 12 inches, and then, depending on the amount of

error, you stretch the curve out more or less. In this case 24 inches

falls about here on the curve, and if you calculate the area under the

curve you get the probability. In this case 25 percent. If the real robot were

at the same location as a simulated robot, it would have a

25 chance of getting a reading of 24 inches from the sensor.

If we add a few other robots here, they'll have different percentages

based on their readings. Remember, these percentages describe how similar

the real sensor readings and the simulated sensor readings are to each

other, and not where the robot is. The robot

could be near or far away from these three robots.

The robots are removed from the map and then placed back on the map

according to the probabilities. Positions with higher probabilities are more

likely to have one or multiple robots placed there,

and the robots will be placed at exactly the same location. I've overlapped them a

little bit here so you can see that there are

multiple robots. Positions with low probabilities are

unlikely to have a robot. So, maybe this is the final distribution of robots.

Then, the robots can be moved, redistributed, moved, and redistributed

again and again in a loop. Over time, the robots begin to cluster

around a single spot. Sometimes, other clusters might break off

into areas that look similar to the one the real robot is in,

but they disappear as the robot moves into a new area.

The exception to this is when the robot is driving somewhere where the map looks

exactly the same from several locations. The robot could be in any of these four

places and the sensor readings would always be exactly the same

no matter how the robot moves. If there ends up being only one cluster,

where the final cluster ends up is actually just a matter of chance.

If the clusters don't form in the right place you can

increase the number of robots, or you can also

make the robots scatter a little bit every time you redistribute the robots.

You can also kidnap the robot (that's actually what it's called in robotics),

then detect when the cluster is in the wrong spot and re-scatter the robots.

If you're interested in exploring particle filters more, we have the app

available for download on github. It's linked below in the description.

You can move the robot, control how the simulated robots look

and how they move, and a bunch of other things. If you enjoy coding, you can take

a look and modify the code on github to explore the particle filter even more.

We hope you enjoyed learning about particle filters.