YouTube

Got a YouTube account?

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

English subtitles

← 20-14 Path Planning Examples

Get Embed Code
2 Languages

Showing Revision 1 created 11/28/2012 by Amara Bot.

  1. [Thrun] Now here is an actual result of applying this A* algorithm
  2. for our vehicle that sits over here.
  3. Real obstacles--these are laser scans of parked cars--
  4. and a target location over here.
  5. And while the curve isn't super smooth,
  6. you can still see it is able to find a continuous and drivable curve
  7. to the parking location over here
  8. by this small but important modification of A*.
  9. There are a few other modifications of A* which I can't go into detail,
  10. but here you can see a typical attempt of a robot to navigate a parking lot
  11. here in simulation.
  12. You can see the tree that is being expanded in that search.
  13. And every time it gets stuck, it does a new A* search.
  14. You can see how the map is being acquired as the robot moves.
  15. In its state that's in front of the robot, it not only considers the x, y and hidden direction
  16. but also allows the robot to go forward and backwards,
  17. and driving backwards is just a different state than going forwards.
  18. Now you can see how it backs up, finds a new path, and it is an incomplete maze
  19. until it finally is able to reach the goal location through an actual opening.
  20. We made this maze really hard to test our algorithms.
  21. The nice thing is these algorithms work almost real time.
  22. It takes less than a tenth of a second to build this entire search tree,
  23. and the robot is able to navigate this parking lot really, really efficiently.
  24. This was one of the fastest motion planning algorithms that I saw
  25. in the DARPA Urban Challenge.
  26. In fact, in all of robotics it's been one of the fastest algorithms
  27. I've personally seen in my life.
  28. Here is the same algorithm applied to an actual parking example using our robot Junior.
  29. It's driving over here, it wishes to get over there,
  30. and you can see it has backed up into a parking gap over here,
  31. which is an amazing precision for a robot, and then moved forward along the line over here.
  32. Our state space is, I guess, 4-dimensional.
  33. It comprises x, y, hidden direction, and whether the car is going forward or backwards.
  34. There is a cost to changing directions, so it doesn't change direction too often.
  35. You can see it navigate to its target location.
  36. Details I am not telling you include that the trajectory that the planner generates
  37. is subsequently smoothed using a quadratic smoother
  38. so that we get rid of the kinks,
  39. and the car drives much nicer as a result.
  40. But the workhorse here that does all the work to find the best path
  41. is actually A* modified into hybrid A*, as I told you.
  42. And in this final video we see the car navigating a parking lot with lots of traffic cones.
  43. On the left you see the video imagery, on the right side you can see the internal map
  44. and the path planner,
  45. and it attempts to park itself in the designated spot on the left.