CE40 - Mathématiques, informatique théorique, automatique et traitement du signal

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

Résumé de soumission

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.

Coordinateur du projet

Monsieur Pierre Marquis (Centre de Recherche en Informatique de Lens)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

CRIL Centre de Recherche en Informatique de Lens
IRIT Institut de Recherche en Informatique de Toulouse
LaBRI Laboratoire Bordelais de Recherche en Informatique
GREYC Groupe de recherche en Informatique, Image, Automatique et Instrumentation de Caen

Aide de l'ANR 375 990 euros
Début et durée du projet scientifique : février 2019 - 48 Mois

Liens utiles