程序代做CS代考 CSC242: Introduction to Artificial Intelligence

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

State-Space Search

Problem (Domain):
⟨S, A, ACTIONS, RESULT, COST⟩
{ a ∈ A : a can be executed (is applicable) in s }
ACTIONS :s∈S→ RESULT : s ∈ S , a ∈ A →
sʹ ∈ S s.t. sʹ is the result of performing a in s COST : Assigns a cost to each path/step c(s, a, s0 )
Problem (Instance):
⟨I ∈ S, G ⊆ S⟩
Solution: ⟨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):
⟨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
COST : Assigns a cost to each path/step c(s, a, s0 )
Problem (Instance):
⟨I ∈ S, G ⊆ S⟩
Solution: ⟨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;
public Player getWinner() {
int nwhite = 0;
}
} …
}
if (nblack == 0) {
return Player.WHITE;
} else if (nwhite == 0) {
return Player.BLACK;
} else {
return null;
}
}
int ncols;
Piece[][] grid;
public Board(int nrows, int ncols) {
this.nrows = nrows;
this.ncols = ncols;
this.grid = new Piece[nrows][ncols];
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 nwhite += 1; } } } . 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 Represent State This Way Bottom Line Write Solve Code Any Once Problem Example Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Assign a color to each region such that no two neighboring regions have the same color Variables Color WA, NT, Q, NSW, V, SA, T Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Values Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Assignment Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Assignment Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Empty assignment: { } Assignment Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Western Australia Northern Territory Queensland South Australia New South Wales Victoria Tasmania Partial assignment: { WA=red } Assignment Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Western Australia Northern Territory Queensland South Australia New South Wales Victoria Tasmania Complete assignment: { WA=red, NT=red, Q=green, NSW=blue, V=red, SA=blue, T=green } Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Assign a color to each region such that no two neighboring regions have the same color Constraints Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Constraints Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Constraints Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA Rule out impossible assignments Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Inconsistency Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA { WA=red, NT=red, Q=green, NSW=blue, V=red, SA=blue, T=green } ✘ Consistency (Satisfaction) Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA { WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red } ✔ Solution Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA { WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red } Complete & Consistent ✔ 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 Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} Western Australia Northern Territory Queensland South Australia New South Wales Victoria Tasmania Partial assignment: { WA=red } 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 Color WA, NT, Q, NSW, V, SA, T enum Color {red, green, blue} WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA { WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=red } Complete & Consistent ✔ 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,2 X1=v1,2 {X1=v1,1}{X1=v1,2} ... X2=v2,1 {X2=v2,1}{X2=v2,2} ... State-Space Search for CSPs X1=v1,1 {} X2=v2,2 X1=v1,2 {X1=v1,1}{X1=v1,2} ... X2=v2,1 X =v ... 2 2,2 X2=v2,1 {X2=v2,1}{X2=v2,2} ... {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... {X1=v1,1, ..., Xn=vn,1} n X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... {X1=v1,1, ..., Xn=vn,1} Consistent? n X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... {X1=v1,1, ..., Xn=vn,1} Consistent? Yes: solution! n X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... n X2=v2,2 {X1=v1,1, ..., Xn=vn,1} Consistent? No: Backtrack (keep searching) State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... {X1=v1,1, ..., Xn=vn,1} n X2=v2,2 State-Space Search for CSPs X1=v1,1 {} X2=v2,2 X1=v1,2 {X1=v1,1}{X1=v1,2} ... X2=v2,1 {X2=v2,1}{X2=v2,2} ... n×d State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... n×d X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... (n-1)×d X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... n×d X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... (n-1)×d {X1=v1,1, ..., Xn=vn,1} 1×d X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... n×d X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... (n-1)×d {X1=v1,1, ..., Xn=vn,1} 1×d (n×d)×((n-1)×d)×((n-2)×d)×...×(2×d)×(1×d) X2=v2,2 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... n×d X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} n ... (n-1)×d 1×d X2=v2,2 {X1=v1,1, ..., Xn=vn,1} O(n!dn) e5 = 148 5! = 120 160 140 120 100 80 60 40 20 0 012345 exp(x) (int(x))! e10 ≈ 22,026 10! = 3,628,800 4x106 3.5x106 3x106 2.5x106 2x106 1.5x106 1x106 500000 0 0 2 4 6 8 10 exp(x) (int(x))! State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... n×d X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... (n-1)×d X2=v2,2 {X1=v1,1, ..., Xn=vn,1} 1×d O(n!dn) State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X2=v2,1}{X2=v2,2} ... n×d X2=v2,1 {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... (n-1)×d {X1=v1,1, ..., Xn=vn,1} 1×d O(n!dn) ≫ O(dn) X2=v2,2 Variables: X, Y Domains: { a, b } X←a {} Y←b X←b Y←a {X=a} {X=b} {Y=a} {Y=b} Y←a Y←b Y←a Y←b X←a X←b X←a X←b {X=a, {X=a, {X=b, {X=b, {Y=a, {Y=a, {Y=b, {Y=b, Y=a} Y=b} Y=a} Y=b} X=a} X=b} X=a} X=b} Variables: X, Y Domains: { a, b } X←a {} Y←b X←b Y←a {X=a} {X=b} {Y=a} {Y=b} Y←a Y←b Y←a Y←b X←a X←b X←a X←b {X=a, {X=a, {X=b, {X=b, {Y=a, {Y=a, {Y=b, {Y=b, Y=a} Y=b} Y=a} Y=b} X=a} X=b} X=a} X=b} Variables: X, Y Domains: { a, b } X←a {} Y←b X←b Y←a {X=a} {X=b} {Y=a} {Y=b} Y←a Y←b Y←a Y←b X←a X←b X←a X←b {X=a, {X=a, {X=b, {X=b, {Y=a, {Y=a, {Y=b, {Y=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 State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X1=v1,d} d {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... d n {X1=v1,1, ..., Xn=vn,1} d State-Space Search for CSPs {} {X1=v1,1}{X1=v1,2} ... {X1=v1,d} d {X1=v1,1, X2=v2,1}{X1=v1,1, X2=v2,2} ... d n {X1=v1,1, ..., Xn=vn,1} d O(dn) Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA WA=red WA=green WA=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA WA=red WA=green WA=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales WA NT WA=red ∅ WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales WA NT WA=red ∅ WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales WA NT WA=red ∅ WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales WA NT WA ≠ NT WA=red ∅ WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales WA NT Inconsistent! WA=red ∅ WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA NT Prune! WA=red WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA NT WA=red WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA NT Q WA=red WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue WA=red, NT=green, Q=red WA=red, NT=green, Q=green WA=red, NT=green, Q=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA NT Q WA=red WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue WA=red, NT=green, Q=red WA=red, NT=green, Q=green NT ≠ Q WA=red, NT=green, Q=blue Northern Territory Western Australia Queensland South Australia Victoria Tasmania New South Wales ∅ WA NT Q WA=red WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue WA=red, NT=green, Q=red WA=red, NT=green, Q=green Prune! WA=red, NT=green, Q=blue Early Pruning of Inconsistent States ∅ WA NT Q WA=red WA=green WA=blue WA=red, NT=red WA=red, NT=green WA=red, NT=blue WA=red, NT=green, Q=red WA=red, NT=green, Q=green WA=red, NT=green, Q=blue Backtracking Search function BT(csp) return backtrack({}, csp) function backtrack(assignment, csp) if (assignment is complete) AIMA Fig 6.5 return assignment var = SelectUnassignedVar(csp) foreach value in OrderDomainValues(var,assignment,csp) if (value is consistent with assignment) add to assignment
result = backtrack(assignment, csp)
if (result != failure)
return result
else
remove from assignment
return failure

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!

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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales

WA
r
NT
g
SA
b
Q
r
NSW
g
V
r
T
r
Solution

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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales

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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales

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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales
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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales
WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA

WA
r, g
NT
r, g
SA
b
Q
r, g
NSW
r, g
V
r, g
T
r, g, b
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales
Remaining possibilities: 25×3=96
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 • 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:morethantwovars
• 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:morethantwovars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
Can be reduced to set of binary constraints (possibly inefficiently)
•

NT WA
Q
SA
V
T
NSW
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales
WA ≠ NT, WA ≠ SA, NT ≠ Q, NT ≠ SA, Q ≠ NSW, Q ≠ SA, NSW ≠ V, NSW ≠ SA, V ≠ SA

Constraints • Binary constraint: two variables
• e.g., NSW ≠ WA, Xi > Xj, Xi+Xj = 2 • “Global”constraint:morethantwovars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
Can be reduced to set of binary constraints (possibly inefficiently)
• Unary constraint: one variable
• e.g., NSW ≠ red, Xi is even, Xi = 2
•

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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales
SA≠g
Unary constraint

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
Northern Territory
Western Australia
Queensland
South Australia
Victoria Tasmania
New South Wales
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

Arc Consistency • Unary constraint: one variable
• e.g., NSW ≠ red, Xi is even, Xi = 2
• “Global”constraint:morethantwovars
• e.g., Xi is between Xj and Xk, AllDiff(Xi,Xj,Xk)
Can be reduced to set of binary constraints (possibly inefficiently)
• Binary constraint: two variables
• e.g., NSW ≠ WA, Xi > Xj, Xi+Xj = 2
•

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
Y=X2 XY
{ 0,1,2,3,4,5,6,7,8,9 }
# possible assignments: 10×10 = 100
{ 0,1,2,3,4,5,6,7,8,9 }

Arc Consistency
Y=X2 XY
{ 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
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,2,3,4,5,6,7,8,9 }
X arc-consistent with respect to Y

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,2,3,4,5,6,7,8,9 }
Make Y arc-consistent with respect to X

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,4,9 }
Y arc-consistent with respect to X

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,4,9 }
X and Y arc-consistent

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,4,9 }
X and Y arc-consistent
# possible assignments: 4×4 = 16

boolean AC3(csp) {
Set queue = all arcs in csp
while (queue is not empty) {
boolean revise(csp, i, j) {
boolean changed = false
foreach vi in Di {
boolean ok = false
foreach vj in Dj {
if ( satisfies Cij )
ok = true
}
= queue.removeFirst()
if (revise(csp, i, j)) {
if Di is empty {
return false
}}
foreach k in neighbors(i) {
add to queue
} }
}}
return true
}
return changed
AC-3
}
}
if (!ok) {
delete vi from Di
changed = 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
• “Afterconstraintpropagation,weare 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.”

Constraint Propagation (inference)
State-Space Search

Interleaving Search and
Inference
• Aftereachchoiceduringsearch,we can perform inference to reduce future search

Interleaving Search and Inference
Node Consistency Inconsistent? Fail
CSP:
• Variables
• Domains
• Constraints
Arc Consistency (AC-3)
Inconsistent?
Solved? Yes Done! No
OK
No
Assign a variable Backtrack

Interleaving Search and
Inference
• Aftereachchoiceduringsearch,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

Related Posts