Probabilistic Constraint Reasoning

Author: 

Elsa Carvalho

School: 

Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa

Supervisors: 

Jorge Cruz
Pedro Barahona

Abstract: 

The continuous constraint paradigm has been often used to model safe reasoning in applications where uncertainty arises. Constraint propagation propagates intervals of uncertainty among the variables of the problem, eliminating values that do not belong to any solution. However, constraint programming is very conservative: if initial intervals are wide (reflecting large uncertainty), the obtained safe enclosure of all consistent scenarios may be inadequately wide for decision support. Since all scenarios are considered equally likely, insufficient pruning leads to great inefficiency if some costly decisions may be justified by very unlikely scenarios. Even when probabilistic information is available for the variables of the problem, the continuous constraint paradigm is unable to incorporate and reason with such information. Therefore, it is incapable of distinguishing between different scenarios, based on their likelihoods.

This thesis presents a probabilistic continuous constraint paradigm that associates a probabilistic space to the variables of the problem, enabling probabilistic reasoning to complement the underlying constraint reasoning. Such reasoning is used to address probabilistic queries and requires the computation of multi-dimensional integrals on possibly nonlinear integration regions. Suitable algorithms for such queries are developed, using safe or approximate integration techniques and relying on methods from continuous constraint programming in order to compute safe covers of the integration region.

The thesis illustrates the adequacy of the probabilistic continuous constraint framework for decision support in nonlinear continuous problems with uncertain information, namely on inverse and reliability problems, two different types of engineering problems where the developed framework is particularly adequate to support decision makers.

The main contributions of this thesis can be summarized as follows.

  • Extension of the continuous constraint paradigm to handle and reason with probabilistic information, providing a new formalism to model continuous constraint problems that includes probability distributions for the variables of the problem.

  • Theoretically characterization of the framework that performs probabilistic constraint reasoning and address its operational aspects.

  • Development of a prototype that implements the operational aspects of the probabilistic constraint framework, to test its capabilities as an alternative approach to decision support in the presence of stochastic uncertainty and non-linearity.

  • Illustration of the adequacy and potential of the framework by applying the prototype to inverse problems and reliability problems.

Graduated: 

Monday, November 26, 2012

PDF of thesis: