Active Structures Support Problem-driven Learning for Constraint Satisfaction

Cuny Hunter College, New York NY

Investigators

Abstract

Proposal 0739122 ""Active Structures Support Problem-driven Learning for Constraint Satisfaction"" PI: Susan L. Epstein CUNY Hunter College ABSTRACT Many important large-scale, real-world problems can be readily represented, solved and understood as constraint satisfaction problems (CSPs). However, different kinds of CSPs respond to different combinations of solution methods. As a result, there is a persistent bottleneck in constraint satisfaction problem solving: the need for a human expert armed with hard-to-extract domain knowledge and with expert knowledge about CSP methods to select, combine, and tune available techniques into an appropriate CSP solver for the problem at hand. Furthermore, such solvers are typically not re-used to solve similar problems or to reformulate seemingly unsolvable problem into solvable ones. The long-range goal is to understand how to build advanced CSP tools that combine ""class-based learning"" that tailors solution methods to classes of similar problems and ""problem-driven learning"" that tailors solution methods to an individual problem. Problem-driven learning involves detection of ""active"" structures, that is, the most informative and often conflict-ridden sub-problems detected during search and constraint-satisfaction problem solving, particularly in difficult or one-of-a-kind problems, and the use of these structures to generate a class of similar problems from which methods and heuristics for the class can be learned and then applied back to the problem at hand. The specific focus of this project is the detection and harnessing of active structures in problem-driven learning. The project involves collaboration among the PI, the Cork Constraint Computation Center in Ireland, and an expert on visual representation. Results of the project will be made available on a publicly accessible website. The resulting knowledgebase of active structures will help support other research projects on CSP.