1 Solving Constraint Satisfaction Problems: Arc Consistency and Constraint Propagation 1 Brian Williams 16.410 - 13 September 29 th , 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 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 (V i , V j ) is arc consistent if ? For every x in D i , there exists some y in D j such that assignment (x,y) is allowed by constraint C ij ?Or ?x∈D i ?y∈D j such that (x,y) is allowed by constraint C ij 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). V i V j {1,2,3} {1,2} = 5 Arc Consistency ? Directed arc (V i , V j ) is arc consistent if ? ?x∈D i ?y∈D j such that (x,y) is allowed by constraint C ij Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). V i V j {1,2,3} {1,2} = Example: Given: Variables V 1 and V 2 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 (V i , V j ) is arc consistent if ?x∈D i ?y∈D j such that (x,y) is allowed by constraint C ij 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 D i of each arc that fails this condition, ? Repeat until quiescence: ? If element deleted from D i then ?check directed arc consistency for each arc with head D i ? Maintain arcs to be checked on FIFO queue (no duplicates). 7 Constraint Propagation Example R,G,B GR, G Graph Coloring Initial Domains Different-color constraint V 1 V 2 V 3 Each undirected constraint arc denotes two directed constraint arcs. 8 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 Value deletedArc examined R,G,B GR, G V 2 V 3 V 1 Graph Coloring Initial Domains Arcs to examine V 1 -V 2 , V 1 -V 3 , V 2 -V 3 ? Introduce queue of arcs to be examined. ? Start by adding all arcs to the queue. 9 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 > V 2 Value deletedArc examined R,G,B GR, G V 2 V 3 V 1 Graph Coloring Initial Domains Arcs to examine V 1 <V 2 , V 1 -V 3 , V 2 -V 3 ?V i –V j denotes two arcs between V i and V j . ? Vi < Vj denotes an arc from V j and V i . ? Delete unmentioned tail values 10 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 noneV 1 > V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 <V 2 , V 1 -V 3 , V 2 -V 3 ?V i –V j denotes two arcs between V i and V j . ? Vi < Vj denotes an arc from V j and V i . ? Delete unmentioned tail values 11 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 2 > V 1 noneV 1 > V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 -V 3 , V 2 -V 3 ?V i –V j denotes two arcs between V i and V j . ? Vi < Vj denotes an arc from V j and V i . ? Delete unmentioned tail values 12 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 noneV 2 > V 1 noneV 1 > V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 -V 3 , V 2 -V 3 ?V i –V j denotes two arcs between V i and V j . ? Vi < Vj denotes an arc from V j and V i . ? Delete unmentioned tail values 13 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 -V 3 , V 2 -V 3 ?V i –V j denotes two arcs between V i and V j . ? Vi < Vj denotes an arc from V j and V i . ? Delete unmentioned tail values 14 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 >V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 <V 3 , V 2 -V 3 ?V i –V j denotes two arcs between V i and V j . ? Vi < Vj denotes an arc from V j and V i . ? Delete unmentioned tail values 15 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 (G)V 1 >V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 <V 3 , V 2 -V 3 IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue. 16 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 (G)V 1 >V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R,G,B GR, G V 2 V 3 V 1 Arcs to examine V 1 <V 3 , V 2 -V 3 , V 2 >V 1 , V 1 <V 3 , IF An element of a variable’s domain is removed, THEN add all arcs to that variable to the examination queue. 17 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 <V 3 V 1 (G)V 1 >V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR, G V 2 V 3 V 1 Arcs to examine V 2 -V 3 , V 2 >V 1 ? 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 GR, G Different-color constraint V 1 V 2 V 3 noneV 1 <V 3 V 1 (G)V 1 >V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR, G V 2 V 3 V 1 Arcs to examine V 2 -V 3 , V 2 >V 1 ? 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. 19 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 2 >V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR, G V 2 V 3 V 1 Arcs to examine V 2 <V 3 , V 2 >V 1 ? 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 GR, G Different-color constraint V 1 V 2 V 3 V 2 (G)V 2 >V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR, G V 2 V 3 V 1 Arcs to examine V 2 <V 3 , V 2 >V 1 ? 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. 21 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 2 (G)V 2 >V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR, G V 2 V 3 V 1 Arcs to examine V 2 <V 3 , V 2 >V 1 , V 1 >V 2 ? 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. 22 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 3 > V 2 V 2 (G)V 2 >V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine V 2 >V 1 , V 1 >V 2 ? 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. 23 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 noneV 3 > V 2 V 2 (G)V 2 >V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine V 2 >V 1 , V 1 >V 2 ? 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. 24 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 2 >V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine V 1 >V 2 ? 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. 25 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 noneV 2 >V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine V 1 >V 2 ? 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. 26 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 >V 2 noneV 2 >V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine ? 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. 27 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 (R)V 1 >V 2 noneV 2 >V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine ? 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. 28 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 1 (R)V 1 >V 2 noneV 2 >V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains R, B GR V 2 V 3 V 1 Arcs to examine V 2 >V 1 , V 3 >V 1 ? 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. 29 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 V 3 >V 1 V 2 >V 1 V 1 (R)V 2 -V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains B GR V 2 V 3 V 1 Arcs to examine ? 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. 30 Constraint Propagation Example R,G,B GR, G Different-color constraint V 1 V 2 V 3 noneV 3 >V 1 noneV 2 >V 1 V 1 (R)V 2 -V 1 V 2 (G)V 2 -V 3 V 1 (G)V 1 -V 3 noneV 1 –V 2 Value deletedArc examined Graph Coloring Initial Domains B GR V 2 V 3 V 1 Arcs to examine IF examination queue is empty THEN arc (pairwise) consistent. 31 Outline ? What is a constraint satisfaction problem (CSPS)? ? Solving CSPs ? Arc-consistency and propagation ? Analysis of constraint propagation ?Search 32 What is the Complexity of Constraint Propagation? Assume: ? domains are of size at most d ?there are e binary constraints. Which is the correct complexity? 1. O(d 2 ) 2. O(ed 2 ) 3. O(ed 3 ) 4. O(e d ) 33 Complexity of Constraint Propagation Assume: ? domains are of size at most d ?there are e binary constraints. Complexity: ? Straight forward arc consistency is O(ed 3 ) ? There are 2 * e arcs to check ? Verifying arc consistency takes O(d 2 ) for each arc. ? An arc is checked at most O(d) times. 34 Is arc consistency sound and complete? R, G R, GR, G Each arc consistent solution selects a value for every variable from the arc consistent domains. Completeness: Does arc consistency rule out any valid solutions? ?Yes ?No Soundness: Is every arc-consistent solution a solution to the CSP? ? Yes ?No 35 Arc consistency doesn’t rule out all infeasible solutions R, G R, GR, G R, G R, G B, G Graph Coloring arc consistent but no solutions arc consistent but 2 solutions, not 8. B,R,G B,G,R 36 Next: To Solve CSPs we combine arc consistency and search 1. Arc consistency (Constraint propagation), ? eliminates values that are shown locally to not be a part of any solution. 2. Search ? explores consequences of committing to particular assignments. Methods Incorporating Search: ? Standard Search ? BackTrack search (BT) ? BT with Forward Checking (FC) ? Dynamic Variable Ordering (DV) ? Iterative Repair ? Backjumping (BJ)