3a_Constraint_Satisfaction.dvi
COMP9414 Constraint Satisfaction 1
This Lecture
� Constraint Satisfaction Problems (CSPs)
� Standard search methods
◮ Backtracking search and heuristics
◮ Forward checking and arc consistency
◮ Domain splitting and arc consistency
◮ Variable elimination
� Local search
◮ Hill climbing
◮ Simulated annealing
UNSW ©W. Wobcke et al. 2019–2021
COMP9414: Artificial Intelligence
Lecture 3a: Constraint Satisfaction
Wayne Wobcke
e-mail:w. .au
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 3
Example: Map Colouring
Western
Australia
Northern
Territory
South
Australia
Queensland
New South Wales
Victoria
Tasmania
Variables: WA, NT, Q, NSW, V, SA, T
Domains: Di = {red, green, blue}
Constraints: Adjacent regions have different colours (WA 6= NT, etc.)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 2
Constraint Satisfaction Problems
� Constraint Satisfaction Problems are defined by a set of variables Xi,
each with a domain Di of possible values, and a set of constraints C
� Aim is to find an assignment to each the variables Xi (a value from
the domain Di) such that all of the constraints C are satisfied
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 5
Example: n-Queens Puzzle
� Put n queens on n×n board so that no two queens attack one another
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 4
Example: Map Colouring
� Solution is an assignment that satisfies all the constraints
Western
Australia
Northern
Territory
South
Australia
Queensland
New South Wales
Victoria
Tasmania
{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=green}
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 7
Example: Cryptarithmetic
S E N D
+ M O R E
M O N E Y
Variables:
D E M N O R S Y
Domains:
{0,1,2,3,4,5,6,7,8,9}
Constraints:
M 6= 0, S 6= 0 (unary constraints)
Y = D+E or Y = D+E −10, etc.
D 6= E, D 6= M, D 6= N, etc.
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 6
n-Queens Puzzle as a CSP
Assume one queen in each column. Domains are possible positions of
queen in a column. Assignment is when each domain has one element.
Variables: Q1, Q2, Q3, Q4
Domains: Di = {1,2,3,4}
Constraints:
Qi 6= Q j (cannot be in same row)
|Qi −Q j| 6= |i− j| (or same diagonal)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 9
Example: Sudoku
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 8
Cryptarithmetic with Hidden Variables
We can add “hidden” variables to simplify the constraints
OWTF U R
+
OWT
OWT
F O U R
X
2
X
1
X
3
Variables: F T U W R O X1X2X3
Domains: {0,1,2,3,4,5,6,7,8,9}
Constraints:
AllDifferent(F,T,U,W,R,O)
O + O = R + 10·X1, etc.
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 11
Varieties of CSPs
Discrete variables
� Finite domains; size d ⇒ O(dn) complete assignments
◮ e.g. Boolean CSPs, incl. Boolean satisfiability (NP-complete)
� Infinite domains (integers, strings, etc.)
◮ Job shop scheduling, variables are start/end days for each job
◮ 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 polynomial time by LP methods
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 10
Real World CSPs
� Assignment problems (e.g. who teaches what class)
� Timetabling problems (e.g. which class is offered when and where?)
� Hardware configuration (e.g. minimize space for circuit layout)
� Transport scheduling (e.g. courier delivery, vehicle routing)
� Factory scheduling (optimize assignment of jobs to machines)
� Gate assignment (assign gates to aircraft to minimize transit)
Many real world CSPs are also optimization problems
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 13
Backtracking Search
CSPs can be solved by assigning values to variables one by one, in
different combinations. Whenever a constraint is violated, go back to the
most recently assigned variable and assign it a new value.
Can be implemented using Depth First Search on a special kind of state
space, where states are defined by the values assigned so far
� Initial state: Empty assignment
� Successor function: Assign a value to an unassigned variable that
does not conflict with previously assigned values of other variables
� Goal state: All variables are assigned a value and all constraints are
satisfied
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 12
Types of Constraint
� Unary constraints involve a single variable
◮ M 6= 0
� Binary constraints involve pairs of variables
◮ SA 6= WA
� Higher-order constraints involve 3 or more variables
◮ Y = D+E or Y = D+E −10
� Inequality constraints on continuous variables
◮ EndJob1 + 5 ≤ StartJob3
� Soft constraints (Preferences)
◮ 11am lecture is better than 8am lecture!
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 15
Backtracking Search Example
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 14
Path Search vs Constraint Satisfaction
Important difference between path search problems and CSPs
� Constraint Satisfaction Problems (e.g. n-Queens)
◮ Difficult part is knowing the final state
◮ How to get there is easy
� Path Search Problems (e.g. Rubik’s Cube)
◮ Knowing the final state is easy
◮ Difficult part is how to get there
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 17
Problem with Backtracking Search
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 16
Backtracking Search Example
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 19
Improvements to Backtracking Search
General-purpose heuristics can give huge gains in speed
1. Which variable should be assigned next?
2. In what order should its values be tried?
3. Can inevitable failure be detected early?
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 18
Backtracking Search Space Properties
The search space has very specific properties
� If there are n variables, every solution is at depth exactly n
� Variable assignments are commutative
[WA = red then NT = green] same as [NT = green then WA = red]
Backtracking search can solve n-Queens for n ≈ 25
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 21
Degree Heuristic
� Tie-breaker among MRV variables
◮ Choose variable with most constraints on remaining variables
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 20
Minimum Remaining Values
� Minimum Remaining Values (MRV)
◮ Choose the variable with the fewest legal values
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 23
Constraint Graph
Binary CSP: Each constraint relates at most two variables
Constraint Graph: Nodes are variables, arcs show constraints
WA
NT
SA
Q
NSW
V
T
General-purpose CSP algorithms use the graph structure to speed up
search, e.g. Tasmania is an independent subproblem!
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 22
Least Constraining Value
� Given a variable, choose the least constraining value
◮ One that rules out the fewest values in the remaining variables
More generally, 3 allowed values would be better than 2, etc.
Combining these heuristics makes 1000-Queens feasible
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 25
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
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 24
Forward Checking
Idea: Keep track of remaining legal values for unassigned variables
WA NT Q NSW V SA T
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 27
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
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 26
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
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 29
Arc Consistency
Simplest form of constraint propagation is arc consistency
Arc (constraint) X → Y is arc consistent if
for every value x in dom(X) there is some allowed y in dom(Y )
WA NT Q NSW V SA T
Make X → Y arc consistent by removing any such x from dom(X)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 28
Constraint Propagation
Forward checking propagates information from assigned to unassigned
variables, but doesn’t provide early detection for all failures
WA NT Q NSW V SA T
NT and SA cannot both be blue!
Constraint propagation repeatedly enforces constraints locally
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 31
Arc Consistency
Arc (constraint) X → Y is arc consistent if
for every value x in dom(X) there is some allowed y in dom(Y )
WA NT Q NSW V SA T
If X loses a value, neighbours of X need to be rechecked
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 30
Arc Consistency
Simplest form of constraint propagation is arc consistency
Arc (constraint) X → Y is arc consistent if
for every value x in dom(X) there is some allowed y in dom(Y )
WA NT Q NSW V SA T
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 33
Domain Splitting and Arc Consistency
States are whole CSPs (not partial assignments)
� Make CSP domain consistent and arc consistent
◮ Domain consistent = all unary constraints are satisfied
� To solve CSP using Depth First Search
◮ Choose a variable v with more than one value in domain
◮ Split the domain of v into two subsets
◮ This gives two smaller CSPs
◮ Make each CSP arc consistent (if possible)
◮ Solve each resulting CSP (or backtrack if unsolvable)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 32
Arc Consistency
Arc (constraint) X → Y is arc consistent if
for every value x in dom(X) there is some allowed y in dom(Y )
WA NT Q NSW V SA T
Arc consistency detects failure earlier than forward checking
For some problems, it can speed up the search enormously
For others, it may slow the search due to computational overheads
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 35
Variable Elimination
� If there is only one variable, return the intersection of its (unary)
constraints
� Otherwise
◮ Select a variable X
◮ Join the constraints in which X appears, forming constraint R1
◮ Project R1 onto its variables other than X, forming R2
◮ Replace all of the constraints in which X appears by R2
◮ Recursively solve the simplified problem, forming R3
◮ Return R1 joined with R3
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 34
Constraint Optimization Problems
States are whole CSPs (not partial assignments) with costs
� Make CSP domain consistent and arc consistent
� Add CSP to priority queue
� To solve CSP using Greedy Search
◮ Remove CSP with minimal h from priority queue
◮ Choose a variable v with more than one value in domain
◮ Split the domain of v into two subsets
◮ This gives two smaller CSPs
◮ Make each CSP arc consistent (if possible) – add to priority queue
� cost(CSP) ≈ sum of costs to violate soft constraints
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 37
Variable Elimination Example
r1 : C 6= E C E
3 2
3 4
4 2
4 3
r2 : C > D C D
3 2
4 2
4 3
r3 : r1 ⊲⊳ r2 C D E
3 2 2
3 2 4
4 2 2
4 2 3
4 3 2
4 3 3
r4 : π{D,E}r3 D E
2 2
2 3
2 4
3 2
3 3
→֒ new constraint
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 36
Variable Elimination Example
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 39
Local Search
� Iterative Improvement
◮ Assign all variables randomly (possibly violating constraints)
◮ Change one variable at a time, trying to reduce the number of
violations at each step
◮ Greedy Search with h = number of constraints violated
h = 5 h = 2 h = 0
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 38
Variable Elimination Example
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 41
Plateaux and Local Optima
Sometimes, have to go sideways or even backwards to make progress
towards a globally optimal solution
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 40
Hill Climbing by Min-Conflicts
2
2
1
2
3
1
2
3
3
2
3
2
3
0
� Variable selection: randomly select any conflicted variable
� Value selection by min-conflicts heuristic
◮ Choose value that violates fewest constraints
◮ Can (often) solve n-Queens for n ≈ 10,000,000
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Constraint Satisfaction 43
Simulated Annealing
� Stochastic hill climbing based on difference between evaluation of
previous state (h0) and new state (h1)
◮ If h1 < h0, definitely make the change ◮ Otherwise, make the change with probability e−(h1−h0)/T where T is a “temperature” parameter � Reduces to ordinary hill climbing when T = 0 � Becomes totally random search as T → ∞ � Sometimes, gradually decrease value of T during search UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Constraint Satisfaction 42 Inverted View When minimizing violated constraints, it makes sense to think of starting at the top of a ridge and climbing down into the valleys UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Constraint Satisfaction 45 Summary � Much interest in CSPs for real-world applications � Backtracking = depth-first search with one variable assigned per node � Variable and value ordering heuristics help significantly � Forward checking helps by detecting inevitable failure early � Hill climbing by min-conflicts often effective in practice � Simulated annealing can help to escape from local optima � Which method(s) are best varies from one task to another! UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Constraint Satisfaction 44 Phase Transitions in CSPs Given random initial state, hill climbing by min-conflicts with random restarts can solve n-Queens in almost constant time for arbitrary n with high probability (e.g. n = 10,000,000) Randomly-generated CSPs tend to be easy if there are very few or very many constraints, but become extra hard in a narrow range of the ratio R = number of constraints number of variables R CPU time critical ratio UNSW ©W. Wobcke et al. 2019–2021