## 06-16 Graph Slam

• 0:00 - 0:04
Let me tell you about my favorite method of all, called "Graph SLAM."
• 0:04 - 0:09
This is one of many methods for SLAM, and it's the one that is by far the easiest to explain.
• 0:09 - 0:11
Let's assume we have a robot,
• 0:11 - 0:17
and let's call arbitrarily the initial location x equals zero and y equals zero.
• 0:17 - 0:20
For this example, we just assume the road has a perfect compass,
• 0:20 - 0:23
and we don't care about heading direction just to keep things simple.
• 0:23 - 0:29
Let's assume the robot moves to the right in x-direction by 10, so it's now over here.
• 0:29 - 0:34
In a perfect world, we would know that x1, the location after motion,
• 0:34 - 0:40
is the same as x0+10 and y1 is the same as y0.
• 0:40 - 0:44
But we learned from our various robotic Kalman filter lessons and others
• 0:44 - 0:47
that the location is actually uncertain.
• 0:47 - 0:52
Rather than assuming in our (x, y) coordinate system the robot moved to the right by 10 exactly,
• 0:52 - 0:58
we know that the actual location is a Gaussian centered around (10, 0),
• 0:58 - 1:00
but it's possible the robot is somewhere else.
• 1:00 - 1:03
Remember we worked out the math for this Gaussian?
• 1:03 - 1:06
Here's how it looks just for the x variable.
• 1:06 - 1:11
Rather than setting x1 to x0 plus 10, we try to express the Gaussian
• 1:11 - 1:14
that peaks when these two things are the same.
• 1:14 - 1:18
If we subtract from x1 x0 and 10,
• 1:18 - 1:22
put this into a squared format and turn this into a Gaussian,
• 1:22 - 1:27
we get a probability distribution that relates x1 and x0.
• 1:27 - 1:29
We can do the same for y.
• 1:29 - 1:32
Since there is no change in y, according to our motion,
• 1:32 - 1:37
all we ask is that y1 and y0 are as close together as possible.
• 1:37 - 1:41
The product of these two Gaussians is now our constraint.
• 1:41 - 1:50
We wish to maximize the likelihood of the position x1 given the position x0 is (0, 0).
• 1:50 - 1:59
What Graph SLAM does is defining our probabilities using a sequence of such constraints.
• 1:59 - 2:03
Say we have a robot that moves in some space,
• 2:03 - 2:07
and each location is now characterized by a vector x0
• 2:07 - 2:13
and a vector x1, vector x2, vector x3. Often they are 3-dimensional vectors.
• 2:13 - 2:18
What Graph SLAM collects is initial location, which is a (0, 0, 0) initially--
• 2:18 - 2:20
although here it looks a little bit different--
• 2:20 - 2:23
then, really importantly, lots of relative constraints
• 2:23 - 2:28
that relate each robot pose to the previous robot pose.
• 2:28 - 2:30
We call them relative motion constraints.
• 2:30 - 2:32
You can think of those as rubber bands.
• 2:32 - 2:38
In expectation, this rubber band will be exactly the motion the robot sensed or commanded,
• 2:38 - 2:43
but in reality, it might have to bend it a little bit to make the map more consistent.
• 2:43 - 2:47
Speaking about maps, let's use landmarks as an example.
• 2:47 - 2:50
Suppose there is a landmark out here, and the landmark is being seen
• 2:50 - 2:54
from the robot with some relative measurement--z0, z1.
• 2:54 - 2:58
Perhaps I didn't see it it during time 2, but this is z3.
• 2:58 - 3:01
All these are also relative constraints
• 3:01 - 3:03
very much like the ones before.
• 3:03 - 3:07
Again, they are captured by Gaussians, and we get relative measurement contraints.
• 3:07 - 3:11
One such constraint is every time the robot sees a landmark.
• 3:11 - 3:15
Graph SLAM collects thosee constraints, and as we'll see,
• 3:15 - 3:19
they're insanely easy to collect, and it just relaxes the set of rubber bands
• 3:19 - 3:25
to find the most likely configuration of robot path along with the location of landmarks.
• 3:25 - 3:27
That is the mapping process.
• 3:27 - 3:30
Let me ask you a quick quiz that'll take thinking.
• 3:30 - 3:35
Suppose we have six robot poses--that is, one initial and five motions.
• 3:35 - 3:39
We have eight measurements of landmarks that we've seen.
• 3:39 - 3:42
These might be multiple landmarks. Sometimes the robot saw more than one.
• 3:42 - 3:46
The question now is how many total constraints do we have if we count each
• 3:46 -
of these constraints as exactly one constraint.
Title:
06-16 Graph Slam
Description:

Other units in this course below:

To gain access to interactive quizzes, homework, programming assignments and a helpful community, join the class at http://www.udacity.com

more » « less
Video Language:
English
Team:
Udacity
Project:
CS373 - Artificial Intelligence
Duration:
03:51