MODULE-3

INFORMED SEARCH STRATEGIES

​

Greedy best first search

A*search

Heuristic Functions

Introduction

• An informed search strategy one that uses problem-specific knowledge beyond the definition of the problem itself can find solutions more efficiently than can an uninformed strategy.
• The general approach we consider is called best-first search. Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f(n).
• The evaluation function is construed as a cost estimate, so the node with the lowest evaluation is expanded first. The implementation of best-first graph search is identical to that for uniform-cost search, except for the use of f instead of g to order the priority queue. The choice of f determines the search strategy. Most best-first algorithms include as a component of f a heuristic function, denoted h(n):

Cont…

• h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
• (Notice that h(n) takes a node as input, but, unlike g(n), it depends only on the state at that node.)
• For example, in Romania, one might estimate the cost of the cheapest path from Arad to Bucharest via the straight-line distance from Arad to Bucharest.
• Heuristic functions are the most common form in which additional knowledge of the problem is imparted to the search algorithm.
• For now, we consider them to be arbitrary, nonnegative, problem-specific functions, with one constraint: if n is a goal node, then h(n)=0. The remainder of this section covers two ways to use heuristic information to guide search.

Greedy best-first search

• Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n) = h(n).
• Let us see how this works for route-finding problems in Romania; we use the straight line distance heuristic, which we will call hSLD.
• If the goal is Bucharest, we need to know the straight-line distances to Bucharest, which are shown in Figure 3.22.
• For example, hSLD (In(Arad)) = 366. Notice that the values of hSLD cannot be computed from the problem description itself.
• Moreover, it takes a certain amount of experience to know that hSLD is correlated with actual road distances and is, therefore, a useful heuristic.

Cont…

Cont…

• Figure 3.23 shows the progress of a greedy best-first search using hSLD to find a path from Arad to Bucharest.
• The first node to be expanded from Arad will be Sibiu because it is closer to Bucharest than either Zerind or Timisoara.
• The next node to be expanded will be Fagaras because it is closest. Fagaras in turn generates Bucharest, which is the goal.
• For this particular problem, greedy best-first search using hSLD finds a solution without ever expanding a node that is not on the solution path; hence, its search cost is minimal.
• It is not optimal, however: the path via Sibiu and Fagaras to Bucharest is 32 kilometers longer than the path through Rimnicu Vilcea and Pitesti.
• This shows why the algorithm is called “greedy” at each step it tries to get as close to the goal as it can.

Cont…

• Greedy best-first tree search is also incomplete even in a finite state space, much like depth-first search. Consider the problem of getting from Iasi to Fagaras.
• The heuristic suggests that Neamt be expanded first because it is closest to Fagaras, but it is a dead end. The solution is to go first to Vaslui a step that is actually farther from the goal according to the heuristic and then to continue to Urziceni, Bucharest, and Fagaras.
• The algorithm will never find this solution, however, because expanding Neamt puts Iasi back into the frontier, Iasi is closer to Fagaras than Vaslui is, and so Iasi will be expanded again, leading to an infinite loop.
• The worst-case time and space complexity for the tree version is O(bm), where m is the maximum depth of the search space. With a good heuristic function, however, the complexity can be reduced substantially. The amount of the reduction depends on the particular problem and on the quality of the heuristic.

A* search: Minimizing the total estimated solution cost

• The most widely known form of best-first search is called A∗ Search (pronounced “A-star search”).
• It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:
• f(n) = g(n) + h(n) .
• Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have

f(n) = estimated cost of the cheapest solution through n .

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n).

It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, A∗ search is both complete and optimal. The algorithm is identical to UNIFORM-COST-SEARCH except that A∗ uses g + h instead of g.

Conditions for optimality: Admissibility and consistency

• The first condition we require for optimality is that h(n) be an admissible heuristic. An admissible heuristic is one that never overestimates the cost to reach the goal.
• Because g(n) is the actual cost to reach n along the current path, and

f(n) = g(n) + h(n),

• we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n.
• Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.
• An obvious example of an admissible heuristic is the straight-line distance hSLD that we used in getting to Bucharest.
• Straight-line distance is admissible because the shortest path between any two points is a straight line, so the straight line cannot be an overestimate.

Cont…

Optimality of A*

Cont…

Cont…

Memory-bounded heuristic search

• The simplest way to reduce memory requirements for A∗ is to adapt the idea of iterative deepening to the heuristic search context, resulting in the iterative-deepening A∗ (IDA∗) algorithm.
• The main difference between IDA∗ and standard iterative deepening is that the cutoff used is the f-cost (g +h) rather than the depth; at each iteration, the cutoff value is the smallest f-cost of any node that exceeded the cutoff on the previous iteration.
• IDA∗ is practical for many problems with unit step costs and avoids the substantial overhead associated with keeping a sorted queue of nodes.
• This section briefly examines two other memory-bounded algorithms, called RBFS (Recursive best-first search)and MA∗(Memory Based A*).

Recursive best-first search (RBFS)

• Recursive best-first search (RBFS) is a simple recursive algorithm that attempts to mimic the operation of standard best-first search, but using only linear space.
• The algorithm is shown in Figure 3.26. Its structure is similar to that of a recursive depth-first search, but rather than continuing indefinitely down the current path, it uses the f limit variable to keep track of the f-value of the best alternative path available from any ancestor of the current node.
• If the current node exceeds this limit, the recursion unwinds back to the alternative path. As the recursion unwinds, RBFS replaces the f-value of each node along the path with a backed-up value—the best f-value of its children.
• In this way, RBFS remembers the f-value of the best leaf in the forgotten subtree and can therefore decide whether it’s worth reexpanding the subtree at some later time. Figure 3.27 shows how RBFS reaches Bucharest.

Cont…

Cont…

Cont…

Learning to search better

• We have presented several fixed strategies—breadth-first, greedy best-first, and so on that have been designed by computer scientists. Could an agent learn how to search better?
• The answer is yes, and the method rests on an important concept called the metalevel state space.
• Each state in a metalevel state space captures the internal (computational) state of a program that is searching in an object-level state space such as Romania.
• For example, the internal state of the A∗ algorithm consists of the current search tree. Each action in the metalevel state space is a computation step that alters the internal state;
• For example, each computation step in A∗ expands a leaf node and adds its successors to the tree.
• Thus, Figure 3.24, which shows a sequence of larger and larger search trees, can be seen as depicting a path in the metalevel state space where each state on the path is an object-level search tree.

Cont…

• Now, the path in Figure 3.24 has five steps, including one step, the expansion of Fagaras, that is not especially helpful.
• For harder problems, there will be many such missteps, and a metalevel learning algorithm can learn from these experiences to avoid exploring unpromising subtrees.
• The goal of learning is to minimize the total cost of problem solving, trading off computational expense and path cost.

HEURISTIC FUNCTIONS

• The 8-puzzle was one of the earliest heuristic search problems. As mentioned in Section 3.2, the object of the puzzle is to slide the tiles horizontally or vertically into the empty space until the configuration matches the goal configuration (Figure 3.28).
• The average solution cost for a randomly generated 8-puzzle instance is about 22 steps. The branching factor is about 3.
• When the empty tile is in the middle, four moves are possible; when it is in a corner, two; and when it is along an edge, three.
• This means that an exhaustive tree search to depth 22 would look at about 322 ≈ 3.1 × 1010 states.
• A graph search would cut this down by a factor of about 170,000 because only 9!/2 = 181, 440 distinct states are reachable.

Cont…

Cont…

• This is a manageable number, but the corresponding number for the 15-puzzle is roughly , so the next order of business is to find a good heuristic function.
• If we want to find the shortest solutions by using A∗, we need a heuristic function that never overestimates the number of steps to the goal.
• There is a long history of such heuristics for the 15-puzzle; here are two commonly used candidates:

The effect of heuristic accuracy on performance

Cont…

• To test the heuristic functions h1 and h2, we generated 1200 random problems with solution lengths from 2 to 24 (100 for each even number) and solved them with iterative deepening search and with A∗ tree search using both h1 and h2.
• Figure 3.29 gives the average number of nodes generated by each strategy and the effective branching factor.
• The results suggest that h2 is better than h1, and is far better than using iterative deepening search.
• Even for small problems with d = 12, A∗ with h2 is 50,000 times more efficient than uninformed iterative deepening search.

Cont…

Generating admissible heuristics from relaxed problems

• We have seen that both h1 (misplaced tiles) and h2 (Manhattan distance) are fairly good heuristics for the 8-puzzle and that h2 is better.
• How might one have come up with h2? Is it possible for a computer to invent such a heuristic mechanically?
• h1 and h2 are estimates of the remaining path length for the 8-puzzle, but they are also perfectly accurate path lengths for simplified versions of the puzzle.
• If the rules of the puzzle were changed so that a tile could move anywhere instead of just to the adjacent empty square, then h1 would give the exact number of steps in the shortest solution.
• Similarly, if a tile could move one square in any direction, even onto an occupied square, then h2 would give the exact number of steps in the shortest solution. A problem with fewer restrictions on the actions is called a relaxed problem.

Cont…

• Because the relaxed problem adds edges to the state space, any optimal solution in the original problem is, by definition, also a solution in the relaxed problem;
• But the relaxed problem may have better solutions if the added edges provide short cuts.
• Hence, the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.
• Furthermore, because the derived heuristic is an exact cost for the relaxed problem, it must obey the triangle inequality and is therefore consistent.
• If a problem definition is written down in a formal language, it is possible to construct relaxed problems automatically.

Cont…

• For example, if the 8-puzzle actions are described as
• A tile can move from square A to square B
• if A is horizontally or vertically adjacent to B and B is blank,
• we can generate three relaxed problems by removing one or both of the conditions:
• (a) A tile can move from square A to square B if A is adjacent to B.
• (b) A tile can move from square A to square B if B is blank.
• (c) A tile can move from square A to square B.
• From (a), we can derive h2 (Manhattan distance). The reasoning is that h2 would be the proper score if we moved each tile in turn to its destination.

​

Generating admissible heuristics from subproblems: Pattern databases

• Admissible heuristics can also be derived from the solution cost of a subproblem of a given problem. For example, Figure 3.30 shows a subproblem of the 8-puzzle instance in Figure 3.28.
• The subproblem involves getting tiles 1, 2, 3, 4 into their correct positions. Clearly, the cost of the optimal solution of this subproblem is a lower bound on the cost of the complete problem. It turns out to be more accurate than Manhattan distance in some cases.
• The idea behind pattern databases is to store these exact solution costs for every possible subproblem instance—in our example, every possible configuration of the four tiles and the blank. (The locations of the other four tiles are irrelevant for the purposes of solving the subproblem, but moves of those tiles do count toward the cost.)
• Then we compute an admissible heuristic hDB for each complete state encountered during a search simply by looking up the corresponding subproblem configuration in the database.

Cont…

• The database itself is constructed by searching back13 from the goal and recording the cost of each new pattern encountered; the expense of this search is amortized over many subsequent problem instances.
• The choice of 1-2-3-4 is fairly arbitrary; we could also construct databases for 5-6-7-8, for 2-4-6-8, and so on.
• Each database yields an admissible heuristic, and these heuristics can be combined, as explained earlier, by taking the maximum value.
• A combined heuristic of this kind is much more accurate than the Manhattan distance; the number of nodes generated when solving random 15-puzzles can be reduced by a factor of 1000.

​

Cont…

Learning heuristics from experience