Lecture 18

CONSTRAINT
SATISFACTION PROBLEMS
Artificial Intelligence
COSC-3112

Ms. Humaira Anwer

humaira.anwer@kfueit.edu.pk

Lecture 18- Constraint Satisfaction Problems 1

Today’s Agenda
• Variations on CSP Formalism
• Variable Types
• Constraint Types
• Convert n-ary constraint to binary
• Inference in CSP
• Local Consistency
• Node Consistency
• Arc Consistency
• Path Consistency
• K- Consistency

Lecture 18- Constraint Satisfaction Problems 2

 Variations on CSP Formalism
Variable Types
• Simplest CSPs define variables that have discrete,
finite domains.
• E.g. map coloring, 8-queens.
• Discrete domains can be infinite
• e.g. set of integers or strings.
• cannot enumerate all possible combinations of values
• Thus need to use a constraint language.

Lecture 18- Constraint Satisfaction Problems 3

 Variations on CSP Formalism
Variable Types
• E.g., for a job scheduling problem,
• might have T 1 + d 1 <= T 2
• where T 1 and T 2 are start times for two
tasks and
• d 1 is the duration of the first one
• This describe that the first task must finish
before the second one starts

Lecture 18- Constraint Satisfaction Problems 4

 Variations on CSP Formalism
Variable Types
• CSPs with continuous domains are common in the
real world and are studied in operations research.
• E.g., scheduling experiments on Hubble Telescope
requires meeting astronomical, precedence, and power
constraints.
• Best-known category of continuous-domain CSPs is
linear programming problems
• where all constraints are linear equalities or inequalities.

Lecture 18- Constraint Satisfaction Problems 5

 Variations on CSP Formalism
Constraint Types
• The simplest type is the unary constraint, which
restricts the value of a single variable:
• <(SA), SA ≠ green>
• A binary constraint relates two variables:
• <(SA, NSW), SA ≠ NSW>
• A binary CSP is one with only binary constraints; it can
be represented as a constraint graph.
• Higher-order constraints are possible.
• E.g. Between (X, Y, Z) that specifies that Y is between X
and Z

Lecture 18- Constraint Satisfaction Problems 6

 Variations on CSP Formalism
Constraint Types
• A constraint involving an arbitrary number of
variables is called a global constraint.
• One of the most common global constraints is Alldiff.
• Many real-world CSPs include preference
constraints indicating which solutions are
preferred:
• constraint optimization problem (COP)

Lecture 18- Constraint Satisfaction Problems 7

Convert n-ary constraint to binary
one
• Example: How a single ternary constraint such as “A
+ B = C” can be turned into three binary
constraints?
• Using an auxiliary variable:
• First introduce a new variable AB and its domain.
• Then create appropriate relations between
the new variables and old ones.

Lecture 18- Constraint Satisfaction Problems 8

Inference in CSP
• In regular state-space search, an algorithm can do
only one thing: search.
• In CSPs there is a choice:
• an algorithm can search (choose a new variable
assignment from several possibilities) or
• do a specific type of inference called constraint
propagation
• Constraint Propagation
• using the constraints to reduce the number of legal
values for a variable,
• which in turn can reduce the legal values for another
variable, and so on (Local Consistency)
Lecture 18- Constraint Satisfaction Problems 9
Local Consistency
• Node consistency
• Arc consistency
• Path consistency
• k-consistency

Lecture 18- Constraint Satisfaction Problems 10

 Local Consistency
Node Consistency
• A single variable is node-consistent if all the values
in the variable’s domain satisfy the variable’s unary
constraints.
• A network is node-consistent if every variable in
the network is node-consistent.
• It can be done as a preprocessing step:
• eliminate all inconsistent values from variables'
domains.

Lecture 18- Constraint Satisfaction Problems 11

 Local Consistency
Arc Consistency
• A variable in a CSP is arc-consistent if every value in
its domain satisfies the variable’s binary
constraints.
• More formally:
• Xi is arc-consistent with respect to another variable Xj if
• for every value in the current domain Di there is some
value in the domain Dj that satisfies the binary
constraint on the arc (Xi , Xj ).
• A network is arc-consistent if every variable is arc
consistent with every other variable.

Lecture 18- Constraint Satisfaction Problems 12

 Local Consistency
Path Consistency
• For many kind of problems, arc consistency fails to
make enough inferences. Consider the map-
coloring problem on Australia, but with only two
colors allowed, red and blue...

Lecture 18- Constraint Satisfaction Problems 13

 Local Consistency
Path Consistency
• A two-variable set {Xi , Xj } is path-consistent with
respect to a third variable X m if, for every
assignment {Xi = a, Xj = b} consistent with the
constraints on {Xi , Xj }, there is an assignment to X
m that satisfies the constraints on {Xi , Xm } and
{Xm , Xj }
• This is called path consistency because one can
think of it as looking at a path from Xi to Xj with X
m in the middle.

Lecture 18- Constraint Satisfaction Problems 14

 Local Consistency
Path Consistency (Example)
• We will make the set {WA, SA} path consistent with
respect to NT .
• We start by enumerating the consistent
assignments to the set.
• In this case, there are only two: {WA = red , SA = blue}
and {WA = blue, SA = red}.
• We can see that with both of these assignments NT
can be neither red nor blue.
• We eliminate both assignments, and we end up with no
valid assignments for {WA, SA}.

Lecture 18- Constraint Satisfaction Problems 15

 Local Consistency
K Consistency
• A CSP is k-consistent if, for any set of k − 1 variables
and for any consistent assignment to those
variables
• A consistent value can always be assigned to any
kth variable.
• 1-consistency: Node consistency.
• 2-consistency: Arc consistency.
• 3-consistency: Path consistency.
• A CSP is strongly k-consistent if it is k-consistent
and is also (k−1)-consistent, (k−2)-consistent, . . . all
the way down to 1-consistent.

Lecture 18- Constraint Satisfaction Problems 16

 Local Consistency
Find a Soluction
• Suppose there is a CSP with n nodes and strongly n-
consistent. Now a solution can be found in this way:
• Choose a consistent value for X1 .
• It is guaranteed to be able to choose a value for X2 because
the graph is 2-consistent, for X3 because it is 3-consistent, and
so on.
• It is guaranteed to find a solution in time O(n2d):
• For each variable Xi , the algorithm only searches through the
d values in the domain to find a value consistent with X1 , . . . ,
Xi−1.
• Any algorithm for establishing n-consistency must take
time exponential in n in the worst case.

Lecture 18- Constraint Satisfaction Problems 17