Particle Filters
and the Kidnapped Vehicle Project

Tiffany Huang and Maximilian Muffert from Mercedes-Benz

Once again Udacity team up with the best to bring us top quality teaching. In this section we learn from Tiffany Huang and Maximillian Muffert from the localisation team in Mercedes-Benz. In other words they are on the team that help figure out where you car is located as opposed to other aspects of autonomous driving such as controlling steering angles or speed. 

 

As usualy there is quite a bit of theory and Sebasitan founder of Udacity also weigh is in this section to give a background in the localisation theory which also applies to robots in general.

Particle Filters are a bit difficult. It’s easier to see them in action and then explain. So I will ask you to look at the series of 5 pictures below. Just have a look at all of them and see what you notice for a moment. Then below the pictures continue reading.

These images are a bit small but it is useful to have them side by side for now. Notice that they all in have the same dark gray areas. This represents a map of some rooms in a building. Notice the first one on the left has many many red dots, the next also has red dot but less of them and they are clustered in some areas. The next images have  dots and the dots are clustered in fewer and fewer areas.

What you saw above is a particle filter in action. Imagine if you were to have 1000 guesses of where you were on a map. Each dot represents a guess. After you scatter your guesses around randomly you can compare your guesses to any measurement you have. So you might say well I am sure that I am 10 meters from a wall and this guess has no walls within 20 meters therefore this guess must be wrong. If you did this for all your guesses you could eliminate many of them. This is what happens in the first couple of images. Then as your robot or car moves it sensors pick up more information and you can continue to evaluate your guesses inst more information. Eventually you get more certain of the location. The blue lines in the above images are measurements that the robot (in this case) is using to eliminate guesses. Each guess is a point called a particle and that’s where the name comes from

Above is the process flow for the program. Not nearly as complicated as the Kalman Filter but plenty for what we needs.

Some times our mearurements and the map don’t quite work perfectly. Our sensors might say there is a lappost 10 meteres away but the map might say 11. In such cases we need to adjust and select the nearest credible point as being the right one. THis is becuase both sensors and maps can be inaccurate. If the map says there is a lamppost every 10 meters and your sensor sees one 9 meters from another and nothing that looks like a lamppost nearby then sometimes is is acceptable to make adjustments and assumptions.

Similar to the Kalman Filter and Unscented Kalman filter project the graphical illustration aspect to the project is not amazing but it is adequate. And similar to the other projects what is shown here are representations of calculations that normally would not be shown at all in a real car so its the calculations that matter and the graphic presentation of them less so.

Having said that there is enough here to explain what is happening. The scenario represents a kidnapped vehicle and it needs to locate itself. We can see a little blue car and there are green lines extending out from the car. There are also black circles. The lines represent measurements to the map points that are the black circles. Here also you can see in the left side of the image there is another dark blue circle. This represents where the program thinks the car is. So clearly this is not working.

 In the next picture you can see the blue car and the blue circle are in the same place. In this successful version of the program the car drove around a course and the blue circle followed it quite well showing that the computer was locating the car correctly. What you see is a simulator that is testing the code and it tell us when it works which is very handy for Udacity to automatically correct work. But there is something else too, many companies use a system called build to test where a test for a program to pass is written and then when the program or program section like a function is finished it is tested against a test to check it. This is important for quality control and is known as “build to test”. And so the Udacity C++ projects are being done in the “build to test” way and this is a useful experience for us to work in this way.

In the end I found this easier than Kalman and Unscented Kalman filters, I also found the concept behind it fascinating. At this stage I was really starting to feel more confident with my C++ and that was major point in doing this course. 

You can see the code here on Github