04.Constraints Satisfaction Problem (CSP)

Constraints Satisfaction Problem (CSP)

Some problems could be classified as CSP when we can define these elements:

• A set of variables $X_1...X_n$
• For each variable $X_i$ we associate a domain $X_i$ = set of values that $X_i$ can assume
• The set of constraints $C_1...C_n$ which specifies allowable combinations of values. The constaints can be:
  • unary (they involve only one variable),
  • binary (they involve two variables)
  • n-nary It’s proved that any n-nary constraint can be turned into a set of binary constraints.

Constraint propagation.

We use constraints in order to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.

• 1-consistency (node-consistency): that is based basically on the domains of variables.
• 2-consistency (Arc-consistency): the one we will check using the AC-3 algorithm. $X_i\to X_j$ is arc consistency if for each value of $X_i$ exists a value in $X_j$ .
• Path-consistency: extension of the previous to more variables

AC-3 arc consistency algorithm that can be applied only to all CSPs formulated with binary constraints. The algorithm is very intuitive and simple.

CSP as Search Problem

An important behavour of the CSPs is that they are commutative! This reduces a lot the branching factor on our trees when we try to perform a search tree to solve this kind of problems. With this consideration with ended up we can perform a depth search tree giving possible values from the domain to the variables. Also we could perform the DFS with some variants:

• Backtracking

• Forward Checking: using AC-3 each time a variable is assigned. For each variable not assigned that involves X (which is just assigned) is checked the arc-consistency.

• MRV (Minimum Remaing Values): When we try to assign a value to a variable we follow a policy to choose which variables assign and not just take a random one. So we choose the variable with minimum ‘legal’ values in the domain.

• LCV (Least Constraints Value) : the MRV policy interest the variable choosen for the next assigment. The LCV policy tells us which value assign to the variable: we choose the value that is involved in the less numbe of constraints with other values.