Fast Solutions to CSPs Presented by: Robert Effinger Dan Lovell Presented To: 16.412J Cognitive Robotics MIT References: “Dynamic Backtracking” Matthew L. Ginsberg, CIRL, University of Oregon Journal of Artificial Intelligence Research 1 (1993) p. 25-46 “Hybrid algorithms for the constraint satisfaction problem” Prosser, P. Computational Intelligence 9 (1993), 268-299. April 5, 2004 Motivation ? Mobile robot planning ? Resource scheduling ? laying out a silicon chip ? interpret a visual image ? manufacturing processes ? design of airline timetable ? radio frequency planning Quick Definition of a CSP Constraint Satisfaction Problem (I,V,C) - I , a set of variables - Vi, a set of possible values for each variable in I. - C, a set of Cij constraints, each a binary relation C = {C1,1 … C1,n C2,1 … C2,n … Cn,n} A Solution is found when each variable I is assigned a value from it’s domain Vi and the set of all Constraints {C} is satisfied. Go Backwards Go Forwards Chronological Backtracking Backmarking Forward Checking Backjumping Conflict-Directed Backjumping More informed Styles Different styles Six base styles of CSP search Hybrid Algorithms Generally Faster How our two talks fit together Dynamic Backtracking (Bobby) (Dan) (Dan) (1970’s) (80’s and 90’s) (80’s and 90’s) Dynamic Backtracking and a review of: Chronological Backtracking and Conflict-Directed Backjumping Presented by: Robert Effinger Presented To: 16.412J Cognitive Robotics MIT Reference: “Dynamic Backtracking” Matthew L. Ginsberg, CIRL, University of Oregon Journal of Artificial Intelligence Research 1 (1993) p. 25-46 April 5, 2004 Advanced Lecture Topic: Fast Solutions to CSPs Overview ? Definition of a CSP ? Simple Map Coloring Example – Representing a CSP as a Search Tree – Introduce the Example Problem ? Compare Three Backtracking Algorithms – Chronological Backtracking – Conflict-Directed Backjumping – Dynamic Backtracking ? Summary of Dynamic Backtracking – Pros and Cons April 5, 2004 Quick Definition of a CSP Constraint Satisfaction Problem (I,V,C) - I , a set of variables - Vi, a set of possible values for each variable in I. - C, a set of Cij constraints, each a binary relation C = {C1,1 … C1,n C2,1 … C2,n … Cn,n} A Solution is found when each variable I is assigned a value from it’s domain Vi and the set of all Constraints {C} is satisfied. I = {A,B,C,D,E} Vi = {red,yellow,blue} Cij = (no neighbor can be the same color) Simple Example Problem Search Tree Representation of a CSP A B C D E Instantiation Order ? Variables are assigned values according to an instantiation order ? The search tree grows downward as until each variable is assigned a value from it’s domain. ? Dynamic Backtracking allows a dynamic instantiation order 1.) 2.) 3.) 4.) 5.) Search Tree Simple Map Coloring Example Changing the Color Ordering to Create an Interesting Example Problem A B C D E ? Pushes the first feasible solution further into the search tree ? Still covers all possible permutations of value assignments to variables ? Still a valid CSP Search Tree Instantiation Order 1.) 2.) 3.) 4.) 5.) Compare Three Backtracking Algortihms 1.) Chronological Backtracking 2.) Conflict-Directed Backjumping 3.) Dynamic Backtracking Sneak Preview of the Solution Solve map example using: 1.) Chronological Backtracking 2.) Conflict-Directed Backjumping 3.) Dynamic Backtracking Note: This is what the solution will look like each time. We will compare the # of nodes expanded (i.e. regions colored) until the first solution is found A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Chronological_Backtrack() 1.) Set P = {null} (P is the partial solution to the CSP) Set Vi = {1} (start with first variable in instantiation order) 2.) If P = solution, return Success. If Vi = 0 return Failure Else if P = Consistent, set (Vi) to the next variable in instantiation order and assign it’s next domain color (c). Else if P = Inconsistent, remove (c) from domain of (Vi) and continue 3.) While domain of (Vi) is not empty, choose the next domain color (c) and return to step 2. 4.) If domain of (Vi) is empty (i.e. out of colors to try for (Vi) Remove (Vi) from P, set Vi = Vi – 1, and return to step 3. 1.) Chronological Backtracking E Instantiation Order : A B C D 1.) 2.) 3.) 4.) 5.) Notes: Helpful notes will go here # of Nodes Expanded 1 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: Helpful notes will go here # of Nodes Expanded 2 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 3 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 4 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 5 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 6 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 7 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 8 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 8 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 8 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 9 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 9 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 10 s a m e s u b t r e e ! ! ! Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) S a m e s u b t r e e ! ! ! Notes: Chronological backtracking doesn’t notice this is the same subtree, and still searches it. (a.k.a. thrashing) 1.) Chronological Backtracking BT searches same subtree again!!! # of Nodes Expanded 15 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 16 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 16 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: # of Nodes Expanded 16 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 1.) Chronological Backtracking Notes: BT searches wrong subtree again!!! # of Nodes Expanded 16 Notes: Search is repeating the same problem. No solution is possible. Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Cost = 16 Sa me p r o b l e m ! ! ! 1.) Chronological Backtracking BT searches wrong subtree again!!! # of Nodes Expanded 32 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: Now we’re getting somewhere 1.) Chronological Backtracking # of Nodes Expanded 33 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: Now we’re getting somewhere 1.) Chronological Backtracking # of Nodes Expanded 34 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: Now we’re getting somewhere 1.) Chronological Backtracking # of Nodes Expanded 35 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: Now we’re getting somewhere 1.) Chronological Backtracking # of Nodes Expanded 36 Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: Solution Found!! # of Nodes Checked = 37 1.) Chronological Backtracking # of Nodes Expanded 37 2.) Conflict-Directed Backjumping 2.) Conflict-Directed Backjumping Conflict-Directed Backjumping() 1.) Set P = {null} and Set E = {null} 2.) If P = solution, return Success. If Vi = 0 return Failure. Else if P = Consistent, set next as (Vi) and assign next color (c), and goto step 2. Else if P = Inconsistent, remove (c) from domain of (Vi) and continue 3.) While domain of (Vi) is not empty choose the next domain color (c) and goto step 2. 4.) If domain of (Vi) is empty add ( Vi , c ) to Ei set Vi = most recent variable in Ei, and un-assign any variable later in the instantiation order remove any (Ej) involving (Vi), return to step 3. Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) (A database of Conflicts) there are many ways to store these conflicts (E) Eliminating Explanations Notes: Helpful notes will go here. Region A B C D E Elimination Explanations: Color red red yellow blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 2.) Conflict-Directed Backjumping # of Nodes Expanded 1 Region A B C D E Elimination Explanations: Color red yellow red yellow blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 2 Elimination Explanations: Color red yellow blue red yellow blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 3 Region A B C D E Elimination Explanations: Color red yellow blue yellow red yellow A,B blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 4 Elimination Explanations: Color red yellow blue blue red yellow A,B blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 5 Elimination Explanations: Color red yellow blue blue yellow red yellow A,B A,B,D blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 6 Elimination Explanations: Color red yellow blue blue yellow red yellow A,B A,B,D blue A,B,D Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 7 Elimination Explanations: Color red yellow blue blue red Red A,B,D yellow A,B A,B,D blue A,B,D Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue blue red Red A,B,D yellow A,B A,B,D blue A,B A,B,D Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue blue red Red yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue red Red yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue red Red A,B yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 2.) Conflict-Directed Backjumping # of Nodes Expanded 9 Elimination Explanations: Color red yellow blue Red A,B yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: Conflict-Directed Backjumping knows to skip the circled nodes 2.) Conflict-Directed Backjumping # of Nodes Expanded 9 Elimination Explanations: Color red yellow Red A,B yellow A A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 8 nodes expanded so far vs. about 16 for chronological backtracking 2.) Conflict-Directed Backjumping # of Nodes Expanded 9 Elimination Explanations: Color red blue Red yellow A blue A Region A B C D E Notes: Will explore this tree even though no chance of success Cost = 9 nodes better than the 16 nodes during chronological backtracking. Sa me p r o b l e m ! ! ! Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) S a m e p ro b l e m ! ! ! Cost = 9 nodes 2.) Conflict-Directed Backjumping # of Nodes Expanded 18 Elimination Explanations: Color red red Red yellow A blue A Region A B C D E Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 2.) Conflict-Directed Backjumping Notes: Now we’re on the right track # of Nodes Expanded 19 Elimination Explanations: Color red red blue Red yellow A blue A Region A B C D E 2.) Conflict-Directed Backjumping Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: # of Nodes Expanded 20 Elimination Explanations: Color red red blue yellow Red yellow A blue A Region A B C D E 2.) Conflict-Directed Backjumping Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: # of Nodes Expanded 21 Elimination Explanations: Color red red blue yellow yellow Red yellow A A,B,D blue A Region A B C D E 2.) Conflict-Directed Backjumping Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: # of Nodes Expanded 22 Elimination Explanations: Color red red blue yellow blue Red yellow A A,B,D blue A Region A B C D E 2.) Conflict-Directed Backjumping Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: Solution Found!! So l u t i o n F o u n d ! # of Nodes Expanded 23 3.) Dynamic Backtracking 3.) Dynamic Backtracking A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Elimination Explanations: Color red yellow blue Dynamic Backtracking() 1.) Set P = {null} and Set E = {null} 2.) If P = solution, return Success. If Vi = 0 return Failure. Else if P = Consistent, set next as (Vi) and assign next color (c), and goto step 2. Else if P = Inconsistent, remove (c) from domain of (Vi) and continue 3.) While domain of (Vi) is not empty choose the next domain color (c) and goto step 2. 4.) If domain of (Vi) is empty add ( Vi , c ) to Ei Remove (Vi) from P set Vi = most recent variable in Ei any variable not in P remove any (Ej) involving (Vi), return to step 3. Allows a dynamic Instantiation order! Notes: Helpful notes will go here. Region A B C D E Elimination Explanations: Color red red yellow blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) 3.) Dynamic Backtracking # of Nodes Expanded 1 Region A B C D E Elimination Explanations: Color red yellow red yellow blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: 3.) Dynamic Backtracking # of Nodes Expanded 2 Elimination Explanations: Color red yellow blue red yellow blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 3 Region A B C D E Elimination Explanations: Color red yellow blue yellow red yellow A,B blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Notes: 3.) Dynamic Backtracking # of Nodes Expanded 4 Elimination Explanations: Color red yellow blue blue red yellow A,B blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 5 Elimination Explanations: Color red yellow blue blue yellow red yellow A,B A,B,D blue Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 6 Elimination Explanations: Color red yellow blue blue yellow red yellow A,B A,B,D blue A,B,D Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 7 Elimination Explanations: Color red yellow blue blue red Red A,B,D yellow A,B A,B,D blue A,B,D Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue blue red Red A,B,D yellow A,B A,B,D blue A,B A,B,D Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue blue red Red yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue red Red yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 8 Elimination Explanations: Color red yellow blue red Red A,B yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: 3.) Dynamic Backtracking # of Nodes Expanded 9 Elimination Explanations: Color red yellow blue Red A,B yellow A,B blue A,B Instantiation Order : A B C D E 1.) 2.) 3.) 4.) 5.) Region A B C D E Notes: Dynamic Backtracking doesn’t have to erase C. 3.) Dynamic Backtracking # of Nodes Expanded 9 needs to change o.k. Elimination Explanations: Color red Red A,B yellow A,B blue A,B Instantiation Order : A D E 1.) B 2.) 4.) 5.) Region A D E Notes: Dynamic Backtracking doesn’t have to erase C. 3.) Dynamic Backtracking C blue C 3.) B yellow A # of Nodes Expanded 9 Elimination Explanations: Color red blue Red yellow A blue Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: A is recorded as the reason B can’t be yellow 3.) Dynamic Backtracking o.k. # of Nodes Expanded 9 Elimination Explanations: Color red blue blue Red yellow A blue A Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: This is the same problem as before but only costs 6 nodes, since it is lower in the tree. 3.) Dynamic Backtracking S a m e p ro b l e m ! ! ! b u t l e s s c o s t l y ! # of Nodes Expanded 16 Cost = 7 Elimination Explanations: Color red blue blue Red yellow A blue A Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: Now we’re on the right track. 3.) Dynamic Backtracking # of Nodes Expanded 17 Elimination Explanations: Color red blue blue yellow Red yellow A blue A Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: Now we’re on the right track. 3.) Dynamic Backtracking # of Nodes Expanded 18 Elimination Explanations: Color red blue blue yellow Red yellow A A,B,D blue A Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: Now we’re on the right track. 3.) Dynamic Backtracking # of Nodes Expanded 19 Elimination Explanations: Color red blue blue yellow Red yellow A A,B,D blue A Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: Now we’re on the right track. 3.) Dynamic Backtracking # of Nodes Expanded 19 Elimination Explanations: Color red blue blue yellow Red yellow A A,B,D blue A Instantiation Order : A C B D E 1.) 3.) 2.) 4.) 5.) Region A C B D E Notes: Solution Found!! 3.) Dynamic Backtracking So l u t i o n F o u n d ! # of Nodes Expanded 20 Dynamic Backtracking Summary ? Positive Features – Allows a Variable Instantiation Order – Allows partial assignments to remain assigned (if they are not part of a conflict) ? Negative Features – Requires a conflict-detection sub-routine – Requires more memory than simple backtrack search – Completeness proof is not easy to understand or visualize (the proof that it doesn’t skip over any of the search space) A B C D E 1.) 2.) 3.) 4.) 5.) Map Example Results Chronological BT Conflict-Directed BT Dynamic BT 37 23 20 Any Questions?