Solving constraint satisfaction Problems Arc Consistency and constraint propagation Brian Williams 16410-13 September 29th, 2003 Slides adapted from 6.034 Tomas lozano perez and AIMA Stuart Russell Peter Norvig Outline Recap: constraint satisfaction problems(CSP) Solving CSP Arc-consistency and propagation Analysis of constraint propagation · Search
1 Solving Constraint Satisfaction Problems: Arc Consistency and Constraint Propagation 1 Brian Williams 16.410 - 13 September 29th, 2003 Slides adapted from: 6.034 Tomas Lozano Perez and AIMA Stuart Russell & Peter Norvig 2 Outline • Recap: constraint satisfaction problems (CSP) • Solving CSPs • Arc-consistency and propagation • Analysis of constraint propagation • Search
Solving CsPs Solving CSPs involves some combination of 1. Constraint propagation eliminates values that cant be part of any solution 2. Search explores valid assignments Arc Consistency Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc {1,2, {1,2} Directed arc(V, V is arc consistent if For every x in D, there exists some y in D, such that assignment (x,y)is allowed by constraint Ci Or WXEDi EyeD, such that(x,y)is allowed by constraint Ci Where · Y denotes“ for al ·彐 denotes“ there exists ·∈ denotes“in
3 Solving CSPs Solving CSPs involves some combination of: 1. Constraint propagation • eliminates values that can’t be part of any solution 2. Search • explores valid assignments 4 Arc Consistency • Directed arc (Vi , Vj ) is arc consistent if • For every x in Di , there exists some y in Dj such that assignment (x,y) is allowed by constraint Cij • Or ∀x∈Di ∃y∈Dj such that (x,y) is allowed by constraint Cij where • ∀ denotes “for all” • ∃ denotes “there exists” • ∈ denotes “in” Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). Vi Vj {1,2,3} {1,2} =
Arc Consistency Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint(an arc) V {1,2, {1,2} Directed arc ( Vi, vi is arc consistent if VXED,EyED, such that (x,y)is allowed by constraint Ci Example: Given: Variables V, and v2 with Domain (1, 2, 3, 4) Constraint:{(1,3)(1,4)(2,1)} What is the result of arc consistency? Achieving Arc Consistency via Constraint Propagation Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc Directed arc(Vi, vi is arc consistent if WXED; EyeD. such that(x,y) is allowed by constraint Cil Constraint propagation: To achieve arc consistency Delete every value from each tail domain d of each arc that fails this condition Repeat until quiescence If element deleted from D then .check directed arc consistency for each arc with head d Maintain arcs to be checked on FiFo queue(no duplicates)
5 Arc Consistency • Directed arc (Vi , Vj ) is arc consistent if • ∀x∈Di ∃y∈Dj such that (x,y) is allowed by constraint Cij Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). Vi Vj {1,2,3} {1,2} = Example: Given: Variables V1 and V2 with Domain {1,2,3,4} Constraint: {(1, 3) (1, 4) (2, 1)} What is the result of arc consistency? 6 Achieving Arc Consistency via Constraint Propagation • Directed arc (Vi , Vj ) is arc consistent if ∀x∈Di ∃y∈Dj such that (x,y) is allowed by constraint Cij Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). Constraint propagation: To achieve arc consistency: • Delete every value from each tail domain Di of each arc that fails this condition, • Repeat until quiescence: • If element deleted from Di then •check directed arc consistency for each arc with head Di • Maintain arcs to be checked on FIFO queue (no duplicates)
Constraint Propagation Example Graph Coloring R G. B Different-color constraint Initial Domains Each undirected constraint arc denotes two directed constraint arcs Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted G Arcs to examine V-VoV-VoV. Introduce queue of arcs to be examined Start by adding all arcs to the queue
7 Constraint Propagation Example R,G,B R, G G Graph Coloring Initial Domains Different-color constraint V1 V2 V3 Each undirected constraint arc denotes two directed constraint arcs. 8 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 Arc examined Value deleted R,G,B R, G G V2 V3 V1 Graph Coloring Initial Domains Arcs to examine V1-V2, V1-V3, V2-V3 • Introduce queue of arcs to be examined. • Start by adding all arcs to the queue
Constraint Propagation Example Graph Coloring R G. B *Different-color constraint Initial Domains Arc examined Value deleted R.G.B v1> R G G Arcs to examine V,<Vo,V-VoV. Delete unmentioned tail values .Vi-V, denotes two arcs between V; and Vi Vi<Vj denotes an arc from V, and Vig Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted R G. B none Arcs to examine V1<v2,V1-3V2-V3 Delete unmentioned tail values .V-V denotes two arcs between v and v Vi< Vi denotes an arc from V, and V-10
9 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1 > V2 Arc examined Value deleted R,G,B R, G G V2 V3 V1 Graph Coloring Initial Domains Arcs to examine V1 V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1<V2, V1-V3, V2-V3 • Vi – Vj denotes two arcs between Vi and Vj . • Vi < Vj denotes an arc from Vj and Vi . • Delete unmentioned tail values
Constraint Propagation Example Graph Coloring R G. B *Different-color constraint Initial Domains Arc examined Value deleted R.G.B none V>V R G G Arcs to examine Delete unmentioned tail values .Vi-V, denotes two arcs between V; and Vi ViV none Arcs to examine Delete unmentioned tail values .V-V denotes two arcs between v and v Vi< Vi denotes an arc from V, and Vi-12
11 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V2 > V1 V1 > V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1-V3, V2-V3 • Vi – Vj denotes two arcs between Vi and Vj . • Vi V1 none V1 > V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1-V3, V2-V3 • Vi – Vj denotes two arcs between Vi and Vj . • Vi < Vj denotes an arc from Vj and Vi . • Delete unmentioned tail values
Constraint Propagation Example Graph Coloring R G. B *Different-color constraint Initial Domains Arc examined Value deleted R.G.B none R G G Arcs to examine Delete unmentioned tail values .Vi-V, denotes two arcs between V; and Vi Vi<Vj denotes an arc from V, and V.-13 Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted G non Arcs to examine V1V3s V2-V3 Delete unmentioned tail values .V-V denotes two arcs between v and v Vi< Vi denotes an arc from V, and V-14
13 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1-V3, V2-V3 • Vi – Vj denotes two arcs between Vi and Vj . • Vi V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1<V3, V2-V3 • Vi – Vj denotes two arcs between Vi and Vj . • Vi < Vj denotes an arc from Vj and Vi . • Delete unmentioned tail values
Constraint Propagation Example Graph Coloring R G. B Different-color constraint Initial Domains Arc examined Value deleted R, 2, B none V1>V2 V1(G) R G G Arcs to examine V,V V,(G) Arcs to examine V,V,yV IF An element of a variables domain is removed THEN add all arcs to that variable to the examination queue
15 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1 V (G) 1>V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R,G,B R, G G V2 V3 V1 Arcs to examine V1V1, V1<V3, IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue
Constraint Propagation Example Graph Coloring R G. B Different-color constraint Initial Domains Arc examined Value deleted R, B none V.>V. V,IG R G G V.V1 Delete unmentioned tail values IF An element of a variables domain is removed THEN add all arcs to that variable to the examination qu
17 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R, B R, G G V2 V3 V1 Arcs to examine V2-V3, V2>V1 • Delete unmentioned tail values IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue. 18 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V1V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R, B R, G G V2 V3 V1 Arcs to examine V2-V3, V2>V1 • Delete unmentioned tail values IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue
Constraint Propagation Example Graph Coloring R G. B Different-color constraint Initial Domains Arc examined Value deleted R, B none V1(G) R G G V2>V2 Arcs to examine VV Delete unmentioned tail values F An element of a variable 's domain is removed THEN add all arcs to that variable to the examination queue Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted R, B V>V V2(G) Arcs to examine V2V1 Delete unmentioned tail values IF An element of a variables domain is removed THEN add all arcs to that variable to the examination qu
19 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V2 >V3 V1 V (G) 1-V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R, B R, G G V2 V3 V1 Arcs to examine V2V1 • Delete unmentioned tail values IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue. 20 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V2 V (G) 2 >V3 V1 V (G) 1-V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains R, B R, G G V2 V3 V1 Arcs to examine V2V1 • Delete unmentioned tail values IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue