Chapter 5
Constraint Satisfaction Problems  

powered by FreeFind

Modified: 

Outline

5.1 CONSTRAINT SATISFACTION PROBLEMS

CSP definitions

 

CSP formulation

 

Example: Map coloring

State - one of many but not a solution:

{WA=red, NT=red, Q=red, NSW=red, V=red, SA=red, T=red}

Solution - one of many; constraints satisfied, all variables assigned:

{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red}

 

One Solution

A complete assignment satisfying all constraints, for example:

{ WA=red, NT=green, SA=blue, Q=red, NSW=green, V=red, T=green}

  • One variable is assigned at each step, how deep is the search?
  • What is the number of complete assignments including those that violate constraints. These would be at leaf nodes.
  • What is the total size of the state space?
  • What are some of the invalid successor states of the assignment {WA=red}?
  • What are some of the valid successor states of the assignment {WA=red}?

 

Constraint graph

    Represents CSP.

  • The constraint a != b in map coloring means that no adjacent Australian states are the same color.
  • What is meaning of arcs from SA under the a != b constraint?
  • What about the fact that there are no arcs to T.
  • What is the implication of the arcs between WA, NT and SA?

Benefit of CSPs

Standard pattern - a set of variables assigned values, the successor function and goal test are generic for all CSPs

Generic heuristics - require no domain-specific knowledge

Constraint graph - structure used to simplify solution process, sometime exponential reduction over general-purpose search (e.g. depth-first).

 

CSP search formulation

 

Varieties of CSPs

 

Varieties of constraints

Example: Cryptarithmetic

Constraints are square boxes connected to variables it constrains

Order 2 - F, X3

Order 3 - O, R, X1

Order 6 - F, T, U, W, R, O

O + O = R + 10 * X1

X1 + W + W = U + 10 * X2

X2 + T + T = O + 10 * X3

X3 = F

where X1, X2 and X1  are auxiliary variables representing the 0 or 1 carry.

  • What are some of the constraints on F?
  • on X3 ?
  • What is the domain of X1, X2, X3?
  • What are some valid successor states involving T and O for the assignment {F=0}?

Other, real-world problem examples:

Assignment: who will teach what class given qualifications and schedule

Timetabling: which class is offered when and where

Hardware configuration

Scheduling observation time on the Hubble Space Telescope

Notice that many real-world problems involve real-valued variables

 

Standard search formulation

 

5.2 BACKTRACKING SEARCH FOR CSPs

def BACKTRACKING_SEARCH(csp) :
   return RECURSIVE_BACKTRACKING( {}, csp)

def RECURSIVE_BACKTRACKING( assignment, csp) :
   if COMPLETE(assignment, csp.VARIABLES ) : return assignment
   var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
   for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
      if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
         assignment[var]=value                     # Add var=value
         result = RECURSIVE_BACKTRACKING(assignment, csp)
         if result != 'failure' : return result
         del assignment[var]                          # Remove var=value
   return 'failure'

 

Backtracking example

 

 

Constraints on SA will eventually cause failure when WA != Q. When not the same color (bottom right), SA cannot be assigned.

The algorithm will backtrack to a node with unexplored states.

For example, such as WA=red, NT=blue.

 

  • Is SA in successor states after assigning {WA=red, NT=green, Q=blue}?
  • What are some legal successor states after  {WA=red, NT=green, Q=red}?

 

Python Constraint Satisfaction Problem solution (Download)

Binary CSP specified by four inputs:

  1. VARIABLES      - A list of variables; each is atomic (e.g. int or string).
  2. DOMAINS         - A dict of {var:[possible_value, ...]} entries.
  3. NEIGHBORS     - A dict of {var:[var,...]} that for each variable lists
                             the other variables that participate in constraints.
  4. CONSTRAINTS - A binary function f(A, a, B, b) that returns true if
                             neighbors A, B satisfy constraint with values A=a, B=b.
# Figure 5.3 page 142

class CSP :
   def __init__(self, vars, domains, neighbors, constraints):
      self.VARIABLES=vars
      self.DOMAINS=domains
      self.NEIGHBORS=neighbors
      self.CONSTRAINTS=constraints
# ---------------------------------------------------------------------------------
def BACKTRACKING_SEARCH(csp) :
   return RECURSIVE_BACKTRACKING( {}, csp)

def RECURSIVE_BACKTRACKING( assignment, csp) :
   if COMPLETE(assignment, csp.VARIABLES ) : return assignment
   var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
   for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
      if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
         assignment[var]=value
         result = RECURSIVE_BACKTRACKING(assignment,csp)
         if result != 'failure' : return result
         del assignment[var]
   return 'failure'

def SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp) :
   for var in vars :
      if not (var in assignment) : return var

def COMPLETE(assignment, vars) :
   for var in vars :
      if not (var in assignment) : return False
   return True

def ORDER_DOMAIN_VALUES( var, assignment, csp) :
   return csp.DOMAINS[var][:]

def CONSISTENT(var, value, assignment, constraints, neighbors) :
   if not assignment : return True
   for c in constraints.keys() :
      for var2 in neighbors[var] :
         if var2 in assignment and
                        not constraints[c](var, value, var2, assignment[var2]) :
            return False
   return True

def Australia() : # Return a CSP instance of the Map Coloring of Australia.
   WA,Q,T,V,SA,NT,NSW = 'WA','Q','T','V','SA','NT','NSW'
   values = ['R', 'G', 'B']
   vars = [WA, Q, T, V, SA, NT, NSW]
   domains = {SA: values[:], WA:values[:], NT:values[:],
                     Q:values[:], NSW:values[:], V:values[:], T:values[:]}
   neighbors = {WA: [SA, NT], Q: [SA, NT, NSW], T: [],V: [SA, NSW],
                        SA: [WA, NT, Q, NSW, V], NT: [SA, WA, Q], NSW: [SA, Q, V]}
   constraints = {SA: constraint, WA:constraint, NT:constraint, Q:constraint,
                         NSW:constraint, V:constraint, T:constraint}
   return CSP(vars, domains, neighbors, constraints)

def constraint(A, a, B, b): # Two neighboring variables must differ in value.
   return a != b

def run():
   print BACKTRACKING_SEARCH(Australia())

Note: Domains are copies (e.g. SA: values[:]) so that modifying one domain will not affect the domain of other variables.

 

 

 

 

 

 

  • What is returned by: Australia()?
  • What is returned by: BACKTRACKING_SEARCH(Australia())?
  • What purpose is the assignment variable below?
  • What purpose is the var variable below?
  • What purpose is:

for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :

  • What would the following do?

    if CONSISTENT(Q, red, {NT:blue, NSW:green}, csp.CONSTRAINTS, [NT,SA,NSW]) :         
          assignment[var]=value
     

  • What is assignment variable now?
  • What is the effect of:

          del assignment[var]

def RECURSIVE_BACKTRACKING( assignment, csp) :
   if COMPLETE(assignment, csp.VARIABLES ) : return assignment
   var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
   for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
      if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
         assignment[var]=value
         result = RECURSIVE_BACKTRACKING(assignment,csp)
         if result != 'failure' : return result
         del assignment[var]
   return 'failure'

 

Improving backtracking efficiency

Consider the search tree nodes produced by the successor function:

0 level - 0 variables assigned branching factor is nd since any of the n variables can be assigned any of the d values;

1 level - 1 variable is assigned (next level) branching factor is (n-1)d, a total of n(n-1)d2

2 level - branching factor is (n-2)d, a total of n(n-1)(n-2)d3.

n-1 level - branching factor is (n-(n-1))d, a total of n(n-1)(n-2)d3*...*d.

State space size is then n!dn

Australia has 7!*37 or 5040*2187=11022480


Consider

  1. Which variable should be assigned next?
  2. In what order should the variables be tried?
  3. Can we detect inevitable failure early?
  4. Can we take advantage of problem structure?

 

Most constrained variable or minimum remaining values (MRV)

Idea is that variable with fewest choices will likely fail sooner allowing branch to be pruned early.

Choose the variable with the fewest legal values

Legal values are those that do not conflict with any already assigned to a neighbor (i.e. do not violate constrains).

After WA=red, NT and SA have only 2 remaining legal values, the other unassigned variables all have 3.

Choose between NT and SA.

  • After assigning NT=red what some of the possible assignments for neighbors?
  • Under MRV, pick a variable and value to assign next after NT=red assigned.
  • What are the possible MRV assignments now?

Python minimum remaining values

  1. SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp)
    • Now instead of returning the first unassigned variable, returns the unassigned variable with the minimum remaining values
  2. num_legal_values(self, var, assignment)
    • Returns the number of legal values for var (those that do not violate constraints) given current assignment
  3. nconflicts(self, var, value, assignment)
    • Return number of conflicts for var value with neighbor's values
  4. countTrue( fn, list)
    • Counts the number of true results from applying fn to every element in list.
class CSP :
   def __init__(self, vars, domains, neighbors, constraints):
      self.VARIABLES=vars
      self.DOMAINS=domains
      self.NEIGHBORS=neighbors
      self.CONSTRAINTS=constraints

   def num_legal_values(self, var, assignment):      # Number of legal values
      def legal(value) :                                            # True if legal value
         return self.nconflicts(var, value, assignment) == 0
      return countTRUE(legal, self.DOMAINS[var])

   def nconflicts(self, var, value, assignment):         # Number of conflicts
      "Return the number of conflicts var=val has with other variables."
      def conflict(var2):
         val2 = assignment.get(var2, None)               # var=None if not assigned
         return val2 != None and not self.CONSTRAINTS[var](var, value, var2, val2)
      return countTRUE(conflict, self.NEIGHBORS[var])

def countTRUE( fn, list) :     # return the number of fn(v) that are True
   n=0
   for v in list :
      if fn(v) : n=n+1
   return n

def SELECT_UNASSIGNED_VARIABLE( vars, assignment, csp) :
   mrv={}
   for v in vars :                          # Calculate number of legal values for each
      if v not in assignment :         # unassigned var
         mrv[v]=csp.num_legal_values(v, assignment)
   minimum=mrv.keys()[0]          # Find var with Minimum Remaining Values
   for v in mrv.keys() :
      if mrv[v] < mrv[minimum] :
          minimum = v
   return minimum

 

Most constraining variable

Choose the variable that constrains the most remaining variables

SA places constrains on 5 variables; WA, NT, Q, V, NSW only on 3, T on 0.

Purpose is to prune early by reducing number of choices.

Tie breaker among minimum remaining variables (MRV)

 

Least constraining value

Given a variable, choose the least constraining value:

the one that rules out the fewest values in the remaining variables

Idea is to explore paths, those with most options, most likely to lead to a solution.

 

Forward checking

Keep only legal values in domain for unassigned variables

  1. Prune illegal values from domain of connected (neighbors) unassigned variables after each assignment
  2. Backtrack search when any variable has no legal values
  3. When backtracking to undo an assignment, restore pruned values to domain of connected (neighbors) unassigned variables

Reduces search tree by pruning branches destined to eventually fail due to values that violate constraints in the domains of neighbors

  • How far ahead does forward checking look? That is, unassigned immediate neighbors, or unassigned neighbors of unassigned neighbors of ...
  • Complete the following using forward checking.
  WA NT Q NSW V SA T
Domain RGB RGB RGB RGB RGB RGB RGB
SA=R              
V=G              
WA=B              

Python forward checking

Basic idea is to prune values from domain of unassigned neighbors of X that conflict with the value just assigned to X, eliminating known inconsistent states from the search space.

            assignment[var]=value
            csp.forward_check(var, value, assignment)

When backtracking occurs, the pruning of neighbors domain must be undone and assignment of variable deleted.

 csp.undo_forward_check(var)
 del assignment[var]
 

class CSP :
   def __init__(self, vars, domains, neighbors, constraints):
      self.VARIABLES=vars
      self.DOMAINS=domains
      self.NEIGHBORS=neighbors
      self.CONSTRAINTS=constraints
      self.PRUNED = {}
      for v in vars: self.PRUNED[v] = []

   def forward_check(self, var, val, assignment):
      # Prune any B=b from unassigned neighbors domain that conflict with var=val
      for B in self.NEIGHBORS[var]:
         if B not in assignment:
            for b in self.DOMAINS[B][:]:
               if not self.CONSTRAINTS[var](var, val, B, b):
                  self.DOMAINS[B].remove(b)
                  self.PRUNED[var].append((B, b))

   def undo_forward_check(self, var) :
      # Restore prunings from previous value of var
      for (B, b) in self.PRUNED[var]:
         self.DOMAINS[B].append(b)
         self.PRUNED[var] = []

# _____________________________________________________________

def BACKTRACKING_SEARCH(csp) :
   return RECURSIVE_BACKTRACKING( {}, csp)

def RECURSIVE_BACKTRACKING( assignment, csp) :
   if COMPLETE(assignment, csp.VARIABLES ) : return assignment
      var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
      for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
         if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
            assignment[var]=value
            csp.forward_check(var, value, assignment)
            result = RECURSIVE_BACKTRACKING(assignment,csp)
            if result != 'failure' : return result
            csp.undo_forward_check(var)
            del assignment[var]
   return 'failure'

 

Constrain propagation

Forward checking propagates values from assigned to unassigned variables (by pruning neighbors domain) but does not provide early detection of all failures. Only looks at conflicts with immediate neighbors.

Constrain propagation propagates implication of constrains on one variable to others.

Propagating WA=red and Q=green constrains NT and SA to blue; cannot both be blue since adjacent.

Constraint propagation repeatedly enforces constraints locally

Arc consistency

Arc from SA to NSW is consistent because SA (blue) allows NSW (red)

 

Arc from NSW to SA is not consistent because NSW (blue) does not allow SA (blue)

Can be made consistent by removing blue from NSW domain

 

After removing blue from NSW, must check neighbors for consistency leading to removal of red from V.

After removing blue, SA domain is {}, pruning SA completely for the two assignments {NSW=red, Q=green} and forcing backtracking.

  1. Is the arc (WA,NSW) consistent?

  2. Is the arc (NSW,WA) consistent?
  3. If not, what should be the domain of NSW and WA?
  4. Is the arc (SA,T) consistent?
  5. is the arc (T, SA) consistent?
  6. The full tree contains 7!*37 nodes. With 2 variables assigned {NSW=red, Q=green} lower branches contain how many nodes?

  7. Should any lower branches be expanded for assignment {NSW=red,Q=green}?

Arc consistency algorithm

Note:

Chris raised the question: How does AC3 remove any inconsistencies when run as a preprocessing step, when all variables have domain of [R, G, B]? The answer is that there are no inconsistencies since for any x in [R, G, B] there is some y in [R, G, B] that the constraint x!=y is satisfied. AC3 does nothing!

In fact, running as a preprocessing step before backtracking search or after a variable assignment makes no difference, assuming the domains are not changed elsewhere by some other pruning heuristic. With only AC3 changing domains, inconsistencies never occur. Inconsistencies can be created by initially restricting SA=R for example (see Homework 4).

Running AC3 after assignment makes sense only if the domain is restricted to the value assigned, that is if SA=R then domain SA=R. AC3 can then remove any inconsistencies created by the assignment. But when failure occurs and the assignment is removed, the old domains for all variables must be restored. The Python code below implements the BACK_TRACKING_SEARCH with those modifications.

Interestingly, the execution time using AC3 increases BACK_TRACKING_SEARCH due to the overhead of copying the entire original domain of each variable and removing conflicts from starting at the backtracked variable. One solution, not implemented here, would be to keep track of values pruned at each level of backtracking and restore only those.

function AC3( csp ) returns the CSP possibly with reduced domains
   local variables: queue, queue of arcs, initially all the arcs in csp

  
loop while queue  is not empty do
       (Xi, Xj) = REMOVE-FRONT(queue)
      
if REMOVE-INCONSISTENT(Xi, Xj) then     # Neighbors may be inconsistent
          for each Xk in NEIGHBORS[Xi] do          # add to queue to check
             add (Xk, Xi) to queue 
function REMOVE-INCONSISTENT(Xi, Xj) returns True iff Xi value removed

    removed = False
    for each x in DOMAIN[Xi] do
        if (x, y) is inconsistent for every value y in DOMAIN[Xj]
             then delete x from DOMAIN[Xi]
             removed = True
    return removed
import copy

def BACKTRACKING_SEARCH(csp) :
   csp.OLD=copy.deepcopy(csp.DOMAINS)      # Copy DOMAINS
   return RECURSIVE_BACKTRACKING( {}, csp)

def RECURSIVE_BACKTRACKING( assignment, csp) :
   if COMPLETE(assignment, csp.VARIABLES ) : return assignment
      var = SELECT_UNASSIGNED_VARIABLE( csp.VARIABLES, assignment, csp)
      for value in ORDER_DOMAIN_VALUES( var, assignment, csp) :
         if CONSISTENT(var, value, assignment, csp.CONSTRAINTS, csp.NEIGHBORS) :
            assignment[var]=value
            csp.DOMAINS[var]=[value]                     # Restrict domain
            AC3(csp)
            result = RECURSIVE_BACKTRACKING(assignment,csp)
            if result != 'failure' : return result
            csp.DOMAINS=copy.deepcopy(csp.OLD)   #Restore DOMAINS
            del assignment[var]
   return 'failure'

  • Representing an arc from NSW to V as (NSW,V), give the starting queue in AC3.
  • Restrict the domain of SA=[R] and the remaining variables to [R, G, B]. Record each variables domain while propagating the constraint using AC3 for several queue entries.

O(n2d3) is worst case time but cannot detect all failures in polynomial time.

AC3 checks all neighbors and removes inconsistencies, the effectiveness can be seen when applied to the Australia map coloring.

In practice, AC3 can be called one time before calling the backtracking search or each time after assigning a variable a consistent value according to problem constraints.

Problems

Arc consistency does not reveal every possible inconsistency.

The partial assignment {WA=red, NSW=red} is inconsistent but AC3 will not find it because only considers 2 variables at a time.

  • Why is the assignment {WA=red, NSW=red} inconsistent?

1-consistent is node consistency, each variable is consistent. WA cannot be pink.

2-consistent is arc consistency.

3-consistent is path consistency, any pair of adjacent variables can be extended to a third neighboring variable. e.g. (WA,SA,NSW)

k-consistent if for k-1 variables and any consistent assignment to those variables, a consistent value can be assigned to kth variable. All k variables can be assigned consistent values.

Strongly k-consistent if k, k-1, k-2, ..., 1 consistent. Can then solve problem with no backtracking but propagation is still exponential cost.

 

5.3 LOCAL SEARCH FOR CONSTRAINT SATISFACTION PROBLEMS

Iterative algorithms for CSPs

 

Example 4-queens problem

 

Performance of min-conflicts

MIN-CONFLICTS

Idea:

  1. assignment = initially a value assigned to each variable, could be all the same value, random, etc.
  2. for i=1 to max_steps
    1. Determine conflicted variables in assignment.
    2. if no conflicted variables in assignment then return assignment
    3. Select one conflicted variable at random
    4. value = the value for variable that minimizes the number of conflicts
    5. Change value of variable in assignment

Example: 8-queens with number of pairs of conflicts with queens in other columns.

In leftmost figure, column 8 variable changed to row 3 with minimum conflicts value of 1. Since tie in row 3 and 6, choose between them at random.

In next figure, column 6 has been randomly selected and changed to row 8 with minimum conflicts value of 0.

Solution in last figure.

  • What is the assignment in the leftmost figure?
  • In the rightmost figure?
  • What are the problem constraints?

Figure 5.8 page 151 Min-Conflicts

def MIN_CONFLICTS(csp, max_steps=1000000) :
   current = {};                                         # current assignment all the same
   for var in csp.VARIABLES : current[var]=csp.DOMAINS[var][0]

   for i in range(max_steps) :
      conflicted = csp.conflicted_vars(current)      # List of conflicted vars
      if not conflicted : return current                  # Solution
      var = conflicted[int(random.uniform(0, len(conflicted)))]   # Random conflicted var
      val = min_conflicts_value(csp, var, current) # value with minimum conflicts
      current[var]=val
   return None

def min_conflicts_value(csp, var, current):
   """Return the value giving var the least number of conflicts. Random on tie."""
   return argmin(csp.DOMAINS[var],
      lambda val: csp.nconflicts(var, val, current))

def argmin(seq, fn) :                # Return seq that evaluate to minimum fn(seq[0..n])
   min = 0
   minvalue = fn(seq[min])
   for i in range(len(seq)) :
      testvalue = fn(seq[i])
      if testvalue == minvalue :   # Select randomly when equal
         if random.uniform(0, 1) > 0.5 : min = i
      if testvalue < minvalue :
         min = i
         minvalue = testvalue
   return seq[min]

def countTRUE( fn, list) :
   n=0
   for v in list :
      if fn(v) : n=n+1
   return n
#______________________________________________________________

class CSP :
   def __init__(self, vars, domains, neighbors, constraints):
      self.VARIABLES=vars
      self.DOMAINS=domains
      self.NEIGHBORS=neighbors
      self.CONSTRAINTS=constraints

   def conflicted_vars(self, current):
      "Return a list of variables in current assignment that are in conflict"
      return [var for var in self.VARIABLES
                     if self.nconflicts(var, current[var], current) > 0]

   def nconflicts(self, var, value, assignment):
      "Return the number of conflicts var=val has with other variables."
      def conflict(var2):
         val2 = assignment.get(var2, None)
         return val2 != None and not self.CONSTRAINTS[var](var, value, var2, val2)
   return countTRUE(conflict, self.NEIGHBORS[var])
What is the effect of initializing current={WA=R, NT=R, Q=R, SA=R, NSW=R, V=R, T=R}?

What is nconflicts(WA, R, {WA=R, NT=R, Q=R, SA=R, NSW=R, V=R, T=R})?

What is conflicted_vars({WA=G, NT=B, Q=G, SA=R, NSW=B, V=G, T=R})

5.4 THE STRUCTURE OF PROBLEMS

Problem structure

 

 

Tree-structured CSPs

 

Algorithm for tree-structured CSPs

 

Nearly tree-structured CSPs

 

Summary