slide 1 Informed Search Xiaojin Zhu [email protected] Computer Sciences Department University of Wisconsin, Madison [Based on slides from Andrew Moore http://www.cs.cmu.edu/~awm/tutorials ]slide 2 Main messages • A*. Always be optimistic.slide 3 Uninformed vs. informed search • Uninformed search (BFS, uniform-cost, DFS, ID etc.)  Knows the actual path cost g(s) from start to a node s in the fringe, but that’s it. • Informed search  also has a heuristic h(s) of the cost from s to goal. (‘h’= heuristic, non-negative)  Can be much faster than uninformed search. start s goal g(s) start s goal g(s) h(s) slide 4 Recall: Uniform-cost search • Uniform-cost search: uninformed search when edge costs are not the same. • Complete (will find a goal). Optimal (will find the least-cost goal). • Always expand the node with the least g(s)  Use a priority queue: • Push in states with their first-half-cost g(s) • Pop out the state with the least g(s) first. • Now we have an estimate of the second-half-cost h(s), how to use it? start s goal g(s) h(s) slide 5 First attempt: Best-first greedy search • Idea 1: use h(s) instead of g(s) • Always expand the node with the least h(s)  Use a priority queue: • Push in states with their second-half-cost h(s) • Pop out the state with the least h(s) first. • Known as “best first greedy” search • How’s this idea?slide 6 Best-first greedy search looking stupid • It will follow the path ACG (why?) • Obviously not optimal B A G C h=3 h=2 h=1 h=0 1 1 1 999slide 7 Second attempt: A search • Idea 2: use g(s)+h(s) • Always expand the node with the least g(s)+h(s)  Use a priority queue: • Push in states with their first-half-cost g(s)+h(s) • Pop out the state with the least g(s)+h(s) first. • Known as “A” search • How’s this idea? • Works for this example B A G C h=3 h=2 h=1 h=0 1 1 1 999slide 8 A search still not quite right • A search is not optimal. B A G C h=3 h=1000 h=1 h=0 1 1 1 999slide 9 Third attempt: A* search • Same as A search, but the heuristic function h() has to satisfy h(s)  h*(s), where h*(s) is the true cost from node s to the goal. • Such heuristic function h() is called admissible. • An admissible heuristic never over-estimates • A search with admissible h() is called A* search. It is always optimisticslide 10 Admissible heuristic functions h • 8-puzzle example • Which of the following are admissible heuristics? 8 4 7 3 6 2 5 1 8 7 6 5 4 3 2 1 Example State Goal State •h(n)=number of tiles in wrong position •h(n)=0 •h(n)=1 •h(n)=sum of Manhattan distance between each tile and its goal locationslide 11 Admissible heuristic functions h • 8-puzzle example • Which of the following are admissible heuristics? 8 4 7 3 6 2 5 1 8 7 6 5 4 3 2 1 Example State Goal State •h(n)=number of tiles in wrong position YES •h(n)=0 YES, uninformed uniform cost search •h(n)=1 NO, goal state •h(n)=sum of Manhattan distance between each tile and its goal location YESslide 12 Admissible heuristic functions h • In general, which of the following are admissible heuristics? h*(n) is the true optimal cost from n to goal. •h(n)=h*(n) •h(n)=max(2,h*(n)) •h(n)=min(2,h*(n)) •h(n)=h*(n)-2 •h(n)=sqrt(h*(n))slide 13 Admissible heuristic functions h • In general, which of the following are admissible heuristics? h*(n) is the true optimal cost from n to goal. •h(n)=h*(n) YES •h(n)=max(2,h*(n)) NO •h(n)=min(2,h*(n)) YES •h(n)=h*(n)-2 NO, possibly negative •h(n)=sqrt(h*(n)) NO if h*(n)<1slide 14 Heuristics for Admissible heuristics • How to construct heuristic functions? • Often by relaxing the constraints 8 4 7 3 6 2 5 1 8 7 6 5 4 3 2 1 Example State Goal State •h(n)=number of tiles in wrong position Allow tiles to fly to their destination in one step •h(n)=sum of Manhattan distance between each tile and its goal location Allow tiles to move on top of other tilesslide 15 “my heuristic is better than yours” • A heuristic function h2 dominates h1 if for all s h1(s)  h2(s)  h*(s) • We prefer heuristic functions as close to h* as possible, but not over h*. But • Good heuristic function might need complex computation • Time may be better spent, if we use a faster, simpler heuristic function and expand more nodesslide 16 Q1: When should A* stop? • Idea: as soon as it generates the goal state? • h() is admissible • The goal G will be generated as path ABG, with cost 1000. B A G C 999 1 1 1 h=2 h=1 h=0 h=0slide 17 Q1: The correct A* stop rule • A* should terminate only when a goal is popped from the priority queue • If you have exceedingly good memory, you’ll remember this is the same rule for uniform cost search on cyclic graphs. • Indeed A* with h()0 is exactly uniform cost search! B A G C 999 1 1 1 h=2 h=1 h=0 h=0slide 18 Q2: A* revisiting expanded states • One more complication: A* can revisit an expanded state, and discover a shorter path • Can you find the state in question? B A D C 999 1 1 1 h=1 h=900 h=1 h=1 G h=0 2slide 19 Q2: A* revisiting expanded states B A D C 999 1 1 1 h=1 h=900 h=1 h=1 G h=0 2 • One more complication: A* can revisit an expanded state, and discover a shorter path • Can you find the state in question? We shall put D back into the priority queue, with the smaller g+hslide 20 Q3: What if A* revisits a state in the PQ? • We’ve seen this before, with uniform cost search • ‘promote’ D in the queue with the smaller cost B A D C 999 1 2 1 h=3 h=2 h=1 h=2 G h=0 999 (Note the numbers are different) slide 21 The A* algorithm 1. Put the start node S on the priority queue, called OPEN 2. If OPEN is empty, exit with failure 3. Remove from OPEN and place on CLOSED a node n for which f(n) is minimum 4. If n is a goal node, exit (trace back pointers from n to S) 5. Expand n, generating all its successors and attach to them pointers back to n. For each successor n' of n 1. If n' is not already on OPEN or CLOSED estimate h(n'),g(n')=g(n)+ c(n,n'), f(n')=g(n')+h(n'), and place it on OPEN. 2. If n' is already on OPEN or CLOSED, then check if g(n') is lower for the new version of n'. If so, then: 1.Redirect