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*)