Week 3c - Constraint Satisfaction Problems II

Commutativity

• In CSPs, variable assignments are commutative.
  • It doesn't matter which order you assign the variables
  • e.g. [WA=red then NT=green] == [NT=green then WA=red]
• Only need to consider assignments to a single variable at each level/depth
  • Branching factor is the domain size d
  • We have
    $d^n$ leaves now instead of
    $n!d^n$ leaves

Backtracking Search

Overview

• Backtracking Search is essentially like DFS for CSPs with single-variable assignments
  • Backtracking occurs when there are no legal values for a variable
  • Uses commutativity to reduce search from
    $n!d^n$ leaves to
    $d^n$ leaves
• Backtracking search is the basic uninformed algorithm for CSPs

Algorithm

Example: Map Coloring

Improving Backtracking Search

• General-purpose methods can give huge gains in speed:
  • Which variable should be assigned next?
    • Idea 1: Min. remaining values
    • Idea 2: Degree heuristic
  • In what order should its values be tried?
    • Idea 3: Least constraining value
  • Can we detect inevitable failure early?
    • Idea 4: Forward checking / AC-3 Algorithm
  • Can we take advantage of problem structure?
    • Idea 5: Tree-structured CSPs

Minimum Remaining Values

• Choose the variable with the fewest legal values, i.e., the most constrained variable
• We choose the variable with the least remaining legal value, which means most likely to fail. If it fails early, we will ignore the entire branch and avoid wasting time.
  

Degree Heuristic

• What happens when multiple variables have the same MRV?
• Degree Heuristic: Choose the variable with the most constraints on remaining variables (i.e. choose the variable that has the most impact on the domains of the other variables)
  

Least Constraining Value

• Given a variable, choose the least constraining value, i.e. the one that rules out the fewest values in the remaining variables
  
  
  In the example above, using the principle of least constraining value, we will go with coloring the state red instead of blue, since it has more values left available for SA as opposed to 0.

Forward Checking

• Keep track of remaining legal values for unassigned variables
  • Terminate search when any variable has no legal values
    
• Limitation of forward checking:
  • Forward checking propagates information from assigned to unassigned variables
    • However, it does not provide early detection for all failures
    • Hence, we need to repeatednly enforce constraints locally, i.e., constraint propagation
      

Arc Consistency

• Simplest form of propagation make each arc consistent
• X → Y is consistent iff
  • For every value x of X there is some allowed y.
    
• If X loses a value, neighbors of X need to be rechecked if they are still arc consistent.
• Arc consistency detects failure earlier than forward checking. It can be run as a preprocessor or after each assignment

Algorithm

Exercise: Application of AC-3

The ordering of arcs do not matter since it will still end up with one of the variables having no legal values remaining

Time Complexity of AC-3

Problem Structure

• Tasmania and mainland are independent subproblems
• Identifiable as connected components of constraint graph
• Suppose each subproblem has c variables out of total n variables
• Worst-case solution cost is
  $(n/c)\cdot d^c$, linear in n
  • e.g. n=80, d=2,c=20
    • $2^{80}$ = 4 billion years at 10m nodes/sec
    • broken down to 4 independent subproblems:
      $4\times 2^{20}$= 0.4 seconds at 10 million nodes/sec

Tree-structured CSPs

• Theorem: if the constraint graph has no loops, the CSP can be solved in
  $O(n{d}^2)$ time
• Compared to general CSPs, where worst-case time is
  $O(d^n)$

Algorithm

1. Choose a variable as root, order variables from root to leaves such that every node's parent precedes it in the ordering (this step is to order the graph as a tree)
2. For j from n down to 2, apply RemoveInconsistent(Parent(X_j),X_j)
3. For j from 1 to n, assign X_j consistently with Parent(X_j)

Another example:

Nearly Tree-Structured CSPs

• Conditioning: Instantiate a variable, prune its neighbors' domains
• Cutset conditioning: instantiate (in all ways) a set of variables such that the remaining constraint graph is a tree
• Cutset size c → runtime
  $O(d^c\cdot (n-c)d^2)$, very fast for small c