Computing explanations for interactive constraint-based systems
Loading...
Files
Full text available
Date
2011-12
Authors
Papadopoulos, Alexandre
Journal Title
Journal ISSN
Volume Title
Publisher
University College Cork
Published Version
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.
Description
Keywords
Explanations , Configuration
Citation
Papadopoulos, A. 2011. Computing explanations for interactive constraint-based systems. PhD Thesis, University College Cork.