Fast solutions to csps B ased on PROSSER, P Hybrid algorithms for the constraint satisfaction problem Computational Intelligence 9 (1993),268-299 Outline · Motivation Methods of advancing csp search Backmarking Forward Checking Hybrid algorithms · Conclusion
Fast Solutions to CSP’s Based on PROSSER, P. Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9 (1993), 268--299 Outline • Motivation • Methods of advancing CSP search – Backmarking – Forward Checking • Hybrid algorithms • Conclusion
Problem to be solved Given a set of n variables where the ith variable 1<=k<=n, has a discrete domain of values it can take, domain/i and a set of binary relations C 1nC21…C2n…Cnn, find the first consistent instantiation of these variables which satisfies all the relations Notation Current variable is indexed with 1, Vi Past variables will be variables that have already been instantiated (those whose index is <1) Future variables will be those yet to be instantiated (those whose index is >1) Why Binary CSPs Every higher order(multiple variables), finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introduced
Problem to be solved Given a set of n variables where the ith variable, 1<= i<=n, has a discrete domain of values it can take, domain[i], and a set of binary relations C = {C1,1 … C1,n C2,1 … C2,n … Cn,n}, find the first consistent instantiation of these variables which satisfies all the relations. Notation: Current variable is indexed with i, Vi Past variables will be variables that have already been instantiated (those whose index is <i ) Future variables will be those yet to be instantiated (those whose index is >i ) Why Binary CSP’s Every higher order (multiple variables) , finite domain constraint can be reduced to a set of binary constraints if enough auxillary variables are introduced
What is the forward move and why change it? Forward move- the procedure that determines what actions to take(consistency checks, bookkeeping, etc)when the next variable is instantiated Goal: avoid unnecessary computation .Backmarking(BM)-remembers consistency checks it already erformed Forward Checking(FC)-doesn't expand nodes it knows arent feasible The 5 Base styles of search Go Backwards More BJ CBJ informed BM yards algorithms FC Generally Faste Different styles
What is the forward move and why change it? Forward move – the procedure that determines what actions to take (consistency checks, bookkeeping, etc) when the next variable is instantiated. Goal : avoid unnecessary computation •Backmarking (BM) – remembers consistency checks it already performed •Forward Checking (FC) – doesn’t expand nodes it knows aren’t feasible Go Backwards Go Forwards BT BM FC BJ CBJ More informed styles Different styles The 5 Base styles of search Hybrid Algorithms Generally Faster
Outline · Motivation Methods of advancing CSP search Backmarking Forward Checking ° Hybrid algorithms · Conclusion What does bm do? Objective: BM prevents redundant consistency checks when The current variable is known to fail with its current value because of some variable in the past still has the value that made the current variable fail The current variable is known to succeed with its current value in a check against a past value that still has the same value that made the current variable succeed Tradeoff: must spend time doing, and allot space for, bookkeeping
Outline • Motivation • Methods of advancing CSP search – Backmarking – Forward Checking • Hybrid algorithms • Conclusion What does BM do? • Objective : BM prevents redundant consistency checks when – The current variable is known to fail with its current value because of some variable in the past still has the value that made the current variable fail. – The current variable is known to succeed with its current value in a check against a past value that still has the same value that made the current variable succeed. • Tradeoff : must spend time doing, and allot space for, bookkeeping
What does bm do? Maximum checking level(mcl)array Size= number of variables x domain size mcli, k] holds the index of the deepest variable that v=k, kEDi, was checked against Minimum backup level(mbl)array Size= number of variablesx 1 mbl[i] the index of the shallowest past variable that has changed value since v[i] was the current variable What does bm do? mcli k]< mbl] means the previous consistency check between v-k and some variable in the past of mcli, k] failed and will still fail because mcli, k] hasnt been changed mcll, k>=mbll] means[=k passed consistency checking for all variables in the past of mbl1]. Vi] only needs to be checked for consistency with the new variables, those in the future of mbl[]
What does BM do? • Maximum checking level (mcl) array – Size = Number of variables x domain size – mcl[i,k] holds the index of the deepest variable that v[i] = k, k ∊ Di , was checked against • Minimum backup level (mbl) array – Size = Number of variables x 1 – mbl[i] the index of the shallowest past variable that has changed value since v[i] was the current variable What does BM do? • mcl[i,k] < mbl[i] means the previous consistency check between v[I] = k and some variable in the past of mcl[i,k] failed and will still fail because mcl[i,k] hasn’t been changed • mcl[I,k] >= mbl[i] means v[i] = k passed consistency checking for all variables in the past of mbl[i]. V[i] only needs to be checked for consistency with the new variables, those in the future of mbl[i]