Constraint Satisfaction
Constraint Satisfaction Problem
(CSPs)
⚫ Standard search problem: state is a "black box“ – any data structure that
supports successor function and goal test
⚫ CSP:
⚫ state is defined by variables Xi with values from domain Di
⚫ goal test is a set of constraints specifying allowable combinations of values
for subsets of variables
⚫ CSP can be defined as an variable assignment problem
⚫ Hard vs. Soft Constraint
Example: Map-Coloring
⚫ Variables WA, NT, Q, NSW,V, SA,T
⚫ Domains Di = {red,green,blue}
⚫ Constraints: adjacent regions must have different colors
e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red),
(green,blue),(blue,red),(blue,green)}
Example: Map-Coloring
⚫ Solutions are complete and consistent assignments
⚫ e.g., WA = red, NT = green, Q = red, NSW = green,V = red,SA = blue,T = green
Constraint graph
⚫ Binary CSP: each constraint relates two variables
⚫ Constraint graph: nodes are variables, arcs are constraints
Varieties of CSPs
⚫ Discrete variables
⚫ finitedomains:
⚫ n variables, domain size d O(dn) complete assignments
⚫ Boolean CSPs
⚫ infinite domains:
⚫ integers, strings, etc.
⚫ e.g., job scheduling, variables are start/end days for each job
⚫ need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3
⚫ Continuous variables
⚫ e.g., start/end times for Hubble Space Telescope observations
⚫ linear constraints solvable in polynomial time by LP
Varieties of constraints
⚫ Unary constraints involve a single variable,
⚫ e.g., SA ≠ green
⚫ Binary constraints involve pairs of variables,
⚫ e.g., SA ≠ WA
⚫ Higher-order constraints involve 3 or more variables,
⚫ e.g., cryptarithmetic column constraints
Example: Cryptarithmetic Puzzle
Real-world CSPs
⚫ Assignment problem
⚫ Timetabling problems
e.g., which class is offered when and where?
⚫ Transportation scheduling
⚫ Factory scheduling
⚫ Notice that many real-world problems involve real-valued variables
Standard search formulation
(incremental)
States are defined by the values assigned so far
⚫ Initial state: the empty assignment { }
⚫ Successor function: assign a value to an unassigned variable that does not conflict
with current assignment. It fail if no legal assignments
⚫ Goal test: the current assignment is complete
Backtracking search
⚫ Variable assignments are commutative, i.e.,
[ WA = red then NT = green ] same as [ NT = green then WA = red ]
⚫ => Only need to consider assignments to a single variable at each node
⚫ Depth-first search for CSPs with single-variable assignments is called
backtracking search
⚫ Can solve n-queens for n ≈ 25
Backtracking example
Backtracking example
Backtracking example
Backtracking example
Improving backtracking efficiency
⚫ General-purpose methods can give huge gains in speed:
⚫Which variable should be assigned next?
⚫In what order should its values be tried?
⚫Can we detect inevitable failure early?
Minimum Remaining Value
⚫ Minimum remaining value variable:
choose the variable with the fewest legal values
Most constraining variable
⚫ A good idea is to use it as a tie-breaker among most constrained variables
⚫ Most constraining variable:
⚫choose the variable with the most constraints on remaining variables
Least constraining value
Given a variable to assign, choose the least constraining value: the one that rules
out the fewest values in the remaining variables
Forward checking
⚫ Idea:
⚫ Keep track of remaining legal values for unassigned variables
⚫ Terminate search when any variable has no legal values
Forward checking
⚫ Idea:
⚫ Keep track of remaining legal values for unassigned variables
⚫ Terminate search when any variable has no legal values
Forward checking
⚫ Idea:
⚫ Keep track of remaining legal values for unassigned variables
⚫ Terminate search when any variable has no legal values
Forward checking
⚫ Idea:
⚫ Keep track of remaining legal values for unassigned variables
⚫ Terminate search when any variable has no legal values
Constraint propagation
⚫ Forward checking propagates information from assigned to unassigned
variables, but doesn't provide early detection for all failures:
⚫ NT and SA cannot both be blue!
⚫ Constraint propagation algorithms repeatedly enforce constraints locally…
Arc consistency
⚫ Simplest form of propagation makes each arc consistent
⚫ X Y is consistent iff for every value x of X there is some allowed y
Arc consistency
⚫ Simplest form of propagation makes each arc consistent
⚫ X Y is consistent iff for every value x of X there is some allowed y
Arc consistency
⚫ Simplest form of propagation makes each arc consistent
⚫ X Y is consistent iff
for every value x of X there is some allowed y
⚫ If X loses a value, neighbors of X need to be rechecked
Arc consistency
⚫ Simplest form of propagation makes each arc consistent
⚫ X Y is consistent iff for every value x of X there is some allowed y
⚫ If X loses a value, neighbors of X need to be rechecked
⚫ Arc consistency detects failure earlier than forward checking
⚫ Can be run as a preprocessor or after each assignment
Arc consistency algorithm AC-3
Tutorial I
You are in charge of scheduling for computer science classes that meet
Mondays, Wednesdays and Fridays. There are 5 classes that meet on these
days and 3 professors who will be teaching these classes.You are
constrained by the fact that each professor can only teach one class at a
time.
The classes are:
• Class 1 - Intro to Programming: meets from 8:00-9:00am
• Class 2 - Intro to Artificial Intelligence: meets from 8:30-9:30am
• Class 3 - Natural Language Processing: meets from 9:00-10:00am
• Class 4 - Computer Vision: meets from 9:00-10:00am
• Class 5 - Machine Learning: meets from 9:30-10:30am
The professors are:
• Professor A, who is available to teach Classes 3 and 4.
• Professor B, who is available to teach Classes 2, 3, 4, and 5.
• Professor C, who is available to teach Classes 1, 2, 3, 4, 5.
(i) Formulate this problem as a CSP problem in which there is one variable per class,
stating the domains, and constraints. Constraints should be specified formally and
precisely, but may be implicit rather than explicit.
(ii) Draw the constraint graph associated with your CSP
(iii) Show the domains of the variables after running arc-consistency on this initial graph
(after having already enforced any unary constraints).
V ariable Domain
C1 C
C2 B
C3 A, C
C4 A, C
C5 B, C
Note that C5 cannot possibly be C, but arc consistency does not rule it out.
(4) Give one solution to this CSP.
C1 = C, C2 = B, C3 = C, C4 = A, C5 = B. One other solution is possible (where C3 and
C4 are switched)
