CSC384: Introduction to Artificial Intelligence
Constraint Satisfaction Problems (Backtracking Search)
• Chapter 6
– 6.1: Formalism
– 6.2: Constraint Propagation
– 6.3: Backtracking Search for CSP
– 6.4 is about local search which is a very useful idea but we won’t cover it in class.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 1
Representing States with Feature Vectors
• Foreachproblemwehavedesignedanewstate representation (and coded the sub-routines called by search to use this representation).
• Feature vectors provide a general state representation that is useful for many different problems.
• Feature vectors are also used in many other areas of AI, particularly Machine Learning, Reasoning under Uncertainty, Computer Vision, etc.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 2
Feature Vectors
• We have
– A set of k variables (or features)
– Each variable has a domain of different values.
– A state is specified by an assignment of a value for each variable.
• height = {short, average, tall},
• weight = {light, average, heavy}
– A partial state is specified by an assignment of a value to some of the variables.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 3
Example: Sudoku
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 4
Example: Sudoku
• 81 variables, each representing the value of a cell.
• Domain of Values: a single value for those cells that are already filled in, the set {1, …9} for those cells that are empty.
• State: any completed board given by specifying the value in each cell (1-9, or blank).
• Partial State: some (but not all) cells filled in
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 5
Example: 8-Puzzle
2
3
7
6
4
8
5
1
• Variables: 9 variables Cell1,1, Cell1,2, …, Cell3,3
• Values: {‘B’, 1, 2, …, 8}
• State: Each “Celli,j” variable specifies what is in that position of the tile.
– If we specify a value for each cell we have completely specified a state.
This is only one of many ways to specify the state.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 6
Constraint Satisfaction Problems
• Notice that in these problems some settings of the variables are illegal.
– In Sudoku, we can’t have the same number in any column, row, or subsquare.
– In the 8 puzzle each variable must have a distinct value (same tile can’t be in two places)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 7
Constraint Satisfaction Problems
• In many practical problems finding a legal setting of the variables is difficult.
• We want to find a state (setting of the variables) that satisfies certain constraints.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 8
Constraint Satisfaction Problems
• In Suduko: The variables that form – a column must be distinct
– a row must be distinct
– a sub-square must be distinct.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 9
Constraint Satisfaction Problems
• In these problems we do not care about the sequence of moves needed to get to a goal state.
• We only care about finding a setting of the variables that satisfies the goal.
– A setting of the variables that satisfies some constraints.
• In contrast, in the 8-puzzle, the setting of the variables satisfying the goal is given. We care about the sequence of moves needed to move the tiles into that configuration.
– In Search we care about finding a path to the goal state.
– In CSPs we care about finding the goal state (not how to get there).
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 10
Example Car Sequencing
Car Factory Assembly Line—back to the days of Henry Ford
Move the items to be assembled, don’t move the workers
12346
The assembly line is divided into stations. A particular task is preformed at each station.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
Example Car Sequencing
1 sunroof 3 Heated 6 seats
Some stations install optional items…not every car in the assembly line is worked on in that station.
As a result the factory is designed to have lower capacity in those stations.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
Example Car Sequencing
Slot1 Slot2 Slot3 Slot4 Slot5 Slot6 Slot7
Cars move through the factory on an assembly line which is broken up into slots.
The stations might be able to process only a limited number of slots out of some group of slots that is passing through the station at any time.
E.g., the sunroof station might accommodate 4 slots, but only has capacity to process 2 slots out of the 4 at any one time.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
Example Car Sequencing
Car1 Car2 Car3 Car4 Car5 Car6 Car7
Max 2
Max 2
Max 2
Max 2
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
Example Car Sequencing
Car1 Car2 Car3 Car4 Car5 Car6 Car7
Each car to be assembled has a list of required options.
We want to assign each car to be assembled to a slot on the line.
But we want to ensure that no sequence of 4 slots has more than 2 cars assigned that require a sun roof.
Finding a feasible assignment of cars with different options to slots without violating the capacity constraints of the different stations is hard.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
Formalization of a CSP
• A CSP consists of
– A set of variables V1, …, Vn
– For each variable a (finite) domain of possible values Dom[Vi].
– A set of constraints C1,…, Cm.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 16
Formalization of a CSP
• Eachvariablecanbeassignedanyvaluefromitsdomain. • Vi = d where d ∈ Dom[Vi]
• EachconstraintC
– Constrains a particular set of variables it is over, called its
scope
• E.g., C(V1, V2, V4) is a constraint over the variables V1, V2, and V4. Its scope is {V1, V2, V4}
– Given an assignment to its variables the constraint returns:
• True—this assignment satisfies the constraint – e.g., C(V1=a, V2=b, V4=c)àTrue
• False—this assignment falsifies the constraint. – e.g., C(V1=a, V2=b, V4=a)àFalse
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 17
Formalization of a CSP
• We can specify the constraint with a table
• C(V1, V2, V4) with Dom[V1] = {1,2,3} and Dom[V2] = Dom[V4] = {1, 2}
V1
V2
V4
C(V1,V2,V4)
1
1
1
False
1
1
2
False
1
2
1
False
1
2
2
False
2
1
1
True
2
1
2
False
2
2
1
False
2
2
2
False
3
1
1
False
3
1
2
True
3
2
1
True
3
2
2
False
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 18
Formalization of a CSP
• Often we can specify the constraint more compactly with an expression:
C(V1, V2, V4) = (V1 = V2+V4)
V1
V2
V4
C(V1,V2,V4)
1
1
1
False
1
1
2
False
1
2
1
False
1
2
2
False
2
1
1
True
2
1
2
False
2
2
1
False
2
2
2
False
3
1
1
False
3
1
2
True
3
2
1
True
3
2
2
False
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 19
Formalization of a CSP
• UnaryConstraints(overonevariable) – e.g. C(X):X=2; C(Y): Y>5
• BinaryConstraints(overtwovariables) – e.g. C(X,Y): X+Y<6
• Higher-orderconstraints:over3ormorevariables.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 20
Formalization of a CSP
• Solutions:
– A solution to a CSP is an assignment of a value to all of the variables such that every constraint is satisfied.
– A CSP is unsatisfiable if no solution exists.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 21
Example: Sudoku
• Variables: V11, V12, ..., V21, V22, ..., V91, ..., V99
• Domains:
– Dom[Vij]={1-9}foremptycells
– Dom[Vij]={k}afixedvaluekforfilledcells.
V33 =4
V88 = 3
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 22
Example: Sudoku
• Variables: V11, V12, ..., V21, V22, ..., V91, ..., V99
• Domains:
– Dom[Vij]={1-9}foremptycells
– Dom[Vij]={k}afixedvaluekforfilledcells.
• Constraints:
– Rowconstraints:
• All-Diff(V11, V12, V13, ..., V19) • All-Diff(V21, V22, V23, ..., V29) • ...., All-Diff(V91, V92, ..., V99)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 23
Example: Sudoku
• Variables: V11, V12, ..., V21, V22, ..., V91, ..., V99
• Domains:
– Dom[Vij]={1-9}foremptycells
– Dom[Vij]={k}afixedvaluekforfilledcells.
• Constraints:
– Rowconstraints:
• All-Diff(V11, V12, V13, ..., V19) • All-Diff(V21, V22, V23, ..., V29) • ...., All-Diff(V91, V92, ..., V99)
– ColumnConstraints:
• All-Diff(V11, V21, V31, ..., V91) • All-Diff(V21, V22, V13, ..., V92) • ...., All-Diff(V19, V29, ..., V99)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 24
Example: Sudoku
• Variables: V11, V12, ..., V21, V22, ..., V91, ..., V99
• Domains:
– Dom[Vij]={1-9}foremptycells
– Dom[Vij]={k}afixedvaluekforfilledcells.
• Constraints:
– Rowconstraints:
• All-Diff(V11, V12, V13, ..., V19) • All-Diff(V21, V22, V23, ..., V29) • ...., All-Diff(V91, V92, ..., V99)
– ColumnConstraints:
• All-Diff(V11, V21, V31, ..., V91) • All-Diff(V21, V22, V13, ..., V92) • ...., All-Diff(V19, V29, ..., V99)
– Sub-SquareConstraints:
• All-Diff(V11, V12, V13, V21, V22, V23, V31, V32, V33) • ..., All-Diff(V77, V78, V79,..., V97, V98, V99)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 25
Example: Sudoku
• Thus Sudoku has 3x9 ALL-DIFF constraints, one over each set of variables in the same row, one over each set of variables in the same column, and one over each set of variables in the same sub-square.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 26
Example: Sudoku
• Each of these constraints is over 9 variables, and they are all the same constraint:
– Any assignment to these 9 variables such that each variable has a different value satisfies the constraint.
– Any assignment where two or more variables have the same value falsifies the constraint.
• This is a special kind of constraint called an ALL-DIFF constraint.
– ALL-Diff(V1, .., Vn) can also be encoded as a set of binary not-equal constraints between all possible pairs of variables:
V1 ≠ V2, V1 ≠ V3, ..., V2 ≠ V1, ..., Vn ≠ V1, ..., Vn ≠ Vn-1
• But this collection of binary constraints has less pruning power under GAC (as we will see later)
• ALL-DIFF appears in many CSP problems.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 27
CSP as a Search Problem
A CSP could be viewed and solved as a traditional search problem
• However, CSPs do not require finding a path (to a goal). They only need the configuration of the goal state.
• Traditional search is an inefficient way to solve CSPs because it does not exploit the additional structure of the problem.
• This additional structure can be exploited in a process called constraint propagation.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 28
Solving CSPs
• CSPs are best solved by a specialized version search called Backtracking Search.
• Key intuitions:
– Wecanbuilduptoasolutionbysearchingthroughthespaceof
– Orderinwhichweassignthevariablesdoesnotchangethe correctness of search – eventually they all have to be assigned. It can have a huge impact on the search’s efficiency! We can decide on a suitable value for one variable at a time!
– Ifwefalsifyaconstraintduringtheprocessofbuildingupasolution, we can immediately reject the current partial assignment:
• All extensions of this partial assignment will falsify that constraint, and thus none can be solutions.
èThis is the key idea of backtracking search.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 29
partial assignments (rather than paths)
Backtracking Search
• Specialized version of depth first search
• Explores partial assignments to the variables.
• A node is terminated if it violates a constraint
• A node specifying a total assignment is a solution.
Backtracking Search is one of the fundamental Computer Science Algorithms (Knuth “The Art of Computer Programming” Volume 4A is devoted to Backtracking Search)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 30
Backtracking Search–Support Functions
• ClassVariable—variousmemberfunctionstodeal with individual variables
– .domain()
Returns list of values in variable’s domain
– .domainSize()
Returns number of values in domain
– .getValue() / .setValue()
Gets/sets variable’s current assigned value. variable is unassigned if and only if its current assigned value is None
– .isAssigned()
Returns True/False if variable has an assigned value (i.e., its getValue() != None)
– .name()
Returns string specifying the variable’s name (for documenting the CSP model)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 31
Backtracking Search–Support Functions
• Class Constraint—various member functions to deal with individual constraints
– .scope()
Returns list of variables in the constraint’s scope.
– .arity()
Returns number of variables in constraint’s scope.
– .numUnassigned()
Returns number of variables in constraint’s scope that are not assigned. (Other variables have been assigned)
– .check()
Returns True if the values currently assigned to the variables in .scope() satisfy the constraint. False if not.
If .numUnassigned() > 0 returns True (not yet able to check that the constraint is falsified).
– name()
Returns string specifying the constraint’s name
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 32
Backtracking Search–Support Functions
• variables
List containing all variables of the CSP problem (list of Variable class instances)
• constraints
List containing all constraints of the CSP problem (list of Contraint class instances)
• constraintsOf(var)
Returns list of constraints that have var in their scope (list of Constraint class instances)
• allSolutions
Boolean flag. If True we want to enumerate all solutions
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 33
Backtracking Search–Support Functions
• We will extend these support function/variables when we discuss extensions of simple backtracking that do domain filtering (pruning)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 34
Backtracking Search: The Algorithm BT
BT(unAssignedVars) #pass collection of unassigned variables if unAssignedVars.empty(): #no more unassigned variables
for var in variables:
print var.name(), “ = “, var.getValue()
if allSolutions:
return #continue search to print all solutions
else: EXIT #terminate after one solution found.
var := unAssignedVars.extract() #select next variable to assign for val in var.domain():
var.setValue(val)
constraintsOK = True
for constraint in constraintsOf(var):
if constraint.numUnassigned() == 0: if not constraint.check():
constraintsOK = False
break
if constraintsOK:
BT(unAssignedVars)
var.setValue(None) #undo assignemnt to var unAssignedVars.insert(var) #restore var to unAssignedVars return
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 35
Backtracking Search—initial call
• Initially all variables are unassigned (var.getValueI() == None for every variable).
• InitiallyunAssignedVarscontainsall variables.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 36
Backtracking Search–What variable to assign next?
• The decision of which variable to assign next does not affect whether or not backtracking search will find a solution.
• But it does have a tremendous impact on efficiency!
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 37
Backtracking Search
• The algorithm searches a tree of partial assignments.
Children of a node are all possible values of some (any) unassigned variable
Vi=a
Root {} Vi=b
Vj=1
The root has the empty set of assignments
Vj=2
Vi=c
Search stops descending if the assignments on path to the node
violate a constraint
Subtree
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
38
Backtracking Search
• Heuristics are used to determine
– the order in which variables are assigned:
UnAssignedVars.extract()
– determines the order of values tried for each variable.
– As in search, this collection can be kept in heuristic order so that we always select the first variable.
– But the best variable can change every time we assign another variable.
– In general, the best variable depends on the collection of assigned variables as well as the values these variables have been assigned.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 39
Backtracking Search
• Hence, the choice of the next variable can vary from branch to branch, e.g.,
– under the assignment V1=a we might choose to assign V4 next, while under V1=b we might choose to assign V5 next.
• This “dynamically” chosen variable ordering can have a tremendous impact on performance.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 40
Example: N-Queens
• Place N Queens on an N X N chess board so that no Queen can attack any other Queen.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 41
Example: N-Queens
• Problem formulation:
– N variables (N queens)
– N2 values for each variable representing the positions on the chessboard
• Value i is i’th cell counting from the top left as 1, going left to right, top to bottom.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 42
Example: N-Queens
• Q1=1,Q2=15,Q3=21,Q4=32, Q5 = 34, Q6 = 44, Q7 = 54, Q8 = 59
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 43
Example: N-Queens
• This representation has (N2)N states (different possible assignments in the search space)
– For 8-Queens: 648 = 281,474,976,710,656
• Is there a better way to represent the N-queens problem?
– We know we cannot place two queens in a single row àwe can exploit this fact in the choice of the CSP representation
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 44
Example: N-Queens
• Better Modeling:
– N variables Qi, one per row.
– Value of Qi is the column the Queen in row i is placed; possible values {1, …, N}.
• This representation has NN states: – For 8-Queens: 88 = 16,777,216
• The choice of a representation can make the problem solvable or unsolvable!
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 45
Example: N-Queens
• Q1=1,Q2=7,Q3=5,Q4=8, Q5 = 2, Q6 = 4, Q7 = 6, Q8 = 3
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 46
Example: N-Queens
• Constraints:
– Can’t put two Queens in same column
Qi ≠ Qj for all i ≠ j
– Diagonal constraints
abs(Qi-Qj) ≠ abs(i-j)
• i.e., the difference in the values assigned to Qi and Qj can’t be equal to the difference between i and j.
• E.g. 4 Queens:
Q1 ≠ Q2, Q1 ≠ Q3, Q1 ≠ Q4, Q2 ≠ Q3, Q2 ≠ Q4, Q3 ≠ Q4, abs(Q1-Q2) != 1, abs(Q1-Q3) != 2, abs(Q1-Q4) != 3, abs(Q2-Q3) != 1, abs(Q2-Q4) != 2, abs(Q3-Q4) != 1
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 47
Example: N-Queens
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 48
Example: N-Queens
Q1 ≠ Q2
abs(Q1-Q3) != 2
Constraint Check inner loop of BT:
for constraint in constraintsOf(var):
if constraint.numUnassigned() == 0:
if not constraint.check(): constraintsOK = False break
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
49
Example: N-Queens
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 50
Example: N-Queens
Solution!
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
51
Example: N-Queens
Solution!
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
52
Problems with Plain Backtracking
Sudoku: The 3,3 cell has no possible value.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 53
Problems with Plain Backtracking
• In the backtracking search we won’t detect that the (3,3) cell has no possible value until all variables of the row/column (involving row or column 3) or the sub-square constraint (first sub-square) are assigned.
So we have the following situation:
Variable has no possible value, but we don’t detect this. Until we try to assign it a value
• Leads to the idea of constraint propagation/domain filtering
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 54
Constraint Propagation
• Constraint propagation refers to the technique of “looking ahead” at the yet unassigned variables in the search .
• Try to detect obvious failures: “Obvious” means things we can test/detect efficiently.
• Even if we don’t detect an obvious failure we might be able to eliminate some possible part of the future search.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 55
Constraint Propagation
• Propagation has to be applied during the search; potentially at every node of the search tree.
• Propagation itself is an inference step that needs some resources (in particular, it requires time)
– If propagation is slow, this can slow the search down to the point where using propagation makes finding a solution take longer!
– There is always a tradeoff between searching fewer nodes in the search, and having a higher nodes/second processing rate.
– A similar tradeoff occurs if we try to compute an expensive heuristic in A* search—we might expand fewer nodes but take more time.
• We will look at two main types of propagation: Forward Checking & Generalized Arc Consistency
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 56
Constraint Propagation: Forward Checking
• Forward checking is an extension of backtracking search that employs a “modest” amount of propagation (look ahead).
• When a variable is instantiated we check all constraints that have only one uninstantiated variable remaining (constraint.numUnassigned() = 1)
• For that uninstantiated variable, we check all of its values, pruning those values that violate the constraint.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 57
Forward Checking–Support Functions
• During search the domains of unassigned variables (future variables) can be pruned because these values are incompatible with the values given to currently assigned variables.
• During backtracking search, we will be making new variable assignments, and undoing them when we backtrack.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 58
Forward Checking–Support Functions
• Henceanimportantcomponentofalgorithmsthat use constraint propagation is that
1. Theymusthavefacilitiestoprunevaluesfromthe domains of the future variables—we have to keep track of the unpruned values remaining for the future variables.
2. Theymustalsohavethefacilitytorestorepruned values to the domains of the future variables on backtrack when we undo some variable assignments.
• This is accomplished by keeping track of which variable assignment caused the pruning to occur, and then restoring the values pruned by that variable assignment when it is undone by backtracking
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 59
Forward Checking–Support Functions
• Additional member functions/variables for Variable class
– .curDomain()
Returns list of variable’s current values (the currently unpruned values).
– .curDomainSize()
Returns number of variable’s current values.
– .pruneValue(value, assigned_var, assigned_val)
Removes value from variable’s current values. Remembers that assigned_var being assigned assigned_val’ is the reason this value is being pruned
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 60
Forward Checking–Support Functions
• Additional member function for Constraint class
– .unassignedVars()
Returns list of unassigned variables in constraint’s .scope() (variable is unassigned if its current value is None)
• Additional function
– restoreValues(variable, value)
returns all values pruned because of the passed variable/value assignment to the current domain of their respective variable.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 61
Forward Checking (detect values to prune)
• Called on a single constraint that has numUnassigned() = 1
FCCheck(constraint,assignedvar,assignedval): #prune domain of unassigned variable
var = constraint.unassignedVars()[0]
#.unassignedVars() should be list of length 1
#var is the single unassigned variable of constraint
for val in var.curDomain():
var.setValue(val) #trial assign and check constraint
if not constraint.check():
var.pruneValue(val,assignedvar,assignedval)
if var.curDomainSize() == 0:
return ”DWO” #domain wipe out
#no values left for var
else: return ”OK”
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 62
Forward Checking Algorithm
FC(unAssignedVars): #Forward checking, pass unassigned variables if unassignedVars.empty(): #no more unassigned variables
for var in variables:
print var.name(), “,”, var.getValue() if allSolutions:
return #continue search to print all solutions else: EXIT #terminate after one solution found.
var = unassignedVars.extract() #select next variable to assign for val in var.curDomain(): #current domain!
var.setValue(val)
noDWO = True
for constraint in constraintsOf(var):
if constraint.numUnassigned() == 1:
if FCCheck(C,var,val) == ”DWO” #prune future variables
noDwo = False
break if noDwo:
FC(unassignedVars) restoreValues(var, val)
var.setValue(None)
unAssignedVars.insert(var) #restore var to unAssignedVars return
#pass var/val as reason
#restore values pruned by this assigment
#undo assignemnt to var
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 63
Forward Checking–initial call
• Initially all variables are unassigned
• Initially unAssignedVars contains all variables
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 64
4
•
–
Queens Problem
Encoding with Q1, …, Q4 denoting a queen per row
– cannot put two queens in same column. Binary constraint between every pair of variables.
1234 1
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 65
4
•
–
Queens Problem
Forward checking reduced the domains of all variables that are involved in a constraint with one unassigned variable:
– each binary constraint with Q1
1234 1
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 66
4
–
Queens Problem
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 67
4
–
Queens Problem
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
DWO
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 68
4
–
Queens Problem
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 69
4
–
Queens Problem
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 70
4
–
Queens Problem
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 71
4
–
Queens Problem
Q1 {1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
72
DWO
4
•
–
Queens Problem
Exhausted the subtree with Q1=1; try now Q1=2
Q1
{1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 73
4
–
Queens Problem
Q1
{1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 74
4
–
Queens Problem
Q1
{1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 75
4
–
Queens Problem
Q1
{1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 76
4
–
Queens Problem
Q1
{1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
1234 1
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 77
4
•
–
Queens Problem
We have now find a solution: an assignment of all variables to values of their domain so that all constraints are satisfied
1234 1
Q1
{1,2,3,4}
Q2 {1,2,3,4}
Q3 {1,2,3,4}
Q4 {1,2,3,4}
2 3 4
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 78
Example: N-Queens FC search Space
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 79
FC: Minimum Remaining Values Heuristics (MRV)
• FC also gives us for free a very powerful heuristic to guide us which variables to try next:
– Always branch on a variable with the smallest remaining values (smallest .curDomainSize()).
– If a variable has only one value left, that value is forced, so we should assign it and propagate its consequences right away
– This heuristic tends to produce skinny trees at the top. This means that more variables can be instantiated with fewer nodes searched, and thus more constraint propagation/DWO failures occur when the tree starts to branch out (we start selecting variables with larger domains)
– We can find a inconsistency much faster
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 80
MRV Heuristic: Human Analogy
• Whatvariableswouldyoutryfirst?
Most restricted variables! = MRV
Domain of each variable: {1, …, 9}
(1, 5): impossible values: Row: {1, 4, 5, 6, 8} Column: {1, 3, 4, 5, 7, 9} Subsquare: {5, 7, 9} àDomain = {2}
(9, 5): impossible values: Row: {1, 5, 7, 8, 9} Column: {1, 3, 4, 5, 7, 9} Subsquare: {1, 5, 7, 9} àDomain = {2, 6}
After assigning value 2 to
cell (1,5): Domain of (9,5) = {6}
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
81
Example – Map Colouring
• Color the following map using red, green, and blue such that adjacent regions have different colors.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 82
Example – Map Colouring
• Modeling
– Variables: WA, NT, Q, NSW, V, SA, T
– Domains: Di={red, green, blue}
– Constraints: adjacent regions must have different colors.
• E.g. WA 1 NT
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 83
Example – Map Colouring
• Forward checking: keep track of remaining legal values for unassigned variables.
• Terminate search when any variable has no legal values.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 84
Example – Map Colouring
• Assign {WA=red}
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 85
Example – Map Colouring
• Effects on other variables connected by constraints to WA
– NT can no longer be red
– SA can no longer be red
• Assign {Q=green} (Note: Not using MRV)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 86
Example – Map Colouring
• Effects on other variables connected by constraints with Q
– NT can no longer be green
– NSW can no longer be green
– SA can no longer be green
• Assign {V=blue} (not using MRV)
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
87
DWO
Example – Map Colouring
• Assign {V=blue} (not using MRV)
• Effects on other variables connected by constraints with V
– NSW can no longer be blue
– SA is empty
• FC has detected that partial assignment is inconsistent with the constraints and backtracking can occur.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto
88
DWO
Empirically
• FC often is about 100 times faster than BT
• FC with MRV (minimal remaining values) often 10000 times faster.
• But on some problems the speed up can be much greater
– Converts problems that are not solvable to problems that are solvable.
• Still FC is not that powerful. Other more powerful forms of constraint propagation are used in practice.
• Try the previous map coloring example with MRV.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 89
Constraint Propagation: Generalized Arc Consistency
• GAC—GeneralizedArcConsistencyisthemostcommonly used domain filtering (propagation) method used.
• PlainBacktrackingcheckaconstraintonlywhenithas
.numUnassigned() = 0
• Forwardcheckingchecksaconstraintonlywhenithas
.numUnassigned() = 1
• GACchecksallconstraints!Thisleadstomuchmorepruning
in general.
– GAC ensures that all constraints satisfy a certain level of consistency (called GAC!) with respect to the already assigned variables
– This level of consistency is achieved by pruning values from the domains of the unassigned variables.
– Even at the root before any variables have been assigned, we can get some pruning by making the constraints GAC consistent.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 90
Constraint Propagation: Generalized Arc Consistency
First we define formally the notion of consistency.
1. Aconstraint,C(V1,V2,V3,…,Vn)isGACwith respect to variable Vi, if and only if
For every value of Vi, there exists values of V1, V2, Vi-1, Vi+1, …, Vn that satisfy C.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 91
Constraint Propagation: Generalized Arc Consistency
2. C(V1,V2,…,Vn)isGACifandonlyif
It is GAC with respect to every variable in its scope.
3. ACSPisGACifandonlyif
all of its constraints are GAC.
So we achieve GAC by achieving GAC for each constraint, and we achieve GAC for a constraint by achieving for every variable in the constraint’s scope.
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 92
Constraint Propagation: GAC
• Achieving GAC for a constraint with respect to a particular variable:
– Say we find a value d of variable Vi that is not consistent: That is, there is no assignments to the other variables that satisfy the constraint when Vi = d
– d is said to be Arc Inconsistent
– We can remove d from the domain of Vi—this value cannot lead to a solution
(much like Forward Checking, but more powerful).
• e.g. C(X,Y): X>Y Dom(X)={1,5,11} Dom(Y)={3,8,15}
– ForX=1thereisnovalueofYs.t.1>Y=>sowecanremove1 from domain X
– For Y=15 there is no value of X s.t. X>15, so remove 15 from domain Y
– We obtain the more restricted domains Dom(X)={5,11} and Dom(Y)={3,8}
Fahiem Bacchus, CSC384 Introduction to Artificial Intelligence, University of Toronto 93
Constraint Propagation: GAC
• Propagation: pruning the domain of a variable to make a constraint GAC can make a different constraint no longer GAC
• C1(X,Y): X>Y
C2(Y,Z): Z