Solving Constraint Satisfaction Problems Forward Checking Brian C. Williams 16410 October 1st 2003 Slides adapted from 6.034 Tomas Lozano perez With help from Stuart russell Peter norvig CSPS and Encoding 4 Queens Problem: Place queens so that Q none can attack the other Q Assume one queen per column What row should each queen be in? 1234 A Constraint Satisfaction Problem is a triple Variables v 12,3,以4, Domains d {1,2,3,4} Constraints Q<> On different rows Q-Q|<> Stay off the diagonals Example:C12={(1,3)(14)(2,4)(3,1)(4,1)(4,2)} CSP solution: any assignment to v, such that all constraints in C are satisfied
1 Solving Constraint Satisfaction Problems: Forward Checking 1 Brian C. Williams 16.410 October 1st, 2003 Slides adapted from: 6.034 Tomas Lozano Perez With help from: Stuart Russell & Peter Norvig 2 CSPS and Encoding 4 Queens Variables V Constraints C Qi <> Qj On different rows Domains D {1, 2, 3, 4} Q1, Q2, Q3, Q4, 1 2 3 4 12 34 Q Problem: Place queens so that none can attack the other. Q Q Q A Constraint Satisfaction Problem is a triple : |Qi - Qj | <> |i-j| Stay off the diagonals Example: C1,2 = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)} • Assume one queen per column. • What row should each queen be in? CSP solution: any assignment to V, such that all constraints in C are satisfied
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, v) is arc consistent if VXED, 3yED, such that(x, y) is allowed by constraint C 12队 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 Di then check directed arc consistency for each arc with head d Maintain arcs to be checked on FIFo queue(no duplicates). 3 Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted V2(G) V,(R) Arcs to examine none V3>V1 none F examination queue is empty THEN arc(pairwise) consistent
3 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). Vi Vj {1,2,3} {1,2} = 4 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V3>V1 none V2>V1 none V1 V (R) 2-V1 V2 V (G) 2 -V3 V1 V (G) 1-V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains B R G V2 V3 V1 Arcs to examine IF examination queue is empty THEN arc (pairwise) consistent
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 explores consequences of committing to particular assignments Methods Incorporating Search Standard search Back Track search (BD BT with Forward Checking(FC) Dynamic Variable Ordering(DV Iterative Repair Backjumping(BJ) Solving CSPs with Standard Search · State Variables assigned thus far · Initial state · No assignments Operator Assign value to any unassigned variable ·Goa|Test All variables assigned All constraints satisfied · Branching factor? 2 Sum of domain size of all variables O(v*d) Performance? 9 exponential in branching factor R. G
5 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 • Back Track search (BT) • BT with Forward Checking (FC) • Dynamic Variable Ordering (DV) • Iterative Repair • Backjumping (BJ) 6 Solving CSPs with Standard Search • State • Initial State • Operator • Goal Test • Variables assigned thus far • No assignments • Assign value to any unassigned variable • All variables assigned • All constraints satisfied • Branching factor? Î Sum of domain size of all variables O(v*d) • Performance? Î exponential in branching factor R, G R, G R, G, B V1 V3 V2
Search Performance on n queens Standard search A handful of queens Backtracking Solving CSPs with Standard Search Standard Search Children select any value to any variable [O(v*d)] Test complete assignments against CSP Observations 1. The order in which variables are assigned does not change the solution e Many paths denote the same solution(nI), e so expand only one path 2. We can identify a dead end before assigning all variables 9 Extensions to inconsistent partial assignments are always inconsistent So check after each assignment. R. G
7 Search Performance on N Queens • Standard Search • Backtracking • A handful of queens 1 2 3 4 Q Q Q Q 8 Solving CSPs with Standard Search Standard Search: • Children select any value to any variable [O(v*d)] • Test complete assignments against CSP Observations: 1. The order in which variables are assigned does not change the solution. Î Many paths denote the same solution (n!), Î so expand only one path. 2. We can identify a dead end before assigning all variables Î Extensions to inconsistent partial assignments are always inconsistent Î So check after each assignment. R, G R, G R, G, B V1 V3 V2
BackTrack Search(BT) 1. Expand the assignments of only one variable at each step 2. Pursue depth first 3. Check consistency after each expansion, and backup V, assignments V2 assignments V3 assignments Select variable Expand ordering to assign designated G variable R. G R, G BackTrack Search(BT) Expand the assignments of only one variable at each step 2. Pursue depth first 3. Check consistency after each expansion, and backup B V, assignments G Backup at ordering to assign designated inconsistent variable assignment R. G
9 BackTrack Search (BT) 1. Expand the assignments of only one variable at each step. 2. Pursue depth first. 3. Check consistency after each expansion, and backup. R, G R, G R, G, B V1 V3 V2 V1 assignments V2 assignments V3 assignments Select variable ordering to assign R G B Expand designated variable 10 BackTrack Search (BT) 1. Expand the assignments of only one variable at each step. 2. Pursue depth first. 3. Check consistency after each expansion, and backup. R, G R, G R, G, B R G R G V1 V3 V2 R G R G R G B R G R G R G Assign designated variable V1 assignments V2 assignments V3 assignments Select variable ordering to assign Backup at inconsistent assignment
Search Performance on n queens Standard Search A handful of queens Backtracking About 15 queens Search Performance on n Queens Standard search a handful of queens Backtracking About 15 queens BT with Forward Checking
11 Search Performance on N Queens • Standard Search • Backtracking • A handful of queens • About 15 queens 1 2 3 4 Q Q Q Q 12 Search Performance on N Queens • Standard Search • Backtracking • BT with Forward Checking • A handful of queens • About 15 queens 1 2 3 4 Q Q Q Q
Combine Backtracking Limited Constraint Propagation Initially: Prune domains using constraint propagation If complete consistent assignment, then return Choose unassigned variable Choose assignment from pruned domain Prune domains using constraint propagation if a domain has no remaining elements, then backtrack Question: Full propagation is O(ed3) How much propagation should we do? Very little Just check arc consistency for those arcs terminating on the new assignment o(ed) called forward checking(FC) Backtracking with Forward Checking (BT-FC) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V, assignments R, G 1. Perform initial pruning
13 Combine Backtracking & Limited Constraint Propagation Initially: Prune domains using constraint propagation Loop: • If complete consistent assignment, then return. • Choose unassigned variable • Choose assignment from pruned domain • Prune domains using constraint propagation • if a domain has no remaining elements, then backtrack. Question: Full propagation is O(ed3), How much propagation should we do? Very little: •Just check arc consistency for those arcs terminating on the new assignment O(ed). • called forward checking (FC). 14 Backtracking with Forward Checking (BT-FC) R, G R, G R, G, B V1 V3 V2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V1 assignments V2 assignments V3 assignments 1. Perform initial pruning
Backtracking with Forward Checking(BT-Fc) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V2 assignments V3 assignments G G 1. Perform initial pruning Backtracking with Forward Checking (BT-FC) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V, assignments 1. Perform initial pruning
15 Backtracking with Forward Checking (BT-FC) R, G R, G R V1 V3 V2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V1 assignments V2 assignments V3 assignments 1. Perform initial pruning. 16 Backtracking with Forward Checking (BT-FC) G G R V1 V3 V2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V1 assignments V2 assignments V3 assignments 1. Perform initial pruning
Backtracking with Forward checking (BT-Fc) 1. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V2 assignments V3 assignments G 1. Perform initial pruning Backtracking with Forward Checking (BT-FC) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V, assignments a 3. We have a conflict whenever a domain becomes empty · Back trac 1. Perform initial pruning
17 Backtracking with Forward Checking (BT-FC) G G R V1 V3 V2 R V1 assignments V2 assignments V3 assignments G 1. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. 1. Perform initial pruning. 18 Backtracking with Forward Checking (BT-FC) G R V1 V3 V2 R V1 assignments V2 assignments V3 assignments G x 3. We have a conflict whenever a domain becomes empty. • Back track 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. 1. Perform initial pruning. x
Backtracking with Forward Checking(BT-Fc) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment G V2 assignments 3. We have a conflict whenever a domain becomes empty · Back track G Restore domain values V2 R G 1. Perform initial pruning Backtracking with Forward Checking (BT-FC) 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment V, assignments G 3. We have a conflict whenever a domain becomes empty · Back track Restore domain values R G R, G 1. Perform initial pruning
19 Backtracking with Forward Checking (BT-FC) R, G R, G R, G, B V1 V3 V2 V1 assignments G V2 assignments V3 assignments 3. We have a conflict whenever a domain becomes empty. • Back track • Restore domain values 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. 1. Perform initial pruning. 20 Backtracking with Forward Checking (BT-FC) R, G R, G G V1 V3 V2 V1 assignments G V2 assignments V3 assignments 3. We have a conflict whenever a domain becomes empty. • Back track • Restore domain values 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. 1. Perform initial pruning