RI: Small: Towards Practical Tractability in Constraint Processing

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

Many problems in artificial intelligence, engineering, and management can be advantageously modeled and solved as Constraint Satisfaction Problems, but scalability remains in practice a major obstacle to the successful deployment of Constraint Solvers. The goal of this project is to design algorithms and strategies that enable computers to overcome, in practice, the scalability barrier. To this end, the proposed research targets the two fundamental mechanisms in Constraint Processing that are the most promising for breaking the complexity barrier, namely, enforcing consistency and detecting and breaking symmetry. This project aims to design new algorithms for those two mechanisms and develop strategies for intertwining them. The tractability of a problem is guaranteed by a relationship between a structural parameter of the problem and its level of consistency. This project aims to design algorithms that enforce the needed level of consistency without adversely modifying the structure of the problem. Symmetries can be detected and exploited to dramatically reduce the cost of problem solving. This project aims to (1) design algorithms for detecting symmetries, and (2) develop approximation strategies for exploiting them without sacrificing the soundness and completeness of problem solving. A key observation is that algorithms for enforcing consistency and those for locally detecting symmetry are based on the same atomic operations. Furthermore, they seem to be effective under complementary operating conditions. This project further aims to design strategies for intertwining the operation of the two types of algorithms so that the application of the one type enables and facilitates that of the other type, in order to yield new opportunities to control the combinatorial explosion. The approach will be validated on applications of practical importance and extended to address similar combinatorial problems in other areas of Computer Science such as Databases and Software Engineering.The proposed activities contribute to the progress of the research on two fundamental aspects of Constraint Processing. From a practical perspective, this research directly benefits many combinatorial problems of practical importance. From a scientific standpoint, this project will identify connections and build new bridges with other areas of Computer Science, such as Databases and Software Engineering. The insight gained from these investigations will be used to improve the scope and content of introductory and advanced courses on Constraint Processing. The opportunities and research avenues will be heavily exploited to involve undergraduate students in research and to give them experience in using the project's insights on problems that they find engaging (e.g., Sudoku) and for understanding the operation of algorithms in Computer Science courses; the goal is to motivate students to conduct research in Constraint Processing and to transfer results from this field to other students and researchers in Computer Science, Mathematics, Engineering, to entice high-school students to study Computer Science, and in addition, to explain to the general public some of the fundamental mechanisms at the heart of complex problem solving.