 ## ← 04-33 Left Turn Policy

• 1 Follower
• 58 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=bQA2ELDNmmg" data-team="udacity"></div> ``` 3 Languages

• English [en] original
• Japanese [ja]
• Russian [ru]

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.