Interactive Constraint-Satisfaction Search

Constraint-satisfaction problems provide a general framework for defining problems of interest in many areas of artificial intelligence, such as scheduling and satisfiability [48]. In their most general form, constraint-satisfaction problems involve a set of variables whose domains are finite and discrete, along with a set of constraints that are defined over some subset of the variables and that limit the value combinations those variables can take. The goal is to find an assignment of values to variables that satisfies the given constraints. [25] define the class of interactive constraint-satisfaction problems that involve three extensions to the standard formulation. First, they include a constraint acquisition stage during which a user can incrementally add new constraints to the problem being solved. Second, a variable's domain can include both a defined and undefined portion, and the user can add new values to the defined portion during constraint acquisition. Third, they allow incremental update of a partial solution based on the domain and constraint updates. This framework can encompass the item search portion of the conversations managed by the ADAPTIVE PLACE ADVISOR; it does not include the item presentation portion. In our setting, constraints are simply attribute-value specifications, such as cuisine = Chinese. The PLACE ADVISOR's search is not as fully general as this framework, in that it does not incorporate the notion of undefined portions of domains. However, it does acquire constraints via the user's specifications during a conversation and incrementally updates solutions in response.