Publication Details

Closures of Uncertain Constraint Satisfaction Problems

by Yorke-Smith, N. and Gervet, C.

in Proceedings of CP’05 Workshop on Quantification in Constraint Programming pp. 114-129,

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.

Electronic Copies

Adobe PDF

BibTeX

EndNote

AIC Personnel

	Name	Title	E-mail
	Yorke-Smith, Neil	Computer Scientist