CS188 – Week 4 Discussion NoteNuttapong Chentanez

Constraints Satisfaction Problem (CSP)

Set of variables: X1, X2, …. , Xn

Each variables has a non-empty domain Di of possible values

Set of constraints: C1, C2, …., Cm involve some subset of variables

Consistent assignment, Complete assignment

Solution = Complete & Consistent assignment

How to solve CSP?

Pick a variable, then pick a value that is consistent, go to the next variable, until all variables are assigned or consistent assignment does not exist. Does the order of variable chosen matter? How many possible assignments (in term of |Di| )?

Pseudo-Code

CSP-solve(numUnassigned)

If (numUnassigned == 0):

Found = True;

Solution = (X1, …., Xn)

Done

Pick an unassigned variable, Xi

Pick a consistent value from diremaining Di

If (can’t): return

Xi = di

PruneDomains()

CSP-solve(numUnassigned – 1)

Xi = unassigned

CSP-wrapper()

Set X1 … Xn to unassigned

Found = False

CSP-solve(n)

Heuristics for solving CSP

Picking variables:

1. Minimum remaining values (MRV) – Pick variable with smallest number of values it can be, that still consistent. Why?Will make it fail fast. Why we want to fail fast? Better know sooner than later. Example: X1 with 2 different values left {1,2}, X2 with 100 different values left {1,..100}, X3 with 50 different values left {0,..49}. Constraint: X2 and X3 has to be < X1. If choose X1 first, will eliminate lots of possibility for X2 and X3

2. Degree Heuristic – Pick variable that involves in largest number of constraints. Why?

Rule out most possibility fast (if no-solution exist, will fail fast. If solution exist, will find one fast) Will likely to conflict with other variable and hence fail fast. Example: X0 can be {1,2}. Must be same as X1, X2, X3 {1,3} Star graph. Picking X0 = 1will force X1, X2, X3 to be 1quickly.

Picking value for a variable:

1. Least-constraining value. Pick Xi that rules out fewest choices for neighboring variables in the constraint graph.Why?We want to pick value that will likely to find solution. (We don’t want to fail anymore.) Can someone tell me why this is different from when you pick variable? The reason is that we need to try all consistent values for this variable anyway (in case no solution exist), so we would pay the same price anyway. But if sol exist, we want to find it fast.

Pruning (Constraint Propagation) – Early detection of failure that can be implied (cheaply) from current assignment of variables.

Forward Checking:

When assign Xi, look at each unassigned variable Xj that is connected to Xi, delete the value of Xj that inconsistent with the chosen value of Xi. If any empty, fail immediately.If one value left, assign the value to Xj and then check the neighbors of Xj. When would this be useful? Will help detecting inconsistent assignment faster. Eg. Same example as Degree Heuristic. If we pick X0 = 2, will fail immediately without having to get to the assignment of X1, X2, X3

Arc Consistency for (XiXj):

(Xi Xj) is consistent if for every value of Xi there is some value of Xj that is consistent

What’s the cost of checking if (Xi Xj) is consistent, in terms of |Di|, |Dj|? |Di| |Dj|

Does Xi Xj implies Xj Xi ? No. Example? X1 < X2, X1{1,3} X3{0,7}

How can we use this information? Eliminate inconsistency to reduce domain size

When to check for Arc Consistency? Every time we assign a value to a variable Xi, check all arc Xk Xi. If we reduce domain of some Xk, then need to check Xq Xk as well. AC-3

This improves the performance of the algorithm significantly.

A partial assignment is arc-consistent if all arcs are consistent.

k-consistency of a CSP:

If for any consistent assignment to a subset of size k-1 of variables, it’s possible to assign the value of the kth variable consistently. How to check? |Di||Dj||Dk| bruteforce

Strongly k-consistent, if is 1..k consistent. If we know a CSP is strongly n-consistent, how to solve CSP, at what cost? O(N*max|Di|) for each Xj just find value from Dj that consistent with all previously assigned variables

Can use k-consistent to reduce domain, but can be costly.

Problems:

(Modified from a homework from AI class of U of Pittsburgh)

Each variable can be {0..9}. The edge between variables (a,b) with label C indicates the constraints (a mod C == b mod C)

List the variables, domain, and binary constraints:

List theremaining possible values of each variablethat can be inferred after the assignment of {x = 2, y = 0, t = 0} by

  1. Forward checking

When x = 2, z in {2,5,8}

When y = 0, z = 5, so w in {1,5,9}

When t = 0, v = 0, so u in {0, 3, 6, 9}

So x=2, y = 0, t = 0, z = 5, v = 0, w in {1,5,9}, u in {0,3,6,9}

  1. Arc consistency

Everything forward checking can do, arc consistency can do as well: x=2, y = 0, t = 0, z = 5, v = 0, w in {1,5,9}, u in {0,3,6,9}

Check wu, If w = 1, u must be 1,4,7. not true, hence w can’t be 1

Now w in {5,9}. If w = 5, u in {2,5,8}. not true, hence w can’t be 5

So w = 9.

So x = 2, y = 0, t = 0, z = 5, v = 0, w = 9, u in {0, 3, 6,9}

Find one solution to this CSP

From arc consistency, we can pick u to be 0 or 3 or 6 or 9 and then done

Converting Arbitrary Constraints to Binary Constraints

Cryptography

SEND

MORE

====

MONEY

Write the variables, the domains and the constraint graph. Annotate each constraints.

Convert this problem into binary constraints. Ideas? How many variables you need to introduce? What are their domains? Constraints?