Knowledge Compilation techniques for reducing
complexity of
algorithms
when solving problems with uncertainty and preferences
The complexity of many
of the
problems issued from AI models is high (beyond NP), and this is
particularly so for those involving preferences and uncertain
knowledge. Hence the difficulty to handle these problems on line. A
solution is to “compile” the original description of the problem in
such a way that on line requests can be handled in polynomial time
w.r.t. the compiled form. There is no free lunch: in the worst case,
the size of the compiled form can be exponential with respect to the
size of the original description. Nevertheless, for most real world
cases, this combinatorial explosion stays theoretical; the compiled
form is tractable and sometimes more compact than the original form.
Our first results have confirmed the pertinence of this hypothesis when
applied to the domain of car configuration. At the international level,
several teams have successfully applied this idea to domains like
planning, constraint satisfaction and diagnosis.
The aim of this project is to develop compilation models and algorithms
for the on line optimization of problems dealing with preferences
and/or uncertainties, be the uncertainty/preference model quantitative
(e.g. GAI nets, Bayesian nets, Temporal CSPs) or qualitative (e.g. CP
nets, logical approaches, point and interval algebra). The project
articulates two main research lines:
The first research line is algorithmic: the idea is to take advantage
of the preferences to reduce the size of the compiled form. One
approach is to discard less preferred models (in car configuration, the
cars which are seldom bought by the users). An alternative is to
slightly modify the preference in order to factorize them more easily:
e.g., consider similar utility functions as identical and merge them.
One can also decide to restrict the target representation language
(e.g. to capture preferences by a lextree representing rather than a
Bayesian net – the former language being less expressive but more
compact than the second one). Finally, we will study on line
compilation of data acquired on the fly, be these data coming from a
dynamical learning sets or be they issued from (local) search
algorithm. The main question of the idea of an “approximate
compilation” that we will explore, is to decide to what extend it is
possible to lose precision in order to gain space.
The second research line is theoretical: we will build a formal
framework that allows the comparison of target compilation languages,
and this even when the original and target languages are not standard
logical languages (a “classical” compilation map is an analysis of the
space and temporal complexity of target languages, fragments of
propositional logic). But consider temporal reasoning frameworks: point
algebra, Allen's algebra, TCSP and difference decision diagrams are
heterogeneous and cannot easily be considered as sublanguages of a
common temporal logic. Our compilation maps will include, beyond the
complexity analysis in terms of time and space, the study of the
relative expressiveness of the languages along with the complexity of
the elicitation and learning of instances of these languages (VC
dimension and “sample complexity”)
We add third an experimental axis: the validation of the
approaches on real-world case studies (product configuration, temporal
planning problems, industrial design)
Research lines:
- Approximate
compilation
- Target languages for the efficient handling of preferences and
uncertainties,
- Hererogenous compilation maps,
- ML compilation
maps,
- On-the-Fly compilation
On going Ph. D and
post-doctoral positions:
Related projects:
- Compile !
- BR4CP
- Ping-Ack
- CAASC
- PER4MANCE
