CSC242 Lecture 2.1 Constraint Satisfaction Problems
CSC242:
Introduction to
Artificial Intelligence
Lecture 2.1
Please put away all electronic devices
Announcements
• Exam 1 has been graded
• Feedback in “My Grades”
• Complaints: email me today
• Help: Study session
• Project 1 is being graded
• Watch BlackBoard for announcements
Announcements
• Project 2 available after class
• Due Sunday October 10
• Before Fall Break
• Exam 2 Thursday October 14
Course Calendar
https://www.cs.rochester.edu/u/ferguson/csc/242/Fall2021/calendar.html
State-Space Search
Problem (Domain):
Problem (Instance):
Solution:
COST : Assigns a cost to each path/step c(s, a, s0)
⟨S, A, ACTIONS, RESULT, COST⟩
ACTIONS : s ∈ S →
{ a ∈ A : a can be executed (is applicable) in s }
RESULT : s ∈ S , a ∈ A →
sʹ ∈ S s.t. sʹ is the result of performing a in s
⟨I ∈ S, G ⊆ S⟩
⟨a1, a2, …, an⟩ ∈ An s.t.
RESULT(··· RESULT(RESULT(I, a1), a2) ···, an) ∈ G
Universal Problem-
Solving Procedure
Initialize the frontier to just I
While the frontier is not empty:
Remove a state s from the frontier
If s ∈ G:
Return solution to s
else:
Add successors(s) to the frontier
Fail!
State
Problem (Domain):
Problem (Instance):
Solution:
COST : Assigns a cost to each path/step c(s, a, s0)
⟨S, A, ACTIONS, RESULT, COST⟩
ACTIONS : s ∈ S →
{ a ∈ A : a can be executed (is applicable) in s }
RESULT : s ∈ S , a ∈ A →
sʹ ∈ S s.t. sʹ is the result of performing a in s
⟨I ∈ S, G ⊆ S⟩
⟨a1, a2, …, an⟩ ∈ An s.t.
RESULT(··· RESULT(RESULT(I, a1), a2) ···, an) ∈ G
Problem (Domain):
Problem (Instance):
Solution:
COST : Assigns a cost to each path/step c(s, a, s0)
⟨S, A, ACTIONS, RESULT, COST⟩
ACTIONS : s ∈ S →
{ a ∈ A : a can be executed (is applicable) in s }
RESULT : s ∈ S , a ∈ A →
sʹ ∈ S s.t. sʹ is the result of performing a in s
⟨I ∈ S, G ⊆ S⟩
⟨a1, a2, …, an⟩ ∈ An s.t.
RESULT(··· RESULT(RESULT(I, a1), a2) ···, an) ∈ G
Problem (Domain):
Problem (Instance):
Solution:
COST : Assigns a cost to each path/step c(s, a, s0)
⟨S, A, ACTIONS, RESULT, COST⟩
ACTIONS : s ∈ S →
{ a ∈ A : a can be executed (is applicable) in s }
RESULT : s ∈ S , a ∈ A →
sʹ ∈ S s.t. sʹ is the result of performing a in s
⟨I ∈ S, G ⊆ S⟩
⟨a1, a2, …, an⟩ ∈ An s.t.
RESULT(··· RESULT(RESULT(I, a1), a2) ···, an) ∈ G
State
public class State {
protected Board board;
protected Player nextToMove;
…
}
public class Board {
int nrows;
int ncols;
Piece[][] grid;
public Board(int nrows, int ncols) {
this.nrows = nrows;
this.ncols = ncols;
this.grid = new Piece[nrows][ncols];
}
…
}
public Player getWinner() {
int nwhite = 0;
int nblack = 0;
for (int c=0; c < this.numColumns; c++) {
for (int r=0; r < this.numRows; r++) {
Piece piece = this.grid[c][r];
if (piece != null) {
if (piece.player == Player.BLACK) {
nblack += 1;
} else if (piece.player == Player.WHITE) {
nwhite += 1;
}
}
}
}
if (nblack == 0) {
return Player.WHITE;
} else if (nwhite == 0) {
return Player.BLACK;
} else {
return null;
}
}
Representation
Representation
• Impose a structure on the representation
of states
Representation
• Impose a structure on the representation
of states
• Using that representation, successor
generation and goal tests are domain-
independent
Representation
• Impose a structure on the representation
of states
• Using that representation, successor
generation and goal tests are domain-
independent
• Can also develop effective problem- and
domain-independent heuristics
Bottom Line
Represent
State
This Way
Write
Code
Once
Solve
Any
Problem
Example
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Assign a color to each region such that no
two neighboring regions have the same color
Variables
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Color WA, NT, Q, NSW, V, SA, T
Values
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Assignment
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Assignment
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Empty assignment: { }
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Assignment
Partial assignment: { WA=red }
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Assignment
Complete assignment:
{ WA=red, NT=red, Q=green, NSW=blue,
V=red, SA=blue, T=green }
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Assign a color to each region such that no
two neighboring regions have the same color
Constraints
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Constraints
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA ≠ NT, WA ≠ SA, NT ≠ Q,
NT ≠ SA, Q ≠ NSW, Q ≠ SA,
NSW ≠ V, NSW ≠ SA, V ≠ SA
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Constraints
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Rule out impossible assignments
WA ≠ NT, WA ≠ SA, NT ≠ Q,
NT ≠ SA, Q ≠ NSW, Q ≠ SA,
NSW ≠ V, NSW ≠ SA, V ≠ SA
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Inconsistency
✘
{ WA=red, NT=red, Q=green, NSW=blue,
V=red, SA=blue, T=green }
WA ≠ NT, WA ≠ SA, NT ≠ Q,
NT ≠ SA, Q ≠ NSW, Q ≠ SA,
NSW ≠ V, NSW ≠ SA, V ≠ SA
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Consistency
(Satisfaction)
✔
{ WA=red, NT=green, Q=red, NSW=green,
V=red, SA=blue, T=red }
WA ≠ NT, WA ≠ SA, NT ≠ Q,
NT ≠ SA, Q ≠ NSW, Q ≠ SA,
NSW ≠ V, NSW ≠ SA, V ≠ SA
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Solution
WA ≠ NT, WA ≠ SA, NT ≠ Q,
NT ≠ SA, Q ≠ NSW, Q ≠ SA,
NSW ≠ V, NSW ≠ SA, V ≠ SA
Complete & Consistent
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
✔
{ WA=red, NT=green, Q=red, NSW=green,
V=red, SA=blue, T=red }
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, ..., Xn }
• D: Set of domains { D1, ..., Dn }
• Each Di : set of values { v1, ..., vki }
• C: Set of constraints { C1, ..., Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, ..., Xn }
• D: Set of domains { D1, ..., Dn }
• Each Di : set of values { v1, ..., vki }
• C: Set of constraints { C1, ..., Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, ..., Xn }
• D: Set of domains { D1, ..., Dn }
• Each Di : set of values { v1, ..., vki }
• C: Set of constraints { C1, ..., Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, ..., Xn }
• D: Set of domains { D1, ..., Dn }
• Each Di : set of values { v1, ..., vki }
• C: Set of constraints { C1, ..., Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, ..., Xn }
• D: Set of domains { D1, ..., Dn }
• Each Di : set of values { v1, ..., vki }
• C: Set of constraints { C1, ..., Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Factored Representation
• Splits a state into factors (attributes,
features, variables) that can have
values
Factored Representation
• Splits a state into factors (attributes,
features, variables) that can have
values
• Factored states can be more or less
similar (unlike atomic states)
Factored Representation
• Splits a state into factors (attributes,
features, variables) that can have
values
• Factored states can be more or less
similar (unlike atomic states)
• Can also represent uncertainty (don’t
know the value of some attribute)
Assignment
Partial assignment: { WA=red }
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
Factored Representation
• Splits a state into factors (attributes,
features, variables) that can have
values
• Factored states can be more or less
similar (unlike atomic states)
• Can also represent uncertainty (don’t
know the value of some attribute)
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, ..., Xn }
• D: Set of domains { D1, ..., Dn }
• Each Di : set of values { v1, ..., vki }
• C: Set of constraints { C1, ..., Cm }
• Solution: Assign to each Xi a value from
Di such that all the Cj are satisfied
Solution
WA ≠ NT, WA ≠ SA, NT ≠ Q,
NT ≠ SA, Q ≠ NSW, Q ≠ SA,
NSW ≠ V, NSW ≠ SA, V ≠ SA
Complete & Consistent
enum Color {red, green, blue}
Color WA, NT, Q, NSW, V, SA, T
✔
{ WA=red, NT=green, Q=red, NSW=green,
V=red, SA=blue, T=red }
State-Space Search for
CSPs
State-Space Search for
CSPs
• States: assignments (possibly partial)
State-Space Search for
CSPs
• States: assignments (possibly partial)
• Actions: pick an unassigned variable and
assign it a value from its domain
State-Space Search for
CSPs
• States: assignments (possibly partial)
• Actions: pick an unassigned variable and
assign it a value from its domain
• Result: extends assignment
State-Space Search for
CSPs
• States: assignments (possibly partial)
• Actions: pick an unassigned variable and
assign it a value from its domain
• Result: extends assignment
• Cost: ?
State-Space Search for
CSPs
• States: assignments (possibly partial)
• Actions: pick an unassigned variable and
assign it a value from its domain
• Result: extends assignment
• Cost: constant
State-Space Search for
CSPs
• States: assignments (possibly partial)
• Actions: pick an unassigned variable and
assign it a value from its domain
• Result: extends assignment
• Cost: constant
• Initial state: empty assignment
State-Space Search for
CSPs
• States: assignments (possibly partial)
• Actions: pick an unassigned variable and
assign it a value from its domain
• Result: extends assignment
• Cost: constant
• Initial state: empty assignment
• Goal states: complete, consistent assignments
State-Space Search for
CSPs
• Search strategy: ?
State-Space Search for
CSPs
• Search strategy: ?
• n variables: depth of solution = n
State-Space Search for
CSPs
• Search strategy: ?
• n variables: depth of solution = n
• Depth-limited search to depth n
State-Space Search for
CSPs
{}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
X1=v1,1
X1=v1,2 X2=v2,1
X2=v2,2
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
...
X1=v1,1
X1=v1,2 X2=v2,1
X2=v2,2
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2 n
{X1=v1,1, ..., Xn=vn,1}
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2 n
{X1=v1,1, ..., Xn=vn,1}
Consistent?
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2 n
{X1=v1,1, ..., Xn=vn,1}
Consistent? Yes: solution!
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2 n
{X1=v1,1, ..., Xn=vn,1}
Consistent? No: Backtrack (keep searching)
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
{X1=v1,1, ..., Xn=vn,1}
n
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ... n×d
X1=v1,1
X1=v1,2 X2=v2,1
X2=v2,2
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ... n×d
{X1=v1,1, X2=v2,1} ... (n-1)×d
X2=v2,1
X2=v2,2
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
{X1=v1,1, ..., Xn=vn,1} 1×d
n×d
(n-1)×d
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
{X1=v1,1, ..., Xn=vn,1} 1×d
n×d
(n-1)×d
(n×d)×((n-1)×d)×((n-2)×d)×...×(2×d)×(1×d)
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2 n
{X1=v1,1, ..., Xn=vn,1} 1×d
n×d
(n-1)×d
O(n!dn)
e5 = 148
5! = 120
0
20
40
60
80
100
120
140
160
0 1 2 3 4 5
exp(x)
(int(x))!
e10 ≈ 22,026
10! = 3,628,800
0
500000
1x106
1.5x106
2x106
2.5x106
3x106
3.5x106
4x106
0 2 4 6 8 10
exp(x)
(int(x))!
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
{X1=v1,1, ..., Xn=vn,1} 1×d
n×d
(n-1)×d
O(n!dn)
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1} {X2=v2,1}{X1=v1,2} {X2=v2,2}... ...
{X1=v1,1, X2=v2,1} ...
X2=v2,1
X2=v2,2
{X1=v1,1, ..., Xn=vn,1} 1×d
n×d
(n-1)×d
O(n!dn) ≫ O(dn)
{}
{X=a} {Y=a}{X=b} {Y=b}
Variables: X, Y
Domains: { a, b }
X←a
X←b Y←a
Y←b
{X=a,
Y=a }
{X=a,
Y=b }
{X=b,
Y=a }
{X=b,
Y=b }
{Y=a,
X=a }
{Y=a,
X=b }
{Y=b,
X=a }
{Y=b,
X=b }
Y←a Y←b Y←a Y←b X←a X←b X←a X←b
{}
{X=a} {Y=a}{X=b} {Y=b}
Variables: X, Y
Domains: { a, b }
X←a
X←b Y←a
Y←b
{X=a,
Y=a }
{X=a,
Y=b }
{X=b,
Y=a }
{X=b,
Y=b }
{Y=a,
X=a }
{Y=a,
X=b }
{Y=b,
X=a }
{Y=b,
X=b }
Y←a Y←b Y←a Y←b X←a X←b X←a X←b
{}
{X=a} {Y=a}{X=b} {Y=b}
Variables: X, Y
Domains: { a, b }
X←a
X←b Y←a
Y←b
{X=a,
Y=a }
{X=a,
Y=b }
{X=b,
Y=a }
{X=b,
Y=b }
{Y=a,
X=a }
{Y=a,
X=b }
{Y=b,
X=a }
{Y=b,
X=b }
Y←a Y←b Y←a Y←b X←a X←b X←a X←b
CSPs are Commutative
• CSPs are commutative because we
reach the same partial assignment
regardless of order
• Need only consider assignment to a
single variable at each node in the
search tree
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1}{X1=v1,2} ...
{X1=v1,1, X2=v2,1} ...
{X1=v1,1, ..., Xn=vn,1} d
d
d
{X1=v1,d}
n
{X1=v1,1, X2=v2,2}
State-Space Search for
CSPs
{}
{X1=v1,1}{X1=v1,2} ...
{X1=v1,1, X2=v2,1} ...
{X1=v1,1, ..., Xn=vn,1} d
d
d
{X1=v1,d}
n
O(dn)
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
∅
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
∅
WA=greenWA=red WA=blueWA
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
∅
WA=greenWA=red WA=blueWA
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
WA ≠ NT
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
Inconsistent!
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
Prune!
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
WA=red,
NT=green
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
WA=red,
NT=green,
Q=green
WA=red,
NT=green,
Q=blue
WA=red,
NT=green,
Q=red
Q
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
WA=red,
NT=green,
Q=green
WA=red,
NT=green,
Q=blue
WA=red,
NT=green,
Q=red
Q
NT ≠ Q
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
WA=red,
NT=green,
Q=green
WA=red,
NT=green,
Q=blue
WA=red,
NT=green,
Q=red
Q
Prune!
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Early Pruning of
Inconsistent States
WA=red,
NT=blue
WA=red,
NT=green
∅
WA=greenWA=red WA=blueWA
WA=red,
NT=redNT
WA=red,
NT=green,
Q=green
WA=red,
NT=green,
Q=blue
WA=red,
NT=green,
Q=red
Q
Backtracking Search
function BT(csp)
return backtrack({}, csp)
function backtrack(assignment, csp)
if (assignment is complete)
return assignment
var = SelectUnassignedVar(csp)
foreach value in OrderDomainValues(var,assignment,csp)
if (value is consistent with assignment)
add
result = backtrack(assignment, csp)
if (result != failure)
return result
else
remove
return failure
AIMA Fig 6.5
Backtracking Search
• DFS search through the space of
assignments
• Assign one variable at a time
• Early pruning of inconsistent states
• Solves ANY CSP
Heuristics for CSPs
• Minimum-remaining values (most
constrained variable)
• Degree heuristic (variable involved in
most constraints with unassigned
variables)
• Least constraining value (if we only
want to find one solution)
But wait, there’s more!
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA r, g, b
NT r, g, b
SA r, g, b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
WA r
NT g
SA b
Q r
NSW g
V r
T r Solution
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA r, g, b
NT r, g, b
SA r, g, b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA r, g, b
NT r, g, b
SA b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Remaining possibilities: 36=729
WA r, g, b
NT r, g, b
SA b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA r, g, b
NT r, g, b
SA b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA,
Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA,
V ≠ SA
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
Remaining possibilities: 25×3=96
WA r, g
NT r, g
SA b
Q r, g
NSW r, g
V r, g
T r, g, b
WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA,
Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA,
V ≠ SA
Constraint Propagation
• Using the constraints to reduce the set
of possible values of a variable, which
can in turn reduce the possible values of
another variable, and so on
• Not a search process!
• Part of state update during state-space
search
Constraint Propagation
• Using the constraints to reduce the set of
possible values of a variable, which can in
turn reduce the possible values of
another variable, and so on
• Not a search process!
• Part of state update in state-space search
• A form of inference
Constraint Propagation
• Good:
• Can significantly reduce the space of
assignments left to search
• Bad:
• It takes time. How much?
Constraints
• Unary constraint: one variable
• e.g., NSW ≠ red, Xi is even, Xi = 2
• Binary constraint: two variables
• e.g., NSW ≠ WA, Xi > Xj, Xi+Xj = 2
• “Global” constraint: more than two vars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
Constraints
• Unary constraint: one variable
• e.g., NSW ≠ red, Xi is even, Xi = 2
• Binary constraint: two variables
• e.g., NSW ≠ WA, Xi > Xj, Xi+Xj = 2
• “Global” constraint: more than two vars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
• Can be reduced to set of binary constraints
(possibly inefficiently)
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA
NT
SA
Q
NSW
V
T
WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA,
Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA,
V ≠ SA
Constraints
• Unary constraint: one variable
• e.g., NSW ≠ red, Xi is even, Xi = 2
• Binary constraint: two variables
• e.g., NSW ≠ WA, Xi > Xj, Xi+Xj = 2
• “Global” constraint: more than two vars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
• Can be reduced to set of binary constraints
(possibly inefficiently)
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
SA≠g
WA r, g, b
NT r, g, b
SA r, g, b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
Unary constraint
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
SA≠g
WA r, g, b
NT r, g, b
SA r, g, b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
Unary constraint
Western
Australia
Northern
Territory
South
Australia
Queensland
New
South
Wales
Victoria
Tasmania
WA r, g, b
NT r, g, b
SA r, b
Q r, g, b
NSW r, g, b
V r, g, b
T r, g, b
SA≠g
Unary constraint
Node Consistency
• Every possible value of every variable is
consistent with the unary constraints
Node Consistency
• Every possible value of every variable is
consistent with the unary constraints
• Propagate unary constraints at the
start
• Inconsistent? Fail!
• Otherwise never have to test them
again
Node Consistency
• Every possible value of every variable is
consistent with the unary constraints
• Propagate unary constraints at the start
• Inconsistent? Fail!
• Otherwise never have to test them again
• Complexity: Each variable, each value, each
unary constraint
Arc Consistency
• Unary constraint: one variable
• e.g., NSW ≠ red, Xi is even, Xi = 2
• Binary constraint: two variables
• e.g., NSW ≠ WA, Xi > Xj, Xi+Xj = 2
• “Global” constraint: more than two vars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
• Can be reduced to set of binary constraints
(possibly inefficiently)
Arc Consistency
Xi is arc-consistent w.r.t. Xj if
for every value in the domain Di,
there is some value in the domain Dj
that satisfies the binary constraint
on the arc (Xi, Xj)
Arc Consistency
X Y
Y=X2
{ 0,1,2,3,4,5,6,7,8,9 } { 0,1,2,3,4,5,6,7,8,9 }
# possible assignments: 10×10 = 100
Arc Consistency
X Y
Y=X2
{ 0,1,2,3,4,5,6,7,8,9 } { 0,1,2,3,4,5,6,7,8,9 }
Make X arc-consistent with respect to Y
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,2,3,4,5,6,7,8,9 }
X arc-consistent with respect to Y
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,2,3,4,5,6,7,8,9 }
Make Y arc-consistent with respect to X
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,4,9 }
Y arc-consistent with respect to X
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,4,9 }
X and Y arc-consistent
Arc Consistency
X Y
Y=X2
{ 0,1,2,3 } { 0,1,4,9 }
# possible assignments: 4×4 = 16
X and Y arc-consistent
AC-3
boolean revise(csp, i, j) {
boolean changed = false
foreach vi in Di {
boolean ok = false
foreach vj in Dj {
if (
ok = true
}
}
if (!ok) {
delete vi from Di
changed = true
}
}
return changed
}
boolean AC3(csp) {
Set queue = all arcs in csp
while (queue is not empty) {
if (revise(csp, i, j)) {
if Di is empty {
return false
}
foreach k in neighbors(i) {
add
}
}
}
return true
}
AC-3 Analysis
• CSP with n variables, domain size O(d),
c constraints (arcs)
• Each arc can be inserted in the queue at
most d times
• Checking a single arc takes O(d 2) time
• Total time: O(cd 3)
• Independent of n
More Constraint
Propagation
• Path consistency
• k-consistency
• Generalization of node (1-), arc (2-), and
path (3-) consistency
• Establishing k-consistency is exponential in
k
• Typically use node- and arc-consistency
and rarely path-consistency
Constraint Propagation
• “After constraint propagation, we are
left with a CSP that is equivalent to
the original CSP—they both have the
same solutions—but the new CSP will in
most cases be faster to search because
its variables have smaller domains.”
State-Space
Search
Constraint
Propagation
(inference)
Interleaving Search and
Inference
• After each choice during search, we
can perform inference to reduce future
search
Interleaving Search and
InferenceCSP:
• Variables
• Domains
• Constraints Node Consistency
Arc Consistency (AC-3)
Solved?
Assign a variable
OK
No
Backtrack
No
Yes
Done!
FailInconsistent?
Inconsistent?
Interleaving Search and
Inference
• After each choice during search, we
can perform inference to reduce future
search
• Forward checking
• MAC: Maintaining Arc Consistency
• Bottom line: Cost of inference is
subsumed by cost of search, so do it
Solving CSPs
• Search through space of assignments
• Commutativity => Only have to
consider assignment to one variable
at a time
• Interleave search and inference
• Constraint propagation to reduce
domains of variables for subsequent
search
Constraint Satisfaction
• Impose a structure on the representation of
states: Variables, Domains, Constraints
• Backtracking (DFS) search for complete,
consistent assignment of values to variables
• Inference (constraint propagation) can reduce
the domains of variables
• Preprocessing and/or interleaved with search
• Useful problem-independent heuristics
CSP Secret Sauce
• Factored representation of state:
• Variables, Domains, Constraints
• Allows:
• Early pruning of inconsistent states
• Inference during search to reduce
alternatives
For next time:
AIMA 7.0 – 7.4