Search Methods |

- Definitions
- General Paradigms
- Brute-Force / Blind Search Methods
- Heuristic Search
- Performance of Search Algorithms
- AND/OR Graphs
- Game Trees / Adversarial Search
- Performance of Game Searching Algorithms
- Real-Time Algorithms
- Constraint-Satisfaction Problems
- Other Search Methods
- Notable Search Programs
- Sources

**heuristic**- Heuristics (the term was coined by Polya) are rules of thumb that may solve a given problem, but do not guarantee a solution. Put another way, heuristics are knowledge about the domain that helps guide search and reasoning in the domain.
**admissible search algorithm**- A search algorithm that always terminates in an optimal path from the initial node to a goal node if one exists. A* is admissible when the heuristic function never overestimates.
**problem space**- The environment in which the search takes place; it consists of a set of states of the problem and a set of operators that change the states.
**problem instance**- A problem space, together with an initial state and a goal state.
The problem is to find a sequence of operators that transform the
initial state into the goal state; such a sequence is called a
*solution*to the problem. **branching factor**- The average number of children of a given node, or the average number of new operators applicable to a given state.
**weak methods**- General search methods that use no domain knowledge.
**heuristic evaluation function**- A function that estimates the likelihood of a given state leading to a goal state. Heuristic functions can be used to guide search with efficient guesses about the "goodness" of a state.
**more informed function**- A function h
_{1}is more informed than a function h_{2}if for all non-goal nodes n, h_{2}(n) > h_{1}(n). **monotonic cost function**- A cost function that never decreases along a path away from the
initial state. Any nonmonotonic cost function can be converted to a
monotonic one by setting the value of a node equal to the maximum
value of a path to the node. A heuristic function is monotonic if it
is locally
*consistent*-- that is, it obeys the triangle inqeuality of cost. **dynamic programming principle**- The best way
*through*a place is the best way*to*it followed by the best way*from*it. **effective****branching factor**- A measure of the average number of branches explored by an
algorithm from a typical node of the search space. If
*I(d)*is the average number of nodes generated during a search of depth*d*, then*lim*is the effective branching factor._{d->inf}(I(d))^(1/d) **constraint satisfaction problem**- A problem in which there is a set of variables each of which has a
range of possible values, and for which there are constraints on the
values. The goal is to find values for all the variables that satisfy
the constraints.
More specifically, a set of

*n*variables X1, ... Xn, each having a value in a corresponding domain R1, ..., Rn. A constraint Ci(Xi, ..., Xj) is a subset of the Cartesian product Ri1 x ... x Rij that specifies which variable values are compatible with one another. **constraint graph**- CSPs can be represented as
*constraint graphs*in which nodes represent variables and arcs connect pairs of variables that are constrained. **ordered****constraint graph**- A constraint graph where the nodes are linearly ordered to reflect the sequence of variable assignments set by the search algorithm.
**arc consistency**- A directed arc between two nodes is arc consistent exactly when, for any value of the variable corresponding to the first node, there is a value for the second that satisfies the problem constraints. Arc consistency is a directional concept.
**path consistency**- A path through a sequence of nodes is consistent exactly when there is a set of variable assignments such that there is simultaneous arc consistency between each pair of nodes in order in the sequence.
**d-arc-consistent**- Given an order
*d*on a constraint graph R, R is*d-arc-consistent*if all edges directed along*d*are arc consistent. *k*-consistency- If, when some
*k - 1*variables are given values satisfying their constraints, there exists a value for any remaining variable that satisfies all constraints among the*k*variables. **futility**- If the estimated cost of a solution becomes greater than FUTILITY, abandon the search.
**credit assignment problem**- [Minsky, 1963] The problem of deciding which of a series of actions is actually responsible for a particular outcome.
**backjumping**- [Gaschnig, 1979] A backtracking scheme in CSPs. When a dead-end is hit, backjumping marks each value of the dead-end variable with the age of the oldest ancestor forbidding that value. It then jumps back to the youngest among these ancestors. Picking the youngest ancestor guarantees completeness.
**OPEN and CLOSED lists**- In most search techniques that explore graphs, it is necessary to record two kinds of nodes: the nodes we have seen but not explored, and the nodes we have seen and explored. The OPEN list is the former, and the CLOSED list is the latter. Generally, search proceeds by examining each node on the OPEN list, performing some expansion operation that adds its children to the OPEN list, and moving the node to the CLOSED list.
**Manhattan distance**- The sum of the vertical and horizontal offsets between two places in a grid. (So called because, in Manhattan, you can't fly directly from one place to another; you have to travel in an L-shape instead.) A standard heuristic in the Eight Puzzle.
**classes of search**- [from "Tweak" article] There are eight: no backtracking, explicitly represented alternatives, dependency-directed modification, chronological backtracking, dependency-directed backtracking, heuristic search, metaplanning, and protection (once a goal is achieved it stays achieved).

A generator makes hypotheses and a tester tests them. Good
generators have three properties:

**completeness**-- They eventually produce all possible solutions.**non-redundant**-- They never propose a solution more than once.-
**informed**-- They use information to limit the possibilities and hence the number of solutions proposed.

DENDRAL uses the generate-and-test approach.

This approach tries to minimize differences between the
current state and the goal. It chooses a difference and then applies
an operator to remove it. Sometimes the operator cannot be applied
directly; in this case a *subgoal* is established to reach a
state where it can. This kind of backward chaining is called
*operator subgoaling*. Differences can be prioritized.

In GPS [Newell, Shaw, and Simon, 1957], each rule had preconditions
and a list of effects. A data structure called a *difference
table* indexed the rules by the differences they could reduce.

Simultaneously search from the initial state toward the goal and from the goal state back toward the initial state, until a common state is found along the frontier. Requires an explicit goal state and invertible operators (or backward chaining). Note that if a heuristic function is inaccurate, the two searches might miss one another.

[Slate and Atkin, 1977] Invented for CHESS 4.5. Search the entire tree to a depth of one, evaluate the results, then repeat to depth of two, and so on. Previous iterations can be used to guide search (use the best result to date as the starting point of the next level's search in e.g., minimax).

**direction in which to search**-- search forward through the state space, or backward from the goal**matching**-- production systems need efficient ways to match preconditions in their rules**knowledge representation****tree vs. graph**

Also called *weak search methods*, most general methods are
brute-force because they do not need domain knowledge; however, they
are less efficient as a result.

All brute-force search algorithms must take O(b^{d}) time,
and use O(d) space.

Generate nodes in the tree in order of their distance from the root. That is, all nodes at distance one, followed by all nodes at distance two, etc. The first path to a goal will be of shortest length. The corresponding data structure for storing nodes during search is a queue.

Iterative deepening is an *anytime algorithm* in the sense
that it can be stopped at any time and will produce the best move
found so far.

[Ginsberg] Rather than increasing the depth of the search, iterative broadening increases its breadth at every iteration. Thus on the first iteration only the first child of every node is expanded; on the next iteration both the first and second, and so forth.

The intuition is that goal nodes are not usually randomly distributed in a tree, and so it is wasteful to explore an entire portion of a tree at once.

Look everywhere until you find the solution. That is, BFS or DFS
throughout the entire graph. Necessary on a finite graph where cost
is an arbitrary value associated with arc lengths.

Heuristic searches use some function that estimates the cost from the current state to the goal, presuming that such a function is efficient. (Generally speaking, heuristic search incorporates domain knowledge to improve efficiency over blind search.)

Looking at all of our operators, we see which one, when applied, leads to a state closest to the goal. We then apply that operator. The process repeats until no operator can improve our current situation (which may be a relative maximum, such as in the TSP).

Problems with hill climbing: local maxima (we've climbed to the top of the hill, and missed the mountain), plateau (everything around is about as good as where we are), ridges (we're on a ridge leading up, but we can't directly apply an operator to improve our situation, so we have to apply more than one operator to get there).

Solutions include: backtracking, making big jumps (to handle plateaus or poor local maxima), applying multiple rules before testing (helps with ridges).

Hill climbing is best suited to problems where the heuristic gradually improves the closer it gets to the solution; it works poorly where there are sharp drop-offs. It assumes that local improvement will lead to global improvement.

Hill climbing in which you generate all successors of the current state and choose the best one. These are identical as far as many texts are concerned.

Generally, in search we want to find the move that results in the lowest cost (or highest, depending). Branch and bound techniques rely on the idea that we can partition our choices into sets using some domain knowledge, and ignore a set when we can determine that the optimal element cannot be in it. In this way we can avoid examining most elements of most sets. This can be done if we know that a higher bound on set X is lower than a lower bound on set Y (in which case Y can be pruned).

*Example: Travelling Salesman Problem.* We decompose our set
of choices into a set of sets, in each one of which we've taken a
different route out of the current city. We continue to decompose
until we have complete paths in the graph. If while we're decomposing
the sets, we find two paths that lead to the same node, we can
eliminate the more expensive one.

Best-first B&B is a variant in which we can give a lower bound on a set of possible solutions. In every cycle, we branch on the class with the least lower bound. When a singleton is selected we can stop.

Depth-first B&B selects the most recently generated set; it produces DFS behavior but saves memory.

Some types of branch-and-bound algorithms: A^{*},
AO^{*}, alpha-beta, SSS^{*}, B^{*}.

Expand the node that has the best evaluation according to the heuristic function. An OPEN list contains states that haven't been visited; a CLOSED list contains those that have, to prevent loops. This approach doesn't necessarily find the shortest path.

(When the heuristic is just the cost function *g*, this is blind
search. When it's just *h'*, the estimated cost to the goal,
this is steepest ascent (I think -- POD). When it's *g + h'*, this is
A^{*}.

Best-first search where the list of nodes under consideration is
limited to the best *n*. "Beam" is meant to imply the beam of
a flashlight wandering around the search space.

[Nilsson] A kind of best-first search where the cost function
*f(n) = g(n) + h'(n)*, the actual cost of the path so far
(*g(n)*), plus the estimated cost of the path from the current
node to the goal (*h'(n)*).

A^{*} will always find an optimal path to a goal if the
heuristic function is *admissible*; that is, if it never
overestimates the distance to the goal. A^{*} is optimal
among heuristic searches in the sense that it will expand the fewest
number of nodes, up to tie-breaking. If the heuristic function has
constant absolute error (just when will this ever happen? -- POD) the
number of nodes expanded is linear in the solution depth.

Graceful decay of admissibility: if *h'* rarely
overestimates *h* by more than *d*, then the algorithm
will rarely find a solution whose cost is more than *d* than
the cost of the optimal solution.

A version of iterative deepening that keeps track of the
A^{*} heuristic evaluation function. As soon as the cost of
exploring a path exceeds some threshold, that branch is cut off and
search backtracks to the most recently generated node. The cost
threshold starts with the heuristic estimate of the initial state and
in each successive iteration increases to the minimum value that
exceeded the previous threshold.

IDA^{*} is optimal if the heuristic is admissible. It is
also faster and easier to implement than A^{*}, because it is
a DFS that does not need to maintain an OPEN list.

A variant of A^{*} that changes the heuristic evaluation
function when it can be improved. This can happen when the heursitic
value at a node is less than all descendents minus the length to each
of them (so we can increase the length). It can also occur when all
descendents have a better cost evaluation *f* than their
parent, in which case the *h'* value is increased so that their
*f* value equals the parent.

B' can prove that it will not expand the same node more than
O(n^{2}) times, while A^{*} may expand it an
exponential number of times, though this is only relevant if the
heuristic function is non-monotonic.

The goal is to find a minimal energy state. The search descends
except occasionally when, with low probability, it moves uphill
instead. The probability of moving uphill decreases as the
*temperature* of the system decreases, so such moves are much
more likely earlier than later.

Problems include: choosing an initial temperature, choosing the
*annealing schedule* (the rate at which the system cools).

An *agenda* is a list of tasks a system could perform. Each
task has a list of justifications why it is proposed and a rating
representing the overall weight of evidence suggesting it would be a
useful task. The idea is that we should pay attention when several
paths recommend the same action.

Agendas are good for implementing monotonic production systems, and
bad for nonmonotonic ones.

Name | Time Complexity | Space Complexity | Optimal? | Comments |
---|---|---|---|---|

BFS | O(b^{d}) |
O(b^{d}) |
maybe | optimal only when the optimal path is the shortest |

DFS | O(b^{d}) |
O(d) | no | - |

DFID | O(b^{d}) |
O(d) | yes | asymptotically optimal in both time and space among brute-force tree-searching algorithms |

Bi-directional | O(b^{d/2}) |
O(b^{d/2}) |
yes | assumes comparisons for common states can be done in constant time |

British Museum | O(b^{d}) |
O(b^{d}) |
yes | - |

Name | Time Complexity | Space Complexity | Optimal? | Comments |
---|---|---|---|---|

Hill Climbing | N/A | O(1) | no | needs mechanism for escaping from local minima |

Steepest Ascent | N/A | O(1) | no | needs mechanism for escaping from local minima |

Beam Search | N/A | O(1) | no | amount of space depends on size of OPEN list (size of beam) |

A^{*} |
O(2^{N}) |
O(b^{d}) |
yes | optimal if h'(n) never overestimates; a time bound of
O(b^{d}) is possible only for monotonic estimation functions
(N the number of nodes) |

IDA^{*} |
O(2^{N}) |
O(d) | yes | as above; asymptotically optimal in terms of time and space over all heuristic search algorithms with monotonic estimation functions over tree search |

B' | O(N^{2}) |
O(b^{d}) |
yes | - |

Simulated Annealing | unbounded | O(1) | yes | will find optimal solution if cooling is slow enough and as time goes to infinity |

One or two comments on complexity. First, it's important to note
in the above tables that in the case of BFS, the actual space
complexity is O(*b ^{d+1}*), because in the worst case
all of the nodes at the level below the goal node will be added to the
queue before the goal node is found.

A helpful general formula for doing more detailed analysis than asymptotic is this:

In particular, this is the actual number of nodes explored in
BFS through level *d*. In the case of iterative deepening this
would a summation of this formula for *i = 1* to *i = d*.

In AND/OR graphs, nodes typically represent complete subproblems; the root node is the original problem to be solved, and the leaves are solved problems. Edges represent problem reduction operators, which decompose a problem into subproblems. If only one of the subproblems needs to be solved, the node is an OR node. If all of its subproblems must be solved in order to solve it, it is an AND node.

A solution to an AND/OR graph is a subgraph that contains the root node, an edge from every OR node, and all the branches from every AND node, with only goal states as terminal nodes.

Such graphs are most suitable for problems for which tree structures are the natural representation for the solution, as opposed to a simple path.

*Example: symbolic integration.* The OR links represent
the integrand (find some way to integrate the expression), while the
AND links represent individual summands within the integrand, all of
which must eventually be integrated. The solution required is a
partially-ordered sequence of actions.

The search algorithm **AO ^{*}** estimates the cost of
the solution graphs rooted at various nodes and is guaranteed to find
a cheapest solution if the estimates are optimistic.

Rather than using OPEN and CLOSED lists, AO^{*} uses a
graph structure containing the nodes expanded so far. Each node
points up to its immediate predecessors and down to its immediate
successors. The nodes contain partial solutions, the heuristic
estimate *h'* of the cost of a path to a set of solution nodes.
(It is not possible to store *g* since there may be many paths
*to* the node.)

AO^{*} is a two-step process. The first step is a top-down
algorithm that marks the current, best partial solution. A
nonterminal leaf node of this solution is chosen and expanded. The
second step is a bottom-up, cost-revising, connector-marking step.
The connectors that give the best estimate for a node are marked
"best." Selecting the next node to expand isn't easy; one possibility
is to select the node most likely to change the estimate of the best
partial path solution graph.

Games are a useful domain in which to study machine intelligence because they have clearly defined rules and goals, and highly-structured environments in which success or failure is clearly defined. Although Samuel argued that games were a good subject of study because they require limited knowledge, many standard testbeds (such as chess) are highly stylized in places (such as the opening and the endgame) and can beneficially use databases of stored patterns.

Two-player turn-taking games can be represented as AND/OR trees. The root node is the initial situation, and the edges represent legal moves, alternating at each level between the player and the opponent. Leaf nodes are final positions that are wins, losses, or draws. From the perspective of the player, his moves emanate from OR nodes, since only one must be successful to achieve a win; meanwhile, his opponent's nodes are AND nodes, since the player must find a winning move for each response. The task in a two-player game is to choose a sequence of moves that forces a path that leads to a winning state.

*Solving* a game tree means labeling each leaf node as a
win, loss, or possibly draw. Labeling can be done recursively
beginning with the leaf nodes (since their values can be determined
externally) and backing up toward the root. This is usually done by a
depth-first algorithm that traverses the tree from left to right, but
skips all nodes that cannot provide useful information (e.g., as soon
as one successor of a node is a win, the node can be labeled a win).
In most game trees, the tree is too deep, so moves are determined
heuristically based upon a limited lookahead.

Minimax is a depth-first, depth-limited search procedure, and is
the prevaling strategy for searching game trees. Minimax searches
down to a certain depth, and treats the nodes at that depth as if they
were terminal nodes, invoking a heuristic function (called a
*static evaluation function*) to determine their values.
Assigning values recursively back up the tree, a player's node are
assigned the largest (maximum) value among its successors, and an
opponent's node is assigned the smallest (minimum) value among its
successors.

The problems involved in implementing minimax are when to cut off the recursive search and invoke the static evaulation function, and what evaluation function to use. Considerations include the number of plys explored, how promising the path is, how much time the computer has left to think, and how "stable" the configuration is.

A potential problem in game tree search to a fixed depth is the
*horizon effect*, which occurs when there is a drastic change
in value immediately beyond the place where the algorithm stops
searching. There are two proposed solutions to this problem, neither
very satisfactory.

One proposed solution is to examine the search space beyond the apparently best move to see if something is looming just over the horizon. In that case we can revert to the second-best move. Obviously then the second-best move has the same problem, and there isn't time to search beyond all possible acceptable moves.

This heuristic recommends that, if a good move for the opponent is found, the area of the tree beneath it should be examined early when considering the opponent's options.

Intuitively, alpha-beta is an improvement over minimax that avoids searching portions of the tree that cannot provide more information about the next move. Specifically, alpha-beta is a depth-first, branch-and-bound algorithm that traverses the tree in a fixed order (such as left to right) and uses the information it gains in the traversals to "prune" branches that can no longer change the minimax value at the root. Such cut off branches consist of options at game positions that the player will always avoid, because better choices are known to be available.

*Example*. Suppose the left subtree of an OR node (a
player's move) has value 3. This means the player can get at least a
value of 3 by choosing the move leading to that tree. Now we begin to
explore the right subtree, which consists of moves of the opponent.
The first child we examine has value 2. This means that, if the
player goes to that subtree, the opponent can make a move that results
in a game value of 2. Knowing this, we can prune the rest of the
right subtree, since we know it will have a value of 2 or worse (since
the opponent's goal is to minimize the board value), and we already
know the player can get a 3 by choosing the left subtree.

Two variables are kept during the search. *Alpha* is the
lower bound encountered so far, and *beta* is the upper bound.
At maximizing levels (player's moves), only beta is used to cut off
the search, and at minimizing levels only alpha is used.

A number of refinements are possible to alpha-beta. One is
waiting for quiescence (don't stop if the estimate changes drastically
from one move to another; this avoids the horizon effect). Another is
running a secondary search deeper along the chosen path to make sure
there is no hidden disaster a few moves further along (this is called
*singular extension*). Book moves can be used for openings and
end games in many games where exhaustive search can be done in
advance. Alpha-beta can also be extended to cut off search on paths
that are only slight improvements; this is called *futility
cutoff*.

Alpha-beta is the most popular algorithm for searching game trees.

[Berlinger, 1979] B^{*} proves that an arc from the root of the
search tree is better than any other. For each node expanded, it
computes an upper and a lower bound. These two bounds converge as the
search progresses, producing a natural termination of the search. The
main strength of B^{*} is that it can search branches that are
not known to be best; no other known algorithms can do so, i.e., lower
their optimistic bounds. (I'm unclear on what this means -- POD)

During search, when the maximizing player can show that the pessimistic value of an arc is greater than or equal to the optimistic values of any other arcs, it can either raise the lower bound on the most optimistic node, or lower the upper bound on all other nodes.

The important thing to note about B^{*} is that it
transfers control decisions (how deep to search, etc.) to the
evaluation functions which now determine the effort limit by their
crispness and ability to narrow the range between optimistic and
pessimistic evaluations.

B^{*} can be used both for 1-person and 2-person
(adversary) search.

[Stockman, 1979] SSS^{*} is a best-first search procedure that
keeps upper bounds on the values of partially developed candidate
strategies, choosing the best for further exploration. A
*strategy* specifies one response of the player to each of the
opponent's possible moves. The process continues until one strategy
is fully developed, at which point it is the optimal strategy.

SSS^{*} is optimal in the average number of nodes examined
in a two-player game, just as A^{*} is for single-person
search. It examines a (sometimes proper) subset of the nodes examined
by alpha-beta. However, its superior pruning power is offset by the
substantial storage space and bookkeeping required.

SCOUT evaluates a position J by computing the minimax value
*v* of its first successor. It then "scouts" the remaining
successors to see whether any produces a value higher than *v*,
since testing this limited supposition is faster than evaluating the
minimax value of each successor. If a successor passes this test, its
minimax value is computed and used as *v* in subsequent tests.
The best successor is then returned.

**Every search strategy that evaluates a game tree must examine at
least twice the square root of the number of nodes in the tree.** This
can be established by the following argument.

Evaluating a game with value *V* amounts to showing that, no
matter how the opponent reacts, the player can guarantee a payoff of
at least *V* and, simultaneously, no matter what the player
does the opponent can limit the payoff to *V*. Each of these
two verification tasks requires the display of an adversary strategy
producing value *V*. Since each strategy branches on every
*other* move (since the opposing side will always pick the best
move for it), the number of nodes in such a tree is roughly the square
root of the number of nodes in the entire game tree. Thus twice that
number must be explored to establish the value *V* for the
game.

This lower bound rarely occurs in practice, since we don't know in advance which strategies are "compatible." If no information is available regarding the benefits of impending moves, roughly the 3/4th-root of the number of nodes will be explored, on average. As move-rating information becomes more accurate, the number of nodes explored will approach the twice-square-root bound.

Assuming a uniform *b*-ary tree searched to depth
*d*, with values associated randomly with nodes at the
frontier, it can be shown that the effective branching factor of
alpha-beta pruning (and SCOUT and SSS^{*}) is

Moreover, this is the best branching factor achievable by
*any* game searching algorithm.

Roughly, alpha-beta will search only *b ^{3/4}* of
the

If the successors are perfectly ordered (i.e., to minimize search
using alpha-beta), alpha-beta examines 2b^{d/2} - 1 game
positions. Thus, when *B* is the effective branching factor,
we have

*B = b*for exhaustive search,*B ~= b*for alpha-beta with random ordering, and^{3/4}*B = b*for alpha-beta with perfect ordering.^{1/2}

In systems that have limited time to act, or in which new information is arriving during the search process (such as robots or vehicle navigation), it's necessary to interleave search and action. Some algorithms for real-time search are described below.

[Korf] Minmin searches to a fixed depth determined by resources.
The A^{*} evaluation function (*f(n) = g(n) + h'(n)*)
is used at the horizon, and search is moved to best frontier node.
The value at the root is the minimum of the frontier values.

A branch-and-bound extension of minmin. It improves efficiency by
evaluating both interior nodes and frontier nodes. If the heuristic
function is monotonic, then *f* (the evaulation function) is
nondecreasing, so we can prune any path when its cost equals or
exceeds the cost seen so far. This results in a dramatic performance
improvement over minmin.

[Korf] This algorithm produces an action every *k* seconds,
where *k* depends upon the depth of the search horizon. Rather
than simply repeating minmin search at each action (which could result
in infinite loops) it records each action taken and its second-best
successor; if the node is encountered again it looks up the heuristic
estimate on the node rather than re-doing minmin. Backtracking occurs
when the cost to go forward is greater than the estimated cost of
going back to a previous state and proceeding from there to the goal
state.

RTA^{*} will find a path to a solution if one exists and
the search graph is completely accessible. The path will not
necessarily be optimal, though RTA^{*} will make locally
optimal decisions.

In some search problems, there is no explicit goal state; rather,
there is a set of *constraints* on a possible solution that
must be satisfied. The task is not to find a sequence of steps
leading to a solution, but instead to find a particular state that
simultaneously satisfies all constraints.

The approach is to assign values to the constrained variables, each such assignment limiting the range of subsequent choices. Even though the sequence is not of interest, the problem can still be regarded as a search through state space.

*Example: the eight-queens problem.* The Eight-Queens
Problem is to place eight queens on a standard chessboard in such a
way that no two queens are attacking one another.

The topology of a constraint graph can sometimes be used to
identify solutions easily. In particular, binary CSPs whose
constraint graph is a tree can be solved optimally in time
O(*nk ^{2}*) where

The most common algorithm for solving CSPs is a type of depth-first
search called *backtracking*. The most primitive version
assigns variables to values in a predetermined order, at each step
attempting to assign a variable to the next value that is consistent
with previous assignments and the constraints. If no consistent
assignment can be found for the next variable, a dead-end is reached.
In this case the algorithm goes back to one of the earlier variables
and tries a different value.

The obvious approach is to assign variables in some order, then go
back and change assignments when a conflict is detected. However, the
run-time complexity of this approach is still exponential, and it
suffers from *thrashing*; that is, search in different parts of
the space keeps failing for the same reasons.

The simplest cause of thrashing is *node inconsistency*, in
which there is some possible value of a variable that will cause it to
fail in and of itself; when it is instantiated it always fails
immediately. This can be resolved by removing such values before
search begins.

Since backtracking is used in many AI applications (solving CSPs,
TMSs, PROLOG, etc.) there are a number of schemes to improve its
efficiency. Such schemes, called *dependency-directed
backtracking*, or sometimes *intelligent backtracking*
[Stallman and Sussman, 1977], can be classified as follows:

These schemes control which variable to instantiate next or what value to choose among the consistent options.

**Variable ordering**: This approach tries to choose a variable that will make the rest of the problem easier to solve. This is usually done by choosing the variable involved in the most constraints.**Value ordering**: A value is chosen that will maximize the number of options available for future assignments.

These approaches control the decision of where and how to go back in case of dead-ends. There are two basic approaches:

**Go back to source of failure**: Try to change only those past decisions that caused the error, leaving other past decisions unchanged.**Constraint recording**: Record the "reasons" for the dead-end so that they will be avoided in future search.

Gashnig's "backjumping" [1979] is the best-known go-back scheme (q.v.). A simpler version jumps to the youngest ancestor constraining the dead-end variable.

Dependency-directed backtracking is also used in truth-maintenance
systems (Doyle's RMS, 1979). It works as follows. A variable is
assigned some value, and a justification for that value is recorded
(and it may be simply that there is no justification for any other
values). Then a default value is assigned to some other variable and
justified. At this point the system checks whether the assignments
violate any constraints; if so, it records that the two are not
simultaneously accpetable, and this record is used to justify the
choice of some other variable. This continues until a solution is
found. Such a system never performs redundant backtracking and never
repeats computations.

Constraint recording can be implemented by preprocessing the
problem or by recording constraints as they are encountered during
search. The most common approaches are *arc consistency* and
*path consistency*.

Arc consistency deletes values of variables that have no consistent matches in adjacent (i.e., directly connected) variables. Path consistency records sets of forbidden value pairs when they can't be matched at some third variable.

Preprocessing for path consistency can be expensive;
O(n^{3}k^{3}) operations, while many forbidden pairs
would never actually be encountered. There are more efficient
learning techniques that process constraints as the search is
performed.

[Dechter and Pearl, 1987] Another approach to improving
backtracking performance. The goal is to identify a set of nodes
that, when removed, leave a tree-structured (i.e., cycle-free)
constraint graph. Once in tree form, the CSP can be solved in linear
time. This gives an upper complexity bound on the complexity of CSPs
-- if *c* is the size of some cycle cutset, and we instantiate
the variables in the cutset first, then the complexity of the search
is at most O(*nk ^{c}*), rather than the
O(

**Theorem [Freuder]**: A k-consistent CSP having a width (k - 1)
ordering admits a backtrack-free solution in that ordering.

In particular, a graph of width 1 (i.e., a tree) that is arc
consistent admits of backtrack free solutions; a graph of width 2 that
is path consistent admits of backtrack free solutions.

Search proceeds outward from islands in the search space; this form
of search is usually from hierarchical planning.

[Newell, Shaw, and Simon, 1956] The Logic Theorist was a joint production of the RAND Corporation and CMU, designed to prove theorems in propositional calculus. It was one of the first programs to rely heavily upon the use of heuristics to guide search.

The Logic Theorist introduced the ideas of *forward
chaining* and *backward chaining* in the proof procedure.
The general algorithm it used was a blind, breadth-first search with
backward reasoning.

[Newell, Shaw, and Simon, 1957] The successor to the Logic Theorist research, GPS had two main goals: to design a machine that could solve problems requring intelligence, and to learn how human beings solved problems.

Notable innovations in GPS were the clear distinction between
problem-solving knowledge and domain knowledge and the introduction of
*means-ends analysis* as a means of search.

Though GPS was meant to be general-purpose, it largely could solve problems only in the domain of logic; later extensions by Ernst allowed to solve problems in areas such as resolution theorem proving, symbolic integration, and a variety of puzzles.

More specifically, a simplified version of the problem is stated in
a *higher level problem space* or *abstraction space*,
and the detailed, implementable version in the *ground space*.
This is obviously generalizable to more than two levels of hierarchy.

Hierarchy was formed by giving each precondition on actions a
*criticality value*. The hierarchy was defined in terms of the
criticality levels; on the level of criticality *n*, all
operators of criticality less than *n* were ignored.

Search in ABSTRIPS used means-ends analysis, as GPS. The search
strategy could be described as *length-first*, as a complete
plan is formed at one level before being refined at a deeper level.

Ronny Kohavi, *AI Qual Note #7: Search Methods*.

Pearl and Korf, *Search Techniques*.

Ginsberg, *Introduction to Artificial Intelligence*.

Kumar, *Algorithms for Constraint-Satisfaction Problems: A
Survey*.

`Feigenbaum and Cohen, Handbook of AI.
`

See the AI Qual Reading List for further details on these sources.

Patrick Doyle | pdoyle@cs.stanford.edu |