Heuristic Search

• information about a particular problem can be used to help to reduce the search time.

• ways of using heuristic information:

  1. deciding which node to expand next, instead of doing it in strictly breadth-first or depth-first order.

  2. in the course of expanding a node, decide which successor or successors to generate, instead of blindly generate all possible successors at one time.

  3. deciding certain nodes should be discarded, or pruned from the search tree.

Principle of Dynamic Programming

• the best way through a particular, intermediate place X, is the best way to X from the starting place, followed by the best way from X to the goal.

Ordered state-space search

• The promise of a node can be defined in various ways, e.g. estimate its distance from a goal node using an evaluation function f*.

• Example: Heuristics that can be used in 8-puzzle
  3 kinds of heuristics that can be used in 8-puzzle problem.
  final state is:

1	2	3
8		4
7	6	5

• Note that heuristic does not necessarily gives the best solution.

• local choice (i.e. choice within descendants only) - Hill climbing
  global choice (i.e. choice among all other possible nodes.) - best first search

  
  

• Example:
  Use distance from the start node as the evaluation measure.

• Same as depth-first search, except that after each expansion, the expanded list is sorted before inserted in front of the OPEN list.

• Global choice:

Algorithm:

1. Put the start node S on a list, called OPEN, of unexpanded nodes. Calculate f*(S)

2. if OPEN is empty, exit with failure.

3. Select from OPEN a node i at which f* is minimum. If several nodes qualify, choose arbitrarily.

4. Remove node i from OPEN and place it on a list called CLOSED of expanded nodes.

5. If i is a goal node, exit with success.

6. Expand node i, creating nodes for all its successors. For every successor node j or i:

   1. calculate f*(j)

   2. if j is neither in list OPEN nor in CLOSED, add it to OPEN, with its f* value.

   3. If j was already on either OPEN or CLOSED, compare the f* value just calculated for j with the previous value. If new value is lower, then

      • substitute it for the old value

      • if node j was on the CLOSED list, moved it back to OPEN

7. goto 2.

• step 6c is required for a general graph

• Breadth-first search, uniform cost search and depth-first search are all special cases of ordered search, by setting suitable f* function.

  • Breadth-first search, f*=depth of nodes

  • Uniform cost search, f*=cost of path from start node

  • depth-first search, f*=-(depth of node)

Problem with Hill-Climbing

• foothill problem 0 existence of secondary peak (search is trapped at local maximum)

• plateau problem 0 a mostly flat area, cannot climb

• ridge problem 0 problem with direction of search, need more directions.

Beam Search

• beam search only expand the best w nodes at each level, the other nodes are ignored.

Beam Search for w=2

Choices of Search Strategies

• depth-first search is good when unproductive partial paths are never too long.

• Breadth-first search is good when the branching factor is never too large.

• Non-deterministic search is good when you are not sure whether depth-first search or breadth-first search would be better.

• Hill climbing is good when there is a natural measure of distance from each place to the goal and a good path is likely to be among the partial paths that appear to be good at each choice point.

• Beam search is good when there is a natural measure of goal distance and a good path is likely to be among the partial paths that appear to be good at all levels.

• Best-first search is good when there is a natural measure of goal distance and a good partial path may look like a bad option before more promising partial paths are played out.

• Search family:

Branch and Bound and A*

• Problem: finding a minimal-cost path joining the start node and a goal node in a state-space graph.

• The branch and bound algorithms uses
  f*(n) = path length from s to n
  and the ordered search algorithm.

Expand A

D has least cost expand D

E has least cost
expand E

.

.

.

• Branch and bound is a special case of the A* algorithm where
  f*(n) = g*(n) + h*(n)

• g* estimates the min. cost of a path from the start node to node n}
  h* estimates the min. cost from node n to a goal node
  f* estimates the min. cost of a solution path

• the corresponding actual value is denoted as f, g, h.

• Since at the time when node n is considered, g is already known, i.e. g*=g 0 perfect estimate

• the function h* is the carrier of heuristic information and can be defined in any way appropriate to problem domain.

• However, there are condition where h* has to satisfy if an optimal solution is to be obtained 0 the admissibility condition:

  h* should be non-negative, and should never overestimate the cost (i.e. h* should be an underestimate),
  i.e. h*(n) <= h(n), "n.

• Admissibility: if h* satisfies the admissibility condition and if all arc costs are positive and can be bounded from below by a positive number, then A* is guaranteed to find a solution path of minimal cost if any solution path exists.
  [Proof can be found in Gelperin D, "On the Optimality of A*", Artificial Intelligence, Vol. 8, pp. 69-76, 1977.]

• the more nearly h* approximates h, the better the algorithm performs. In particular,

  if h*=h, A* will never expand a path off the solution path

  if h*=0, resulted in branch and bound/uniform cost search

• If algorithm A₁ and A₂ uses h₁* and h₂*, then A₁ is said to be more informed than A₂ if
  h₁*(n) > h₂*(n) "n.
  and A₁ will never expands a node that is not also expanded by A₂.

• Problem: with a poor but admissible heuristic function (in the extreme case when h*=0), A* reduces to branch and bound.

Minimizing Search Effort

• use a modified evaluation function:
  f* = (1-w)g* + wh*, wÎ [0,1]
  giving relative performance to g and h

• Some results:

  • assuming a simplified state space whose graph is an infinite m-ary tree, and assume the error in h* is bounded by e>0, (maybe over- or underestimates), then

    max. no. of nodes expanded by f*=h* > max. no. of nodes expanded by f*=g*+h*

  • This difference is exponential in e (worst case)

  • empirical result with a 15-puzzle, 0.5 < w < 1 gives best result.

• some researchers argues that the function should also take explicit account of the probability of the node being on the solution path.

• Other variations:

  • dynamic weighting
    f*(n) = g*(n) + w(n)h*(n)
    where w(n) varies with the depth of node n.

  • bandwidth search

    if we can find f* such that it never overestimate by e, and underestimate by d, then, all node m can be dropped if there is a node q such that
    f*(m) - (e+d) > f*(q)

• heuristic search of and/or graph will not be discussed.