Two weeks ago, I was granted the Lyft scholarship for the Intro to self-driving car Nanodegree at Udacity. I have studied probabilistic inference before, but I never was able to relate it into a real-world case, no even think that it was the core of self-driving cars or any type of autonomous robot, not until now.
That’s is why I want to share what I have learned in the first lesson, I want to explain the principles that allow a Robot handle uncertainty, know where it is standing, move through the world, and even furthermore like driving for us.
The first step is to know the place where the robot is going to live and the objects that reside on there, these objects are extremely important because the robot senses them and it is by this sense that it can determine the best location where he can be by a given measure. For this explanation, the world where our robot is going to live in is a grid with a size of 2x2 and for simplicity, the robot can stand either on a red cell or a green cell.
Now is time to introduce my robot he is Carlos and he will help us to understand how he sees the world where he is living in. At the beginning when he is turned on he only knows that is in a world of size 2x2 and he can be either on a red cell or a green one. This step in the life of Carlos is called “Maximum confusion” that only means that he can be equally likely in either of the 4 cells in the world. Mathematically speaking by using a uniform distribution we can equally likely assign probabilities for each cell this will mean that each cell has 1/4 (0.25) chances to be in any of the cells.
But Carlos still confused, he is just waking up and doesn’t have a clue on where exactly he is, So he decided to open his big eye and he sees Red! He now knows that he may be on one of the red cells in the world, but he is not perfect, he knows that can make a mistake (seeing Red but standing in a Green cell). That is why he needs to know the probability of being in that cell given that he saw Red. Let’s say that Carlos eyes can see Red 80% of the time given the place where he is standing, but the probability of mistake is 15% (seeing Red but standing in a Green cell), with this new information he can update his current belief (A uniform distribution), but how?.
Now is time to call Carlos’s best friend Bayes.
Bayes answer the call: “Hey, Carlos are you having troubles with knowing where you are again?”
Carlos: “Hey Bayes, yes indeed I do, but as always I hope you can help me I little bit”
Bayes: “Of course I can! Tell me where you think you are?”
Carlos: “Well, I know for sure that I’m at any place of a 2x2 World, that means that I have 25% chances to be at any place here”
Bayes: “Okay gotcha, can you tell me a little bit more, what about, do you see something special?”
Carlos: “Yes, I do, I see Red! And I’m 80% sure of this. I also know that my eyes are not perfect so I see Red where is not red 15% of the time”
Bayes: “Done! you have 42.1% probabilities to be in a cell of color Red and just 7.9% probabilities to be in a cell of color Green.”
Carlos: “Thank you so much, Bayes, now I can update my current belief thanks to you!”
So now thanks to Carlos ‘s friend, he now has a new belief of where he is standing in his world! And now seems like he is pretty likely to be on the first row in the grid.
So what just happened, how is Bayes and why he was able to give that answer to Carlos.
It’s time to introduce the Bayes Theorem Formula:
The formula seems a little bit complex but is pretty simple once we understand what each term represent and what the output is.
P(Xi | Z) It means that given the measure Z, the probability of the cell Xi will be equal to the output of the expression after the equal sign.
P(Z | Xi) Is the probability of seeing the measure Z given the cell Xi
P(Xi) Is the probability of being in the cell Xi
p(Z) This is a little bit tricky since is the probability of the measure Z, and is calculated as the sum of all P(Z | Xi) * P(Xi) in a grid.
Below you will find a link to a Jupyter notebook where I go through the same explanation but more programming oriented, I strongly suggest to check it out so you can get your hand dirty :)
https://github.com/stevenandersonz/robot-localization
This was the first step in the journey of Carlos to know where he is more likely to be. After Carlos senses the world for the first time he understands a little bit more about where he can be, but that is not enough Carlos, He still had the same probability of being in cell one than in cell two as we will see in the next chapter Carlos need to move in order to sense a new part of his world and improve their belief. There is a lot implied in the movement of Carlos to explore, so I see you there.
Further Research:
* Khan Academy video on Bayes Theorem: https://www.khanacademy.org/partner-content/wi-phi/wiphi-critical-thinking/wiphi-fundamentals/v/bayes-theorem
