Computing explanations for interactive constraint-based systems

Show simple item record

dc.contributor.advisor O'Sullivan, Barry Papadopoulos, Alexandre 2012-02-02T14:06:50Z 2012-02-02T14:06:50Z 2011-12 2011-07-27
dc.identifier.citation Papadopoulos, A. 2011. Computing explanations for interactive constraint-based systems. PhD Thesis, University College Cork. en
dc.description.abstract Constraint programming has emerged as a successful paradigm for modelling combinatorial problems arising from practical situations. In many of those situations, we are not provided with an immutable set of constraints. Instead, a user will modify his requirements, in an interactive fashion, until he is satisfied with a solution. Examples of such applications include, amongst others, model-based diagnosis, expert systems, product configurators. The system he interacts with must be able to assist him by showing the consequences of his requirements. Explanations are the ideal tool for providing this assistance. However, existing notions of explanations fail to provide sufficient information. We define new forms of explanations that aim to be more informative. Even if explanation generation is a very hard task, in the applications we consider, we must manage to provide a satisfactory level of interactivity and, therefore, we cannot afford long computational times. We introduce the concept of representative sets of relaxations, a compact set of relaxations that shows the user at least one way to satisfy each of his requirements and at least one way to relax them, and present an algorithm that efficiently computes such sets. We introduce the concept of most soluble relaxations, maximising the number of products they allow. We present algorithms to compute such relaxations in times compatible with interactivity, achieving this by indifferently making use of different types of compiled representations. We propose to generalise the concept of prime implicates to constraint problems with the concept of domain consequences, and suggest to generate them as a compilation strategy. This sets a new approach in compilation, and allows to address explanation-related queries in an efficient way. We define ordered automata to compactly represent large sets of domain consequences, in an orthogonal way from existing compilation techniques that represent large sets of solutions. en
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher University College Cork en
dc.rights © 2011, Alexandre Papadopoulos en
dc.rights.uri en
dc.subject Explanations en
dc.subject Configuration en
dc.subject.lcsh Constraint programming (Computer science) en
dc.title Computing explanations for interactive constraint-based systems en
dc.type Doctoral thesis en
dc.type.qualificationlevel Doctoral en
dc.type.qualificationname PhD (Computer Science) en
dc.internal.availability Full text available en
dc.description.version Accepted Version en
dc.contributor.funder Science Foundation Ireland en
dc.description.status Not peer reviewed en Computer Science en

Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record

© 2011, Alexandre Papadopoulos Except where otherwise noted, this item's license is described as © 2011, Alexandre Papadopoulos
This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement