Content area
Full text
We review constraint-based approaches to handle preferences. We start by defining the main notions of constraint programming and then give various concepts of soft constraints and show how they can be used to model quantitative preferences. We then consider how soft constraints can be adapted to handle other forms of preferences, such as bipolar, qualitative, and temporal preferences. Finally, we describe how AI techniques such as abstraction, explanation generation, machine learning, and preference elicitation can be useful in modeling and solving soft constraints.
Preferences and constraints occur in real-life problems in many forms. Intuitively, constraints are restrictions on the possible scenarios. For a scenario to be feasible, all its constraints must be satisfied. For example, if we want to buy a personal computer (PC), we may pose a lower limit on the size of its screen. Only PCs that respect this limit will be considered. Constraint programming (Rossi, Van Beek, and Walsh 2006) is an area of AI that provides the formalisms and solving techniques to model and solve problems with constraints.
Preferences, on the other hand, express desires, satisfaction levels, rejection degrees, or costs. For example, we may prefer a tablet PC to a regular laptop, we may desire having a webcam, and we may want to spend as little as possible. In this case, all PCs will be considered, but some will be more preferred than others. Such concepts can be expressed in either a qualitative or a quantitative way.
Preferences and constraints are closely related notions, since preferences can be seen as a form of "tolerant" constraints. For this reason, there are several constraint-based frameworks to model preferences. One of the most general frameworks, based on soft constraints (Meseguer, Rossi, and Schiex 2006), extends the classical constraint formalism to model preferences in a quantitative way, by expressing several degrees of satisfaction that can be either totally or partially ordered. When there are both levels of satisfaction and levels of rejection, preferences are bipolar and can be modeled by extending the soft constraint formalism (Bistarelli et al. 2006).
Preferences can also be modeled in a qualitative way (also called ordinal), that is, by pairwise comparisons. In this case, soft constraints (or their extensions) are not suitable. However, other AI preference formalisms are...