Metrics
13 Record Views
Journal article
Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies
Artificial intelligence, Vol.174(3-4), pp.270-294
03/2010
Web of Science ID: WOS:000274974100002
Abstract
We consider soft constraint problems where some of the preferences may be unspecified. This models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define algorithms, that interleave search and preference elicitation, to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. We define a combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm, which we compare experimentally. We compute both the number of elicited preferences and the user effort, which may be larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate as little information as possible, the user effort measures also the hidden work the user has to do to be able to communicate the elicited preferences. Our experimental results on classical, fuzzy, weighted and temporal incomplete CSPs show that some of our algorithms are very good at finding a necessarily optimal solution while asking the user for only a very small fraction of the missing preferences. The user effort is also very small for the best algorithms. (C) 2009 Elsevier B.V. All rights reserved.
Related links
Details
- Title
- Elicitation strategies for soft constraint problems with missing preferences
- Publication Details
- Artificial intelligence, Vol.174(3-4), pp.270-294
- Resource Type
- Journal article
- Publisher
- Elsevier
- Number of pages
- 25
- Grant note
- Department of Broadband, Communications and the Digital Economy Australian Research Council 2005015491 / Italian MIUR PRIN; Ministry of Education, Universities and Research (MIUR); Research Projects of National Relevance (PRIN)
- Copyright
- © 2009 Elsevier B.V. All rights reserved.
- Identifiers
- WOS:000274974100002; 99380590496806600
- Academic Unit
- Hal Marcus College of Science and Engineering ; Intelligent Systems and Robotics; Institute for Human and Machine Cognition
- Language
- English