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

Projet commun aux laboratoires CRIL, GREYC (Caen), IRIT (Toulouse) et LaBRI (Bordeaux)

Concevoir des algorithmes assurant des temps de réponse rapides est un problème fondamental en informatique. Son importance est cruciale lorsque ces algorithmes sont utilisés dans des applications nécessitant des interactions fréquentes avec les humains, comme on en trouve souvent dans la vie quotidienne (par exemple, lors de l’utilisation d’applications sur le Web ou via un smartphone). En outre, dans de nombreuses applications, une grande partie des informations données au début ou échangées avec l’utilisateur se présentent sous la forme de «connaissances» sur la base desquelles des raisonnements ou des processus décisionnels s’appuient. Malheureusement, les tâches basées sur les connaissances sont typiquement NP-difficiles, ce qui implique que, dans le cas général, elles souffrent de limitations de calcul intrinsèques ne permettant pas de garantir des temps de réponse acceptables (sauf si P = NP).

La compilation de connaissances est une approche permettant de contourner ces limitations en pré-traitant, lors d’une phase hors ligne, une partie des connaissances disponibles (la partie F dite “fixe”). Deux problématiques principales ont été étudiées à ce sujet au cours des vingt dernières années. D’une part, développer un modèle de compilabilité permettant de décider si une tâche d’intérêt est compilable ou non (c’est-à-dire réalisable efficacement quand une représentation compilée de F de taille polynomiale a été calculée au préalable). D’autre part, établir des cartes de compilation de connaissances pour choisir un langage de représentation L dans lequel F devrait être compilée. Il s’agit d’un problème de décision multicritères, le choix de L dépendant à la fois de son efficacité spatiale (c’est-à-dire de sa capacité relative à coder des informations en utilisant peu d’espace mémoire) et de son efficacité temporelle (c’est-à-dire de la complexité temporelle des sous-tâches élémentaires du problème étudié). Cependant, le modèle actuel de compilabilité présente l’inconvénient majeur de classer comme non-compilables de nombreuses tâches pour lesquelles la compilation des connaissances apparaît comme une approche intéressante en pratique. Un tel écart entre la théorie et la pratique vient du fait que le cadre de compilabilité se concentre sur le cas le plus défavorable et n’est pas suffisamment précis pour prendre en compte des caractéristiques spécifiques des entrées. De plus, 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 constructions plus sophistiquées.

L’objectif de PING / ACK est de s’attaquer aux manques des travaux existants en matière de compilation de connaissances, en élargissant son champ d’application, à la fois du côté théorique et du côté pratique. Nous prévoyons de définir de nouvelles cartes de compilation de connaissances adaptées à des langages de représentation plus expressifs que ceux existants et d’améliorer l’applicabilité de la compilation de connaissances. Notre objectif est aussi de préciser le concept de compilabilité, en élaborant des cartes plus fines (qui ne seraient pas centrées sur les scénarios les plus défavorables) et en explorant d’autres approches permettant d’améliorer les avantages offerts par la compilation des connaissances. Sont attendus des résultats de caractérisation de différents types (expressivité, concision, complexité), mais aussi de nouveaux concepts et langages, de nouveaux algorithmes (compilateurs et raisonneurs), qui seront mis en œuvre et évalués expérimentalement sur des problèmes variés (recommandation, configuration robotique et, dans une perspective plus risquée, bioinformatique).

Plus d’informations sur le site web du projet.