A* Review A* uses both backward costs g and forward estimate h: f(n) = g(n) + h(n) A* tree search is optimal with admissible heuristics (optimistic future cost estimates) Heuristic design is key: relaxed problems can helpCombining UCS and Greedy Uniform-cost orders by path cost, or backward cost g(n) Best-first orders by goal proximity, or forward cost h(n) A* Search orders by the sum: f(n) = g(n) + h(n) S a d b G h=5 h=6 h=2 1 5 1 1 2 h=6 h=0 c h=7 3 e h=1 1UCS vs A* Contours Uniform-cost expanded in all directions A* expands mainly toward the goal, but does hedge its bets to ensure optimality Start Goal Start Goal [Is A* Optimal? A G S 1 3 h = 6 h = 0 5 h = 7 What went wrong? Actual bad goal cost < estimated good goal cost We need estimates to be less than actual costs!A* Graph Search Gone Wrong S A B C G 1 1 1 2 3 h=2 h=1 h=4 h=1 h=0 S (0+2) A (1+4) B (1+1) C (2+1) G (5+0) C (3+1) G (6+0) S A B C G State space graph Search treeConsistency 3 A C G h=4 h=1 1 The story on Consistency: • Definition: cost(A to C) + h(C) ≥ h(A) • Consequence in search tree: Two nodes along a path: NA, NC g(NC) = g(NA) + cost(A to C) g(NC) + h(C) ≥ g(NA) + h(A) • The f value along a path never decreases • Non-decreasing f means you’re optimal to every state (not just
View Full Document