Pré-traitement d'informations pour la résolution de tâches complexes / Compilation avancée de connaissances – PING-ACK

- Intelligence artificielle
- Représentation des connaissances
- Raisonnement automatisé
- Informatique théorique
- Complexité

Un aspect marquant des résultats obtenus (et de la production scientifique réalisée jusqu’ici) est la variété des sujets abordés mais aussi de la nature de la production, qui va d’articles décrivant des résultats à visée théorique jusqu’à des développements logiciels (conception et évaluation de programmes).

Les perspectives envisagées sont doubles :

- Diffuser largement les résultats obtenus durant la réalisation du projet (définition de langages de compilation, étude de leurs propriétés et autres résultats de caractérisation, prise en compte de nouvelles requêtes et transformations, conception et évaluation de compilateurs et raisonneurs dédiés, etc.)

- Mettre en place un réseau international de recherche regroupant les chercheurs intéressés par la thématique, quel que soit leur domaine d’origine (intelligence artificielle, informatique théorique, bases de données, génie logiciel, etc.)

Au 25 mars 2021

Revues internationales

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 (confe´rences internationales)

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, a` parai^tre.

6. F. Capelli, J.-M. Lagniez, and P. Marquis Certifying Top-Down Decision-DNNF Compilers.
Proc. of AAAI’21, a` parai^tre.

7. S. Scheck, A. Niveau and B. Zanuttini
Knowledge Compilation for Nondeterministic Action Languages.
Proc. of ICAPS'21, a` parai^tre.

Communications (confe´rences nationales)

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).

La conception d'algorithmes assurant des temps de réponse rapides est un problème fondamental en informatique. L'importance pratique de ce problème est très élevée pour les algorithmes nécessitant des interactions fréquentes avec des humains. Ainsi, on rencontre souvent ce problème dans la vie de tous les jours (par exemple, lorsqu'on utilise des applications sur le Web ou sur un smartphone, des garanties de temps de réponse très brefs sont obligatoires). Par ailleurs, dans de nombreuses applications, la plupart des informations données au préalable ou échangées avec l'utilisateur prennent la forme ou peuvent être interprétées comme des «connaissances». Malheureusement, les tâches à réaliser quand les entrées sont des connaissances sont typiquement NP-difficiles, ce qui implique des limitations de calcul intrinsèques interdisant les garanties de temps de réponse espérées (sauf si P = NP).

La compilation des connaissances est une approche pour contourner ces limitations en pré-traitant (pendant une phase de calcul hors ligne) une partie des connaissances disponibles (la partie dite «fixe» F). Deux objectifs principaux ont été poursuivis au cours des vingt dernières années dans ce domaine de recherche. D'une part, développer un modèle de compilabilité pour décider si une tâche cible est compilable ou non (c'est-à-dire traitable à condition qu'une forme compilée de F de taille polynomiale ait été calculée au départ). D'autre part, établir des cartes de compilation de connaissances pour sélectionner un langage de représentation L dans lequel F doit être compilé. La décision à prendre est multicritère, le choix de L dépendant à la fois de son efficacité spatiale (c'est-à-dire sa capacité relative à coder de l'information en utilisant peu d'espace mémoire) et de son efficacité temporelle (la complexité temporelle des sous-tâches élémentaires nécessaires pour résoudre le problème considéré). Cependant, le modèle proposé jusqu'ici pour la notion de compilabilité présente l'inconvénient majeur de classer comme non compilables de nombreuses tâches pour lesquelles la compilation des connaissances est utile en pratique. Un tel écart entre théorie et pratique vient du fait que ce cadre de compilabilité se concentre sur le pire des cas et n'est pas assez précis pour prendre en compte les caractéristiques spécifiques des entrées. En outre, l'expressivité des langages L qui ont été utilisés jusqu'à présent dans les cartes de compilation de connaissances est encore trop limitée ou insuffisante pour certaines applications nécessitant des représentations plus sophistiquées.

L'objectif de PING / ACK est de pallier ces insuffisances des travaux existants en compilation des connaissances, en étendant son champ d'application tant du côté théorique que du côté pratique. En un mot, nous prévoyons de définir de nouvelles cartes de compilation de connaissances adaptées à des langages de représentation plus expressifs que ceux considérés jusqu'à présent et d'améliorer l'applicabilité de la compilation des connaissances ; nous visons en particulier à affiner le concept de compilabilité, à élaborer des cartes de compilation plus précises (qui ne seraient pas focalisées sur les pires) et à proposer d'autres approches pour améliorer les avantages offerts par la compilation des connaissances. Le but est de produire des résultats de caractérisation de différents types (expressivité, concision, complexité), mais aussi de définir de nouveaux concepts et langages, de concevoir de nouveaux algorithmes (compilateurs et raisonneurs) qui seront implémentés et évalués expérimentalement sur des problèmes issus de plusieurs domaines à l'intérieur de l'IA mais aussi à l'extérieur de l'IA, y compris en robotique, et dans une perspective plus risquée, en bioinformatique.