Introduction

• Source Pearl & Korf, 1987
  
• Problem Space is the environment in which search takes place
  
• Problem Instance is the problem space combined with initial and goal state
  
• Problem Solving Task is to find a sequence of operators that map the initial state to a goal state. Such a sequence is called a solution to the problem
  

Brute Force or Blind Techniques

• Requires no knowledge other than that contained in the problem space (domain specific knowledge is not required)
  

  Breadth First Search

  • Source: Ginsberg p. 49
    
  • Assuming uniform branching factor b and single goal is at depth d
    

    Best Case

  • Since internal nodes require space and time.
    

  Depth First Search

  • Source: Rich & Knight p. 39 Rich and Knight is not a good source for brute force search techniques
    
  • See source for algorithm
    
  • Advantages: Less memory required then BFS
    
  • DisAd: Does not guarantee shortest path to a goal
    
  • Time Complexity
    
  • Space Complexity: O(d) in best and worst case where d is the depth of the tree
    

  Depth First Iterative Deepening

  • Source Pearl & Korf, 1987
    
  • Time Complexity asymptotically approaches O(bd)
    
  • Space Complexity is O(d)
    
  • DFID is asymptotically optimal in terms of time and space among all brute-force search algorithms that find optimal solutions on a tree.
    

  Bi-Directional Search

  • Source Pearl & Korf, 1987
    
  • Executes two breadth-first searches, one from the initial state and one from the goal state, until a common state is found between the two search frontiers
    
  • Requires explicit goal state rather than a goal criterion
    
  • Time Complexity: O(bd/2)
    
  • Space Complexity: O(bd/2)
    

  Island Driven Search

  • Source Ginsberg Text & CS 221 homework solutions
    
  • Instead of finding a path directly to the goal, one first identifies an "island" that is a node half-way between the initial node and the goal node. We first attempt to find a path to the goal that passes through this node; if none exists, we simply solve the original search problem while ignoring the hypothetical island.
    
  • The expected cost of doing an island driven search is:where c is the cost of identifying the island and p is the probability the island actually lies on a path to the goal.
    
  • To make island driven search worthwhile, we require . We obtain:
    
  • We should use Island driven search on problems with large p 's and small c 's.
    Example: Planning a route from Paris to Cairo with the knowledge that all roads lead to Rome.
    

  Iterative Broadening

  • Source Ginsberg Paper
    
  • Similar to DFID, iteratively increase the breadth cutoff when expanding each node.
    
  • Definition: Successful node - a node is successful if it has at least one goal node somewhere under it.
    
  • Useful if either s > 1.5 (a successful node has, on average, at least 1.5 successful children). Hence, this suggests that IB is useful for problems where there are many goals or multiple paths to a goal.
    
  • Not useful for sliding Tiles ... need a larger branching factor
    
  • Negative results for 2x2x2 Rubik's cube ... typically only one shortest solution to the problem
    
  • Not useful for Adversary search ... current techniques are already near optimal
    

Heuristic Search

• Heuristic Search takes advantage of the fact that most problem spaces provide, at relatively small computational cost, some information that distinguishes among the states in terms of their likelihood of leading to a goal state. This information is called a "heuristic evaluation function" (Pearl & Korf, 1987)
  

  Generate and Test

  • Source: Rich & Knight p.64
    
  • Examples of Generate and Test: Hill Climbing
    
  • Generate a possible solution, test if it is a solution, repeat
    
  • A DFS technique with backtracking. Keep generating possible solutions from the current state.
    
  • Seems like a very abstract search techniques. I don't quite understand how it would be implemented. Do you generate solutions randomly?
    
  • According to my conversation with Karl Pfleger, in Generate and test, the algorithm says nothing about arcs. For example, the algorithm will generate a node in the search space and will test if this node is in the goal set. If it is not, we generate another node. The obvious question is how does the algorithm generate a new node. Well, that is where the heuristic comes in. We can select a new node at random or we can pick some heuristic that selects the next node. Either way, the algorithm just suggest that we keep picking nodes until a goal node is found.
    
  • Source Winston p. 47-50
    
  • Good generators are complete (produce all possible solutions), non-redundant (never propose the same solution twice), and informed (try to limit generation of frivolous solutions)
    
  • Example 1: keep flipping pages in a book until you find the correct one
    
  • Example 2: Trying to crack a safe by sequentially going through all possible combinations
    

  Hill Climbing

  • Source: Rich & Knight p.66
    
  • Start from initial state, loop over operators, generate a state for the current operator. If the newly generated state is better than the current state, go to that state, repeat until a goal is found.
    
  • DisAd: susceptible to local maxima, plateau's and ridges.
    
  • Remember, from any given node, we go to the first node that is better than the current node. If there is no node better than the present node, then hill climbing halts.
    

  Steepest-Ascent Hill Climbing

  • Source: Rich & Knight p.67
    
  • a.k.a. Gradient Search
    
  • Apparently, only RK distinguish between Hill Climbing and Steepest-Ascent Hill Climbing. Others assume Hill Climbing means Steepest Ascent
    
  • Same as Hill climbing except we examine all the possible next states from a given state and we take the best choice among these states.
    
  • Has the same disadvantages as normal hill climbing. Following the steepest path might lead you to the goal faster, but then again, hill climbing does not guarantee you will find a goal.
    

  Simulated Annealing

  • Source: Rich & Knight p.70
    
  • Kirkpatrick, Galatt, Vecchi, 1983 are original authors of this.
    
  • An attempt to solve some of the problems with hill climbing. In particular, how does one get out of local maxima
    

  Best First

  A*

Problem Reduction

And/Or Graphs

AO*

Means-Ends Analysis

• Source: Rich & Knight p.94-
  
• Detect differences between current state and goal state. Identify an operator that is applicable in the current state and reduces the difference between the current state and the goal state.
  
• If goal is not achievable by using one operator from the current state, we set up an achievable subgoal that is reachable by applying one operator. Recurse until goal is achieved. Can prioritize differences when selecting among operators
  

General Problem Solver (GPS) (an example of Means-Ends Analysis)

• Source: Rich & Knight p. 95
  
• References to Newell and Simon, 1963; Ernst and Newell, 1969
  
• Set of rules, preconditions on the rules ad a data structure called a "difference table"
  

Adversarial Search

MiniMax

Alpha-Beta Pruning

Real-Time Heuristic Search

• Source Korf, 1990
  
• Try to use some of the principles of adversarial search to single problem solving situations
  

  Minimin

  • Search forward from the current state to a fixed depth, apply heuristic evaluation function to the nodes at the search frontier.
    
  • The minimum value among the frontier children is determined and a single move is made in the direction of the minimal child (note, we do not go directly to the minimum child)
    
  • Korf seems to intend this for planning
    
  • If there is non-uniform costs, use the A* cost function f(n) = g(n) + h(n) and back up the minimal f(n) value
    Instead of searching forward a fixed number of moves, we can search forward until to a fixed g(n)
    

  Alpha Pruning

  • If the cost function is monotonic, then we can prune interior nodes, in a manner similar to alpha-beta pruning
    
  • In the course of generating the tree, maintain in a variable a the lowest f value of any node encountered on the search horizon so far. As each interior node is generated, compute its f value and terminate search of the corresponding branch when its f value equals or exceeds a
    
  • Given a sufficiently large amount of computation, the search horizon achievable with alpha pruning actually increases with increasing branching factor.
    

  Real-Time A*

  • Minimin has the potential to infinitely recurse
    
  • One should backtrack to a previously visited state when the estimate of solving the problem from that state plus the cost of returning to that state is less than the estimated cost of going forward from the current state.
    
  • the merit of a node n is f(n) = g(n) + h(n) as in A*. However, g(n) is the actual distance of node n from the current state of the problem solver, rather than the original initial state.
    
  • Maintains a hash table of previously visited nodes as well as their h values. When expanding a node, choose the neighbor with the lowest f value
    

Constraint Satisfaction Problems

• Source (Pearl & Korf, 1987), (Kumar, 1992)
  
• Goal State not explicitly given; rather it is specified by a set of constrains that must by satisfied by any goal state. (Pearl & Korf, 1987)
  
• Problem description: We are given a set of variables, a finite and discrete domain for each variable, and a set of constraints. Each constraint is defined over some subset of the original set of variables and limits the combinations of values that the variables in this subset can take. The goal is to find one assignment to the variables such that the assignment satisfies all the constraints. In some problems, the goal is to find all such assignments. (Kumar, 1992)
  
• Example: Eight-Queens Problem, Map-coloring problem
  

  Backtracking

  • Variables are instantiated sequentially. As soon as all the variables relevant to a constraint are instantiated, the validity of the constraint is checked. If a partial instantiation violates any of the constraints, backtracking is performed to the most recent instantiated variables that still has alternatives available
    

  Problems with Backtracking

  Thrashing

  • search in different parts of the space keep failing for the same reasons. Backtracking suffers from this
    

  Node inconsistency

  • If the domain Di of variable Vi contains a value a that does not satisfy the unary constraint on Vi , then the instantiation of Vi to a always results in an immediate failure.
    
  • Can be solved by removing those values from the domains Di of each variable Vi that do not satisfy the unary constraint
    

  Arc inconsistency

  • Suppose that the binary constraint between Vi and Vj is such that for Vi = a , it disallows any value of Vj
    
  • Arc (Vi , Vj ) is arc consistent if for every value x in the current domain of Vi , there is some value y in the domain of Vj such that Vi = x and Vj = y are permitted by the binary constraint between Vi and Vj .
    
  • In general, achieving an arc-consistent constraint graph does not necessarily suggest there is a solution. See Figure 3 on p. 35 of Kumar, 1992. Making the constraint graph arc-consistent reduces the search done by backtracking.
    

  Constraint Propagation: Algorithms for removing arc inconsistencies

  • To try to reduce backtracking, constraints between different variables are propagated to derive s simpler problem. In some cases, the resulting CSP is so simple that its solution can be found without search.
    

    REVISE

  • Arc inconsistency be avoided if each arc (Vi , Vj ) of the constraint graph is made consistent before search starts. To make an arc consistent, delete those values from the domain of Vi for which there is no value in the domain of variable Vj which satisfy the binary constraint between Vi and Vj . See "REVISE" algorithm in [Kumar, 1992; p.34]
    

    AC-1

  • Iteratively call REVISE until no more arc consistency can be removed
    
  • successful revision of even one arc in some iteration forces all the arcs to be revised in the next iteration, even though only a small number of them are affected by this revision
    

    AC-3

  • Only performs re-revision for those arcs that are possibly affected by a previous revision
    

    Complexity of algorithms

  • Domain size for each variable is d , total number of binary constraints is e
    
  • Lower bound of the worst case is O(ed 2)
    

  Degrees of consistency

  K Consistent

  • Choose values of any K-1 variables that satisfy all the constraints among these variables, then choose any K'th variable. If a value for this variable exists that satisfies all the constraints among these K variables, the constraint graph is K consistent
    

    Strongly K consistent

  • A constraint graph is strongly K consistent if it is J consistent for all J <= K.
    
  • Node consistency is equivalent to strong 1 consistency
    
  • Arc consistency is equivalent to strong 2 consistency
    
  • Algorithms exists to make a consistent graph strongly K consistent for K > 2.
    

    Theorem

  • If a constraint graph is strongly K consistent, and K > w , where w is the width of the constraint graph, then a search order exists that is backtrack free.
    
  • The width at a vertex in an ordered constraint graph is the number of constraint arcs that lead from the vertex to the previous vertices. The width of a constraint graph is the minimum width of all the orderings of the graph.
    

  How much Constraint Propagation is useful?

• Although, any n -variable CSP can be solved by achieving n consistency. this approach is usually more expensive than simple backtracking.
  
• Solution: embed a constraint-propagation algorithm inside a backtracking algorithm.
  

  General Algorithm

  • A root node is created to solve the original CSP
    
  • Whenever a node is visited, a constraint-propagation algorithm is first used to attain a desired level of consistency.
    
  • If at a node, the cardinality of the domain of each variable becomes 1, and the corresponding CSP is arc consistent, then the node represents a solution.
    
  • If in the process of performing constraint propagation at the node, the domain of any variable becomes null, then the node is pruned.
    
  • Otherwise, one of the variables (whose current domain size > 1) is selected, and a new CSP is created for each possible assignment of this variable.
    

  Examples

  Generate and Test

  • Generate an instantiation for all variables. After all variables have been instantiated, we check to see if the solution satisfies the constraints. Otherwise, generate another instantiation of all variables.
    

    Simple Backtracking

  • limited arc consistency checking. When a new variable is instantiated, any of its values that are inconsistent with any previous variable instantiations cause immediate failure.
    

    Forward Checking

  • Greater degree of arc consistency than simple backtracking
    
  • Whenever a new variable instantiation is made, the domains of all as-yet-uninstantiated variables are filtered to contain only those values that are consistent with this instantiation.
    
  • In practice, this seems to be the best algorithm
    

    Partial Lookahead, Full Lookahead

  • Augmented versions of forward checking that perform arc consistency even between uninstantiated variables
    

    Really Full Lookahead

  • complete 2-consistency algorithm embedded in backtracking
    

  Intelligent Backtracking and Truth Maintenance

  • Backtracking suffers from thrashing and redundant work
    

    Intelligent Backtracking

    • When a constraint violation is found, backtrack to the variable that caused the violation
      
    • This does not avoid redundant work
      

    Dependency-Directed Backtracking

    • Attempts to address both thrashing and redundant work
      
    • Used in Truth maintenance systems, Doyle's RMS
      

    Algorithm

    • A variable is assigned some value, and a justification in noted (the justification is simply that no justification exists for assigning other possible values)
      
    • A default value is assigned to another variable and is justified
      
    • System checks for constraint violations
      
    • If violation exists, system creates a new node that denotes the pair of values for the two variables in question is not allowed
      
    • This node is used to justify another value assignment to one of the variables
      

    Problem

    • The procedures for determining the culprit of constraint violation and choosing a new value of the variables are complex
      
    • Even schemes that perform only intelligent backtracking can be complex.
      

    Similarity to other problems

    • Intelligent backtracking schemes developed for Prolog
      
    • De Kleer's assumption-based truth maintenance system tries to remedy the drawbacks to simple backtracking
      
    • There are strong similarities between the constraint-propagation methods discussed in Propagating Constraints and ATMS for solving CSPs
      

  Variable Ordering and Value Instantiation

  • The ordering in which variables are chosen for instantiation can have substantial impact on the complexity of the backtrack search
    

    Search-Rearrangement Method

  • the variable with the fewest possible remaining alternatives is selected for instantiation
    
  • For the n -queens problem, experiments [Stone and Stone, 1986] show an improvement of dozens of orders of magnitude for large values of n (~ 100)
    

    Instantiate "stable set" last

  • Instantiate those variables first that participate in the highest number of constraints
    
  • stable set - a set of variables with no direct constraints between any pair of them
    
  • Instantiate all variables in a stable set last
    
  • If a constraint graph has n vertices, and a stable of m vertices exists, then the overall complexity of the backtrack is bounded by d(n-m) * md as opposed to dn . This bound is incorrectly stated in the article.
    
  • Unfortunately, the problem of finding a maximal stable set is NP-Hard
    

    Keep options open

  • When instantiating a variable which has multiple valid instantiations, prefer those values that maximize the number of options available for future assignments.
    
  • This heuristic combined with search-rearrangement were used with Stone and Stone's system to n -queens problem for larger values of n (~ 1000)
    
  • Minton et al were able to solve n-queens for n ~ 1,000,000 using a modified technique
    

    Prefer easiest CSP

  • Prefer the value that leads to the CSP that is easiest to solve
    
  • CSP is converted into a tree-structured CSP by deleting a minimum-number of arcs
    
  • The number of solutions found in the corresponding tree-structured CSP is taken as the measure of difficulty of solving CSP