Computing explanations for interactive constraint-based systems

Simple item page
dc.contributor.advisorO'Sullivan, Barry
dc.contributor.authorPapadopoulos, Alexandre
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2012-02-02T14:06:50Z
dc.date.available2012-02-02T14:06:50Z
dc.date.issued2011-12
dc.date.submitted2011-07-27
dc.description.abstractConstraint 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.description.statusNot peer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationPapadopoulos, A. 2011. Computing explanations for interactive constraint-based systems. PhD Thesis, University College Cork.en
dc.identifier.urihttps://hdl.handle.net/10468/510
dc.language.isoenen
dc.publisherUniversity College Corken
dc.relation.urihttp://library.ucc.ie/record=b2028173~S0
dc.rights© 2011, Alexandre Papadopoulosen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/en
dc.subjectExplanationsen
dc.subjectConfigurationen
dc.subject.lcshConstraint programming (Computer science)en
dc.titleComputing explanations for interactive constraint-based systemsen
dc.typeDoctoral thesisen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD (Computer Science)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
PapadopoulosA_PhD2011.pdf
Size:
855.43 KB
Format:
Adobe Portable Document Format
Description:
Full text available
Download
License bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
license.txt
Size:
5.75 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Thumbnail Image
Name:
AP_e-thesisform001.pdf
Size:
843.56 KB
Format:
Adobe Portable Document Format
Description:
License
Collections
Doctoral Theses
College of Science, Engineering and Food Science - Doctoral Theses
Computer Science - Doctoral Theses