Integrating Planning and Search Methods to Solve Constraint Problems

Cuny Hunter College, New York NY

Investigators

Abstract

This project speeds the uptake of an important technology: constraint satisfaction programming. Many large-scale, real-world problems in areas such as design and configuration, planning and scheduling, and diagnosis and testing are readily understood, represented, and solved as constraint satisfaction problems. Despite a wealth of good, general-purpose methods, each new, large-scale constraint satisfaction problem faces the same bottleneck: scarce human experts must select, combine, and refine the various techniques currently available. This project increases the ability of both people and machines to address new constraint satisfaction problems. The project develops a system that is both an experimental tool for researchers and a problem solver for real problems. It learns and plans to solve particular classes of constraint satisfaction problems. It combines and adapts a broad range of known constraint methods, and explores new ones, to reason about solving hard problems. Learning supports adaptive solvers that tailor themselves to a problem class. Planning supports stronger solvers, and embodies higher-level insights into the solution process. This project addresses, both in its design and its implementation, important questions in the discovery and application of knowledge to problem solving. Expected outcomes include a database of interactions and plans, a development environment that facilitates the integration and evaluation of new methods and plans, and a tool for learning new methods and developing new plans. Broader impacts include improved scheduling algorithms, upgrades to the computation infrastructure for constraint programming worldwide, and the training of students in a predominantly female and minority institution.