Learning from Failure in Constraint Satisfaction Search

Diarmuid Grimes, Richard J. Wallace

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs), etc. Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this paper we present a method for learning from search using restarts, in order to identify these critical variables in a given constraint satisfaction problem, prior to solving. Our method is based on the weighted-degree heuristic introduced by Boussemart et al. and is aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimising the overhead of these restarts/probes. We show that random probing of the search space can boost the heuristics power by improving early decisions in search. We also provide an in-depth analysis of the effects of constraint weighting.

Subjects: 12. Machine Learning and Discovery; 15.2 Constraint Satisfaction

Submitted: May 16, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.