What is Continuous Optimal Path Planning? Supports search as a repetitive online process a Exploits similarities between a series of searches to solve much faster than solving each search starting from scratch a Reuses the identical parts of the previous search tree, while updating differences a Solutions guaranteed to be optimal On the first search behaves like traditional algorithms a d behaves exactly like dijkstras a Incremental a* a* behaves exactly like a*
What is Continuous Optimal Path Planning? Supports search as a repetitive online process. Exploits similarities between a series of searches to solve much faster than solving each search starting from scratch. Reuses the identical parts of the previous search tree, while updating differences. Solutions guaranteed to be optimal. On the first search, behaves like traditional algorithms. D* behaves exactly like Dijkstra’s. Incremental A* A* behaves exactly like A*
Dynamic a*(aka D*) [Stenz, 94 Generate global path plan from initial map 2. Repeat until goal reached, or failure o Execute next step of current global path plan a Update map based on sensor information o Incrementally update global path plan from map changes 1 to 3 orders of magnitude speedup relative to a non-incremental path planner
Dynamic A* (aka D*) [Stenz, 94] 1. Generate global path plan from initial map. 2. Repeat until Goal reached, or failure. Execute next step of current global path plan. Update map based on sensor information. Incrementally update global path plan from map changes. Î 1 to 3 orders of magnitude speedup relative to a non-incremental path planner
Map and Path Concepts c,Y Cost to move from y to x c, Yis undefined if move disallowed Neighbors(入×): Any Y such that cX,Y or c(Y, X)is defined ■O(G,X) Optimal path cost to goal from x h( G, x) Estimate of optimal path cost to goal from X a b(=r: backpointer from x to Y Y is the first state on path from x to g
Map and Path Concepts c(X,Y) : Cost to move from Y to X. c(X,Y) is undefined if move disallowed. Neighbors(X) : Any Y such that c(X,Y) or c(Y,X) is defined. o(G,X) : Optimal path cost to Goal from X. h(G,X) : Estimate of optimal path cost to goal from X. b(X) = Y : backpointer from X to Y. Y is the first state on path from X to G
D* Search Concepts ■ OPEN list States with estimates to be propagated to other states a States on list tagged OPEN a Sorted by key function k ■ State tag t) D NEW has no estimate h 口OPEN estimate needs to be propagated D CLOSED: estimate propagated
D* Search Concepts OPEN list : States with estimates to be propagated to other states. States on list tagged OPEN Sorted by key function k. State tag t(X) : NEW : has no estimate h. OPEN : estimate needs to be propagated. CLOSED : estimate propagated
D*Fundamental Search Concepts a k(G, x): key function minimum of a h(G, x before modification, and a all values assumed by h(G, x) since X was placed on the oPEN list a Lowered state: k(G,X)=current h(G, X) a Propagate decrease to descendants and other nodes a Raised state: k(G, X)< current h(G, X) a Propagate increase to dscendants and other nodes a Try to find alternate shorter paths
D* Fundamental Search Concepts k(G,X) : key function minimum of h(G,X) before modification, and all values assumed by h(G,X) since X was placed on the OPEN list. Lowered state : k(G,X) = current h(G,X), Propagate decrease to descendants and other nodes. Raised state : k(G,X) < current h(G,X), Propagate increase to dscendants and other nodes. Try to find alternate shorter paths