Transcript Binary CSP

Explorations in Artificial Intelligence
Prof. Carla P. Gomes
[email protected]
Module 6
Binary CSP
Binary CSP
Restrict form of CSP with only
Unary constraints
Binary contraints
Constraint graph
Note: unary constraints can be satisfied by reducing the domain of the
constrained variable (node consistency)
Any CSP with n-ary constraints can be
converted to another equivalent
binary CSP.
Example
Original constraint and variables:
X+Y=Z X::[1,2]; Y::[3,4]; Z::[5,6]
X < Z;
How to represent this problem using only binary constraints?
From N-Ary CSP to Binary
Encapsulated variable
•For each constraint: A new variable that encapsulates the
set of constrained variables;
•Domain – set of values that satisfy the constraint (cartesian
product of domains – invalid tuples) (assumed finite
domains)
Example:
original constraint and variables:
X+Y=Z X::[1,2]; Y::[3,4]; Z::[5,6]
encapsulated variable and reduced
domain:U::[(1,4,5),(2,3,5),(2,4,6)]
In fact, this transformation solves individual constraints.
How to combine solutions from different constraints?
Hidden variable encoding (keeping original variables)
Dual encoding
With original variables
(hidden variable encoding)
•A constraint binds the original variable to the corresponding position of the
encapsulated variable; i.e.:
X original variable;
U encapsulated variable;
X=ith_argument_of(U) – i is the "position of X within U".
original (non-binary) CSP:
X+Y=Z, X<Y
X::[1,2]; Y::[3,4]; Z::[5,6]
equivalent binary CSP:
Without original variables (dual encoding)
Constraints bind the encapsulated variables via common components in a
following way
i_th_argument_of(U)=j_th_argument_of(V),
where U and V are encapsulated variables and i and j
respectively are the "positions of common component".
original (non-binary) CSP:
X+Y=Z, X<Y
X::[1,2]; Y::[3,4]; Z::[5,6]
•Each constraint from the original CSP is represented by an encapsulated variable (even binary constraints).
•Constraint network smaller than when using hidden variable
•The valuation of original variables, has to be extracted from the valuation of encapsulated variables.