Fast Solutions to CSPsPresented by: Robert EffingerDan LovellPresented To: 16.412J Cognitive RoboticsMITReferences: “Dynamic Backtracking” Matthew L. Ginsberg, CIRL, University of OregonJournal 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, 2004Motivation• Mobile robot planning• Resource scheduling• laying out a silicon chip• interpret a visual image • manufacturing processes• design of airline timetable• radio frequency planningQuick Definition of a CSPConstraint Satisfaction Problem (I,V,C)--II, a set of variables, a set of variables--Vi,Vi,a set of possible values for each variable in a set of possible values for each variable in II..--CC, a set of, a set ofCijCijconstraints, 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.Go BackwardsGoForwardsChronologicalBacktrackingBackmarkingForward CheckingBackjumpingConflict-DirectedBackjumpingMore informedStylesDifferent stylesSix base styles of CSP searchHybridAlgorithmsGenerallyFasterHow our two talks fit togetherDynamicBacktracking(Bobby)(Dan) (Dan)(1970’s) (80’s and 90’s)(80’s and 90’s)Dynamic Backtrackingand a review of: Chronological Backtracking andConflict-Directed BackjumpingPresented by: Robert EffingerPresented To: 16.412J Cognitive RoboticsMITReference: “Dynamic Backtracking” Matthew L. Ginsberg, CIRL, University of OregonJournal of Artificial Intelligence Research 1 (1993) p. 25-46April 5, 2004Advanced Lecture Topic: Fast Solutions to CSPsOverview• 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 ConsApril 5, 2004Quick Definition of a CSPConstraint Satisfaction Problem (I,V,C)--II, a set of variables, a set of variables--Vi,Vi,a set of possible values for each variable in a set of possible values for each variable in II..--CC, a set of, a set ofCijCijconstraints, 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 ProblemSearch Tree Representation of a CSP ABCDEInstantiation Order• Variables are assigned values according to an instantiation order • The search tree grows downward as until each variable is assigned a valuefrom it’s domain.• Dynamic Backtracking allows a dynamic instantiation order1.)2.)3.)4.)5.)Search TreeSimple Map Coloring ExampleChanging the Color Ordering to Create an Interesting Example ProblemABCDE• Pushes the first feasible solution further into the search tree• Still covers all possible permutations of value assignments to variables• Still a valid CSPSearch TreeInstantiation Order1.)2.)3.)4.)5.)Compare Three Backtracking Algortihms1.) Chronological Backtracking2.) Conflict-Directed Backjumping3.) Dynamic BacktrackingSneak Preview of the SolutionSolve map example using:1.) Chronological Backtracking2.) Conflict-Directed Backjumping3.) Dynamic BacktrackingNote: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 foundABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingInstantiation Order :ABCDE1.)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 continue3.) 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 BacktrackingEInstantiation Order :ABCD1.)2.)3.)4.)5.)Notes:Helpful notes will go here# of Nodes Expanded1Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:Helpful notes will go here# of Nodes Expanded2Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded3Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded4Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded5Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded6Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded7Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded8Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded8Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded8Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded9Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded9Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded10same subtree!!!Instantiation Order :ABCDE1.)2.)3.)4.)5.)Same subtree!!!Notes:Chronological backtracking doesn’t notice this is the same subtree, and still searches it.(a.k.a. thrashing)1.) Chronological BacktrackingBT searches same subtree again!!!# of Nodes Expanded15Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded16Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded16Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:# of Nodes Expanded16Instantiation Order :ABCDE1.)2.)3.)4.)5.)1.) Chronological BacktrackingNotes:BT searches wrong subtree again!!!# of Nodes
View Full Document
Unlocking...