Informed (Heuristic) Search Strategies PDF

1  George Polya defines heuristic as "the study of the methods and rules of discovery and invention".  In state space search, heuristics are formalized as rules for choosing those branches in a state space that are most likely to lead to an acceptable problem solution. I. AI problem s...

1  George Polya defines heuristic as "the study of the methods and rules of discovery and invention".  In state space search, heuristics are formalized as rules for choosing those branches in a state space that are most likely to lead to an acceptable problem solution. I. AI problem solvers employ heuristic in two basic situations:  A problem may not have an exact solution because of inherent ambiguities in the problem statement or available data.  Medical diagnosis is an example of this. A given set of symptoms may have several possible causes; doctors use heuristics to choose the most likely diagnosis and formulate a plan of treatment.  Vision is another example of inexact problem. Visual scenes are often ambiguous, allowing multiple interpretations of the connectedness, extent, and orientation of objects.  Visions systems often use heuristics to select the most likely of several possible interpretations of a scene. II. A problem may have an exact solution, but the computational cost of finding it may be prohibitive. In many problems (such as chess), state space growth is combinatorial explosive, with the number of possible states increasing exponentially or factorially with the depth of the search. In these cases, exhaustive, brute-force search techniques such as depth first or breadth first search may fail to find a solution within any practical length of time. Heuristic attack this complexity by guiding the search a long the most "promising" path through the space.  Unfortunately, like all rules of discovery and invention, heuristic are fallible.  A heuristic is only an informed guess of the next step to be taken in solving a problem.  It is often based on experience or intuition. Because heuristic use limited information, such as knowledge of the present situation or descriptions of states currently on the OPEN list, they are RARLEY able to predict the exact behavior of the state space farther along in the search.  A heuristic can lead a search algorithm to s suboptimal solution or fail to find any solution at all.  Heuristic and the design of algorithms to implement heuristic search have long been a core concern of artificial intelligence.  Game playing and theorem proving are two of the oldest applications in AI; both of these require heuristic to prune spaces of possible solutions.  It is not feasible to examine every inference that can be made in a mathematics domain or every possible move that can be made on a chessboard.  Heuristic search is often the only practical answer.  The "rule of thumb" that a human expert uses to solve problem efficiently are largely heuristic in nature. Fig 4.12 The start state, first moves, and goal state for an example- 8 puzzle. AI Classnotes #5, John Shieh, 2012 8 16 Fig 4.14 Three heuristics applied to states in the 8-puzzle. AI Classnotes #5, John Shieh, 2012 9 Fig 4.15 The heuristic f applied to states in the 8-puzzle. AI Classnotes #5, John Shieh, 2012 10 18 Fig 4.16 State space generated in heuristic search of the 8-puzzle graph. AI Classnotes #5, John Shieh, 2012 11 Fig 4.17 Open and closed as they appear after the 3rd iteration of heuristic search AI Classnotes #5, John Shieh, 2012 12  Comparison of state space searched using heuristic search with space searched by breadth-first search. The proportion of the graph searched heuristically is shaded. The optimal search selection is in bold. Heuristic used is f(n) = g(n) + h(n) where h(n) is tiles out of place. AI Classnotes #5, John Shieh, 2012 13  Varieties of Heuristic Search:-  Generate and test  Hill Climbing  Best First Search  Generate-and-test search algorithm is a very simple algorithm that guarantees to find a solution if done systematically and there exists a solution  Generate a possible solution.  Test to see if this is the expected solution.  If the solution has been found quit else go to step 1.  Potential solutions that need to be generated vary depending on the kinds of problems. For some problems the possible solutions may be particular points in the problem space and for some problems, paths from the start state.  Generate-and-test, like depth-first search, requires that complete solutions be generated for testing. In its most systematic form, it is only an exhaustive search of the problem space. Solutions can also be generated randomly but solution is not guaranteed. This approach is what is known as British Museum algorithm: finding an object in the British Museum by wandering randomly.  While generating complete solutions and generating random solutions are the two extremes there exists another approach that lies in between. The approach is that the search process proceeds systematically but some paths that unlikely to lead the solution are not considered. This evaluation is performed by a heuristic function  It is a depth first search procedure since complete solutions must be generated before they can be tested.  In its most systematic form, it is simply an exhaustive search of the problem space.  Operate by generating solutions randomly.  Also called as British Museum algorithm  The simplest way to implement heuristic search is through a procedure called hill- climbing. Hill climbing strategies expand the current state of the search and evaluate its children. The best child is selected for further expansions; neither its siblings nor its parent are retained. Hill climbing is named for the strategy that might be used by an eager, but blind mountain climber: Go uphill along the steepest possible path until you can go no farther up. Because it keeps no history, the algorithm cannot recover from failure of its strategy.  A major problem of hill climbing strategies is their tendency to become stuck at local maxima. If they reach a state that has a better evaluation than any of its children, the algorithm halts. If this state is not a goal, but just a local maximum, the algorithm may fail to find the best solution. AI: Chapter 4: Informed Search and Exploration January 31, 2006 24 AI: Chapter 4: Informed Search and Exploration January 31, 2006 25 AI: Chapter 4: Informed Search and Exploration January 31, 2006 26  Algorithm: BFS  Start with OPEN containing just the initial state  Until a goal is found or there are no nodes left on OPEN do:  Pick the best node on OPEN  Generate its successors  For each successor do:  If it has not been generated before, evaluate it, add it to OPEN, and record its parent.  If it has been generated before, change the parent if this new path is better than the previous one. In that case, update the cost of getting to this node and to any successors that this node may already have.  Combines the advantages of both DFS and BFS into a single method.  DFS is good because it allows a solution to be found without all competing branches having to be expanded.  BFS is good because it does not get branches on dead end paths.  One way of combining the tow is to follow a single path at a time, but switch paths whenever some competing path looks more promising than the current one does.  At each step of the BFS search process, we select the most promising of the nodes we have generated so far.  This is done by applying an appropriate heuristic function to each of them.  We then expand the chosen node by using the rules to generate its successors  Similar to Steepest ascent hill climbing with two exceptions:  In hill climbing, one move is selected, and all the others are rejected, never to be reconsidered. This produces the straight-line behavior that is characteristic of hill climbing.  In BFS, one move is selected, but the others are kept around so that they can be revisited later if the selected path becomes less promising. Further, the best available state is selected in the BFS, even if that state has a value that is lower than the value of the state that was just explored. This contrasts with hill climbing, which will stop if there are no successor states with better values than the current state.  Informed Search – a strategy that uses problem-specific knowledge beyond the definition of the problem itself  Best-First Search – an algorithm in which a node is selected for expansion based on an evaluation function f(n)  Traditionally the node with the lowest evaluation function is selected  Not an accurate name…expanding the best node first would be a straight march to the goal.  Choose the node that appears to be the best 30  There is a whole family of Best-First Search algorithms with different evaluation functions  Each has a heuristic function h(n)  h(n) = estimated cost of the cheapest path from node n to a goal node  Example: in route planning the estimate of the cost of the cheapest path might be the straight-line distance between two cities AI: Chapter 4: Informed Search and Exploration January 31, 2006 31  Greedy Best-First search tries to expand the node that is closest to the goal assuming it will lead to a solution quickly  f(n) = h(n)  aka “Greedy Search”  Implementation  expand the “most desirable” node into the fringe queue  sort the queue in decreasing order of desirability  Example: consider the straight-line distance heuristic h SLD  Expand the node that appears to be closest to the goal AI: Chapter 4: Informed Search and Exploration January 31, 2006 32 AI: Chapter 4: Informed Search and Exploration January 31, 2006 33  h (In(Arad)) = 366 SLD  Notice that the values of h SLD cannot be computed from the problem itself  It takes some experience to know that h SLD is correlated with actual road distances  Therefore, a useful heuristic AI: Chapter 4: Informed Search and Exploration January 31, 2006 34 AI: Chapter 4: Informed Search and Exploration January 31, 2006 35 AI: Chapter 4: Informed Search and Exploration January 31, 2006 36 AI: Chapter 4: Informed Search and Exploration January 31, 2006 37  g(n) = cost from the initial state to the current state n  h(n) = estimated cost of the cheapest path from node n to a goal node  f(n) = evaluation function to select a node for expansion (usually the lowest cost node) AI: Chapter 4: Informed Search and Exploration January 31, 2006 38  A* (A star) is the most widely known form of Best-First search  It evaluates nodes by combining g(n) and h(n)  f(n) = g(n) + h(n)  where  g(n) = cost so far to reach n  h(n) = estimated cost to goal from n  f(n) = estimated total cost of path through n AI: Chapter 4: Informed Search and Exploration January 31, 2006 39 AI: Chapter 4: Informed Search and Exploration January 31, 2006 40 AI: Chapter 4: Informed Search and Exploration January 31, 2006 41 AI: Chapter 4: Informed Search and Exploration January 31, 2006 42 AI: Chapter 4: Informed Search and Exploration January 31, 2006 43 AI: Chapter 4: Informed Search and Exploration January 31, 2006 44 AI: Chapter 4: Informed Search and Exploration January 31, 2006 45  Complete  Yes, unless there are infinitely many nodes  Time: Exponential  The better the heuristic, the better the time  Best case h is perfect, O(d)  Worst case h = 0, O(bd) same as BFS  Space  Keeps all nodes in memory and save in case of repetition  This is O(bd) or worse  A* usually runs out of space before it runs out of time  Optimal  Yes AI: Chapter 4: Informed Search and Exploration January 31, 2006  When h(n) = actual cost to goal  Only nodes in the correct path are expanded  Optimal solution is found  When h(n) < actual cost to goal  Additional nodes are expanded  Optimal solution is found  When h(n) > actual cost to goal  Optimal solution can be overlooked AI: Chapter 4: Informed Search and Exploration January 31, 2006 47  A* is optimal if it uses an admissible heuristic  h(n) h1(n) for all n (both admissible) then h2(n) dominates h1(n) and is better for the search  Take a look at figure 4.8! AI: Chapter 4: Informed Search and Exploration January 31, 2006 55  A Relaxed Problem is a problem with fewer restrictions on the actions  The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem  Key point: The optimal solution of a relaxed problem is no greater than the optimal solution of the real problem AI: Chapter 4: Informed Search and Exploration January 31, 2006 56  Example: 8-puzzle  Consider only getting tiles 1, 2, 3, and 4 into place  If the rules are relaxed such that a tile can move anywhere then h1(n) gives the shortest solution  If the rules are relaxed such that a tile can move to any adjacent square then h2(n) gives the shortest solution AI: Chapter 4: Informed Search and Exploration January 31, 2006 57  h(n) is an estimate cost of the solution beginning at state n  How can an agent construct such a function?  Experience!  Have the agent solve many instances of the problem and store the actual cost of h(n) at some state n  Learn from the features of a state that are relevant to the solution, rather than the state itself  Generate “many” states with a given feature and determine the average distance  Combine the information from multiple features  h(n) = c(1)*x1(n) + c(2)*x2(n) + … where x1, x2, … are features AI: Chapter 4: Informed Search and Exploration January 31, 2006 58