Constraint Satisfaction Problems
1
Constraint satisfaction problems (CSPs)
Standard search problem:
state is a “black box”—any old data structure
that supports goal test, eval, successor
CSP:
state is defined by variables Xi with values from domain Di
goal test is a set of constraints specifying
allowable combinations of values for subsets of variables
Simple example of a formal representation language
Allows useful general-purpose algorithms with more power than standard search
algorithms
General-purpose algorithms with atomic agent: State is a number, we cannot
look inside it
CSP: State is a set of variables with values, we can understand state better
3
Example: Map-Coloring
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
Variables W A, N T , Q, N SW , V , SA, T
Domains Di = {red, green, blue}
Constraints: adjacent regions must have different colors
e.g., W A 6= N T (if the language allows this), or
(W A, N T ) ∈ {(red, green), (red, blue), (green, red), (green, blue), . . .}
4
Example: Map-Coloring contd.
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
Solutions are assignments to each variable satisfying all constraints, e.g.,
{W A = red, N T = green, Q = red, N SW = green, V = red, SA = blue, T = green}
5
Constraint graph
Binary CSP: each constraint relates at most two variables
Constraint graph: nodes are state variables, arcs show constraints
NT
Q Earlier: each state was node!
WA
SA NSW
V
Victoria
General-purpose CSP algorithms use the graph structure to speed up search.
E.g., Tasmania is an independent subproblem!
6
Varieties of CSPs
Discrete variables
finite domains; size d ⇒ O(dn) complete assignments if there are n variables
♦ e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete)
infinite domains (integers, strings, etc.)
♦ e.g., job scheduling, variables are start/end days for each job (Orion room allotment)
♦ need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3
♦ linear constraints solvable, nonlinear undecidable
Continuous variables
♦ e.g., start/end times for Hubble Telescope observations
♦ linear constraints solvable in poly time by LP methods
7
Varieties of constraints
Unary constraints involve a single variable,
e.g., SA 6= green
Binary constraints involve pairs of variables,
e.g., SA 6= W A
Higher-order constraints involve 3 or more variables,
e.g., cryptarithmetic column constraints
Preferences (soft constraints), e.g., red is better than green
often representable by a cost for each variable assignment
→ constrained optimization problems
8
Example: Cryptarithmetic
T WO F T U W R O
+ T WO
F O U R
X3 X2 X1
Variables: F T U W R O X1 X2 X3 X1, X2, X3, are carry variables
Domains: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Constraints
alldiff(F,T,U,W,R,O)
O + O = R + 10 · X1
W + W + X1 = U + 10 · X2,
etc.
9
Real-world CSPs
Assignment problems
e.g., who teaches what class
Timetabling problems
e.g., which class is offered when and where?
Hardware configuration
Spreadsheets
Transportation scheduling
Factory scheduling
Floorplanning
Notice that many real-world problems involve real-valued variables
10
Standard search formulation (incremental)
Let’s start with the straightforward, dumb approach, then fix it
States are defined by the values assigned so far
♦ Initial state: the empty assignment, { }
♦ Successor function: assign a value to an unassigned variable
that does not conflict with current assignment.
⇒ fail if no legal assignments (not fixable!)
♦ Goal test: the current assignment is complete
1) This is the same for all CSPs!
2) Every solution appears at depth n with n variables
⇒ use depth-first search
3) Path is irrelevant, so can also use complete-state formulation
4) b=(n − `)d at depth `, hence n!dn leaves!!!! >dn because there are repititions
n.d times (n-1).d times (n-2).d times ... times 1.d
11
Backtracking search
Variable assignments are commutative, i.e.,
[W A = red then N T = green] same as [N T = green then W A = red]
Only need to consider assignments to a single variable at each node
⇒ b = d and there are dn leaves
Depth-first search for CSPs with single-variable assignments
is called backtracking search
Backtracking search is the basic uninformed algorithm for CSPs
Can solve n-queens for n ≈ 25
12
Backtracking search
function Backtracking-Search(csp) returns solution/failure
return Recursive-Backtracking({ }, csp)
function Recursive-Backtracking(assignment, csp) returns soln/failure
if assignment is complete then return assignment
var ← Select-Unassigned-Variable(Variables[csp], assignment, csp)
for each value in Order-Domain-Values(var, assignment, csp) do
if value is consistent with assignment given Constraints[csp] then
add {var = value} to assignment
result ← Recursive-Backtracking(assignment, csp)
if result 6= failure then return result
remove {var = value} from assignment
return failure
13
Backtracking example
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
14
Backtracking example
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
15
Backtracking example
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
If Northern Territorry is colored Red,
do backtracking because constraint
violated
16
Backtracking example
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
Inference: this state will not lead to
solution.
because of South Australia has no value
remaining to be assigned.
But our algo does not know that there
will not be solution.
17
Improving backtracking efficiency
General-purpose methods can give huge gains in speed:
1. Which variable should be assigned next?
2. In what order should its values be tried?
3. Can we detect inevitable failure early?
4. Can we take advantage of problem structure?
18
Minimum remaining values
Minimum remaining values (MRV):
choose the variable with the fewest legal values
Pros: chooses a variable that is most likely to Northern
Territory
cause a failure soon, thereby pruning the Western
Australia
Queensland
search tree South
Australia
New South Wales
Cons: does not help at all in choosing the first Victoria
region to color because initially every region
as three legal colors Tasmania
19
Degree heuristic
Tie-breaker among MRV variables
Degree heuristic:
choose the variable with the most constraints on remaining variables
thus reducing branching factor on future choices
For all, MRV is MRV of WA and Q are
For all, MRV is
same: 2 (tie) same: 1 (tie)
same: 3 (tie)
Remaining Degree Remaining Degree of Northern
For all, Remaining Territory
is max for NT, Q, WA is 0, of Q is 1 Western Queensland
Degree is max for Australia
SA: 5 NSW: 2 (tie)
So, color Q South
Australia
New South Wales
So, color SA So, choose and
color randomly Victoria
Tasmania
Question: Which value should I assign first? 20
Least constraining value
Given a variable, choose the least constraining value:
the one that rules out the fewest values in the remaining variables
Allows 1 value for SA
Allows 0 values for SA
This heuristic is trying to leave the maximum
flexibility for subsequent variable assignments
Northern
Territory
Western Queensland
Australia
South
Combining these three heuristics makes 1000 queens feasible Australia
New South Wales
Victoria
Tasmania
21
Constraint Propagation
So far the search algorithm considered the constraints on a variable
only at the time the variable is chosen
Looking at some of the constraints
earlier in the search, or
even before the search has started,
can drastically reduce the search space
Forward checking
Idea: Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
WA NT Q NSW V SA T
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
Tasmania
22
Forward checking
Idea: Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
WA NT Q NSW V SA T
Northern
Territory
Western Queensland
Australia
South
Australia
New South Wales
Victoria
23
Tasmania
Forward checking
Idea: Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
WA NT Q NSW V SA T
NT
Q
WA
SA
NSW
24
T
Forward checking
Idea: Keep track of remaining legal values for unassigned variables
Terminate search when any variable has no legal values
WA NT Q NSW V SA T
backtrack;
go to prev state; NT
Can we do better? assign other WA
Q
Before assigning Blue to Victoria, can we
SA
legal color (red/ NSW
predict that Blue should not be assigned? green) to V
Victoria
25
T
Constraint propagation
Forward checking propagates information from assigned to unassigned vari-
ables, but doesn’t provide early detection for all failures:
WA NT Q NSW V SA T
N T and SA cannot both be blue!
NT
This is like propagating information from one unassigned variable to WA
Q
unassigned variable. SA
NSW
Forward checking cannot do this. To do this, use Arc Consistency. V
T
Constraint propagation repeatedly enforces constraints locally
26
Arc consistency
Simplest form of propagation makes each arc consistent
X → Y is consistent iff WA
NT
Q
for every value x of X there is some allowed y SA
NSW
WA NT Q NSW V SA T
Inference procedure: If for some value of x, there is no allowed value of y,
that value of x is not possible,
so remove it.
It is possible that for some value of z, there is an allowed value of x,
but if that x value has been removed (above), remove the value of z.
And so on..
27
Arc consistency
Simplest form of propagation makes each arc consistent
X → Y is consistent iff WA
NT
Q
for every value x of X there is some allowed y SA
NSW
WA NT Q NSW V SA T
For value blue in NSW, there is no allowed value in SA,
so remove blue in NSW
28
Arc consistency
Simplest form of propagation makes each arc consistent
X → Y is consistent iff WA
NT
Q
for every value x of X there is some allowed y SA
NSW
WA NT Q NSW V SA T
If X loses a value, neighbors of X need to be rechecked
29
Arc consistency
Simplest form of propagation makes each arc consistent
X → Y is consistent iff WA
NT
Q
for every value x of X there is some allowed y SA
NSW
WA NT Q NSW V SA T
Since SA is empty,
don't proceed,
If X loses a value, neighbors of X need to be rechecked backtrack
Arc consistency detects failure earlier than forward checking
Can be run as a preprocessor or after each assignment
30
Arc consistency
Arc consistency
Arc consistency
Arc consistency detects failure earlier than forward checking,
{R,G}
But sometimes may not detect all failures;
All three arcs (AB, BC, CA are consistent); A A≠B
but it will fail later. B≠C
C≠A
read "k-consistency" for further knowledge;
B C
Arc consistency is k-consistency with k=2. {R,G} {R,G}
k=3 will be able to detect failure here by checking
<A-B-C> = {RRR, RRG, RRB, RGR, RGG, ..};
But as k increases, complexity increases: O(dk)
30
Arc consistency algorithm
function AC-3( csp) returns the CSP, possibly with reduced domains
inputs: csp, a binary CSP with variables {X1, X2, . . . , Xn}
local variables: queue, a queue of arcs, initially all the arcs in csp
while queue is not empty do
(Xi, Xj ) ← Remove-First(queue)
if Remove-Inconsistent-Values(Xi , Xj ) then
for each Xk in Neighbors[Xi] do
add (Xk , Xi) to queue
function Remove-Inconsistent-Values( Xi , Xj ) returns true iff succeeds
removed ← false
for each x in Domain[Xi] do
if no value y in Domain[Xj ] allows (x,y) to satisfy the constraint Xi ↔ Xj
then delete x from Domain[Xi ]; removed ← true
return removed
O(n2d3), can be reduced to O(n2d2) (but detecting all failures is NP-hard)
n variables; n2 arcs in constraint graph; each arc can be checked d times because
each variable can take max d values & we invoke arc consistency when one value 31
in a variable is removed; each arc consistency check requires d2 time. So, O(n2d3)
Backtracking Search with Arc consistency
At a current node,
run arc consistency and remove values which are not possible
=> MRV set is pruned
Assign the best value from the remaining set of values (based on
Minimun remaining values and Degree heuristic)
=> we have reached a new node
run arc consistency and repeat
Either solution is obtained or failure is detected
This is search with inference, i.e., intelligent search.
Only search is slow (exponential): O(bd)
Only inference is slow (exponential), if k is large in k-consistency: O(n2dk).
search with inference is faster with k=2 or 3.
31