Reliable Constraint Reasoning with Uncertain Data


Neil Yorke-Smith


Imperial College London


Carmen Gervet


Constraint programming (CP) has proved an effective paradigm to model and solve difficult combinatorial optimisation problems from disparate domains. The need for reliable solutions to real-world applications requires that the uncertainty inherent in these problems is taken into account. To date, however, there has been little work on accommodating uncertainty within CP, apart from seeking a solution that holds in the greatest number of circumstances.

In this thesis we focus on uncertain data arising due to incomplete or erroneous knowledge. The user's current knowledge of the data defines the genuine problem she wishes to solve. Reliable information about solutions to this problem are required. A prerequisite is to formulate a model that faithfully represents the genuine problem, rather than one that approximates it; and then to solve the model, excluding no relevant potential solution to it.

We provide reliable information by enclosing the uncertainty with what is known, thus guaranteeing that the genuine problem is contained in the model. We then find a closure, a set of potential solutions to this model. The closure presents the user with as much relevant information as can be inferred about the problem, given the present knowledge of the uncertain data.

The approach is formalised as the certainty closure framework. We define the concept of an Uncertain Constraint Satisfaction Problem (UCSP) to bring an explicit description of uncertain data into the model. We define several useful closures to a UCSP, and specify how to derive them across disparate domains by giving two resolutions forms. Instances are presented for specific constraint classes.

The practical value of the generic framework is demonstrated in applications to network diagnosis and aerospace planning. Tractable solution methods to derive closures are exhibited for each instance of the framework, and verified by empirical studies.


Tuesday, June 1, 2004