Quality over Quantity in Soft Constraints

摘要

Partial constraint satisfaction and soft constraints enable to deal with over-constrained problems in practice. Constraint relationships have been introduced to provide a qualitative approach to specifying preferences over the constraints that should be satisfied. In contrast to quantitative approaches like weighted or fuzzy CSPs, the preferences just rely on a directed acyclic graph. The approach is particularly aimed at scenarios where soft-constraint problems stemming from several independently modeled agents have to be aggregated into one problem in a multi-agent system. Existing transformations into weighted CSP introduce unintended, additional preference decisions. We first illustrate the application of constraint relationships in a case study from energy management along with deficiencies of existing work. We then show how to embed constraint relationships into the soft constraint frameworks of partial valuation structures and further c-semi rings by means of free constructions. We finally provide a prototypical implementation of heuristics for the well-known branch-and-bound algorithm along with an empirical evaluation.