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.2546 Hybrid algorithms for the constraint satisfaction problem Prosser, P. Computational Intelligence 9 (1993 ) 268-299 Apr5,2004
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Ⅶ sual image manutacturing processes design of airline timetable ° radio frequency planning
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(L,V, C) I a set of variables Vi, a set of possible values for each variable in I C, a set of Ci] constraints, each a binary relation C={Cl,1….C,nC2,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
Quick Definition of a CSP Constraint Satisfaction Problem ( I,V,C ) - I , a set of variables , a set of variables - Vi, a set of possible values for each variable in a set of possible values for each variable in I. - C, a set of , a set of Cij constraints, each a binary relation 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
How our two talks fit together Six base styles of csp search go Backwards(Bobby) More Chronological Dynamic informed Backjumping Conflict-Directed Backtracking Backup 吗 Styles (1970s) (80s and 90s) ,■■■■口■■■■ Backmarking Go Hybrid onwards 80s and 90's ): algorithms Dan) (an Forward Checking Generally Faster Different styles
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 Advanced Lecture Topic: Fast Solutions to CSPs 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 Apm5,2004
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 ot Dynamic Backtracking Pros and cons Apm5,2004
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 C, a set of Ci] constraints, each a binary relation C={Cl,1….C,nC2,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 D C I=A, B,C D,E A B Vi=red, yellow, blue) Cij=(no neighbor can be the same color E
Quick Definition of a CSP Constraint Satisfaction Problem ( I,V,C ) - I , a set of variables , a set of variables - Vi, a set of possible values for each variable in a set of possible values for each variable in I. - C, a set of , a set of Cij constraints, each a binary relation 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
Simple Example Problem
Search Tree Representation of a cSP Simple Map Coloring Example Variables are assigned values according to an instantiation order The search tree grows downward as A B until each variable is assigned a value from it's domain Dynamic Backtracking allows a E dynamic instantiation order Instantiation Search tree Order 000 A 2)⊙oB 3)°oC→·8·60060·6060606 4)⊙06D 4。。 5)oeE-●O
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 Pushes the first feasible solution further into the search tree A B Still covers all possible permutations of value assignments to variables · Still a valid csp E Search tree Instantiation Order OO A ○eB 3)·°C→●·●0●90·0··●0···0●·0 6朵。。 .eo 's E AAAA
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.)