1CS 188: Artificial IntelligenceSpring 2006Lecture 4: A* Search (and Friends)1/26/2006Dan Klein – UC BerkeleyMany slides from either Stuart Russell or Andrew Moore Today A* Search Heuristic Design Local Search2Problem Graphs vs Search TreesSabdpacephfrqqcGaqephfrqqcGaSGdbpqcehafrWe almost always construct both on demand – and we construct as little as possible.Each NODE in in the search tree is an entire PATH in the problem graph.Uniform Cost Problems Remember: explores increasing cost contours The good: UCS is complete and optimal! The bad: Explores options in every “direction” No information about goal locationStartGoal…c ≤ 3c ≤ 2c ≤ 13Best-First SearchSTARTGOALdbpqcehafr299811235344151252h=12h=11h=8h=8h=5h=4h=6h=9h=0h=4h=6h=11Best-First Search A common case: Best-first takes you straight to the (wrong) goal Worst-case: like a badly-guided DFS in the worst case Can explore everything Can get stuck in loops if no cycle checking Like DFS in completeness (finite states w/ cycle checking)…b…b4Combining Best-First and UCS Uniform-cost orders by path cost, or backward cost g(n) Best-first orders by goal proximity, or forward cost h(n) What happens with each ordering? A* orders by the sum: f(n) = g(n) + h(n)S A CB Gh=3 h=2 h=124112h=4 h=0When should A* terminate?SBAG2212h = 1h = 2h = 0h = 3 Should we stop when we enqueue a goal? No: only stop when we dequeue a goal5Is A* Optimal?AGS13h = 6h = 05h = 7 What went wrong? Actual bad goal cost > estimated good goal cost We need estimates to be less than actual costs!Admissible Heuristics A heuristic is admissible (optimistic) if:where is the true cost to a nearest goal E.g. Euclidean distance on a map problem Coming up with admissible heuristics is most of what’s involved in using A* in practice.6Optimality of A*: Blocking Proof: What can go wrong? We’d have to have to pop a suboptimal goal off the fringe queue Imagine a suboptimal goal G’ is on the queue Consider any unexpanded (fringe) node n on a shortest path to optimal G n will be popped before G…This proof assumed tree search! Where?Optimality of A*: Contours Consider what A* does: Expands nodes in increasing total f value (f-contours) Optimal goals have lower f value, so get expanded firstHolds for graph search as well, but we made a different assumption. What?7Consistency Wait, how do we know we expand in increasing f value? Couldn’t we pop some node n, and find its child n’ to have higher f value? YES: What do we need to do to fix this? Consistency: Real cost always exceeds reduction in heuristicABG3h = 0h = 10g = 10h = 8UCS vs A* Contours Uniform-cost expanded in all directions A* expands mainly toward the goal, but does hedge its bets to ensure optimalityStartGoalStartGoal8Properties of A*UCS = BFS*A*SpaceTimeOptimalCompleteAlgorithmYYO(sbs)* O(bs)**Assume all costs are 1 Assume one goal, non-goals have h(n) = g*(G) - aYYO(aba) O(ba)…bs tiers…ba tiersUniform-Cost A*Admissible Heuristics Most of the work is in coming up with admissible heuristics Good news: usually admissible heuristics are also consistent More good news: inadmissible heuristics are often quite effective (especially when you have no choice)98-Puzzle I Number of tiles misplaced? Why is it admissible? h(start) = This is a relaxed-problem heuristic8TILESIDAverage nodes expanded when optimal path has length…22739133.6 x 1066,300112…12 steps…8 steps…4 steps8-Puzzle II What if we had an easier 8-puzzle where any tile could slide any one direction at any time? Total Manhattan distance Why admissible? h(start) =3 + 1 + 2 + …= 18MAN-HATTANTILESAverage nodes expanded when optimal path has length…7325122273913…12 steps…8 steps…4 steps108-Puzzle III How about using the actual cost as a heuristic? Would it be admissible? Would we save on nodes? What’s wrong with it? With A*, trade-off between quality of estimate and work per node!Trivial Heuristics, Dominance Dominance: Heuristics form a semi-lattice: Max of admissible heuristics is admissible Trivial heuristics Bottom of lattice is the zero heuristic (what does this give us?) Top of lattice is the exact heuristic11Course Scheduling From the university’s perspective: Set of courses {c1, c2, … cn} Set of room / times {r1, r2, … rn} Each pairing (ck, rm) has a cost wkm What’s the best assignment of courses to rooms? States: list of pairings Actions: add a legal pairing Costs: cost of the new pairing Admissible heuristics? (Who can think of a cs170 answer to this problem?)Other A* Applications Machine translation Statistical parsing Speech recognition Robot motion planning (next class) Routing problems (see homework!) Planning problems (see homework!) …12Summary: A* A* uses both backward costs and (estimates of) forward costs A* is optimal with admissible heuristics Heuristic design is key: often use relaxed problemsLocal Search Methods Queue-based algorithms keep fallback options (backtracking) Local search: improve what you have until you can’t make it better Generally much more efficient (but incomplete)13Types of Problems Planning problems: We want a path to a solution (examples?) Usually want an optimal path Incremental formulations Identification problems: We actually just want to know what the goal is (examples?) Usually want an optimal goal Complete-state formulations Iterative improvement algorithmsExample: N-Queens Start wherever, move queens to reduce conflicts Almost always solves large n-queens nearly instantly How is this different from best-first search?14Hill Climbing Simple, general idea: Start wherever Always choose the best neighbor If no neighbors have better scores than current, quit Why can this be a terrible idea? Complete? Optimal? What’s good about it?Hill Climbing Diagram Random restarts? Random sideways steps?15Simulated Annealing Idea: Escape local maxima by allowing downhill moves But make them rarer as time goes onSimulated Annealing Theoretical guarantee: Stationary distribution: If T decreased slowly enough,will converge to optimal state! Is this an interesting guarantee? Sounds like magic, but reality is
View Full Document
Unlocking...