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