Localization Overview for Self Driving Cars
Localization overview for autonomous vehicles or self driving cars
Welcome to this medium article based on Artificial Intelligence for Robotics. In this medium article we’ll cover the localization concepts and study about total probability and sense and move methodology.
Introduction
The very first problem based on perception is called localization. It involves a robot that’s lost in space. It could be a car. It could be a mobile robot. So there is an environment, and the poor robot has no clue where it is. Similarly, we might have a car driving on a highway, and this car would like to know where it is. Is it inside the lane or outside? Now the traditional way to solve this problem is by using satellites. Cars perceive the signals emitted by satellites. That’s known as GPS, short for “global positioning system,” and it’s what we have in your dashboard if we have a car with GPS that shows us the maps and shows us where we are. The only disadvantage of GPS is that its not very accurate. It’s really common for a car to believe to be here but it has 2 meters all the way up to 10 meters of error. So if we try to stay in the lane with 10 meters of error, we’re far off, and we’re driving right over here, and we crash. So for the autonomous vehicles, to be able to follow localization, the error should be very less like 2–10 centimeters. Then we can drive with GPS in lanes. Now the main question is, what can we use to figure out where are we with an accuracy of 10 cm?
That’s the localization question.
Localization plays a key role in self driving cars. We record images of the road surface and then use the techniques I’m just about to mention here to find out exactly where the robot is. It does so within a few centimeters of accuracy. Also, makes the self driving vehicle stay inside the lane even if there are no lane markings. So localization has a lot of math, but before diving into mathematical detail, I want to give you an intuition for the basic principles.
Total Probability
Let us begin the visualization with a robot. Let’s assume the robot doesn’t know where it is. Then we would model this with a function where the vertical axis is the probability for any location in this world, and the horizontal axis corresponds to all the places in this 1-dimensional world. The confusion of the robot is given by the robot’s current belief about where it might be. This could be modeled by a uniform function that assigns equal weight to every possible place in this world. It’s called the state of maximum confusion. For the process of localization, the world must have some distinctive features. Let’s assume there are 3 different landmarks in the world. There are three doors.
For the sake of the argument, let’s assume they all look alike, so they’re not distinguishable, but we can distinguish the door from the non-door area — from the wall. Now, let’s figure out how the robot will perform the localization process all by itself by assuming it senses, and it senses that it’s standing right next to a door. So all it knows now is that it is located, likely, next to a door. How would this affect our belief?
Here is the critical step for localization. If we understand this step, we would clearly understand localization. Our belief function is transformed by the measurement of a door, defined over possible locations, to a new function. All the other locations have a decreased belief whereas for the three locations adjacent to the doors, we have an increased belief.
This is a probability distribution that assigns higher probability for being next to a door, and it’s called the posterior belief where the word “posterior” means it’s after a measurement has been taken.
Now, the key aspect of this belief is that we still don’t know where we are. There are 3 possible door locations, and in fact, it might be that the sensors were erroneous, and we accidentally saw a door where there’s none. So there is still a residual probability of being in these places over here, but these three bumps together really express our current best belief of where we are. This representation is absolutely core to probability and to mobile robot localization. Now let’s assume the robot moves.
Say it moves to the right by a certain distance. Then we can shift the belief according to the motion. Obviously, the robot knows its heading direction. It’s moving to the right for example, and it knows roughly how far it moved. Now, robot motion is somewhat uncertain. We can never be certain where the robot moved. The process of moving those beliefs to the right side is technically called a convolution. Let’s now assume the robot senses again, and for the sake of the argument, let’s assume it sees itself right next to a door again, so the measurement is the same as before.
Sense and Move
Now, localization is nothing else but the iteration of “sense” and “move.” There is an initial belief that is tossed into this loop. Localization cycles through these — move, sense, move, sense, move, sense, move, sense, move, sense cycle. Every time the robot moves, it loses information as to where it is. That’s because robot motion is inaccurate. Every time it senses it gains information. That is manifest by the fact that after motion, the probability distribution is a little bit flatter and a bit more spread out. And after sensing, it’s focused a little bit more. In fact, as a foot note, there is a measure of information called “entropy.”
Here is one of the many ways you can write it: [-Ʃp(xi)log p(xi)] as the expected log (logarithmic) likelihood of the probability of each grid cell. Without going into detail, this is a measure of information that the distribution has, and it can be shown that the update step, the motion step, makes the entropy go down, and the measurement step makes it go up.
Summary
We learned that localization maintains a function over all possible places where a road might be, where each cell has an associated probability value. The measurement update function, or “sense,” is nothing else but a product in which we take those probability values and multiply them up or down depending on the exact measurement. Because the product might violate the fact that probabilities add up to 1, there was a product followed by normalization. Motion was a convolution. This word itself might sound cryptic, but what it really means is for each possible location after the motion, we reverse engineered the situation and guessed where the world might have come from and then collected, we added, the corresponding probabilities. Something as simple as multiplication and addition solves all of localization and is the foundation for autonomous driving.
With this, we have come to the end of this article. Thanks for reading this and following along. Hope you loved it! Bundle of thanks for reading it!
My Linkedin :)
