《认知机器人》（英文版） Incremental Path Planning

Incremental Path Planning Dynamic and Incremental a Prof brian Williams (help from Hsiang shu) 16.412/6.834 Cognitive Robotics February 17th, 2004

Incremental Path Planning Dynamic and Incremental A* Prof. Brian Williams (help from Ihsiang Shu) 16.412/6.834 Cognitive Robotics February 17th, 2004

Outline Review: Optimal path planning in Partially Known Environments a Continuous Optimal Path planning 口 Dynamic a iNcremental A* LRTA*)

Outline „ Review: Optimal Path Planning in Partially Known Environments. „ Continuous Optimal Path Planning …Dynamic A* …Incremental A* (LRTA*)

Zelinsky, 92 Generate global path plan from initial map 2. Repeat until goal reached or failure a EXecute next step in current global path plan a Update map based on sensors a If map changed generate new global path from map

[Zellinsky, 92] 1. Generate global path plan from initial map. 2. Repeat until goal reached or failure: … Execute next step in current global path plan … Update map based on sensors. … If map changed generate new global path from map

Compute Optimal Path JEBs D H oGKF

Compute Optimal Path J M N O E I L G B D H K S A C F

Begin Executing Optimal Path h=4 h=3 h=2 h=1 h=3 h=2 h=1 h=0 E FI G h=4 h=2 h=1 B中D中H→K h=5 h=4 h=2 S"A甲CPF Robot moves along backpointers towards goal a Uses sensors to detect discrepancies along way

Begin Executing Optimal 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 = 1 h = 2 h = 2 h = 1 h = 0 h = 1 „ Robot moves along backpointers towards goal. „ Uses sensors to detect discrepancies along way

Obstacle encountered! h=4 h=3 h=1 h=1 h=3 h=2 h=1 h=0 E L中G h=4 h=2 h=1 B DH→K h=5 h=4 h=2 SA中C→F a At state A, robot discovers edge from d to h is blocked(cost 5,000 units) a Update map and reinvoke planner

Obstacle Encountered! 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 = 1 h = 1 h = 2 h = 1 h = 0 h = 1 „ At state A, robot discovers edge from D to H is blocked (cost 5,000 units). „ Update map and reinvoke planner

Continue path Execution h=4 h=3 h=1 h=1 h=3 h=2 h=1 h=0 E L中G h=4 h=2 h=1 B DH→K h=5 h=4h=3 h=2 SA中C→F As previous path is still optimal a Continue moving robot along back pointers

Continue Path Execution 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 = 1 h = 1 h = 2 h = 1 h = 0 h = 1 „ A’s previous path is still optimal. „ Continue moving robot along back pointers

Second Obstacle, replan! h=4 h=3 h=1 h=1 h=3 h=2 h=1 h=0 E L中G h=4 h=2 h=1 B DH→K h=5 h=4 h=2 SA甲C F a At c robot discovers blocked edges from c to f and h(cost 5,000 units a Update map and reinvoke planner

Second Obstacle, Replan! 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 = 1 h = 1 h = 2 h = 1 h = 0 h = 1 „ At C robot discovers blocked edges from C to F and H (cost 5,000 units). „ Update map and reinvoke planner

Path Execution Achieves goal h=4 h=3 h=1 h=1 MNO h=3 h=2 h=1 h=0 E中1→L中G h=4 h=2 h=1 B DH→K h=5 h=4 h=2 SA分CF Follow back pointers to goal a No further discrepancies detected goal achieved!

Path Execution Achieves Goal h = 5 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 = 2 h = 1 h = 1 h = 2 h = 1 h = 0 h = 1 „ Follow back pointers to goal. „ No further discrepancies detected; goal achieved!

Outline Review: Optimal path planning in Partially Known Environments a Continuous Optimal Path Planning 口 DynamIC A iNcremental A* LRTA*)

Outline „ Review: Optimal Path Planning in Partially Known Environments. „ Continuous Optimal Path Planning …Dynamic A* …Incremental A* (LRTA*)