Closures of Uncertain Constraint Satisfaction Problems

Yorke-Smith, N. and Gervet, C. Closures of Uncertain Constraint Satisfaction Problems. Proceedings of CP'05 Workshop on Quantification in Constraint Programming, Sitges, Spain, October 2005.

Abstract: Data uncertainties are inherent in the real world. The uncertain CSP (UCSP) is an extension of classical CSP that models incomplete and erroneous data by coefficients in the constraints whose values are unknown but bounded, for instance by an interval. Formally, the UCSP is a tractable restriction of the quantified CSP. The resolution of a UCSP, a set of its potential solutions called a closure, can take different forms according to the user's requirements and the nature of data uncertainty in the problem specification. In a former paper we presented mainly the full closure, the set of all potential solutions, which finds application in diagnosis problems where the existence of any potential solutions is an objective by itself. In this paper, we develop other commonly-useful closures such as the covering set (found in contingent planning problems) and the most robust solution (found in conformant planning problems). We formally define different closures as solutions to a UCSP model, relate them in a hierarchy, and outline means to derive them from one another.

PDF (153K) | Bibtex entry

Workshop homepage