A logic of soft constraints based on partially ordered preferences
Loading...
Files
Accepted Version
Date
2006-06
Authors
Wilson, Nic
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Published Version
Abstract
Representing and reasoning with an agent's preferences is important in many applications of constraints formalisms. Such preferences are often only partially ordered. One class of soft constraints formalisms, semiring-based CSPs, allows a partially ordered set of preference degrees, but this set must form a distributive lattice; whilst this is convenient computationally, it considerably restricts the representational power. This paper constructs a logic of soft constraints where it is only assumed that the set of preference degrees is a partially ordered set, with a maximum element 1 and a minimum element 0. When the partially ordered set is a distributive lattice, this reduces to the idempotent semiring-based CSP approach, and the lattice operations can be used to define a sound and complete proof theory. A generalised possibilistic logic, based on partially ordered values of possibility, is also constructed, and shown to be formally very strongly related to the logic of soft constraints. It is shown how the machinery that exists for the distributive lattice case can be used to perform sound and complete deduction, using a compact embedding of the partially ordered set in a distributive lattice.
Description
Keywords
Preferences , Soft constraints , Semiring-based CSPs , Possibilistic logic
Citation
Wilson, N; (2006) 'A logic of soft constraints based on partially ordered preferences'. Journal of Heuristics, 12 (4/5): 241-262. doi: 10.1007/s10732-006-6347-5
Link to publisher’s version
Copyright
© Springer Science + Business Media, LLC 2006. The final publication is available at http://link.springer.com/article/10.1007%2Fs10732-006-6347-5