《认知机器人》（英文版） Path Planning in Partially-Known Environments

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*