Preprocessing Information for Nontrivial Goals / Advanced Compilation of Knowledge – PING-ACK

- Artificial intelligence
- Knowledge representation
- Automated Reasoning
- Theoretical Computer Science
- Complexity

A striking aspect of the results obtained so far (and of the scientific production carried out to date) is the variety of subjects covered but also the nature of the production, which ranges from articles describing results for theoretical purposes to software developments (design and evaluation of programs).

The perspectives we have in mind are twofold:

- Widely disseminating the results achieved by the project (definition of compilation languages, study of their properties and other characterization results, definition of new requests and transformations, design and evaluation of dedicated compilers and reasoners, etc.)

- Setting up an international research network bringing together researchers interested in the topic, whatever the field they come from (artificial intelligence, theoretical computer science, databases, software engineering, etc.)

As of March 25th, 2021

Articles

1. J.-M. Lagniez, E. Lonca, and P. Marquis.
Definability for Model Counting
Artificial Intelligence 281: 103229 (2020).

2. B. Zanuttini, J. Lang, A. Saffidine, and F. Schwarzentruber.
Knowledge-based programs as succinct policies for partially observable domains.
Artificial Intelligence 288: 103365 (2020).

Communications (international conferences)

1. E. Grandjean and Th. Grente.
Descriptive complexity for minimal time of cellular automata.
Proc. of LICS’19, 1-13.

2. A. de Colnet, and S. Mengel
Lower Bounds for Approximate Knowledge Compilation.
Proc. of IJCAI-PRICAI'20, 1834-1840.

3. A. de Colnet
A lower bound on DNNF encodings of pseudo-Boolean constraints.
Proc. of SAT'20, 312-321.

4. J. Cle´ment and A. Genitrini. Binary Decision Diagrams: from Tree Compaction to Sampling.
Proc. of LATIN’20, 571-583.

5. H. Fargier, and J. Mengin
A knowledge compilation map for conditional preference statements-based languages.
Proc. of AAMAS’21, to appear.

6. F. Capelli, J.-M. Lagniez, and P. Marquis Certifying Top-Down Decision-DNNF Compilers.
Proc. of AAAI’21, to appear.

7. S. Scheck, A. Niveau and B. Zanuttini
Knowledge Compilation for Nondeterministic Action Languages.
Proc. of ICAPS'21, to appear.

Communications (national - french-speaking - conferences)

1. S. Scheck, A. Niveau, and B. Zanuttini
Knowledge Compilation for Action Languages.
Actes des 15es Journe´es Francophones sur la Planification, la De´cision et l'Apprentissage pour la conduite de syste`mes (JFPDA’20).

2. H. Fargier, and J. Mengin
An incomplete knowledge compilation map for conditional preference statements-based languages.
Actes des 14es Journe´es d'Intelligence Artificielle Fondamentale (JIAF’20).

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 fact 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 to 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 robotics, and in a more risky perspective, bioinformatics.