Many large-scale, real-world problems are readily understood, represented, and solved as constraint satisfaction problems. Organizations throughout the world exploit this approach to solve difficult problems in design and configuration, planning and scheduling, and diagnosis and testing. Nonetheless, each new, large-scale problem faces the same bottleneck: scarce human experts must select, combine, and refine the various techniques currently available for constraint satisfaction and optimization. This cognitively-oriented project increases the ability of both people and machines to address challenging new constraint satisfaction problems.
The resultant autonomous, robust system reasons from past experience, but with the ability to recognize and respond intelligently to novelty. The new approach integrates a variety of techniques to capture crucial subproblems, the most informative and conflict-ridden parts of a problem. Because crucial sub-problems often recur with only small variations, knowledge about how to solve them may be re-used. Moreover, when a problem is unsolvable, the system identifies crucial subproblems for human analysis and reformulation ? a first step toward collaborative problem solving.
This project speeds the uptake of an important technology. It generates knowledge about crucial subproblems, search, representation, and learning for constraint solving, and thereby makes constraint-programming expertise more readily available. This project analyzes the efficacy of its approach on a variety of constraint problems, particularly real-world problems.
