1 Solving Constraint Satisfaction Problems: Forward Checking 1 Brian C. Williams 16.410 October 1 st , 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 Q i <> Q j On different rows Domains D {1, 2, 3, 4} Q 1 , Q 2 , Q 3 , Q 4 , 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 <V,D,C>: |Q i -Q j | <> |i-j| Stay off the diagonals Example: C 1,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. 3 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 Di then check directed arc consistency for each arc with head D i ? Maintain arcs to be checked on FIFO queue (no duplicates). V i V j {1,2,3} {1,2}= 4 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. 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 V 1 V 3 V 2 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 V 1 V 3 V 2 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 V 1 V 3 V 2 V 1 assignments V 2 assignments V 3 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 V 1 V 3 V 2 R G R G R G B R G R G R G Assign designated variable V 1 assignments V 2 assignments V 3 assignments Select variable ordering to assign Backup at inconsistent assignment 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 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(ed 3 ), 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 V 1 V 3 V 2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V 1 assignments V 2 assignments V 3 assignments 1. Perform initial pruning. 15 Backtracking with Forward Checking (BT-FC) R, G R, G R V 1 V 3 V 2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V 1 assignments V 2 assignments V 3 assignments 1. Perform initial pruning. 16 Backtracking with Forward Checking (BT-FC) GG R V 1 V 3 V 2 2. After selecting each assignment, remove any values of neighboring domains that are inconsistent with the new assignment. R V 1 assignments V 2 assignments V 3 assignments 1. Perform initial pruning. 17 Backtracking with Forward Checking (BT-FC) GG R V 1 V 3 V 2 R V 1 assignments V 2 assignments V 3 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 V 1 V 3 V 2 R V 1 assignments V 2 assignments V 3 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 19 Backtracking with Forward Checking (BT-FC) R, G R, G R, G, B V 1 V 3 V 2 GV 1 assignments V 2 assignments V 3 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 V 1 V 3 V 2 GV 1 assignments V 2 assignments V 3 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. 21 Backtracking with Forward Checking (BT-FC) RR G V 1 V 3 V 2 GV 1 assignments V 2 assignments V 3 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. 22 Backtracking with Forward Checking (BT-FC) RR G V 1 V 3 V 2 G R V 1 assignments V 2 assignments V 3 assignments Note: No need to check new assignment against previous 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. 23 Backtracking with Forward Checking (BT-FC) R G V 1 V 3 V 2 G R V 1 assignments V 2 assignments V 3 assignments x 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. 24 Backtracking with Forward Checking (BT-FC) R, G R, G R, G, B V 1 V 3 V 2 B V 1 assignments V 2 assignments V 3 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. 25 Backtracking with Forward Checking (BT-FC) R, G R, G B V 1 V 3 V 2 B V 1 assignments V 2 assignments V 3 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. 26 Backtracking with Forward Checking (BT-FC) RR, G B V 1 V 3 V 2 B R V 1 assignments V 2 assignments V 3 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. 27 Backtracking with Forward Checking (BT-FC) R G B V 1 V 3 V 2 B R V 1 assignments V 2 assignments V 3 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. 28 Backtracking with Forward Checking (BT-FC) R G B V 1 V 3 V 2 B R V 1 assignments V 2 assignments V 3 assignments G Solution! 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. 29 Backtracking with Forward Checking (BT-FC) G R B V 1 V 3 V 2 B G V 1 assignments V 2 assignments V 3 assignments R BT-FC is generally faster than pure BT because it avoids rediscovering inconsistencies. 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. 30 Search Performance on N Queens ? Standard Search ? Backtracking ? BT with Forward Checking ? A handful of queens ? About 15 queens ? About 30 queens 1 2 3 4 Q Q Q Q 31 BT-FC with dynamic ordering Traditional backtracking uses fixed ordering of variables & values Typically better to choose ordering dynamically as search proceeds. ? Most constrained variable when doing forward-checking, pick variable with fewest legal values to assign next (minimizes branching factor) ? Least constraining value choose value that rules out the smallest number of values in variables connected to the chosen variable by constraints. 32 Which country should we color next E most-constrained variable (smallest domain) What color should we pick for it? RED least-constraining value (eliminates fewest values from neighboring domains) A B DE Colors: R, G, B, Y C R, Y G, B, Y F R, B, Y 33 Search Performance on N Queens ? Standard Search ? Backtracking ? BT with Forward Checking ? Dynamic Variable Ordering ? A handful of queens ? About 15 queens ? About 30 queens ? About 1,000 queens 1 2 3 4 Q Q Q Q 34 Back jumping Backtracking At dead end backup to most recent variable, Backjumping At dead end backup to most recent variable that eliminated a value in the current (empty) domain. 1 2 3 4 5 6 123456 Q22 2 2 2 2 Q1 1 1 1 1 1 1 1 1 1 Q3 3 3 3 3 6-Queens variables: board columns domains: board rows 25 253 5 2 3 4 6 35 Back jumping 1 2 3 4 5 6 123456 Q Q 1 2 1 1 1 1 Q 2 2 1 2 3 1 3 1 3 2 1 2 1 3 3 25 2536 253 5 2 3 4 6 6-Queens variables: board columns domains: board rows Q 44 4 Backtracking At dead end backup to most recent variable, Backjumping At dead end backup to most recent variable that eliminated a value in the current (empty) domain. 36 Back jumping 1 2 3 4 5 6 123456 Q Q 1 2 1 1 1 1 Q 2 2 1 2 3 1 3 1 3 2 1 2 1 3 3 25 2536 25364 253 5 2 3 4 6 6-Queens variables: board columns domains: board rows Q 44 4 Q Failures here should look to variable 4. Changing variable 5 won’t help Backtracking At dead end backup to most recent variable, Backjumping At dead end backup to most recent variable that eliminated a value in the current (empty) domain. 37 Search Performance on N Queens ? Standard Search ? Backtracking ? Backjumping ? BT with Forward Checking ? Dynamic Variable Ordering ? Iterative Repair ? A handful of queens ? About 15 queens ? ??? ? About 30 queens ? About 1,000 queens ? About 10,000,000 queens (except truly hard problems) 1 2 3 4 Q Q Q Q