Constraint satisfaction problem (CSP，约束满足问题)

• The search algorithms we discussed so far had no knowledgeof the states representation (black box).
• Instead we can have a general state representation that workswell for many different problems.
• We can build then specialized search algorithms that operateefficiently on this general state representation.

• We call the class of problems that can be represented withthis specialized representation CSPs – Constraint Satisfaction Problems.

• 到目前为止，我们讨论的搜索算法没有状态表示(黑盒)的知识。
• 相反，我们可以有一个适用于许多不同问题的通用状态表示。
• 我们可以构建专门的搜索算法，有效地在这个通用状态表示上操作。
• 我们把可以用这种专门的表示CSPs-Constraint Satisfaction Problems表示的问题类称为CSPs-Constraint Satisfaction Problems。

CSPs: State Representation

The idea: represent states as a vectors of feature values

• A set ofkfeatures (or variables)
• Each variable has a domain of different values,e.g.
  • height ={short, average, tall},
  • weight ={light, average, heavy}
• A state is specified by an assignment of a value for eachvariable.
• A partial state is specified by an assignment of a value tosome of the variables.
• A goal state specified as conditions on the vector of featurevalues.

Formalization of a CSP

• A CSP consists of
  • A set of variablesV1, . . . , Vn
  • For each variable a (finite) domain of possible values Dom[Vi].
  • A set of constraintsC1, . . . , Cm.
• A solution to a CSP is an assignment of a value to all of thevariables such that every constraint is satisfied.
• A CSP is unsatisfiable if no solution exists.
• Each variable can be assigned any value from its domain
  • Vi=dwhered∈Dom[Vi]
• Each constraint C
  • has a set of variables it is over, called its scope,e.g.,C(V1, V2, V4)
  • Acts as a boolean function that maps assignments to thesevariables to true/false,e.g.,
    • C(V1=a, V2=b, V4=c) =True
    • C(V1=b, V2=c, V4=c) =False

Constraints

• Unary Constraints (over one variable)
  • e.g.,C(X) :X= 2;C(Y) :Y >5
• Binary Constraints (over two variables)
  • e.g.,C(X, Y) :X+Y <6
• Higher-order (n-ary) constraints: over 3 or more variables.

Solving CSPs

• We do not care about the sequence of moves needed to get toa goal state.
• We only care about finding a setting of the variables thatsatisfies the goal.
• Thus CSPs can be solved by a specialized version of depthfirst search.
• We can build up to a solution by searching through the spaceof partial assignments.
• In principle, the order in which we assign the variables doesnot matter – eventually they all have to be assigned.
• If we falsify a constraint during the process of building up asolution, we can immediately reject the current partialassignment.

CSP as a Search Problem

• Initial state: empty assignment
• Successor function: a value is assigned to any unassignedvariable, which does not cause any constraint to return false.
• Goal test: the assignment is complete

A generic backtracking algorithm

• We pick a variable*,
• pick a value for it*,
• test the constraints that we can,
• if a constraint is unsatisfied we backtrack,
• otherwise we set another variable.
• When all the variables are set, we’re done.

Backtracking Search

• The algorithm searches a tree of partial assignments.
• Heuristics are used to determine
  • the order in which variables are assigned: PickUnassignedVariable()
  • the order of values tried for each variable.
• The choice of the next variable can vary from branch to branch, e.g.,
  • under the assignment V1=a we might choose to assign V4 next, while under V1=b we might choose to assign V5 next.
• This “dynamically” chosen variable ordering has a tremendous impact on performance.

Forward Checking

• Forward checkingis an extension of backtracking search that employs a “modest” amount of propagation (look ahead).
• When a variable is instantiated we check all constraints that have only one uninstantiatedvariable remaining.
• For that uninstantiatedvariable, we check all of its values, pruning those values that violate the constraint.

Empirically

• FC often is about 100 times faster than BT
• FC with MRV (minimal remaining values) often 10000 timesfaster.
• But on some problems the speed up can be much greater
  • Converts problems that are not solvable to problems that aresolvable
• Still FC is not that powerful.
• Other more powerful forms of constraint propagation are usedin practice

Generalized Arc Consistency (GAC)

• C(X,Y) is consistent iff for every value of X there is somevalue of Y that satisfies C
• C(V1, V2, V3, . . . , Vn)is GAC wrtViiff for every value ofVi,there are values ofV1, . . . , Vi−1, Vi+1, . . . , Vn that satisfyC
• A constraint is GAC iff it is GAC wrt every variable in its scope
• A CSP is GAC iff all of its constraints are GAC
• Say we find a valuedof variableVi that is not consistent wrta constraint
• i.e., there is no assignments to the other variables that satisfythe constraint whenVi=d
• dis said to be arc inconsistent
• We can remove d from the domain ofVias this value cannotlead to a solution
• Much like Forward Checking, but more powerful
  • If d is removed fromCurDom[Vi], it must be the case thatdis arc inconsistent

GAC algorithm

• We make all constraints GAC at every node of the searchspace.
• Like forward checking, GAC could also be performed beforewe even start to search,i.e., before we assign any variables.
• This is accomplished by removing from the domains of thevariables all arc inconsistent values.

Enforce GAC

• A support for V=d in constraint C is an assignment A to all ofthe other variables in scope(C) s.t. A U{V=d}satisfies C.
• Smarter implementations keep track of “supports” to avoidhaving to search through all possible assignments to the othervariables for a satisfying assignment.
• Rather than search for a satisfying assignment to C containingV=d, we check to see if the current support is still valid: i.e.,all values it assigns still lie in the variable’s current domains
• Also we take advantage that a support for V=d, e.g.{V=d,X=a, Y=b, Z=c}is also a support for X=a, Y=b, and Z=c
• However, finding a support for V=d in constraint C still in theworst case requiresO(2k)work, where k is the arity of C.
• Another key development in practice is that for someconstraints this computation can be done in polynomial time.
• e.g., all-diff(V1, . . . , Vn) we can check ifVi=dhas a supportin the current domains of the other variables in polynomialtime using ideas from graph theory.