First of all, I apologize for not blogging yesterday. I had been pretty busy with the company placements in my university. I sincerely apologize for not letting you know things.
This plot is also called Belief Space of the robot.
So, after the apology program is off the memory stack. Let us get to the topic head-on. Localization is a very important concept of Artificial Intelligence. Let us begin with defining this very important term. I shall try to be very informal in my definitions( my sincere apologies to the experts).
Localization
Let us begin with blindfolding a robot (I shall call it Blinder). After we have safely kidnapped the robot, next step is to get into a cab and go to a very unfounded place, which the robot is not aware about. Then we remove the blindfold of the so called angry Blinder. We run away, and leave the robot at its own, to search its way out. Now, the primary task of Blinder is to see through its surrounding and find his position and orientation with respect to the surrounding. Quite an easy task, Huh?.
Well true for the humans, but very false for the robots. There are quite many reasons for that . First, it is next to impossible with the present computational resources to program the robot to make sense of all the things around it. What we see as grass, is nothing but a point in the 3D point cloud for the bot. This ability of ours to make sense of our surrounding is called Contextual knowledge in Robotics. The view of Blinder is constrained too. The most sophisticated sensing equipments, like cameras or L.R.F. (Laser Range Finders) are far less sophisticated in comparison to our simple looking EYE. Yes, the most underrepresented entity of mankind is the most sophisticated sensor in the human civilization till date. Thus various locations look quite similar to the robots and thus the probabilistic approach needs to be adopted to differentiate between them. If you are not making much sense out of this, hang On. I will be giving a detailed illustration of all of it.
Probabilistic Approach
Blinder, and all other robots, determines its present position in a probabilistic manner. It creates a map of all the possible positions a robot can be, and then assigns each location a probability. Now initially when the robot's blindfold has just been removed, and it has not grabbed any sensor reading of the surrounding, he/she is totally lost. He can be in any of the N locations possible.
P(i) = 1/N where, i = 1 to N
Let us for the sake of simplicity assume that N = 5. To simplify even further, let us assume that robot is lost in 1-Dimensional space. Don't loose heart with such generalization. They scale equally to the actual case of billions of equally likely points located in the 2-D space(the case with Blinder) or in 3-D space (the condition with the manipulators that are free to move in the 3-D space).
Let us make an array of 5 locations represented as boxes shown below, and place a probability of 0.2(1/N(=5)) in each one of them.
i = 1 i = 2 i = 3 i = 4 i = 5
0.2
|
0.2
|
0.2
|
0.2
|
0.2
|
So the robot has no idea as to where he or she is. You might have noticed the color of text in each box. The color of the text is the identity of the box. So there are three blue boxes (i = 1,2,5) and two red boxes(i = 3,4). Each box's color is the only thing which the robot can identify. This is analogous to the identity of each location that the location inherits due to its disparate colors, look, feel etc. For us the robot can't see anything for the unknown locations(boxes) apart from its color.
Now comes the hard part. To determine the robot motion model. Generally it is Gaussian in nature when the N is pretty large close to millions, which is quite a commonplace case in the Localization world. But that is very complex to express. Let us make it a bit easy, with a Gaussian like model shown below. Let us assume that the robot intends to move only one step forward at a time from one box to the next box. Also, the path is cyclic in order to ensure consistency in such a small work-space. Thus if the robot moves from i = 5 a step forward, then it reaches i = 1.
On the x axis (Tasks)
1 - the robot does not move
2 - the robot moves the intended one step forward
3 - the robot oversteps and moves two steps instead of one step
On the y axis
1 - Probability of robot to do task 1 = P(1) = 0.2
2 - Probability of robot to do task 2 = P(2) = 0.6
3 - Probability of robot to do task 3 = P(3) = 0.2
Now if we issue a motion command, the probability distribution of the robot changes. This is also called Posterior of the robot motion.
P(i) new = [P(i )old* P(task = 1) + P(i - 1)old * P(task = 2) + P(i - 2)old * P (task = 3)]
After all the P(i) is updated. Do normalize the Probability to sum to 1.
P(i)new normalized = P(i) new / sum(P(i))
.
Now a quick question for all you guys?
Q.1) If the robot being at its initial stage intends to move forward, what is the new probability distribution diagram of the robot ?
A.1) At the end of this blog.
Q.2) Let us assume that the robot is initially at i = 2. What is the new posterior provided the robot intends to move 1 step forward.? Assume the motion model as shown above in the blog.
A.2)
Initial Belief Space
i = 1 i = 2 i = 3 i = 4 i = 5
0
|
1
|
0
|
0
|
0
|
Initial Probability distribution Bar plot
Posterior Belief Space
P(1) = 0 * 0.2 + 0 * 0.6 + 0 * 0.2 = 0
P(2) = 1 * 0.2 + 0 * 0.6 + 0 * 0.2 = 0.2
P(3) = 0 * 0.2 + 1 * 0.6 + 0 * 0.2 = 0.6
P(4) = 0 * 0.2 + 0 * 0.6 + 1 * 0.2 = 0.2
P(5) = 0 * 0.2 + 0 * 0.6 + 0 * 0.2 = 0
Posterior
i = 1 i = 2 i = 3 i = 4 i = 5
0
|
0.2
|
0.6
|
0.2
|
0
|
Posterior Probability distribution bar plot
I leave you to think, that such motion, always deteriorates the accuracy to which the position can be known. Ideally P(i = 3) should have been 1, but due to the inaccurate robot motion and thus a probabilistic motion model, the robot has P(i = 3) = 0.6
Measurement Step
Then we are left with the question as to how to improve the accuracy of the robot motion, or in other words localize the robot in its map. The question might seem tricky, but is very intuitive. We have to measure things to make a more accurate prediction.
Remember, I marked the boxes with a color that identifies and differentiates one set of boxes from others. This is what the robot will tend to measure. Let us assume that robot has a very restrained vision and can only identify if the location(box) is red or blue.
The robot vision is not accurate either, it is bound to report wrongly. Thus let us maintain a measurement model too. In general we use two coefficients shown below.
Hit Coefficient(HC) = 0.6
Miss Coefficient (MC) = 0.2
Note : You can choose any two values for the Hit and Miss Coefficients respectively, but make sure that
HC > MC
Whenever a robot encounters, say a Red box, then it multiplies all the Red boxes in its belief space withe the Hit Coefficient( here = 0.6) , and all the blue boxes with the Miss Coefficient (here = 0.2).
Last but not the least, do not forget to normalize the values of probabilities in the belief space. As sum of these probabilities should always be 1, as the robot can possibly be in only one of these pre defined states.
So let me throw up a quick question?
Q.2 If initially the robot does not know where he/she is, it moves one step with total certainty (notion model is accurate, i.e robot does not under-step or overstep), and measures Red, then it moves another step with total certainty, and measures a Blue. Please define the new belief space for the robot?
A.2) Hint: the robot motion is totally certain, thus a quick method is to move the belief space terms, cyclically one step forward to get the new motion belief space.
Step -1 - Motion Step
Step -2 - Measurement Step (Red)
Step -3 - Motion Step
Step -4 - Measurement Step (Blue)
Answer for each of the four steps is given at the end of the blog. Do solve them first, by yourself, before jumping straight to the answer. You will get to have the essence of the Localization. Those who tend to solve this problem, will have the necessary basics to move on in the vast world of Robotics.
Note - You will also observe that Measurement model, increases the accuracy of robot presence in the belief space, while motion model decreases it.
Q. If the above statement in the note is valid, why do we do the motion update, at all?
A. Because, it is the most accurate representation of the robot model. The robot can't be trusted 100% with its motion capabilities. Ensuring a degree of inaccuracy through probabilistic robot models, helps us identify the true robot behavior.
A.1 )
i = 1 i = 2 i = 3 i = 4 i = 5
0.2
|
0.2
|
0.2
|
0.2
|
0.2
|
A.2)Initial
i = 1 i = 2 i = 3 i = 4 i = 5
0.2
|
0.2
|
0.2
|
0.2
|
0.2
|
Step 1 - Motion
i = 1 i = 2 i = 3 i = 4 i = 5
0.2
|
0.2
|
0.2
|
0.2
|
0.2
|
Step 2 - Measurement - Red
i = 1 i = 2 i = 3 i = 4 i = 5
0.04
|
0.04
|
0.12
|
0.12
|
0.04
|
After Normalization
i = 1 i = 2 i = 3 i = 4 i = 5
1/9
|
1/9
|
1/3
|
1/3
|
1/9
|
Step 3 - Motion
i = 1 i = 2 i = 3 i = 4 i = 5
1/9
|
1/9
|
1/9
|
1/3
|
1/3
|
Step 4 - Measurement - Blue
i = 1 i = 2 i = 3 i = 4 i = 5
0.067
|
0.067
|
0.022
|
0.022
|
.18
|
After Normalization
i = 1 i = 2 i = 3 i = 4 i = 5
0.1667
|
0.1667
|
0.0547
|
0.0547
|
.4478
|
Thus maximum is the probability of the robot being in the state of 5. which is true, as you might have observed, that the only possible way the robot could have most favorably measured Red and Blue consecutively after each motion if it would have been in Step 3 initially. Thus after 2 motions it will be in step 5.
Voila, you have aced the first step of Robotics, Localization concept must have got embedded in your mind. Best of luck for your future in Robotics.
A lot many blogs are to come, so do not forget to subscribe and like this blog.
Regards
Harshal
P.S. Next to Come
1. Localization for Dilettante
2. Localization for Experts
keep a watch at this blog for the links to the new blogs.
P.S. Next to Come
1. Localization for Dilettante
2. Localization for Experts
keep a watch at this blog for the links to the new blogs.
No comments:
Post a Comment