Return to Video

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:
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=PL3475310BFB1CBE34

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
Amara Bot added a translation

English subtitles

Revisions