Lecture 7 - Unit 3

Constraint Satisfaction Problems

Constraint Satisfaction Problems

 Problems can be solved by searching in a space of

states.

 Evaluated by domain specific heuristics and check

whether they are goal state or not.

 From algorithms point of view, each state is indivisible.

Constraint Satisfaction Problems

 Consider a factored representation of each state : set

of variables each of which has a value.

 A problem is solved when each variable has a value

that satisfies all the constraints on the variable.

 A problem described in such a way is called constraint

satisfaction problem (CSP).
Defining CSPs

 A constraint satisfaction problem consists of three

components, X, D, and C:
X is a set of variables, {X1,... ,Xn}.
D is a set of domains, {D1,... ,Dn}, one for each
variable.
C is a set of constraints that specify allowable
combinations of values.
 Each domain Di consists of a set of allowable values,
{v1,... ,vk} for variable Xi.
Defining CSPs

 Each constraint Ci consists of a pair ⟨scope, rel⟩,

where
 scope is a tuple of variables that participate in the
constraint;
 rel is a relation that defines the values that those
variables can take on.
 If X1 and X2 both have the domain {A, B}
 ⟨(X1,X2), X1 ≠ X2⟩
Defining CSPs

 To solve CSP : state space & notion of solution.

 Each state in a CSP is defined by assignment of
values to some or all of the variables.
 An assignment that does not violate any constraints is
called a consistent or legal assignment.
 A complete assignment is one in which every variable
is assigned, and a solution to a CSP is a consistent,
complete assignment.
Example Problem: Map Coloring

 Task : color each region as

red, green and blue.

 Constraint : No
neighboring region must
have the same color.
Example Problem: Map Coloring

 To formulate this as CSP:

X={WA,NT,Q,NSW,V,SA,T}

 The domain of each

variable is the set Di =
{red, green, blue}.
Example Problem: Map Coloring

 The constraints require neighboring regions to have

distinct colors.

 Since there are nine places where regions border, there

are nine constraints:
 C={SA ≠ WA,SA ≠ NT,SA ≠ Q,SA ≠ NSW ,SA ≠ V,
WA ≠ NT,NT ≠ Q,Q ≠ NSW ,NSW ≠ V }
Example Problem: Map Coloring

 SA ≠ WA
{(red,green),(red,blue),(green,red),(green,blue),(blue,re
d),(blue,green)}

 {WA= red, NT= green, Q= red, NSW= green, V=red,

SA= blue, T= red }
Example Problem: Map Coloring

 Visualize a CSP as
constraint graph.

 Nodes : Variables

 Link : connects any two

variables that participate in
a constraint
Example Problem : Job shop scheduling

 Factories have the problem of scheduling a day’s worth

of jobs, subject to various constraints.
 15 task car assembly:
X= {AxleF, AxleB, WheelRF, WheelLF, WheelRB,
WheelLB, NutsRF , NutsLF ,NutsRB, NutsLB, CapRF ,
CapLF, CapRB, CapLB, Inspect}.
 The value of each variable is the time that the task
starts.
Precedence Constraints

 Whenever a task T1 must occur before task T2, and task

T1 takes duration d1 to complete, we add an arithmetic
constraint of the form
T1 + d 1 ≤ T 2

 Axle needs 10 minutes installation

AxleF + 10 ≤WheelRF ; AxleF + 10 ≤WheelLF ;
AxleB + 10 ≤WheelRB; AxleB + 10 ≤WheelLB
Question – How to represent ?

 For each wheel, we must affix the wheel (which takes 1

minute), then tighten the nuts (2 minutes), and finally
attach the hubcap (1 minute).
Disjunctive Constraint

 Suppose we have four workers to install wheels, but

they have to share one tool that helps put the axle in
place.
(AxleF + 10 ≤AxleB) or (AxleB + 10 ≤AxleF ).
Variations on the CSP formalism

Discrete Variables
 Simplest kind of CSP: discrete, finite domains.
 E.g. Map coloring, scheduling jobs with time limits.

 A discrete domain can be infinite. (e.g. set of integers

or strings).
 No longer possible to describe constraints by
enumerating all allowed combinations of values.
 E.g. no deadline job scheduling.
Variations on the CSP formalism

Continuous Variables
 Scheduling experiments on a hubble space telescope.
 Linear programming problems.
Type of Constraints

 Unary Constraint : Restricts the value of a single

variable.
 E.g.South Australians (SA) wont tolerate the color
green
 ⟨(SA),SA ≠ green⟩

 Binary Constraint :SA ≠ NSW is a binary constraint.

 A binary CSP is one with only binary constraints; it
can be represented as a constraint graph.
Type of Constraints

 Global Constraint: A constraint involving an arbitrary

number of variables.
 E.g. Alldiff constraint – all of the variables involved in
a constraint must have different values.

 Preference Constraint : Indicates which solution is

preferred.
 E.g. Class-scheduling problem in university.
Real World CSP Problems

 Teaching assignments
 Allocating timetable for a class
 VLSI layout
 Transportation scheduling
Inference in CSPs

 Regular state-space search algorithm does only search.

 In CSP
 Can search (choose a new assignment from several
possibilities).
 Constraint propagation – specific type of inference.
 Using the constraints can reduce the number of legal
values to a variable.
Local consistency

 Key idea is local consistency.

 If we treat each variable as a node in a graph and each

binary constraint as an arc, then
 the process of enforcing local consistency in each part
of the graph causes inconsistent values to be eliminated
throughout the graph.
Types of Local Consistency

 Node Consistency : A single variable (corresponding

to a node in the CSP network) is node-consistent if all
the values in the variable’s domain satisfy the
variable’s unary constraints.

 E.g. South Australians dislike green, the variable SA

starts with domain {red, green, blue}
 SA with the reduced domain {red, blue}
Types of Local Consistency

 Arc Consistency : A variable in CSP is arc consistent if

every value in its domain satisfies the variable’s binary
constraints.
 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).
 Cannot be applied to map-coloring problem.
Types of Local Consistency

 A network is arc-consistent if every variable is arc

consistent with every other variable.
 E.g.Constraint : X = Y2 where the domain of both X
and Y is a set of digits.
 ⟨(X,Y ),{(0,0),(1,1),(2,4),(3,9))}⟩
 To make X arc-consistent with respect to Y , we reduce
X’s domain to {0,1,2,3}.
 If we also make Y arc-consistent with respect to X, then
Y ’s domain becomes {0,1,4,9}.
CSP is arc-consistent
Types of Local Consistency

 The arc-consistency algorithm AC-3.

 After applying AC-3 algorithm, either every arc is arc-

consistent, or some variable has an empty domain,
indicating that the CSP cannot be solved.
AC-3 Algorithm
Types of Local Consistency

 AC-3 Algorithm:
 Maintains a queue of arcs to consider.
 Initialize : with all the arcs in a CSP.
 popsoff an arbitrary arc (Xi, Xj) from the queue and
makes Xi arc-consistent with respect to Xj.
 Ifthis leaves Di unchanged, the algorithm just moves
on to the next arc.
Types of Local Consistency

 AC-3 Algorithm:

 Ifthis revises Di (makes the domain smaller) then we

add to the queue all arcs (Xk, Xi) where Xk is a
neighbor of Xi.

 IfDi is revised down to nothing, then we know the

whole CSP has no consistent solution
AC-3 Algorithm
Types of Local Consistency

 Path Consistency : Arc consistency tightens down the

domains (unary constraints) using the arcs (binary
constraints).
 Tightens the binary constraints by using implicit A
two-variable set {Xi,Xj} is path-consistent with respect
to a third variable Xm if, for every assignment {Xi = a,
Xj= b} consistent with the constraints on {Xi,Xj}, there
is an assignment to Xm that satisfies the constraints on
{Xi,Xm} and {Xm,Xj}.
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 says : given the empty set, we can make
any set of one variable consistent (node consistency).
2 – consistency
 3-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.
Global Constraint

 Involves arbitrary number of variables.

 E.g. Alldiff constraint

 Simple inconsistency detection

 Ifm variables are involved in the constraint, and if
they have n possible distinct values altogether, and m
> n, then the constraint cannot be satisfied.
Resource Constraint

 Also called atmost constraint.

 Let P1,... ,P4 denote the numbers of personnel
assigned to each of four tasks.
 Constraint: no more than 10 personnel are assigned in
total is written as Atmost(10,P1,P2,P3,P4).
 E.g: if each variable has the domain {3,4,5,6}
 Enforceconsistency by deleting the maximum value of
any domain.
Sudoku Puzzle
Backtracking Search in CSP

 Work on partial assignment.

 Depth Limited Search (DLS) search strategy is used.
 State would be partial assignment and an action would
be adding var = value to the assignment.
 Sudoku problems : solved by inference over constraints
Commutativity – Crucial property
common to all CSP

 CSPs are all commutative.

 Ifthe order of application of any given set of actions
has no effect on the outcome.
 We reach the same partial assignments irrespective of
the order.
 Consider only a single variable at each node in the
search tree.
Backtracking Search

 Used for DFS that chooses value for one variable at a

time and backtracks when a variable has no legal
values to assign.

 It repeatedly chooses an unassigned variable, and then

tries all values in the domain of that variable in turn,
trying to find a solution.
Backtracking Search
Backtracking Search
Backtracking Search

 To solve CSPs efficiently without domain-specific

knowledge, address following questions:
 Function SELECT-UNASSIGNED-VARIABLE:
which variable should be assigned next?
 FunctionORDER-DOMAIN-VALUES: In what order
should we select the values
 Function INFERENCE: What inference should be
performed at each step in the search.
Backtracking Search Algorithm

 var ←SELECT-UNASSIGNED-VARIABLE(csp)
 Choosing the variable with the fewest “legal” values—is
called the minimum-remaining-values (MRV)
heuristic.
 Also called ’most constrained variable’ or ‘fail-first’
heuristic.
Example Problem: Map Coloring

 WA = red
 NT = green
 Only one possible value for
SA compared to Q
Example Problem: Map Coloring

 Degree Heuristic : Reduce

the branching factor on
future choices by selecting
the variables that is
involved with largest
number of constraints on
other unassigned variables.
 Degree of SA = 5.
Example Problem: Map Coloring

 Once variable is chosen,

decide the order to examine
values.
 Least-constraining-value
heuristic.
 Partial assignments: WA =
red and NT = green
 Leave maximum flexibility
to subsequent assignments.
Interleaving Search and Inferences

 Simplest forms of inferences is forward checking.

 When a variable X is assigned, an arc consistency is

established.
 For each unassigned variable Y that is connected to a
constraint X

 Doesn’t detect all inconsistencies.

Interleaving Search and Inferences

 Maintaining Arc Consistency (MAC).

Intelligent Backtracking: Looking
backward

 Chronological Backtracking: When a branch of

search fails in BACKTRACKING-SEARCH
algorithm : back up to the preceding variable and try a
different value for it.
 generated the partial assignment {Q= red,NSW=
green,V= blue,T= red}
 SA = ? [violates the constraint]
Intelligent Backtracking: Looking
backward

 SA = ? [violates the constraint]

 Backtrack to a variable that fixes the problem.
 keep track of a set of assignments that are in conflict
with some value for SA.
 Conflict set for SA = {Q= red,NSW= green,V=blue}
 Backjumping Method: backtracks to the most
recent assignment in the conflict set.