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