Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 04-33 Left Turn Policy

Get Embed Code
3 Languages

Showing Revision 1 created 06/29/2012 by Amara Bot.

  1. Let's now have some fun and apply this to an actual car problem.
  2. The one I'll using is a bit simplified as always,
  3. but it does relate to real world path planning as is done, for example, by Google Maps.
  4. Suppose we have a car down here.
  5. This car now has its state an x, a y, and an orientation, theta.
  6. By orientation for simplicity is chosen from 4 possible directions--up, down, left, and right.
  7. As I quiz you in the beginning, I'd like to get to the location over here, facing left.
  8. Realize that now the state space is 3-dimensional, just like in our localization example.
  9. I now would like to implement a dynamic programming planner
  10. that gives me the optimal path for going from here to here
  11. and that let's me play with cost functions.
  12. There are three principle actions.
  13. One is move in which the car just goes 1 grid cell forward in its present orientation.
  14. It doesn't turn at all. That could be applied anywhere in the maze in any direction.
  15. One is turn left and then move.
  16. This car in this position in the cell over here could chose
  17. the turn left and move, which makes it move over here.
  18. The last one is turn right and move,
  19. in which case it would, from this cell over here,
  20. turn over here and head in this direction.
  21. Here's our world again.
  22. You can see there is a street over here that's navigable, one over here that's navigable.
  23. You see the loop on the right side.
  24. Remember that now this state space is 3-dimensional, not 2- dimensional.
  25. Our goal is to move to cell [2, 0], which is the one over here.
  26. Our initial state is up here,
  27. and the initial state has not just a position of [4, 3] but also an orientation of 0.
  28. It's a 3-dimensional state.
  29. Here are my orientations--0, 1, 2, and 3.
  30. The first one makes the robot go up, the second go left,
  31. third one go down, and the fourth one go right.
  32. Here are the names associated with it---up, left, down, and right.
  33. This thing here is interesting.
  34. As actions, we have 3 actions.
  35. We can add to the index orientation -1, 0, or 1.
  36. If we add -1 we jump 1 up in the cyclic array over here,
  37. which is the same as doing a right turn.
  38. For example, if you go from go left to go up, that the same as turning right.
  39. If we add +1, that's the same as turning left.
  40. If we leave the orientation unchanged,
  41. then we go straight, which is indicated by this hash symbol over here.
  42. These actions come with different costs.
  43. Right now the left turn costs me 2, going straight costs me 1,
  44. and going right costs me 1 as well, which, as we all know,
  45. makes the left turn the preferred solution over here.
  46. Indeed, as I run it, you can see how the car turns left over here to the goal location.
  47. If I were to increase the cost for the left action to 20, then my solution changes.
  48. You can see the car dashes straight ahead over here, turns right over here,
  49. right over here, right over here, and then goes straight to the goal location.
  50. That software I want you to implement. There is one more hint.
  51. The value function itself is 3-dimensional, and here is the code that I've been using.
  52. Not necessarily the most efficient, but it has inside 4 identical arrays
  53. of the size of the grid concatenated into a megagrid
  54. and initialized all by a very large value--999 in this case.
  55. You need functions just like these, and it turns out this makes it more difficult to write the code.
  56. This is our last quiz in this lecture.
  57. Our last programming assignment, and you might spend some time.
  58. It took me a while to program it myself to get an output just like this over here.