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, bookkeepingOutline • 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