RI: Small: Harnessing the Power of Constraint Propagation by Controlling Consistency Levels and Synthesizing Constraints

决策和优化问题在日常生活中以及在商业、工程和科学中都提出了许多挑战。“好”和“快”地解决这些问题直接有益于我们的生活方式和经济，并使我们能够有效地管理我们的资源。许多科学学科都专注于形式化和解决这种困难的组合问题。约束处理(CP)是人工智能的一个子领域，它专注于对管理这些问题并造成其复杂性的约束(即约束)进行透明建模。通过研究约束之间如何相互作用以及相互作用如何沿着约束传播，CP开发了解决问题的通用机制，通过排除被禁止的决定和决策的组合，逐步得出可接受的解决方案和最优选择。为此，CP在一致性属性方面形式化了约束如何在它们之间以及与可能的选项之间进行交互。因此，这种性质的识别和执行它们的算法的设计是CP的核心，并可能构成该领域与其他涉及相同计算问题的科学学科的最大区别。这个项目的目标是了解各种一致性算法的效率和成本之间的权衡，并控制如何在问题求解过程中动态地交织它们来解决困难问题和降低计算成本。特别是，该研究将通过动态地(A)选择在搜索过程中的任何时刻实施的正确的一致性水平，以及(B)对随机选择的变量合成新的约束来从基于一致性的技术中获得最大的计算收益。拟议的活动扩展了最近用于更高级别一致性的实用算法，并有助于CP基本方面的研究进展。开发的方法将有利于其他类型的图形模型，如游戏以及下一代商业和公共领域约束解算器。从这项研究中获得的洞察力将改进本科生和研究生关于CP的入门课程和高级课程的范围和内容。各种研究任务将使年轻工程师和科学家的指导和培训能够理解问题解决过程中复杂性的根源，并学习如何在实践中克服它。

Decision and optimization problems raise many challenges in daily life as well as in business, engineering, and science. Solving them "well" and "quickly" directly benefits our life-styles and economy, and allows us to effectively manage our resources. Many scientific disciplines have focused on formalizing and solving such difficult combinatorial problems. Constraint Processing (CP), a subfield of Artificial Intelligence, has focused on the transparent modeling of the restrictions (i.e., constraints) that govern those problems and create their complexity. By examining how constraints interact among themselves and how interactions propagate along the constraints, CP has developed generic mechanisms to solve a problem by ruling out forbidden decisions and combinations of decisions, gradually eliciting the acceptable solutions and the optimal choices. To this end, CP has formalized in terms of consistency properties how constraints interact among themselves and with the possible options. Thus, the identification of such properties and the design of algorithms for enforcing them are at the heart of CP, and constitute perhaps what best distinguishes this area from other scientific disciplines concerned with the same computational problems. The goal of this project is to understand the tradeoffs between the effectiveness and the cost of a variety of consistency algorithms, and to control how to interleave them dynamically during problem solving to solve difficult problems and reduce computational cost.In particular, the research will garner the most computational benefits from consistency-based techniques by dynamically (a) selecting the right level of consistency to enforce at any point during search, and (b) synthesizing new constraints over opportunistically chosen variables. The proposed activities extend on recent practical algorithms for higher-levels consistency, and contribute to the progress of the research in fundamental aspects of CP. The developed methods will benefit other types of graphical models such as games as well as the next generation of commercial and public-domain constraint solvers. The insight gained from this research will improve the scope and content of the introductory and advanced courses on CP both at the undergraduate and graduate levels. The various research tasks will allow the mentoring and training of young engineers and scientists to understand the roots of complexity in problem solving and to learn how to overcome it in practice.