Integrating Problem-driven and Class-based Learning for Constraint Satisfaction

许多大规模的、现实世界的问题很容易理解、表示和解决约束满足问题。世界各地的组织都利用这种方法来解决设计和配置、计划和调度以及诊断和测试中的难题。尽管如此，每个新的大规模问题都面临着同样的瓶颈：稀缺的人类专家必须选择、组合和改进当前可用的各种技术，以满足约束和优化。这个面向认知的项目增加了人和机器解决具有挑战性的新约束满足问题的能力。由此产生的自主的、健壮的系统从过去的经验中推理，但具有识别和智能响应新事物的能力。这种新方法集成了多种技术来捕获关键的子问题，即问题中信息量最大、冲突最多的部分。因为关键的子问题经常以很小的变化重复出现，关于如何解决它们的知识可能会被重用。此外，当一个问题无法解决时，系统会识别出关键的子问题，供人类分析和重新制定。这是合作解决问题的第一步。这个项目加速了一项重要技术的应用。它生成关于关键子问题、搜索、表示和约束求解学习的知识，从而使约束编程专业知识更容易获得。本项目分析了其方法在各种约束问题上的有效性，特别是现实世界中的问题。

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.