Content

1. Constraint Satisfaction Problems (Backtracking Search) Overview
   1. CSP v.s Traditional Search Problems
   2. Feature Vectors
   3. Constraint Graph
2. Solving CSPs
   1. Viewing CSP as Search Problem
   2. Backtracking Search Algorithm
   3. Constraint Propagation
      1. Forward Checking
      2. Generalizaed Arc Consistency
      3. Heuristics

Constraint Satisfaction Problems (Backtracking Search) Overview

CSP v.s Traditional Search Problems

• CSP does not care about the sequence of moves to reach goal state

Feature Vectors

• Represent states as vectors of feature values
• Formalization
  • A set of features/variables V1, ... Vn
  • Domain for each variable Dom[Vi]
  • A set of constraints C1, ..., Cm
    • Scope: a set of variables it operates over
    • Unary, binary, higher-order constraints
  • State: assignment of value for each variable
  • Partial state: assignment of value for some variables
  • Goal state: a state satisfying all constraints

Constraint Graph

• Nodes: variables; arcs: constraints

Solving CSPs

• Search through the space of partial assignments
• Order of assignments does not matter
• If we falsify a constraint, we immediately reject the current partial assignment

Viewing CSP as Search Problem

• Initial state: empty assignment
• Successor function: a value assigned to any unassigned variable s.t. no constraints return false
• Goal test: complete assignment

Backtracking Search Algorithm

• Similar to DFS

BT(Level):
    If all variables assigned:
        PRINT Value of each Variable
        RETURN

    V := PickUnassignedVariable()
    Assigned[V] := TRUE
    for d := each member of Domain(V):
        Value[V] := d
        ConstraintsOK = TRUE
          for each constraint C such that
            a) V is a variable of C and
            b) all other variables of C are assigned: 
            If C is not satisfied by the set of current assignments:
                ConstraintsOK = FALSE
                break
          If ConstraintsOk == TRUE:
            BT(Level+1)
    Assigned[V] := FALSE //UNDO as we have tried all of V’s values return

Constraint Propagation

• Look ahead

Forward Checking

• When instantiating a variable, check all constrants with only one ininstantiated variable remaining
• Prune values of that variable that violate the constraint

• Algorithm

    FCCheck(C,x):
        // C is a constraint with all its variables already assigned, except for variable x
  
        for d := each member of CurDom[x]:
            If making x = d together with previous assignments
        to variables in scope C falsifies C:
                remove d from CurDom[x]
  
         If CurDom[x] = {}:
             return DWO (Domain Wipe Out)
         Else:
             return ok
  
     FC(Level):
        If all variables assigned:
            PRINT Value of each Variable
            RETURN
  
        V := PickAnUnassignedVariable()
           Assigned[V] := TRUE
           for d := each member of CurDom(V):
            Value[V] := d
            DWOoccured:= False
            for each constraint C over V such that
                a) C has only one unassigned variable X in its scope:
                If (FCCheck(C,X) == DWO):
                    DWOoccurred:= True
                    break
            If(not DWOoccured)
                FC(Level+1)
            RestoreAllValuesPrunedByFCCheck()
        Assigned[V] := FALSE
        return;
  

Generalizaed Arc Consistency

• C(V1, ..., Vn) is GAC with regard to Vi iff for every value of Vi, there exist values of V1, ..., Vn that satisfy C
• If for Vi = d is not consistent wrt the constraint, d is arc inconsistent and can be removed from domain of Vi
• A constraint that is GAC may become non-GAC due to pruning of domain values during search

• Algorithm

    GAC_Enforce():
    // GAC-Queue contains all constraints one of whose variables has had its domain reduced
  
    while GACQueue not empty:
        C = GACQueue.extract()
        for V := each member of scope(C):
            for d := CurDom[V]:
                Find an assignment A for all other variables in scope(C) such that C(A ∪ V=d) = True
                if A not found:
                    CurDom[V] = CurDom[V] – d 
                if CurDom[V] = ∅:
                    empty GACQueue
                    return DWO
                else:
                    push all constraints C’ s.t. V ∈ scope(C’) and C’ !∈ GACQueue on to GACQueue
    return TRUE
  
    GAC(Level):
        If all variables are assigned:
            PRINT Value of each Variable
            RETURN
  
        V := PickAnUnassignedVariable()
        Assigned[V] := TRUE
        for d := each member of CurDom(V):
            Value[V] := d
            Prune all values of V != d from CurDom[V]
            for each constraint C whose scope contains V:
                Put C on GACQueue
            if(GAC_Enforce() != DWO):
                GAC(Level+1)
            RestoreAllValuesPrunedFromCurDoms()
  
        Assigned[V] := FALSE
        return;
  

  • May keep track of supports to avoid having to search through all possible assignments and check satisfication
  • Check if current support still valid, i.e. all values it assigns still lie in the variables' current domains

Heuristics

• Ordering of variables
  • Minimum Remaining Values (MRV): returns the variable with the most constrained current domain
  • Degree Heuristic (DH): returns variable imposing the most constraints on remaining unassigned variables
• Ordering of values
  • Least Constraining Value (LCV): the best value is the one ruling out the fewest domain values in other variables that share at least one constraint with var