
[full paper] 
Nic Wilson
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, semiringbased CSPs, allows a partially ordered set of preference degrees, but this set must form a distributive lattice; whilst this is convenient computationally, it 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 semiringbased CSP approach, and the lattice operations can be used to define a sound and complete proof theory. This case can also be viewed as a latticevalued possibilistic logic. For a general partially ordered set of preference degrees, we show how the machinery that exists for the distributive lattice case can be used to perform sound and complete deduction, using a particular embedding of the partially ordered set in a distributive lattice.
Keywords: Reasoning about preferences, Constraint Satisfaction, soft constraints, possibilistic logic, Qualitative Reasoning
Citation: Nic Wilson: Soft Constraints with Partially Ordered Preferences. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.11111112.