0616 Graph Slam

0:00  0:04Let me tell you about my favorite method of all, called "Graph SLAM."

0:04  0:09This is one of many methods for SLAM, and it's the one that is by far the easiest to explain.

0:09  0:11Let's assume we have a robot,

0:11  0:17and let's call arbitrarily the initial location x equals zero and y equals zero.

0:17  0:20For this example, we just assume the road has a perfect compass,

0:20  0:23and we don't care about heading direction just to keep things simple.

0:23  0:29Let's assume the robot moves to the right in xdirection by 10, so it's now over here.

0:29  0:34In a perfect world, we would know that x1, the location after motion,

0:34  0:40is the same as x0+10 and y1 is the same as y0.

0:40  0:44But we learned from our various robotic Kalman filter lessons and others

0:44  0:47that the location is actually uncertain.

0:47  0:52Rather than assuming in our (x, y) coordinate system the robot moved to the right by 10 exactly,

0:52  0:58we know that the actual location is a Gaussian centered around (10, 0),

0:58  1:00but it's possible the robot is somewhere else.

1:00  1:03Remember we worked out the math for this Gaussian?

1:03  1:06Here's how it looks just for the x variable.

1:06  1:11Rather than setting x1 to x0 plus 10, we try to express the Gaussian

1:11  1:14that peaks when these two things are the same.

1:14  1:18If we subtract from x1 x0 and 10,

1:18  1:22put this into a squared format and turn this into a Gaussian,

1:22  1:27we get a probability distribution that relates x1 and x0.

1:27  1:29We can do the same for y.

1:29  1:32Since there is no change in y, according to our motion,

1:32  1:37all we ask is that y1 and y0 are as close together as possible.

1:37  1:41The product of these two Gaussians is now our constraint.

1:41  1:50We wish to maximize the likelihood of the position x1 given the position x0 is (0, 0).

1:50  1:59What Graph SLAM does is defining our probabilities using a sequence of such constraints.

1:59  2:03Say we have a robot that moves in some space,

2:03  2:07and each location is now characterized by a vector x0

2:07  2:13and a vector x1, vector x2, vector x3. Often they are 3dimensional vectors.

2:13  2:18What Graph SLAM collects is initial location, which is a (0, 0, 0) initially

2:18  2:20although here it looks a little bit different

2:20  2:23then, really importantly, lots of relative constraints

2:23  2:28that relate each robot pose to the previous robot pose.

2:28  2:30We call them relative motion constraints.

2:30  2:32You can think of those as rubber bands.

2:32  2:38In expectation, this rubber band will be exactly the motion the robot sensed or commanded,

2:38  2:43but in reality, it might have to bend it a little bit to make the map more consistent.

2:43  2:47Speaking about maps, let's use landmarks as an example.

2:47  2:50Suppose there is a landmark out here, and the landmark is being seen

2:50  2:54from the robot with some relative measurementz0, z1.

2:54  2:58Perhaps I didn't see it it during time 2, but this is z3.

2:58  3:01All these are also relative constraints

3:01  3:03very much like the ones before.

3:03  3:07Again, they are captured by Gaussians, and we get relative measurement contraints.

3:07  3:11One such constraint is every time the robot sees a landmark.

3:11  3:15Graph SLAM collects thosee constraints, and as we'll see,

3:15  3:19they're insanely easy to collect, and it just relaxes the set of rubber bands

3:19  3:25to find the most likely configuration of robot path along with the location of landmarks.

3:25  3:27That is the mapping process.

3:27  3:30Let me ask you a quick quiz that'll take thinking.

3:30  3:35Suppose we have six robot posesthat is, one initial and five motions.

3:35  3:39We have eight measurements of landmarks that we've seen.

3:39  3:42These might be multiple landmarks. Sometimes the robot saw more than one.

3:42  3:46The question now is how many total constraints do we have if we count each

3:46 of these constraints as exactly one constraint.
 Title:
 0616 Graph Slam
 Description:

Other units in this course below:
Unit 1: http://www.youtube.com/playlist?list=PL1EF620FCB11312A6
Unit 2: http://www.youtube.com/playlist?list=PL107FD47786234011
Unit 3: http://www.youtube.com/playlist?list=PL5493E5D24A081719
Unit 4: http://www.youtube.com/playlist?list=PLAADAB4F235FE8D65
Unit 5: http://www.youtube.com/playlist?list=PL1B9983ACF22B1920
Unit 6: http://www.youtube.com/playlist?list=PLC9ED5AC39694C141
QA: http://www.youtube.com/playlist?list=PL3475310BFB1CBE34To gain access to interactive quizzes, homework, programming assignments and a helpful community, join the class at http://www.udacity.com
 Video Language:
 English
 Team:
 Udacity
 Project:
 CS373  Artificial Intelligence
 Duration:
 03:51
Amara Bot added a translation 