Notes on Search Algorithms

Important issues about Search Algorithms

1. how to write search algorithms. In particular we will examine:
   • the data structure to keep unexplored nodes. We use a queue (often called a list in many AI books) called OPEN.
   • expansion of a node (or generation of its successors). All the successors of a node can be generated at once (method most commonly used) or they could be generated one at a time either in a systematic way or in a random way. The number of successors is called the branching factor.
   • strategies for selecting which node to expand next. Different algorithms result from different choices (e.g. depth-first when successor nodes are added at the beginning of the queue, breadth-first when successor nodes are added at the end of the queue, etc),
   • test for goal. We will assume the existence of a predicate that applied to a state will return true or false.
   • bookkeeping (keeping track of visited nodes, keeping track of path to goal, etc). Keeping track of visited nodes is usually done by keeping them in a queue (or, better a hash-table) called CLOSED. This prevents getting trapped into loops or repeating work but results in a large space complexity. This is (most often) necessary when optimal solutions are sought, but can be (mostly) avoided in other cases.
     Keeping track of the path followed is not always necessary (when the problem is to find a goal state and knowing how to get there is not important).
2. properties of search algorithms and the solutions they find:
   • Termination: the computation is guaranteed to terminate, no matter how large the search space is.
   • Completeness: an algorithm is complete if it terminates with a solution when one exists.
   • Admissibility: an algorithm is admissible if it is guaranteed to return an optimal solution whenever a solution exists.
   • Space complexity and Time complexity: how the size of the memory and the time needed to run the algorithm grows depending on branching factor, depth of solution, number of nodes, etc.
   Let's briefly examine the properties of some commonly used uninformed search algorithms.

   Depth-First Search	Termination: guaranteed for a finite space if repeated nodes are checked. Guaranteed when a depth bound is used. Not guaranteed otherwise. Completeness: not guaranteed. Guaranteed only if the search space is finite (exhaustive search) and repeated nodes are checked. Admissibility: not guaranteed.
   Breadth-First Search	Termination: guaranteed for finite space. Guaranteed when a solution exists. Completeness: guaranteed. Admissibility: the algorithm will always find the shortest path (it might not be the optimal path, if arcs have different costs).
   Depth-First Search Iterative-Deepening	Termination: guaranteed for finite space. Guaranteed when a solution exists. Completeness: guaranteed. Admissibility: the algorithm will always find the shortest path (it might not be the optimal path, if arcs have different costs).

3. classes of search algorithms. We can classify search algorithms along multiple dimensions. Here are some of the most common:
   • uninformed (depth-first, breadth-first, uniform cost, depth-limited, iterative deepening) versus informed (greedy, A*, IDA*, SMA*)
   • local (greedy, hill-climbing) versus global (uniform cost, A*, etc)
   • systematic (depth-first, A*, etc) versus stochastic (simulated annealing, genetic algorithms)

Description of an Uninformed Search Algorithm:
Depth-First Search with depth bound

1. Put the start node on OPEN.
2. until OPEN is empty or a goal node has been reached
   2.1 remove the topmost node from OPEN and put it on
       CLOSED.  Call this node n.
   2.2 if the depth of n is less than the depth bound 
       then
       2.2.1 expand n, generating all successors (if any).  
       2.2.2 if any of these successors is already on 
             the traversal path discard it
       2.2.3 if any of these successors is a goal node, 
             exit 
       2.2.4 put the successors on top of OPEN and 
             provide for each a pointer back to n
       else
       2.2.5 clean up CLOSED.
3. If a goal node is found, 
   then exit with the solution obtained by tracing back 
        through its pointers 
   else announce failure.

• Nodes that have been expanded (i.e. their successors have been generated) are called closed, nodes that were generated and are awaiting expansion are called open. Two queues, CLOSED and OPEN keep track of these two sets of nodes.
• The depth of a node in a graph is defined recursively as 1 + depth of its shallowest parent. The start node has 0 depth.
• If the depth bound is less than the solution depth the algorithm terminates without finding a solution. If the depth bound is greater the algorithm might find a non optimal solution. This can be remedied by completing the search to the depth of the last solution found and then returning the best solution.
• To save memory CLOSED needs to be cleaned up by keeping in it only the nodes on the current traversal path.

Description of an Informed Search Algorithm
Best-First Search

1. Put the start node S on OPEN.
2. until OPEN is empty or a goal node has been reached
   2.1 remove from OPEN a node at which f is minimum (break 
       ties arbitrarily) and put it on CLOSED.  Call this 
       node n.
   2.2 expand n, generating all successors (if any).
   2.3 if any of the successors of n is a goal node, exit.
   2.4 for each successor n' of n
       2.4.1 calculate f(n')
       2.4.2 if n' was neither on OPEN nor CLOSED, add it to 
             OPEN.  Attach the cost f(n') to it.
       2.4.3 if n' was already on OPEN or on CLOSED compare
             the new value f(n') with the previously assigned
             value f(n').  If the old value is lower discard 
             the newly generated node.  If the new value is 
             lower, substitute the new node for the old node.  
             If the old node was on CLOSED move it back to 
             OPEN.
3. If a goal node is found, 
   then exit with the solution obtained by tracing back 
        through pointers
   else announce failure.

• Step 2.3 requires checking if any of the children of the node just expanded is a goal node. This allows terminating as soon as a goal is found, but the solution returned might have a larger value of f than the optimal solution. To guarantee an optimal solution we need to use a f function that understimates the cost (as doen in A*) and to test for goal after a node has been selected for expansion.
• The computation required to do the tests is step 2.4.3 can be substantial. We could eliminate this step, at the cost of having to maintain duplicate descriptions of identical nodes.
• If a lower value has been found for a node n' that had already been visited (step 2.4.3) and the old node was on CLOSED, instead of moving it back to OPEN we could leave it on CLOSED, redirect the pointer to its parent node (so it will point to the new parent on the shorter path), and recompute the f values of its descendants. This requires keeping track of descendants of nodes and not only of their parent (so it makes the program more complex to write), but it saves reexpading nodes that have already been expanded (so it can save time if expansion is an expensive process).
• In general there are no constraints on the function f(n). Best first always selects for expansion the node with the smallest f value, so f values must be smaller for better nodes. Also, best-first discards multiple paths leading to the same node and keeps the path with the smallest f value.
• Properties of Best-First

  Completeness:

  guaranteed on finite search spaces

  Admissibility:

  not guaranteed

  Time Complexity:

  depends on the accuracy of the heuristic function. See more later under A*.

  Space Complexity:

  O(B to the power of d) where B = branching factor, and d = solution depth

A*

1. Put the start node S on OPEN.  Attach to s the cost 
   g(s) = 0.  Initialize CLOSED to the empty queue.  
2. until OPEN is empty or a goal node has been reached
   2.1 remove from OPEN a node at which f is minimum 
       (break ties arbitrarily) and put it on CLOSED.  
       Call this node n.
   2.2 if n is a goal node, exit.
   2.3 expand n, generating all successors (if any).
   2.4 for each successor n' of n
       2.4.1 calculate f(n')= g(n') + h(n')
                            = g(n) + c(n,n') + h(n').
       2.4.2 if n' was neither on OPEN nor CLOSED, add 
             it to OPEN.  Attach the cost f(n') to it.
       2.4.3 if n' was already on OPEN or on CLOSED 
             direct its pointers along the path yielding 
             the lowest g(n') and keep the lowest f(n').
       2.4.4 if n' required pointer adjustment and was 
             found on CLOSED, move it back to OPEN.
3. If a goal node is found, 
   then exit with the solution obtained by tracing back 
        through its pointers
   else announce failure.

• A* is a special case of best-first search where:
  • The cost f(n) of a node is computed as f(n) = g(n) + h(n), where
    g(n) is the cost of the current path from s to n, and
    h(n) is an estimate of the cost of the path from n to goal
  • The g cost of a node n is computed recursively by adding the g cost of its parent node m to the cost of the arc from the parent m to the node n g(n) = g(m) + c(m,n).
    We assume arc costs to be positive. The start node has a cost g(s) = 0.
  • h(n) is an underestimate of the cost of the optimal path from n to goal. If we call h*(n) the cost of the optimal path forall n h(n) < = h*(n). This implies that a goal node has a cost h(goal) = 0
• The check for the goal node (step 2.2) must be done after the node has been selected for expansion to guarentee an optimal solution.
• The redirection of the parent pointer is done using only the g value of the node (not the f value). This guarantees that the path used to any node is the best path.
• When the heuristic used is monotone, A* never reopens nodes from CLOSED. This means that whenever a node is put into CLOSED, A* has already found the optimal path to it.
• If forall n h(n) = 0 the algorithm A* is the same as Branch&Bound (or Uniform Cost).
  If forall n h(n) = 0 and forall n, n' c(n,n')=1 the algorithm A* is the same as Breadth-First Search.
• Properties of A*

  Completeness:

  guaranteed even on infinite graphs provided that the branching factor is finite and that there is some positive constant delta such that every operator cost at least delta.

  Admissibility:

  guaranteed given an admissible heuristics (i.e. h(n) is an underestimate of the cost of the optimal path from n to the goal for every node)

  Time Complexity:

  depends on the accuracy of the heuristic function. If the heuristic function is exact A* runs in linear time, if the heuristic function is useless, the time complexity is exponential (as for uniform cost).

  Space Complexity:

  O(B to the power of d)

Iterative-Deepening A* (IDA*)

Time Complexity:

depends on the accuracy of the heuristic function. If the heuristic function is exact IDA* runs in linear time, if the heuristic function is useless, the time complexity is exponential (as for uniform cost).

Space Complexity:

O(d)

Heuristic functions

• A heuristic function h(n) that underestimates the cost of getting from n to goal is said to be admissible.
• A heuristic funtion is said to be monotone if for all pairs of nodes n and n' (with n' being a successor of n) the following inequality is satisfied h(n) < = c (n,n') + h(n').

Examples of heuristic functions for the 8-puzzle

initial state           goal state
2   8   1		1   2   3
4      	6		8       4
7   5   3		7   6   5

• h1 (n) = number of misplaced tiles
• h2(n) = P(n) + 2 * R(n) where P(n) is the sum of the Manhattan distances that each tile is from home, and R(n) is the number of direct tile reversals (when two adjacent tiles must be exchanged to be in the order of the goal).
• h3(n) = P(n) + 3 * S(n) where P(n) is the sum of the Manhattan distances that each tile is from home, and S(n) is a sequence score obtained by counting 1 for the central tile (if not blank) and counting 2 for each non-blank tile on the board perimeter that is not followed (in clockwise order) by its proper successor. To compute S(n) the blank tile does not count. This heuristic is not admissible.