Return to Video

20-08 Road Graph

  • 0:00 - 0:07
    The exact same algorithm works beautifully for planning the shortest path
  • 0:07 - 0:11
    to a single mission goal from any possible start location,
  • 0:11 - 0:17
    and the only difference here is in this graph over here of an actual road graph
  • 0:17 - 0:21
    we are also incorporating the heading direction as measure of distance.
  • 0:21 - 0:27
    Green corresponds to nearby to large values, red to far away.
  • 0:27 - 0:31
    The reason why the area below the mission goal is green is because we expect
  • 0:31 - 0:35
    the car to point up, to point north, at the time it reached the mission.
  • 0:35 - 0:38
    So if it came from the north, it would point in the wrong direction.
  • 0:38 - 0:41
    The state space is augmented correspondingly.
  • 0:41 - 0:45
    Where if it comes from over here, it points in the correct direction.
  • 0:45 - 0:47
    If you look at the circle over here, it's interesting.
  • 0:47 - 0:50
    If we came from the left side over here, it could do a right turn,
  • 0:50 - 0:55
    but over here it's forced on this one-way circle to do the entire loop to go around,
  • 0:55 - 0:58
    and that increases the value as it comes over here.
  • 0:58 - 1:03
    This is value iteration applied to the road graph where we keep track of heading
  • 1:03 -
    and where the circle over here is a one-way circle.
Title:
20-08 Road Graph
Team:
Udacity
Project:
CS271 - Intro to Artificial Intelligence
Duration:
01:07
Amara Bot added a translation

English subtitles

Revisions