ECAI 2004 Conference Paper

[full paper]

Soft Constraints with Partially Ordered Preferences

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, 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 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. This case can also be viewed as a lattice-valued 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.1111-1112.