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

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

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.