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

点击翻译按钮获取中文摘要

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.