CONSTRAINT SATISFACTION

PROBLEMS
By
Dr. J. Ujwala Rekha
 Introduction
• Previous Search Problems-
– Search in a space of states
– States can be evaluated by domain-specific heuristics
– State is atomic (indivisible)- a black box with no internal
structure
• CSP search algorithms
– States are represented using a factored representation
(a set of variables, each of which has a value)
– General-purpose rather than problem-specific heuristics
Defining Constraint Satisfaction Problems
Defining Constraint Satisfaction Problems
 Example: Map Coloring
• For example, once we have chosen {SA=blue} in the
Australian problem, we can conclude that none of
the five neighboring variables can take on the value
blue.
• Without taking advantage of constraint
propagation, a search procedure would have to
consider 35=243 assignments for the five
neighboring variables.
• With constraint propagation we have 25=32
assignments to look at, a reduction of 87%.
 CSP as a Constraint Graph
• The nodes of the graph correspond to
variables of the problem
• Arc connects two variables that participate in
a constraint.
 Benefits of CSP
• Clean specification of many problems, generic
goal, successor function and heuristics
• Just represent problem as a CSP and solve with
general package.
• CSP search algorithms “knows” which variables
violate a constraint and hence where to focus
the search.
• CSP search algorithms automatically prune off
all branches that violate constraints.
 Constraint Propagation
• 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)
– An algorithm can do inference called constraint propagation (reduce
the number of legal values for a variable, which in turn can reduce
the legal values for another variable, and so on).
• Constraint propagation may be inter wined with search, or it
may be done as a preprocessing step, before search starts.
• Sometimes preprocessing can solve the problem, and no
search is required at all.
 Constraint Satisfaction
• 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.
• There are different types of consistency:
– Node consistency
– Arc consistency
– Path consistency
– K-consistency
 Constraint Propagation
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.
• We say network is node-consistent if every
variable in the network is node-consistent.
 Constraint Propagation
Arc Consistency
• A variable in a CSP is arc-consistent if every value in
its domain satisfies the variable’s binary constraints.
• 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 arch (Xi, Xj).
• A network is arc-consistent if every variable is arc
consistent with every other variable.
 Constraint Propagation
AC-3 Algorithm
• Initially, the queue contains all the arcs in the CSP.
• Then AC-3 pops off an arbitrary arc (X i, Xj) from the queue and
makes Xi arc-consistent with respect to Xj.
– If this leaves Di unchanged, the algorithm just moves on to the next
arc.
– If this revises Di (makes domain smaller), then we add to the queue
all arcs (Xk, Xi) where Xk is a neigbor of Xi.
– If Di is revised down to nothing, then the whole CSP has no
consistent solution.
– Otherwise, we keep checking, trying to remove values from the
domains of the variables until no more arcs are in the queue.
 Constraint Propagation
Path Consistency
• Arc consistency either finds a solution or finds that the CSP
cannot be solved.
• Arc consistency tightens down the domains (unary
constraints) using the arcs (binary constraints).
• To make progress, we need a stronger notion of consistency
called path consistency
• Path consistency tightens binary constraints by using implicit
constraints that are inferred by looking at triples of variables.
• 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}.
 Constraint Propagation
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 is same as node consistency
• 2-consistency is same as arc consistency
• For binary constraint networks, 3-consistency is
the same as path consistency.
 Constraint Propagation
• 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.
• Suppose we have a CSP with n nodes and make it strongly n-
consistent. We can then solve the problem as follows:
• First, we choose a consistent value for X1. We are then
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.
• For each variable Xi, we need only search through the d values
in the domain to find a value consistent with X1,…Xi-1.
• We are guaranteed to find a solution in O(n2d). However, the
algorithm for establishing n-consistency takes time
exponential in n in the worst-case.
 Constraint Propagation
Global Constraints
• Global constraints involve an arbitrary number of variables (but not
necessarily all variables).
• Global constraints can be handled by special-purpose algorithms that are
more efficient than the general-purpose methods described so far.
• For example, in cryptarithmetic problem and Suduku puzzles the global
constraint says that all the variables involved must have distinct values.
• First, remove any variable in the constraint that has a singleton domain,
and delete that variable’s value from the domains of the remaining
variables.
• Repeat as long as there are singleton variables. If at any point an empty
domain is produced or there are more variables than domain values left,
then an inconsistency has been detected.
 Constraint Propagation
• Another important higher-order constraint is the resource
constraint, sometimes called the at most constraint.
– For example, in a scheduling problem, let P1,…,P4 denote the numbers of
personnel assigned to each of four tasks. The constraint that no more
than 10 personnel are assigned in total is called resource constraint.
• In some problems, it is usually not possible to represent the
domain of each variable as a large set of integers.
– Instead, domains are represented by upper and lower bounds and are
managed by bounds propagation.
– We say that a CSP is bounds consistent if for every variable X, and for
both the lower-bound and upper-bound values of X, there exists some
value of Y that satisfies the constraint between X and Y for every variable
Y.
 Backtracking Search for CSPs
• Sudoku problems are designed to be solved by inference
over constraints.
• But many other CSPs cannot be solved by inference alone
and requires search for a solution.
• Backtracking search algorithms work on partial
assignments.
– The term backtracking search is used for a depth-first
search that chooses values for one variable at a time
and backtracks when a variable has no legal values left
to assign.
 Backtracking Search
• Backtracking search repeats the following steps:
– Pick an unassigned variable
– Assign it a value that doesn’t violate any
constraints.
• If there is no such value, then backtrack to the
previous step and choose a new variable.
 Backtracking Search
• A basic backtracking search is complete, i.e., it will find
solutions if one exists, but is very slow on large problems.
• In general, solving CSPs in NP-hard, and so the best known
general-purpose solving algorithms run in worst-case
exponential time.
• Various improvements are made to basic backtracking, such
as
– Rules for choosing the next variable
– Rules for choosing what value to be assigned to the chosen
variable
– Interleaving searching and inference: forward checking
– Rules for choosing what variable to backtrack to
• These improvements on backtracking search are domain-
independent.
 Backtracking Search
Rules for choosing the next variable
• One rule is to always choose the variable with
minimum remaining values (MRV) in its domain
– The intuition is that small domains have fewer
choices and so will hopefully lead to failure more
quickly than big domains.
– In practice, usually performs better than random or
static variable choice, but it depends on the
problem.
 Backtracking Search
Rules for choosing value to be assigned to the
chosen variable
• One rule is to choose the least-constraining
value from the domain of the variable being
assigned, i.e., the value that rules out the
fewest choices for neighbor variables.
• In practice, can perform well, but depends on
the problem.
 Backtracking Search
Interleaving Searching and inference: Forward
Checking
• After a variable is assigned a value, we can
rule out all domain values for associated
variables that are inconsistent with the
assignment.
• Forward-checking combined with the MRV
variable selection heuristic is often a good
combination.
 Backtracking Search
Rules for choosing what variable to backtrack to
• Basic backtracking is some times called
chronological backtracking because it always
backtracks to the most recently assigned
variable.
• But it is possible to do better, e.g., conflict-
directed backtracking (variable that is
responsible for making assignment
impossible)
 Local Search For CSPs
• Local search algorithms use a complete-state formulation:
initial state assigns a value to every variable, and the search
changes the value of one variable at a time.
• For example, in the 8-queens problem, the initial state might be
a random configuration of 8 queens in 8 columns.
• Each step moves a single queen to a new position in its column.
• The initial guess violates several constraints.
• The point of local search is to eliminate the violated
constraints.
• In choosing a new value for a variable, select the value that
results in the minimum number of conflicts with other
variables-the min-conflicts heuristic.
 Local Search for CSPs
• All local search techniques can be applied to CSPs.
• The landscape of a CSP under the min-conflicts heuristic usually has a
series of plateaux.
• Simulated annealing can be used to escape from plateaux.
• Another technique called constraint weighting can help concentrate the
search on the important constraints.
– Each constraint is given a numeric weight. Initially all are 1.
– At each step of the search, the algorithm chooses a variable/value pair
to change that will result in the lowest total weight of all violated
constraints.
– The weights are then adjusted by incrementing the weight of each
constraint that is violated by the current assignment.
– This has two benefits:
• It adds topography to plateaux, making sure that it is possible to
improve from the current state.
• Over time, it adds weight to the constraints that are proving
difficult to solve.
 The Structure of Problems
• The complexity of solving a CSP is strongly related to the
structure of its constraint graph.
• Tree-structured problems can be solved in linear time.
• To solve a tree structured CSP, first pick any variable to be the
root of the tree, and choose an ordering of the variables such
that each variable appears after its parent in the tree. Such an
ordering is called a topological sort.
• Any tree with n nodes has n-1 arcs, so we can make this graph
directed arc-consistent in O(n) steps, each of which must
compare up to d possible domain values for two variables, for
a total of O(nd2).
• Once we have a directed arc-consistent graph, we can just
march down the list of variables and choose any remaining
value.
 The Structure of Problems
• We have efficient algorithm for trees.
• General constraint graphs can be reduced to trees.
• There are two primary ways to reduce a graph to trees:
– based on removing nodes
– based on collapsing nodes
• The first approach involves assigning values to some variables so that
remaining variables form a tree.
– Consider the constraint graph for Australia:
– If we could delete South Australia, the graph would become a tree.
– We can do this by fixing a value for SA and deleting from the domains of the
other variables any values that are inconsistent with the value chosen for SA.
– Solve the remaining tree with the Tree CSP Solver.
– If the value chosen for SA is wrong, we would need to try another possible
value for SA
 The Structure of Problems
The general algorithm is as follows:
 The Structure of Problems
• The second approach for reducing a graph into trees is based on
constructing a tree decomposition of the constraint graph into a
set of connected sub problems.
• Each sub problem is solved independently, and the resulting
solutions are then combined.
• A tree decomposition must satisfy the following three
requirements:
– Every variable in the original problem appears in at least one of the sub
problems.
– It two variables are connected by a constraint in the original problem,
they must appear together in at least one of the sub problems.
– If a variable appears in two sub problems in the tree, it must appear in
every sub problem along the path connecting those sub problems.