1Informed SearchMaterial in part from http://www.cs.cmu.edu/~awm/tutorialsChap. 4Uninformed Search Complexity• N = Total number of states• B = Average number of successors (branching factor)• L = Length for start to goal with smallest number of steps• Q = Average size of the priority queue• Lmax = Length of longest path from START to any stateO(Min(N,2BL/2))O(Min(N,2BL/2))Y, If all trans. have same costYBi- Direction. BFSBIBFSO(BL)O(BL)Y, If all trans. have same costYIterative DeepeningIDSO(Min(N,BLmax))O(Min(N,BLmax))NYMemorizing DFSMEMDFSO(BLmax)O(BLmax)NYPath Check DFSPCDFSO(Min(N,BL))O(log(Q)*Min(N,BL))Y, If cost > 0Y, If cost > 0Uniform Cost SearchUCSO(Min(N,BL))O(Min(N,BL))Y, If all trans. have same costYBreadth First SearchBFSSpaceTimeOptimalCompleteAlgorithm2states expanded so farDEFSearch Revisited1.Store a value f(s) at each state s2.Choose the state with lowest f to expand next3.Insert its successorsIf f(.) is chosen carefully, we will eventually find the lowest-cost sequenceSTARTf(A)f(B)f(C)ABCStates ready to be expanded(the “fringe”)STARTABCf(A)f(B)f(C)DEFExample:• UCS (Uniform Cost Search): f(A) = g(A) = total cost of current shortest path from START to A• Store states awaiting expansion in a priority queue for efficient retrieval of minimum f• Optimal Guaranteed to find lowest cost sequence, but……g(A) =10g(A) =53• Problem: No guidance as to how “far” any given state is from the goal• Solution: Design a function h(.) that gives us an estimate of the distance between a state and the goalSTARTABCGOALh(A) = 3h(B) = 6Our best guess is that A is closer to GOAL than B so maybe it is a more promising state to expandh(B) = 10Heuristic Functions• h(.) is a heuristic function for the search problem• h(s) = estimate of the cost of the shortest path from s to GOAL• h(.) cannot be computed solely from the states and transitions in the current problem If we could, we would already know the optimal path!• h(.) is based on external knowledge about the problem informed search• Questions:1. Typical examples of h?2. How to use h?3. What are desirable/necessary properties of h?4Heuristic Functions Example• h(s) = Euclidean distance to GOALXXxXSTARTGOALThe straight-line distance is lower from s than from s’so maybe s has a better chance to be on the best paths’sHeuristic Functions Example • How could we define h(s)?2831647528316475sGOAL5First Attempt: Greedy Best First Search• Simplest use of heuristic function: Always select the node with smallest h(.) for expansion (i.e., f(s) = h(s))Initialize PQInsert START with value h(START) in PQWhile (PQ not empty and no goal state is in PQ)Pop the state s with the minimum value of h from PQFor all s’ in succs(s)If s’ is not already in PQ and has not already been visited Insert s’ in PQ with value h(s’)Problem• What solution do we find in this case?• Greedy search clearly not optimal, even though the heuristic function is non-stupidSTARTABCGOALh = 4 h = 3 h = 2 h = 1 h = 02 1 1 246Trying to Fix the Problem• g(s) is the cost from START to s only• h(s) estimates the cost from s to GOAL• Key insight: g(s) + h(s) estimates the total cost of the cheapest path from START to GOAL going through s• A* algorithmSTARTABCGOALh(A) = 3f(A) = g(A) + h(A) = 13g(A) = 10h(B) = 6f(B) = g(B) + h(B) = 11 g(A) = 5Can A* Fix the Problem?{(START,4)}{(A,5)} (f(A) = h(A) + g(A) = 3 + g(START) + cost(START, A) = 3 + 0 + 2){(B,5) (C,7)} (f(C) = h(C) + g(C) = 1 + g(A) + cost(A, C) = 1 + 2 + 4){(C,5)} (f(C) = h(C) + g(C) = 1 + g(B) + cost(B, C) = 1 + 3 + 1){(GOAL,6)}STARTABCGOALh = 4 h = 3 h = 2 h = 1 h = 02 1 1 247Can A* Fix the Problem?{(START,4)}{(A,5)} (f(A) = h(A) + g(A) = 3 + g(START) + cost(START, A) = 3 + 0 + 2){(B,5) (C,7)} (f(C) = h(C) + g(C) = 1 + g(A) + cost(A, C) = 1 + 2 + 4){(C,5)} (f(C) = h(C) + g(C) = 1 + g(B) + cost(B, C) = 1 + 3 + 1){(GOAL,6)}STARTABCGOALh = 4 h = 3 h = 2 h = 1 h = 02 1 1 24C is placed in the queue with backpointers {A,START}A lower value of f(C) is found with backpointers{B,A,START} • Termination condition• Revisiting states• Algorithm• Optimality• Avoiding revisiting states• Choosing good heuristics• Reducing memory usage8A* Termination Condition• Stop when GOAL is popped from the queue!Queue:{(B,4) (A,8)}{(C,4) (A,8)}{(D,4) (A,8)}{(A,8) (G,10)}SADBCG111171h = 3h = 2h = 1h = 7h = 8A* Termination Condition• Stop when GOAL is popped from the queue!Queue:{(B,4) (A,8)}{(C,4) (A,8)}{(D,4) (A,8)}{(A,8) (G,10)}We have encountered Gbefore we have a chance to visit the branch going through A. The problem is that at each step we use only an estimate of the path cost to the goalSADBCG111171h = 3h = 2h = 1h = 7h = 89Revisiting States1h = 7ACBSTARTDGOAL1117h = 8h = 3h = 8h = 11/2A state that was already in the queue is re-visited.How is its priority updated?Revisiting States1h = 7ACBSTARTDGOAL1117h = 8h = 3h = 2h = 11/2A state that had been already expanded is re-visited.10A* Algorithm(inside loop)Pop state s with lowest f(s) in queueIf s = GOALreturn SUCCESSElse expand s:For all s’ in succs (s): f’ = g(s’) + h(s’) = g(s) + cost(s,s’) + h(s’) If (s’ not seen before ORs’ previously expanded with f(s’) > f’ ORs’ in PQ with with f(s’) > f’)Promote/Insert s’ with new value f’ in PQprevious(s’) sElseIgnore s’ (because it has been visited and its current path cost f(s’) is still the lowest path cost from START to s’)Under what Conditions is A* Optimal?• Problem: h(.) is a poor estimate of path cost to the goal stateSTARTAGOALh = 6h = 7113{(START,6)}{(GOAL,3) (A,8)}Final path: {START, GOAL}with cost = 311Admissible Heuristics• Define h*(s) = the true minimal cost to the goal from s• h is admissible ifh(s) <= h*(s) for all states s• In words: An admissible heuristic never overestimates the cost to the goal. “Optimistic” estimate of cost to goal.A* is guaranteed to find the optimal path if h is admissibleConsistent (Monotonic) Heuristicsh(s) < h(s’) + cost(s,s’)GOALss’Cost(s,s’)h(s’)h(s)12Consistent (Monotonic) Heuristicsh(s) < h(s’) + cost(s,s’)GOALss’Cost(s,s’)h(s’)h(s)Sort of triangular inequality implies that path cost always increases + need to expand node only oncePop state s with lowest f(s) in queueIf s = GOALreturn SUCCESSElse expand s:For all s’ in succs (s): f’ = g(s’) + h(s’) = g(s) +
View Full Document
Unlocking...