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