A logic of soft constraints based on partially ordered preferences

Thumbnail Image
HEUR230R1NicWilson.pdf(280.39 KB)
Accepted Version
Wilson, Nic
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Journal Issue
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.
Preferences , Soft constraints , Semiring-based CSPs , Possibilistic logic
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
© Springer Science + Business Media, LLC 2006. The final publication is available at http://link.springer.com/article/10.1007%2Fs10732-006-6347-5