Path Planning in Partially-Known Environments Prof. brian Williams (help from Hsiang shu 16. 412/6.834 Cognitive Robotics February 17th, 2004
Path Planning in Partially-Known Environments Prof. Brian Williams (help from Ihsiang Shu) 16.412/6.834 Cognitive Robotics February 17th, 2004
Outline a Path Planning in Partially Known Environments a Finding the Shortest Path to the Goal a Alternative Approaches to Path Planning in Partially Known Environments a Continuous Optimal Path Planning 口 Dynamic a* 口 ncrementala
Outline Path Planning in Partially Known Environments. Finding the Shortest Path to the Goal. Alternative Approaches to Path Planning in Partially Known Environments. Continuous Optimal Path Planning Dynamic A* Incremental A*
EXample: Partially Unknown Environ JEBS LG DHK F States f and h are blocked Robot doesnt know this
Example: Partially Unknown Environ J M N O E I L G B D H K S A C F • States F and H are blocked. • Robot doesn’t know this
Solutions: [Goto& Stenz, 87 Generate global path plan from initial map 2. EXecute path plan While updating map based on sensors 3. If a new obstacle is found obstructing the path, a Then locally circumvent 4. If route is completely obstructed a Then globally replan with updated map
Solutions: [Goto & Stenz, 87] 1. Generate global path plan from initial map. 2. Execute path plan While updating map based on sensors. 3. If a new obstacle is found obstructing the path, Then locally circumvent. 4. If route is completely obstructed, Then globally replan with updated map
Robot generates global path h=3 h=1 h=1 h h=2 h=1 h=0 E G h=3 2 h=1 BDHK h=3 h=2 h=2 h=2 S A C F Single Source Shortest path from Goal Stop when robot location reached
Robot Generates Global Path J M N O E I L G B D H K S A C F h = 3 h = 3 h = 3 h = 3 h = 2 h = 2 h = 2 h = 2 h = 2 h = 2 h = 0 h = 1 h = 1 h = 1 h = 1 h = 1 • Single Source Shortest path from Goal. • Stop when robot location ( ) reached
Robot generates global path h=4 h=2 h=1 h h=2 h=1 h=0 E G h=4 h=2 BDHK h=5 h=4 h=3 h=2 S A C F Single Source Shortest path from Goal Stop when robot location reached
Robot Generates Global Path J M N O E I L G B D H K S A C F h = 5 h = 4 h = 3 h =4 h = 4 h = 3 h = 2 h = 3 h = 3 h = 2 h = 0 h = 2 h = 1 h = 2 h = 1 h = 1 • Single Source Shortest path from Goal. • Stop when robot location ( ) reached
Robot executes global path h=4 h=2 h=1 h h=2 h=1 h=0 E G h=4 h=2 BDHK h=5 h=4 h=3 h=2 S A C F
Robot Executes Global Path J M N O E I L G B D H K S A C F h = 5 h = 4 h = 3 h = 4 h = 4 h = 3 h = 2 h = 3 h = 3 h = 2 h = 0 h = 2 h = 1 h = 2 h = 1 h = 1
Robot Locally Circumvents h=4 h=2 h=1 h h=2 h=1 E G h=4 h=2 B DH K h=5 h=4 h=3 h=2 s A C F
Robot Locally Circumvents J M N O E I L G B D H K S A C F h = 5 h = 4 h = 3 h = 4 h = 4 h = 3 h = 2 h = 3 h = 3 h = 2 h = 2 h = 1 h = 2 h = 1 h = 1
Robot globally replans h=4 h=2 h=1 h h=2 h=1 h=0 E G h=4 h=3 BDHK h=5 h=4 h=5 s A Rerun Single Source Shortest path from Goal Stop when robot location reached
Robot Globally Replans J M N O E I L G B D H K S A C F h = 3 h = 2 h = 3 h = 5 h = 4 h = 3 h = 4 h = 4 h =5 h = 1 h = 0 h = 2 h = 1 h = 1 • Rerun Single Source Shortest path from Goal. • Stop when robot location ( ) reached
Outline a Path Planning in Partially Known Environments Finding the Shortest Path to the Goal a Alternative Approaches to Path Planning in Partially Known Environments a Continuous Optimal Path Planning 口 Dynamic a* 口 ncrementala
Outline Path Planning in Partially Known Environments. Finding the Shortest Path to the Goal. Alternative Approaches to Path Planning in Partially Known Environments. Continuous Optimal Path Planning Dynamic A* Incremental A*