A LOCAL SEARCH APPROACH TO SOLVE INCOMPLETE FUZZY CSPs

Mirco Gelain, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh

2011

Abstract

We consider fuzzy 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 local search algorithms that interleave search and preference elicitation, with the goal to find a solution which is ”necessarily optimal”, that is, optimal no matter what the missing data are, while asking the user to reveal as few preferences as possible. While in the past this problem has been tackled with a branch & bound approach, which was guaranteed to find a solution with this property, we now want to see whether a local search approach can solve such problems optimally, or obtain a good quality solution, with fewer resources. At each step, our local search algorithm moves from the current solution to a new one, which differs in the value of a variable. The variable to reassign and its new value are chosen so to maximize the quality of the next solution. To compute this, we elicit some of the missing preferences in the neighbor solutions. Experimental results on randomly generated fuzzy CSPs with missing preferences show that our local search approach is promising, both in terms of percentage of elicited preferences and scaling properties.

Paper Citation

in Harvard Style

Gelain M., Pini M., Rossi F., Brent Venable K. and Walsh T. (2011). A LOCAL SEARCH APPROACH TO SOLVE INCOMPLETE FUZZY CSPs . In Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-40-9, pages 582-585. DOI: 10.5220/0003174505820585

in Bibtex Style

@conference{icaart11,
author={Mirco Gelain and Maria Silvia Pini and Francesca Rossi and Kristen Brent Venable and Toby Walsh},
title={A LOCAL SEARCH APPROACH TO SOLVE INCOMPLETE FUZZY CSPs},
booktitle={Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2011},
pages={582-585},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003174505820585},
isbn={978-989-8425-40-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - A LOCAL SEARCH APPROACH TO SOLVE INCOMPLETE FUZZY CSPs
SN - 978-989-8425-40-9
AU - Gelain M.
AU - Pini M.
AU - Rossi F.
AU - Brent Venable K.
AU - Walsh T.
PY - 2011
SP - 582
EP - 585
DO - 10.5220/0003174505820585