Roadmap Path Planning Brian C. Williams 16.410-13 October 27 th , 2003 Brian Williams, Fall 03 2 Assignment ? rd , 2003. Reading: Homework: Brian Williams, Fall 03 – Path Planning: AIMA Ch. 25.4 – Online problem set #7 due Monday, November 3 1 courtesy NASA Ames How do we maneuver? 4 Roadmaps are an effective state space abstraction courtesy NASA Lewis Brian Williams, Fall 03 Courtesy of U.S. Geological Survey Images taken from NASA's website: http://www.nasa.gov. 5 Outline path planning – – 6 Path Planning through Obstacles Start position Goal position Creating road maps for Exploring roadmaps: Shortest path Informed search Avoiding adversaries – (Next Lecture) Brian Williams, Fall 03 Brian Williams, Fall 03 7 1. Create Configuration Space Start position Goal position Idea: Transform to equivalent problem of navigating a point. Assume: Vehicle translates, but no rotation 8 2. Map From Continuous Problem to a Roadmap: Create Visibility Graph Start position Goal position Brian Williams, Fall 03 Brian Williams, Fall 03 9 Start position Goal position 2. Map From Continuous Problem to a Roadmap: Create Visibility Graph 10 3. Plan Shortest Path Start position Goal position Brian Williams, Fall 03 Brian Williams, Fall 03 11 Start position Goal position Resulting Solution 12 A Visibility Graph is One Kind of Roadmap Start position Goal position What are some other types of roadmaps? Brian Williams, Fall 03 Brian Williams, Fall 03 13 14 Roadmaps: Fixed Grid Roadmaps: Voronoi Diagrams Lines equidistant from CSpace obstacles Brian Williams, Fall 03 Brian Williams, Fall 03 15 Roadmaps: Fixed Grid 16 Roadmaps: Approximate Cell Decomposition Brian Williams, Fall 03 Brian Williams, Fall 03 Brian Williams, Fall 03 17 Roadmaps: Exact Cell Decomposition 18 Incorporating Vehicle Dynamics into Roadmaps Goal Start Rapidly-exploring Random Trees (RRT) Brian Williams, Fall 03 – Begin at the start state, – attempt to grow into the goal state – by exploring the vehicle’s state space – Search from both sides 19 RRT, T a q init q goal RRT, T b Example: 20 RRT, T a RRT, T b q rand Brian Williams, Fall 03 Brian Williams, Fall 03 21 RRT, T a RRT, T b 22 RRT, T a RRT, T b Brian Williams, Fall 03 Brian Williams, Fall 03 Brian Williams, Fall 03 23 RRT, T a RRT, T b Common Node 24 RRT, T a RRT, T b collision-free path rooted at T a ing at T b 2 RRTs grow into each other to generate a and end Brian Williams, Fall 03 How do we find the shortest path through a roadmap? Start position RRT, T a RRT, Goal T b position Brian Williams, Fall 03 25 How do we plan with adversaries? Start positions Goal Brian Williams, Fall 03 26 position 27 Outline path planning – – – Creating road maps for Exploring roadmaps: Shortest path Dijkstra;s algorithm Bellman-Ford algorithm Floyd-Warshall algorithm Johnson’s algorithm Informed search Greedy search Avoiding adversaries (Next Lecture) Brian Williams, Fall 03 Uniform cost search A* search Beam search Hill climbing