Informed search

Informed search

a.     Best-First branch-and-bound

b.     Hill Climbing / Gradient Descent

c.      A* Search

d.     A* Searching And-Or graphs

Informed search uses some kind of evaluation function to tell us how far each expanded state is from a goal state, and/or some kind of heuristic function to help us decide which state is likely to be the best one to expand next.

The hard part is to come up with good evaluation and/or heuristic functions. Often there is a natural evaluation function, such as distance in miles or number objects in the wrong position.

Sometimes we can learn heuristic functions by analyzing what has worked well in similar previous searches.

The simplest idea, known as greedy best first search, is to expand the node that is already closest to the goal, as that is most likely to lead quickly to a solution. This is like DFS in that it attempts to follow a single route to the goal, only attempting to try a different route when it reaches a dead end. As with DFS, it is not complete, not optimal, and has time and complexity of O(b^m). However, with good heuristics, the time complexity can be reduced substantially.

Branch and Bound: An enhancement of backtracking. Applicable to optimization problems.

For each node (partial solution) of a state-space tree, computes a bound on the value of the objective function for all descendants of the node (extensions of the partial solution).

Uses the bound for:

       Ruling out certain nodes as “nonpromising” to prune the tree – if a node’s bound is not better than the best solution seen so far.

       Guiding the search through state-space.

The search path at the current node in a state-space tree can be terminated for any one of the following three reasons:

       The value of the node’s bound is not better than the value of the best solution seen so far.

       The node represents no feasible solutions because the constraints of the problem are already violated.

       The subset of feasible solutions represented by the node consists of a single point and hence we compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better.

Best-First branch-and-bound:

       A variation of backtracking.

       Among all the nonterminated leaves, called as the live nodes, in the current tree, generate all the children of the most promising node, instead of generation a single child of the last promising node as it is done in backtracking.

       Consider the node with the best bound as the most promising node.

A* Search: Suppose that, for each node n in a search tree, an evaluation function f(n) is defined as the sum of the cost g(n) to reach that node from the start state, plus an estimated cost h(n) to get from that state to the goal state. That f(n) is then the estimated cost of the cheapest solution through n.

A* search, which is the most popular form of best-first search, repeatedly picks the node with the lowest f(n) to expand next. It turns out that if the heuristic function h(n) satisfies certain conditions, then this strategy is both complete and optimal.

In particular, if h(n) is an admissible heuristic, i.e. is always optimistic and never overestimates the cost to reach the goal, then A* is optimal.

The classic example is finding the route by road between two cities given the straight line distances from each road intersection to the goal city. In this case, the nodes are the intersections, and we can simply use the straight line distances as h(n).

Hill Climbing / Gradient Descent: The basic idea of hill climbing is simple: at each current state we select a transition, evaluate the resulting state, and if the resulting state is an improvement we move there, otherwise we try a new transition from where we are.

We repeat this until we reach a goal state, or have no more transitions to try. The transitions explored can be selected at random, or according to some problem specific heuristics.

In some cases, it is possible to define evaluation functions such that we can compute the gradients with respect to the possible transitions, and thus compute which transition direction to take to produce the best improvement in the evaluation function.

Following the evaluation gradients in this way is known as gradient descent.

In neural networks, for example, we can define the total error of the output activations as a function of the connection weights, and compute the gradients of how the error changes as we change the weights. By changing the weights in small steps against

those gradients, we systematically minimize the network’s output errors.

Searching And-Or graphs

The DFS and BFS strategies for OR trees and graphs can be adapted for And-Or trees The main difference lies in the way termination conditions are determined, since all goals following an And node must be realized, whereas a single goal node following

an Or node will do

A more general optimal strategy is AO* (O for ordered) algorithm

As in the case of the A* algorithm, we use the open list to hold nodes that have been generated but not expanded and the closed list to hold nodes that have been expanded

The algorithm is a variation of the original given by Nilsson

It requires that nodes traversed in the tree be labeled as solved or unsolved in the solution process to account for And node solutions which require solutions to all successors nodes.

A solution is found when the start node is labeled as solved

 The AO* algorithm

       Step 1: Place the start node s on open

       Step 2: Using the search tree constructed thus far, compute the most promising solution tree T₀

       Step 3:Select a node n that is both on open and a part of T_0. Remove n from open and place it on closed

       Step 4: If n ia terminal goal node, label n as solved. If the solution of n results

in any of n’s ancestors being solved, label all the ancestors as solved. If the start node s is solved, exit with success where T₀ is the solution tree. Remove from open all nodes with a solved ancestor

       Step 5: If n is not a solvable node, label n as unsolvable. If the start node is labeled as unsolvable, exit with failure. If any of n’s ancestors become unsolvable because n is, label them unsolvable as well. Remove from open all nodes with unsolvable ancestors

       Otherwise, expand node n generating all of its successors. For each such successor node that contains more than one subproblem, generate their successors to give individual subproblems. Attach to each newly generated node a back pointer to its predecessor. Compute the cost estimate h* for each newly generated node and place all such nodes thst do not yet have descendents on open. Next recomputed the values oh h* at n and each ancestors of n

       Step 7: Return to step 2

It can be shown that AO* will always find a minimum-cost solution tree if one exists, provided only that h*(n) ≤ h(n), and all arc costs are positive. Like A*, the efficiency depends on how closely h* approximates h