1 of 10

Constraint Propagation

2 of 10

Constraint Propagation

  • In regular state-space search, an algorithm can do only one thing: search. In CSPs there is a choice: an algorithm can search (choose a new variable assignment from several possibilities) or do a specific type of inference called constraint propagation:
  • using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.
  • Constraint propagation may be intertwined with search, or it may be done as a preprocessing step, before search starts. Sometimes this preprocessing can solve the whole problem, so no search is required at all.
  • local consistency. If we treat each variable as a node in a graph and each binary constraint as an arc, then the process of enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.
  • There are different types of local consistency:
    • Node Consistency
    • Arc consistency
    • Path consistency
    • K-consistency
    • Global constraints

3 of 10

Constraint Propagation

Node consistency:

  • A single variable (corresponding to a node in the CSP network) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.

For example:

  • in the variant of the Australia map-coloring problem where South Australians dislike green, the variable SA starts with domain {red , green, blue}, and we can make it node consistent by eliminating green, leaving SA with the reduced domain {red , blue}.
  • We say that a network is node-consistent if every variable in the network is node-consistent.

Arc Consistency:

  • A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints.
  • More formally, Xi is arc-consistent with respect to another variable Xj if for every value in the current domain Di there is some value in the domain Dj that satisfies the binary constraint on the arc (Xi,Xj).
  • A network is arc-consistent if every variable is arc consistent with every other variable.
  • For example, consider the constraint Y = X 2 where the domain of both X and Y is the set of digits.

(X, Y ), {(0, 0), (1, 1), (2, 4), (3, 9))} .

4 of 10

Constraint Propagation

Arc Consistency:

​

5 of 10

Constraint Propagation

Arc Consistency:

  • AC-3 maintains a queue of arcs which initially contains all the arcs in the CSP.
  • AC-3 then pops off an arbitrary arc (Xi, Xj) from the queue and makes Xi arc-consistent with respect to Xj.
  • If this leaves Di unchanged, just moves on to the next arc;
  • But if this revises Di, then add to the queue all arcs (Xk, Xi) where Xk is a neighbor of Xi.
  • If Di is revised down to nothing, then the whole CSP has no consistent solution, return failure;
  • Otherwise, keep checking, trying to remove values from the domains of variables until no more arcs are in the queue.
  • The result is an arc-consistent CSP that have the same solutions as the original one but have smaller domains.
  • The complexity of AC-3:
  • Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Checking consistency of an arc can be done in O(d2) time, total worst-case time is O(cd3).

6 of 10

Constraint Propagation

Path Consistency:

  • Path consistency: A two-variable set {Xi, Xj} is path-consistent with respect to a third variable Xm if, for every assignment {Xi = a, Xj = b} consistent with the constraint on {Xi, Xj}, there is an assignment to Xm that satisfies the constraints on {Xi, Xm} and {Xm, Xj}.
  • Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.

K-consistency

  • K-consistency: A CSP is k-consistent if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.
  • 1-consistency = node consistency; 2-consisency = arc consistency; 3-consistensy = path consistency.
  • A CSP is strongly k-consistent if it is k-consistent and is also (k - 1)-consistent, (k – 2)-consistent, … all the way down to 1-consistent.
  • A CSP with n nodes and make it strongly n-consistent, we are guaranteed to find a solution in time O(n2d).
  • But algorithm for establishing n-consitentcy must take time exponential in n in the worse case, also requires space that is exponential in n.

​

7 of 10

Constraint Propagation

Global Constraint:

  • A global constraint is one involving an arbitrary number of variables (but not necessarily all variables). Global constraints can be handled by special-purpose algorithms that are more efficient than general-purpose methods.
  • 1) inconsistency detection for Alldiff constraints
  • A simple algorithm: First remove any variable in the constraint that has a singleton domain, and delete that variable’s value from the domains of the remaining variables. Repeat as long as there are singleton variables. If at any point an empty domain is produced or there are more variables than domain values left, then an inconsistency has been detected.
  • A simple consistency procedure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constrains.
  • 2) inconsistency detection for resource constraint (the atmost constraint)
  • We can detect an inconsistency simply by checking the sum of the minimum of the current domains;

Example:

  • Atmost(10, P1, P2, P3, P4): no more than 10 personnel are assigned in total.
  • If each variable has the domain {3, 4, 5, 6}, the Atmost constraint cannot be satisfied.
  • We can enforce consistency by deleting the maximum value of any domain if it is not consistent with the minimum values of the other domains.
  • e.g. If each variable in the example has the domain {2, 3, 4, 5, 6}, the values 5 and 6 can be deleted from each domain.

​

8 of 10

Constraint Propagation

3) inconsistency detection for bounds consistent

  • For large resource-limited problems with integer values, domains are represented by upper and lower bounds and are managed by bounds propagation.

Example:

  • suppose there are two flights F1 and F2 in an airline-scheduling problem, for which the planes have capacities 165 and 385, respectively. The initial domains for the numbers of passengers on each flight are
  • D1 = [0, 165] and D2 = [0, 385].
  • Now suppose we have the additional constraint that the two flight together must carry 420 people: F1 + F2 = 420. Propagating bounds constraints, we reduce the domains to
  • D1 = [35, 165] and D2 = [255, 385].
  • A CSP is bounds consistent if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.

​

9 of 10

Constraint Propagation

10 of 10

Constraint Propagation

Sudoku

  • A Sudoku puzzle can be considered a CSP with 81 variables, one for each square. We use the variable names A1 through A9 for the top row (left to right), down to I1 through I9 for the bottom row. The empty squares have the domain {1, 2, 3, 4, 5, 6, 7, 8, 9} and the pre-filled squares have a domain consisting of a single value.
  • There are 27 different Alldiff constraints: one for each row, column, and box of 9 squares:
  • Alldiff(A1, A2, A3, A4, A5, A6, A7, A8, A9)
  • Alldiff(B1, B2, B3, B4, B5, B6, B7, B8, B9)
  • …
  • Alldiff(A1, B1, C1, D1, E1, F1, G1, H1, I1)
  • Alldiff(A2, B2, C2, D2, E2, F2, G2, H2, I2)
  • …
  • Alldiff(A1, A2, A3, B1, B2, B3, C1, C2, C3)
  • Alldiff(A4, A5, A6, B4, B5, B6, C4, C5, C6)

​