Placeholder Image

Subtitles section Play video

  • Hello, and welcome to BotField. Imagine that you are in your house, but

  • 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.

Hello, and welcome to BotField. Imagine that you are in your house, but

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it