CAREER: Detecting Interchangeability Relations in Constraint Satisfaction Problems and Exploiting them in Problem Solving and Interactions with Users

这是教师早期职业发展(Career)奖。这个项目将提高我们解决约束满足问题的能力，约束满足是建模和解决计算机科学、工程和管理中各种问题的中心范式。它将通过设计和评估算法来实现这一点，这些算法发现并利用作为约束满足问题(CSP)的决策问题模型中嵌入的结构。特别是，这项工作将调查如何使用对称关系，指定为互换性，可以用来建立紧凑和忠实的CSP抽象。这些研究的目标不仅是提高求解CSP的性能，而且通过允许用户构建和导航解决方案空间的景观来支持与人类用户的交互。这些技术将通过让计算机充当主动、知情的助手而不是被动的黑匣子，在解决问题方面建立一种新的范式。该项目的教育计划结合了课程开发、课程教学和对学生的个人指导。该职业奖表彰和支持一位可能成为21世纪学术领袖的教师-学者的早期职业发展活动。约束满足最常用于调度和资源分配应用，以及人工智能规划和协作问题解决。因此，这项研究将改进现有的技术，以解决各种领域中非常困难的实际问题。

This is a Faculty Early Career Development (CAREER) award. This project will improve our ability to solve problems in constraint satisfaction, which is a central paradigm for modeling and solving various problems in computer science, engineering, and management. It will do so by designing and evaluating algorithms that discover and exploit the structure embedded in the model of a decision problem formulated as a Constraint Satisfaction Problem (CSP). In particular, the work will investigate how symmetry relations, specified as interchangeability, can be used to build compact and faithful abstractions of CSPs. The goal of these investigations is not only to enhance the performance of solving CSPs, but also to support interactions with human users by allowing them to build and navigate over landscapes of solution spaces. Such techniques will institute a new paradigm in problem solving by making a computer perform as an active, informed assistant rather than as a passive black box. The project's education plan combines curriculum development, course teaching, and individual mentoring of students.This CAREER award recognizes and supports the early career-development activities of a teacher-scholar who is likely to become an academic leader of the twenty-first century. Constraint satisfaction is most commonly used in scheduling and resource allocation applications, as well as in artificial intelligence planning and collaborative problem-solving. Therefore, this research will improve the techniques available to solve very difficult practical problems in a variety of fields.