Examples of CSPs
Frequency Assignment
assign a frequency to every radio station (frequency assignment) such that stations with overlapping regions use different frequencies (constraints)
Time Table Scheduling
assign (time, slot, room) to every course (variable assignment) such that constraints are met (e.g. no two courses take place at the same time, …)
What does a CSP consist of?
Constraint Satisfaction Problem
A CSP is a tuple ({X1, …, Xn}, {D1, …, Dn}, R) consisting of:
Variables X1, …, Xn
Each variable has an associated Domain Di
e.g. {true, false}, {red, blue, green}, [2, …, 10], N, Z, …
Set of Constraints R
Constraints are defined on variables and restrict the possible values that can be assigned to variables (reduce domain size)
X7 ∈ {red, blue, green}
—> unary constraint
X1 < X2
—> binary constraint
X3 + X4 > X5 + 2X6
—> 4-ary constraint
Solutions / Consistent Assignments
Solution / Consistent Assignments
(Complete) Variable Assignment
assigns to each variable a value from its domain
Partial Variable Assignment
assigns values to a subset of all variable
Consistent Assignment
does not violate any constraints of the Csp
Solution
consistent complete assignment
Consistent CSP
there exists a solution
Main Problem:
Given a CSP,
find a solution or
report that the CSP is inconsistent
CSP Example
Map Coloring
Variables: A, B, C, D, E
Domains: {red, green, blue} for all variables
Constraints:
A ≠ B, A ≠ C, A ≠ D, …
Representation of Constraints
Constraints correspond to first-order predicates P(x1, x2, …, xn)
All constraints must evaluate to true for a solution
X1 < X2: P contains all pairs (v1, v2) over domains X1 and X2 such that v1 < v2
Explicit Representation:
store all n-tuples in P (all the possible values that satisfy the constraint)
Implicit Representation:
implement P as a function that takes n-tuples as input and returns true or false
Example: Presentation of Constraints
consider variables X1, X2 with domains {1, 2, 3}
consider constraint X1 < X2
logically, X1 < X2 is the binary predicate P(X1, X2) = {(1,2), (2,3), (1,3)}
Explicit and Implicit Representation?
Example: Representation of Constraints
Explicit Representation of P:
{(1,2), (2,3), (1,3)} —> assignment (X1=v1, X2=v2) satisfies P iff (v1, v2) ∈ P
Implicit Representation of P:
takes a pair (v1, v2) as argument and return true iff v1<v2
assignment (X1=v1, X2=v2) satisfies P iff P(v1, v2) = true
Which representation is more efficient?
Explicit or Implicit?
if P is represented explicitly, all tuples of P have to be enumerated and we have to test whether(v(X1), v(X2)) is in P
if P is represented implicitly, only one single comparison must be performed —> Test v(X1) < v(X2)
—> So, Implicit Representation is much more efficient (not everything has to be stored in memory + no pre-computation)
—> If P is defined by a criterion that can be computed easily, choose Implicit Representation
Solving CSPs
Naive Approach: enumerate all possible variable assignments
Backtracking Search: assign values variable by variable and do backtracking (change value of last variable assignment) on violations
Runtime depends on Selection Functions
Selection Functions for solving a CSPs
Selection Functions
First-Fail Variable Selection Heuristic (Minimum Remaining Values):
select variable with minimum domain size
Degree Variable Selection Heuristic:
select variable that is involved in the largest number of constraints for unassigned variables
Least Constraining Value Selection Heuristic:
select value that rules out fewest choices for neighbors
Approaches do not take implications of constraints into account, i.e. they check too many configurations that could be ruled out in advance
Selection Function
First-Fail Variable Selection Heuristic / Minimum Remaining Values
First-Fail Variable Selection Heuristic
select variable with minimum domain size (= fewest possible values)
assign the more constraint variable first
less time consuming, if correct: it rules out huge branch first
Degree Variable Selection Heuristic
select variable that is involved in largest number of constraints for unassigned variables
variable that is involved in largest number of constraints for unassigned variables = most demanding variable when it comes to constraints
used when domain size is the same
Least Constraining Value Selection Heuristic
select a value that rules out the fewest possible choices for neighbors
heuristic tries to leave the maximum flexibility for subsequent variable assignments
Normalized CSPs
we are restricted to normalized CSPs —> contain only unary and binary constraints
Domains: D1, D2, …, Dn
Unary Constraints: P1(X1), P2(X2), …, Pn(Xn)
Binary Constraints: P1,2(X1, X2), P1,3(X1, X3), …, Pn-1,n(Xn-1,Xn)
doesn’t mean any loss of generality
(each CSP can be transformed into normalized CSP in polynomial time)
Constraint Graph for normalized CSPs
Node?
Edge?
Node Xi —> unary constraint Pi
Edge between Xi and Xj —> binary constraint Pij
Consistency Concepts for CSPs
What is the basic idea?
Basic Idea: delete useless elements from domains of variables
can be used for pre-processing or in backtracking search after assigning a value to a variable
Most important Consistency Concepts: Node- and Arc Consistency (more involved ones become harder to compute)
Tradeoff: If pre-processing time exceeds time for solving CSP —> we don’t gain anything
Node Consistency
CSP is node consistent iff all nodes are node consistent
e.g. Frequency Assignment: If Pi allows only particular frequencies for Xi, we modify Di accordingly (—> deleting something fro the domain)
Arc Consistency
Constraint in the example given: no 2 adjacent variables can have the same value
AC-1 for establishing Arc Consistency
Example:
Using AC-1 for establishing Arc Consistency
Consistency Concepts and Consistency
if we get empty domain (while establishing node/arc consistency) the CSP must be inconsistent
—> However, if CSP is node + arc consistent it is not necessarily (globally) consistent
Example: Node + Arc Consistent CSP but still inconsistent
e.g. two values and three values (where variables must take pairwise distinct values) —> CSP is inconsistent
Node and Arc Consistency are not sufficient for testing consistency
Path Consistency
Nodes i and j are path consistent with node m iff:
for every arc-consistent assignment of i and j, there is an assignment to m that is arc consistent with both i and j
—> x and y are not path consistent with z
(x = red, y = blue) is an arc-consistent assignment. However, z = red is not arc-consistent with x & z = blue is not arc-consistent with y
More on Consistency Concepts
This CSP is node, arc and path consistent
however, since there are only 3 values and the variables must take pairwise distinct values, the CSP is inconsistent
k-Consistency
Every consistent (k-1)-assignment can be extended to a consistent k-assignment
1-consistency = node consistency
2-consistency = arc consistency
3-consistency = path consistency
—> provided node consistency is guaranteed
if we have a 1-consistency, we can find a value in another variable that can expand this and make it 2-consistent
Strong k-Consistency
The problem is j-consistent for all j ≤ k
so if a problem is k-consistent, it’s called strong k-consistent for all j ≤ k
other versions of the problem are valid, met and satisfied for all values smaller than k
Solving CSPs with Backtracking Search
CSPs and Local Search
Give a local search formulation for a general CSP (state space, neighborhood, objective function)
State Space:
each complete variable assignment (fully assigned, regardless of whether it violates constraints)
Neighborhood:
neighbors of a state (variable assignment) are obtained by changing the assignment of an arbitrary variable
—> hence, one neighbor for each
Variable, and
each Value in the domain of the variable (other than the current one)
Objective Function:
value of state (variable assignment) is defined as
number of constraints that are satisfied in state
(then we can try to maximize this value (count satisfied constraints)) —> if we reach total number of constraints = solution to the problem
Genetic Algorithm for CSPs
Define Genes, Chromosomes, Fitness (Value) of Individuals, Mutation Operation
Genes:
domain elements of all variables (all values)
Chromosomes:
correspond to variable assignments
Fitness:
number of constraints that are satisfied
Mutation Operation:
change a random gene
CSPs and Local Search Solution
What if local search finds
globally optimal solution?
locally optimal solution?
Globally Optimal Solution —> objective function f(s) = number of constraints
globally optimal solution satisfies all constraints by definition
solution is found for the CSP (CSP is consistent)
Locally Optimal Solution —> objective function f(s) < number of constraints
Locally optimal solution violates some constraints
CSP may be inconsistent, but we may also just got stuck in a local optimum
cannot conclude anything in this case
however, solution may be sufficient (soft constraints)
Remarks on Local Search (Properties)
Local Search Properties
tries to return a solution, even if it’s not optimal
does not start with empty configuration (always complete assignment)
In Local Searchwe talk about locally optimal solutions and not globally optimal ones
In Backtracking Search, we start with empty assignment and we cannot reach a non-optimal solution (because we just add values that satisfy the constraints & ignore branch if value violates a constraint + looking for different branch
Solving CSPs with Local Search
Summary
CSPs
Summary: CSPs
A CSP consists of
a set of variables
a domain for each variable (whole space is the assignment space)
a set of constraints (relations for some domains)
Goal: find an assignment that satisfies all constraints (complete assignment)
if no such assignment exists, the CSP is called inconsistent (and consistent otherwise)
Algorithms for solving CSPs
Naive Approach:
generate the whole search tree and test
not practical because of tree size (time & memory consuming)
Backtracking Search:
start with empty assignment (and traverse tree somehow)
systematically extend assignments using heuristics
with each layer, we select value for the variable and if it violates = exclude whole branch and explore other tree-parts
Local Search:
move through space of complete variable assignment
maximize number of satisfied constraints
returns solution no matter what
Consistency Concepts:
can be applied to simplify problem initially (pre-processing)
can be applied to simplify problem during backtracking search
Last changeda year ago