Methods for Interactive Constraint Satisfaction

Abstract

A constraint satisfaction problem involves the assignment of values to variables subject to a set of constraints. A large variety of problems in artificial intelligence and other areas of computer science can be viewed as a special case of the constraint satisfaction problem. In many applications, one example being product configuration, user interaction is required to find a solution. The topic of this thesis is algorithmic methods for solving constraint satisfaction problems interactively. A number of fundamental operations, which form the core of an interactive constraint solver, are identified and described formally. The decision version of the constraint satisfaction problem is NP-complete, so a method of offline compilation is proposed to circumvent this intractability and achieve short response times for these fundamental operations.