Roadmap path planning Brian C. williams 16410-13 October 27th. 2003 Assignment · Reading: Path Planning: AIMA Ch 25.4 Homework Online problem set #7 due Monday, November 3rd, 2003
Roadmap Path Planning Brian C. Williams 16.410-13 October 27th, 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
How do we maneuver? courtesy NasA ames / courtesy NASALew agestakenfromNasa'Swebsitehttp://www.nasa.gov Roadmaps are an effective state space abstraction Brian williams, Fall 03 Courtesy of U.S. Geological Surver
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
Outline Creating road maps for path planning Exploring roadmaps: Shortest path Informed search Avoiding adversaries Brian Williams, Fall 03 Path Planning through Obstacles Brian Williams, Fall 03 tion
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
Create Configuration Space Assume: Vehicle translates. but no rotation Idea: Transform to equivalent Goal problem of navigating a point position 7 2. Map from Continuous Problem to a Roadmap Create Visibility Graph Start position Brian Williams, Fall 03 tion
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
2. Map From Continuous Problem to a Roadmap Create Visibility Graph position Brian Williams, Fall 03 position 9 3. Plan shortest path Start position Brian Williams, Fall 03 tion
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
Resulting solution Start position Brian Williams, Fall 03 position a Visibility graph is One Kind of roadmap Start What are some other types of roadmaps? positi Brian Williams, Fall 03 tion 12
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
Roadmaps: Voronoi diagrams Lines equidistant from CSpace obstacles Roadmaps: Fixed grid
13 14 Roadmaps: Fixed Grid Roadmaps: Voronoi Diagrams Lines equidistant from CSpace obstacles Brian Williams, Fall 03 Brian Williams, Fall 03
Roadmaps: Fixed grid Roadmaps: Approximate Cell Decomposition williams, Fall 03
15 Roadmaps: Fixed Grid 16 Roadmaps: Approximate Cell Decomposition Brian Williams, Fall 03 Brian Williams, Fall 03
Roadmaps: Exact Cell decomposition Incorporating Vehicle Dynamics into roadmaps Rapidly-exploring Random Trees(RRT Begin at the start state, attempt to grow into the goal state y exploring the vehicle's state space Search from both sides Goal Start
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
Example: RRT, T RRT, Th Brian Williams. Fall 03 RRT, T °°° RRT, Th Brian Williams. Fall 03
19 RRT, Ta qinit qgoal RRT, Tb Example: 20 RRT, Ta RRT, Tb qrand Brian Williams, Fall 03 Brian Williams, Fall 03
