ANR PRC PING/ACK
Preprocessing Information for Nontrivial Goals / Advanced Compilation of Knowledge
Project involving the laboratories CRIL, GREYC (Caen), IRIT (Toulouse), and LaBRI (Bordeaux).
Designing algorithms ensuring fast response times is a fundamental problem in Computer Science. Its significance is all the more salient for algorithms requiring frequent interactions with humans. Indeed, one faces this issue quite often in everyday life (e.g., when using applications on the Web or on a smartphone, short response-time guarantees are mandatory). Furthermore, in many applications, much of the information given at the start or exchanged with the user take the form of or can be interpreted as pieces of “knowledge” which must be processed. Unfortunately, knowledge-based tasks are typically NP-hard, which implies that in the general case they suffer from intrinsic computational limitations disallowing response-time guarantees (unless P = NP).
Knowledge compilation is an approach for circumventing such limitations by pre-processing, during an off-line phase, some part of the available knowledge (the so-called “fixed” part F). Two main issues have been investigated for the past twenty years in this research area. On the one hand, developing a compilability model for deciding whether a task of interest is compilable or not (that is – loosely speaking – tractable provided that a polynomial-size compiled form of F has been computed first). On the other hand, drawing up knowledge compilation maps for selecting a representation language L into which F should be compiled. This is a multi-criteria decision, the choice of L depending on both its space efficiency (i.e., its relative ability to encode information using little space) as well as its time efficiency (i.e, the time complexity of the elementary subtasks which are needed to solve the problem under consideration). However, the existing model for compilability has the major drawback of classifying as non-compilable many tasks for which knowledge compilation appears as a valuable approach in practice. Such a gap between theory and practice comes from the facts that the compilability framework focuses on the worst case and is not fine-grained enough to take into account specific features of the inputs. Furthermore, the expressiveness of the languages L which have been used so far in knowledge compilation maps is still too limited or not adequate for some applications requiring more sophisticated constructs.
The objective of PING/ACK is to attack these shortcomings of existing work in knowledge compilation, extending its scope on both the theoretical side and the practical side. In a nutshell, we plan to define new knowledge compilation maps suited to more expressive representation languages than existing ones and to improve the applicability of knowledge compilation; we aim to refine the concept of compilability, drawing up more fine-grained maps (that would not be focused on worst-case scenarios), and investigating other approaches for enhancing the benefits that knowledge compilation offers. This will produce characterization results of various types (expressiveness, succinctness, complexity), but also involve the definition of new concepts and languages, and the conception of new algorithms (compilers and reasoners) as well as their implementation and experimental evaluation on problems from several areas, both inside and outside the standard AI scope, including recommendation, configuration, robotics, and in a more risky perspective, bioinformatics.
More information on the project web site.