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