Transcript Arc Consistency

Arc Consistency
Problem Solving With Constraints
CSCE421/821, Fall 2014
www.cse.unl.edu/~choueiry/F14-421-821
All questions: Piazza
Berthe Y. Choueiry (Shu-we-ri)
Avery Hall, Room 360
Tel: +1(402)472-5444
Foundations of Constraint Processing
Arc Consistency
1
Lecture Sources
Required reading
1. Algorithms for Constraint Satisfaction Problems, Mackworth and
Freuder AIJ'85 (focus on Node consistency, arc consistency)
2. Sections 3.1 & 3.2 Chapter 3. Constraint Processing. Dechter
Recommended reading
1. Bartak: Consistency Techniques (link)
2. Constraint Propagation with Interval Labels, Davis, AIJ'87
Foundations of Constraint Processing
Arc Consistency
2
Outline
1. Motivation (done) & background
2. Node consistency and its complexity
3. Arc consistency and its complexity
Foundations of Constraint Processing
Arc Consistency
3
Basic Consistency: Notation
Examining finite, binary CSPs
Notation:
Given variables i,j,k with values x,y,z, the predicate
Pijk(x,y,z) is true iff the 3-tuple (x,y,z)  Rijk
Node consistency:
Arc consistency:
checking Pi(x)
checking Pij(x,y)
Foundations of Constraint Processing
Arc Consistency
4
Worst-case asymptotic complexity
Worst-case complexity
time
space
as a function of the input parameters
Upper bound: f(n) is O(g(n)) means that f(n)  c.g(n)
f grows as g or slower
Lower bound: f(n) is  (h(n)) means that f(n)  c.h(n)
f grows as g or faster
Input parameters for a CSP:
n = number of variables
a = (max) size of a domain
dk = degree of Vk ( n-1)
e = number of edges (or constraints)  [(n-1), n(n-1)/2]
Foundations of Constraint Processing
Arc Consistency
5
Outline
1. Motivation (done) & background
2. Node consistency and its complexity
3. Arc consistency and its complexity
4. Criteria for performance comparison and CSP
parameters.
5. Experiments
1. Random CSPs (Model B)
2. Statistical Analysis
Foundations of Constraint Processing
Arc Consistency
6
Node consistency (NC)
Procedure NC({V1,V2,…,Vn})
For i  1 until n do DVi  DVi  { x | Pi(x) }
•
•
•
•
For each variable, we check a values
We have n variables, we do n.a checks
NC is O(a.n)
Alert: check for domain wipe-out, domain annihilation
If Dvi (Di=∅) Then BREAK
Foundations of Constraint Processing
Arc Consistency
7
Outline
1. Motivation (done) & background
2. Node consistency and its complexity
3. Arc consistency and its complexity
– Algorithms AC1, AC3, AC4, AC2001
4. Criteria for performance comparison and CSP
parameters.
5. Experiments
– Random CSPs (Model B)
– Statistical Analysis
Foundations of Constraint Processing
Arc Consistency
8
Arc Consistency
Adapted from Dechter
Definition: Given a constraint graph G,
• A variable Vi is arc consistent relative to Vj iff for every value a  DVi,
there exists b  DVj | (a,b)  RVi,Vj
Vi
Vj
1
1
2
Vj
1
2
2
3
Vi
3
2
3
• The constraint CVi,Vj is arc consistent iff
– Vi is arc consistent relative to Vj and
– Vj is arc consistent relative to Vi
• A binary CSP is arc-consistent iff every constraint (or sub-graph of
size 2) is arc consistent
Foundations of Constraint Processing
Arc Consistency
9
Main Functions
• Variable-value pair
– (Vi,a), ⟨Vi,a⟩: variable, value from its domain
• CHECK(⟨Vi,a⟩,⟨Vj,b⟩)
– Returns true if (a,b)∈RVi,Vj, false otherwise
• SUPPORTED(⟨Vi,a⟩,Vj)
– Verifies that ⟨Vi,a⟩ has at least one support in CVi,Vj
– Is not standard ‘terminology,’ but my ‘convention’
• REVISE(Vi,Vj)
– Updates DVi given RVi,Vj
– BREAK when domain wipe-out
Foundations of Constraint Processing
Arc Consistency
10
Arc Consistency Algorithms
• AC-1, AC-3, …, AC2001: arc consistency algorithms
– Update all domains given all constraints
– Call REVISE
– Differ in how they manage updates (queue)
• Complexity
– Nbr of variables: n, Domain size: d, Nbr of constraints: e, degree of
graph deg
• #CC is a global variable
– Keeps track of the number of times that the definition of a binary relation
is accessed
– Is a cost measure, to compare algorithms’ performance in practive
• Assumption
– Domains are sorted alphabetically (lexicographic)
Foundations of Constraint Processing
Arc Consistency
11
CHECK(⟨Vi,a⟩,⟨Vj,b⟩)
• Operation
– Verifies whether a constraint exists between Vi,Vj
– If a constraint exists
• Increases #CC
• Accesses the constraint between Vi,Vj
• Verifies if (a,b)∈RVi,Vj
– Returns true if (a,b) is consistent
– Returns false if (a,b) is not consistent
– If no constraints exist
• Returns true (universal constraint!)
• Pseudo code, necessary?
• Cost in practice depends on implementation
Foundations of Constraint Processing
Arc Consistency
12
SUPPORTED(⟨Vi,a⟩,Vj)
SUPPORTED(⟨Vi,a⟩,Vj)
•
•
1.
support  nil
2.
3.
4.
5.
 b  DVj
If CHECK(⟨Vi,a⟩,⟨Vi,b⟩)
Then Begin
support  true
6.
7.
8.
RETURN support
End
RETURN support
Complexity?
Once you find a support, stop looking
Foundations of Constraint Processing
Arc Consistency
13
REVISE(Vi, Vj): Description
•
•
•
•
•
Function
Updates DVi given the constraint CVi,Vj
Is directional: does not update DVj
Calls SUPPORTED(⟨Vi,*⟩,Vj)
If DVi is modified
– Returns true, false otherwise
Foundations of Constraint Processing
Arc Consistency
14
REVISE(Vi, Vj): Pseudocode
REVISE(Vi, Vj)
1.
2.
3.
4.
5.
6.
7.
8.
9.
•
revised  false
 x  DVi
found  SUPPORTED(⟨Vi,x⟩,Vj)
If found = false
Then Begin
revised  true
DVi  DVi \ {x}
End
RETURN revised
Complexity?
Foundations of Constraint Processing
Arc Consistency
15
REVISE: example
R. Dechter
• REVISE(Vi,Vj)
• REVISE(Vi,Vj)
Vi
Vj
1
2
3
Vi
1
Vj
1
2
2
3
2
3
Foundations of Constraint Processing
Arc Consistency
16
Arc Consistency (AC-1)
Procedure AC-1:
1 NC(Problem)
2 Q  {(i, j) | (i,j)  directed arcs in constraint network of Problem, i  j }
3 Repeat
4
change  false
5
Foreach (i, j)  Q do
6
Begin // for each
7
updated  REVISE(i, j)
8
If DVi = {} Then Return false Else change  (updated or change)
9
End // for each
10 Until change = false
11 Return Problem
• AC-1 does not update Q, the queue of arcs
• No algorithm can have time complexity below O(ea2)
• AC1 should test for empty domains (does not in the paper)
Foundations of Constraint Processing
Arc Consistency
17
Warning
• Most papers do not check for domain wipe-out

• In your code, have AC1
– Always check for domain wipe out and
– terminate/interrupt the algorithm when that occurs
• Complexity versus performance
– Does not affect worst-case complexity
– In practice, saves lots of #CC and cycles
Foundations of Constraint Processing
Arc Consistency
18
Arc Consistency (AC-1)
•
•
If a domain is wiped out, AC1 returns nil
Otherwise, returns the problem given as input (alternatively, change)
Procedure AC-1:
1 NC(Problem)
2 Q  {(i, j) | (i,j)  directed arcs in constraint network of Problem, i  j }
3 Repeat
4
change  false
5
Foreach (i, j)  Q do
6
Begin // for each
7
updated  REVISE(i, j)
8
If DVi = {} Then Return false Else change  (updated or change)
9
End // for each
10 Until change = false
11 Return Problem
Foundations of Constraint Processing
Arc Consistency
19
Arc consistency
1. AC may discover the solution
Example borrowed from Dechter
V1
V1
V3
V2
V1
V2
V3
V2
V2
V3
V2
V1
V3
V1
V1
V2
V3
V1
V3
V2
V3
Foundations of Constraint Processing
Arc Consistency
20
Arc consistency
2. AC may discover inconsistency
Example borrowed from Dechter
X
{ 1, 2, 3 }
Z<X
X<Y
Y
{ 1, 2, 3 }
{ 1, 2, 3 }
Z
Y<Z
Foundations of Constraint Processing
Arc Consistency
21
NC & AC
Example courtesy of M. Fromherz
AC propagates bound
x
[0, 10]
x
x  y-3
y
[0, 10]
Unary constraint x>3 is imposed
AC propagates bounds again
[0, 7]
x
x  y-3
x  y-3
y
[3, 10]
[4, 7]
y
[7, 10]
Foundations of Constraint Processing
Arc Consistency
22
Complexity of AC-1
Procedure AC-1:
1 begin
2 for i  1 until n do NC(i)
3 Q  {(i, j) | (i,j)  arcs(G), i  j
4 repeat
5 begin
6 CHANGE  false
7
for each (i, j)  Q do CHANGE  (REVISE(i, j) or CHANGE)
8 end
9 until ¬ CHANGE
10 end
Note: Q is not modified and |Q| = 2e
• 4  9 repeats at most n·a times
• Each iteration has |Q| = 2e calls to REVISE
• Revise requires at most a2 checks of Pij
 AC-1 is O(a3 · n · e)
Foundations of Constraint Processing
Arc Consistency
23
AC versions
• AC-1 does not update Q, the queue of arcs
• AC-2 iterates over arcs connected to at least
one node whose domain has been modified.
Nodes are ordered.
• AC-3 same as AC-2, nodes are not ordered
Foundations of Constraint Processing
Arc Consistency
24
AC-3
AC-3 iterates over arcs connected to at least one
node whose domain has been modified
Procedure AC-3:
1 for i  1 until n do NC(i)
2 Q  { (i, j) | (i, j)  directed arcs in constraint network of Problem, i  j }
3 While Q is not empty do
4
Begin
5
select and delete any arc (k,m)  Q
6
If Revise(k,m) Then Q  Q  { (i,k) | (i,k)  arcs(G), ik, im }
7
End
(Don’t forget to make AC-3 check for domain wipe out)
Foundations of Constraint Processing
Arc Consistency
25
Complexity of AC-3
Procedure AC-3:
1 begin
2 for i  1 until n do NC(i)
3 Q  {(i, j) | (I,j)  arcs(G), i  j }
4 While Q is not empty do
5 begin
6 select and delete any arc
(k,m)  Q
7 If Revise(k, m) then Q  Q
 { (i,k) | (I,k)  arcs(G), ik,
im }
8 end
9 end
•
•
First |Q| = 2e, then it grows and shrinks
48
Worst case:
– 1 element is deleted from DVk per iteration
– none of the arcs added is in Q
• Line 7: a·(dk - 1)
n
• Lines 4 - 8: 2e  k 1 a  d k  1  2e  a  (2e  n)
• Revise: a2 checks of Pij
 AC-3 is O(a2(2e + a(2e-n)))
 Connected graph (e  n – 1), AC-3 is
O(a3e)
 If AC-p, AC-3 is O(a2e)  AC-3 is (a2e)
 Complete graph: O(a3n2)
Foundations of Constraint Processing
Arc Consistency
26
Example: Apply AC-3
Example: Apply AC-3
Thanks to Xu Lin
V2
V1
{ 1, 2, 3, 4, 5 }
{ 1, 2, 3, 4, 5 }
V3 { 1, 2, 3, 4, 5 }
{ 1, 2, 3, 4, 5 }
V2
V1
V4
V3
{ 1, 3, 5 }
{ 1, 2, 3, 4 }
{ 1, 3, 5 }
{ 1, 2, 3, 5 }
V4
DV1 = {1, 2, 3, 4, 5}
DV2 = {1, 2, 3, 4, 5}
DV3 = {1, 2, 3, 4, 5}
DV4 = {1, 2, 3, 4, 5}
CV2,V3 = {(2, 2), (4, 5), (2, 5), (3, 5), (2, 3), (5, 1), (1, 2), (5, 3), (2, 1), (1, 1)}
CV1,V3 = {(5, 5), (2, 4), (3, 5), (3, 3), (5, 3), (4, 4), (5, 4), (3, 4), (1, 1), (3, 1)}
CV2,V4 = {(1, 2), (3, 2), (3, 1), (4, 5), (2, 3), (4, 1), (1, 1), (4, 3), (2, 2), (1, 5)}
Foundations of Constraint Processing
Arc Consistency
27
Applying AC-3
Thanks to Xu Lin
• Queue = {CV2, V4, CV4,V2, CV1,V3, CV2,V3, CV3, V1, CV3,V2}
• Revise(V2,V4): DV2 DV2 \ {5} = {1, 2, 3, 4}
• Queue = {CV4,V2, CV1,V3, CV2,V3, CV3, V1, CV3, V2}
• Revise(V4, V2): DV4  DV4 \ {4} = {1, 2, 3, 5}
• Queue = {CV1,V3, CV2,V3, CV3, V1, CV3, V2}
• Revise(V1, V3): DV1  {1, 2, 3, 4, 5}
• Queue = {CV2,V3, CV3, V1, CV3, V2}
• Revise(V2, V3): DV2  {1, 2, 3, 4}
Foundations of Constraint Processing
Arc Consistency
28
Applying AC-3 (cont.)
Thanks to Xu Lin
• Queue = {CV3, V1, CV3, V2}
• Revise(V3, V1): DV3  DV3 \ {2} = {1, 3, 4, 5}
• Queue = {CV2, V3, CV3, V2}
• Revise(V2, V3): DV2  DV2
• Queue = {CV3, V2}
• Revise(V3, V2): DV3  {1, 3, 5}
• Queue = {CV1, V3}
• Revise(V1, V3): DV1  {1, 3, 5}
END
Foundations of Constraint Processing
Arc Consistency
29
AC-4
Mohr & Henderson (AIJ 86):
• AC-3 O(a3e)  AC-4 O(a2e)
• AC-4 is optimal
• Trade repetition of consistency-check operations with heavy
bookkeeping on which and how many values support a given value
for a given variable
• Data structures it uses:
–
–
–
•
m: values that are active, not filtered
s: lists all vvp's that support a given vvp
counter: given a vvp, provides the number of support provided by a
given variable
How it proceeds:
1. Generates data structures
2. Prepares data structures
3. Iterates over constraints while updating support in data structures
Foundations of Constraint Processing
Arc Consistency
30
Step 1: Generate 3 data structures
• m and s have as many rows as there are vvp’s in the problem
• counter has as many rows as there are tuples in the constraints
m
(V4 , 5)
(V3 , 2)
(V3 , 3)
(V2 , 2)

(V4 , 4)
s
T
T
T
T

T
(V4 , 5)
(V3 , 2)
(V3 , 3)
(V2 , 2)

(V4 , 4)
counter
NIL
NIL
NIL
NIL

NIL
(V4 , V2 ), 3 0
(V4 , V2 ), 2
0
(V4 , V2 ), 1 0
(V2 , V3 ), 1 0


(V1, V3 ), 4 0
Foundations of Constraint Processing
Arc Consistency
31
Step 2: Prepare data structures
Data structures: s and counter.
•
•
Checks for every constraint CVi,Vj all tuples Vi=ai, Vj=bj_)
When the tuple is allowed, then update:
– s(Vj,bj)  s(Vj,bj)  {(Vi, ai)} and
– counter(Vj,bj)  (Vj,bj) + 1
Update counter ((V2, V3), 2) to value 1
Update counter ((V3, V2), 2) to value 1
Update s-htable (V2, 2) to value ((V3, 2))
Update s-htable (V3, 2) to value ((V2, 2))
Update counter ((V2, V3), 4) to value 1
Update counter ((V3, V2), 5) to value 1
Update s-htable (V2, 4) to value ((V3, 5))
Update s-htable (V3, 5) to value ((V2, 4))
Foundations of Constraint Processing
Arc Consistency
32
Constraints CV2,V3 and CV3,V2
S
(V4, 5)
Counter
Nil
(V3, 2)
((V2, 1), (V2, 2))
(V3, 3)
((V2, 5), (V2, 2))
(V4, V2), 3
0
(V4, V2), 2
0
(V4, V2), 1
0
(V2, 2)
((V3,1), (V3,3), (V3, 5), (V3,2))
(V2, V3), 1
2
(V3, 1)
((V2, 1), (V2, 2), (V2, 5))
(V2, V3), 3
4
(V2, 3)
((V3, 5))
(V4, V2), 5
1
(V1, 2)
Nil
(V2, V4), 1
0
(V2, 1)
((V3, 1), (V3, 2))
(V2, V3), 4
0
(V1, 3)
Nil
(V4, V2), 4
1
(V3, 4)
Nil
(V2, V4), 2
0
(V4, 2)
Nil
(V2, V3), 5
0
(V3, 5)
((V2, 3), (V2, 2), (V2, 4))
(V2, V4), 3
2
(v4, 3)
Nil
(V2, V4), 4
0
(V1, 1)
Nil
(V2, V4), 5
0
(V2, 4)
((V3, 5))
(V3, V1), 1
0
(V2, 5)
((V3, 3), (V3, 1))
(V3, V1), 2
0
(V4, 1)
Nil
(V3, V1), 3
0
(V1, 4)
Nil
…
…
(V1, 5)
Nil
(V3, V2), 4
0
(V4, 4)
Nil
Etc…
Etc
.
Updating m
Note that (V3, V2),4  0 thus
we remove 4 from the domain of V3
and update (V3, 4)  nil in m
Updating counter
Since 4 is removed from DV3 then
for every (Vk, l) | (V3, 4)  s[(Vk, l)],
we decrement counter[(Vk, V3), l] by 1
Foundations of Constraint Processing
Arc Consistency
33
AC2001
• When checking (Vi,a) against Vj
– Keep track of the Vj value that supports (Vi,a)
–Last((Vi,a),Vi)
• Next time when checking again (Vi,a)
against Vj, we start from Last((Vi,a),Vi)
and don’t have to traverse again the
domain of Vj again or list of tuples in CViVj
• Big savings..
Foundations of Constraint Processing
Arc Consistency
34
Summary of arc-consistency algorithms
•
AC-4 is optimal (worst-case)
•
Warning: worst-case complexity is pessimistic.
Better worst-case complexity: AC-4
Better average behavior: AC-3
[Mohr & Henderson, AIJ 86]
[Wallace, IJCAI 93]
•
AC-5: special constraints
[Van Hentenryck, Deville, Teng 92]
functional, anti-functional, and monotonic constraints
•
AC-6, AC-7: general but rely heavily on data structures for bookkeeping
[Bessière & Régin]
•
Now, back to AC-3: AC-2000, AC-2001≡AC-3.1, AC3.3, etc.
•
Non-binary constraints:
– GAC (general)
– all-different (dedicated)
[Mohr & Masini 1988]
[Régin, 94]
Foundations of Constraint Processing
Arc Consistency
35
AC-what?
Instructor’s personal opinion
• Used to recommend using AC-3
• Now, recommend using AC2001
• Do the project on AC-* if you are curious.. [Régin 03]
Foundations of Constraint Processing
Arc Consistency
36
AC is not enough
Example borrowed from Dechter
V1
V1
a
b
b
=
=
V2
a
a
V3
b
a
V2
b
a
b
V3
b
a
=
Arc-consistent?
Satisfiable?
 seek higher levels of consistency
Foundations of Constraint Processing
Arc Consistency
37
WARNING
→ Completeness: (i.e., for solving the CSP) Running the Waltz
Algorithm does not
B solve the problem.
A
{ 1, 2, 3 }
A
{ 2, 3 }
{ 2, 3, 4 }
B
{ 2, 3 }
A=2  B=3 is still not a solution!
→ Quiescence: The Waltz algorithm may go into infinite loops even
if problem is solvable
x  [0, 100]
x=y
y  [0, 100]
x = 2y
→ Davis characterizes the completeness and quiescence of the Waltz
algorithm (see Table 3) in terms of
– constraint types
– domain types
Foundations of Constraint Processing
Arc Consistency
38
Summary
1. Alert
– Do not confuse a consistency property with the algorithms for
reinforcing it
– For each property, many algorithms may exist
2. Local consistency methods
–
–
–
–
–
Remove inconsistent values (node, arc consistency)
Remove inconsistent tuples (path consistency)
Get us closer to the solution
Reduce the ‘size’ of the problem & thrashing during search
Are ‘cheap’ (i.e., polynomial time)
Foundations of Constraint Processing
Arc Consistency
39