.png){kind=icon}
Return
Managing dynamic CSPs with preferences
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-012-0338-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Constraint satisfaction
Soft constraints
Preferences
Fuzzy CSPs
Journal
IF:
3.5
Papers:
7.6K
Citations:
1.7W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
ShareSaveShareSaveShareSaveShareSave
View more