Managing dynamic CSPs with preferences

摘要

We present a new framework, managing Constraint Satisfaction Problems (CSPs) with preferences in a dynamic environment. Unlike the existing CSP models managing one form of preferences, ours supports four types, namely: unary and binary constraint preferences, composite preferences and conditional preferences. This offers more expressive power in representing a wide variety of dynamic constraint applications under preferences and where the possible changes are known and available a priori. Conditional preferences allow some preference functions to be added dynamically to the problem, during the resolution process, if a given condition on some variables is true. A composite preference is a higher level of preference among the choices of a composite variable. Composite variables are variables whose possible values are CSP variables. In other words, this allows us to represent disjunctive CSP variables. The preferences are viewed as a set of soft constraints using the fuzzy CSP framework. Solving constraint problems with preferences consists in finding a solution satisfying all the constraints while optimizing the global preference value. This is handled by four variants of the branch and bound algorithm, we propose in this paper, and where constraint propagation is used to improve the time efficiency in practice. In order to evaluate and compare the performance of these four strategies, we conducted an experimental study on randomly generated dynamic CSPs with quantitative preferences. The results are reported and discussed in the paper.