Un cadre pour la cartographie des langages

Un système (véhicule, instrument) est dit autonome s’il n’est pas contrôlé par un opérateur humain. Ses actions sont alors gérées par un programme interne, qui ne peut être modifié pendant son fonctionnement ; il s’agit d’un programme embarqué, devant permettre au système de « prendre lui-même des décisions ». Les systèmes embarqués font généralement l’objet de fortes limitations (par exemple au niveau de leur prix, poids ou puissance) qui dépendent de la tâche qu’ils doivent accomplir ; ils n’ont par conséquent que peu de ressources à leur disposition, en termes d’espace mémoire et de puissance de calcul. Malgré cela, ils exigent généralement une très forte réactivité. Ces contraintes sont particulièrement significatives dans le cadre des systèmes embarqués contrôlant des systèmes spatiaux et aéronautiques, tels des drones ou des satellites : leurs ressources peuvent être drastiquement limitées, et leur besoin en réactivité crucial.

La prise de décision est l’un des objectifs du domaine de l’intelligence artificielle que l’on nomme planification. Pour produire des décisions adaptées à la situation courante, le programme doit résoudre un problème de planification. Des outils ont été développés pour résoudre de tels problèmes ; grâce à eux, le système peut calculer des décisions convenables. Cependant, dans le cas général, les problèmes de planification sont difficiles à résoudre — ils ont une haute complexité algorithmique. En conséquence, prendre des décisions en résolvant des problèmes de planification prend du temps, et ce en particulier sur les systèmes autonomes, qui ne disposent que d’une puissance limitée. Il est donc impossible de leur assurer une bonne réactivité si le problème est résolu en ligne, c’est-à-dire à chaque fois qu’une décision doit être prise, en n’utilisant que la puissance et la mémoire du système. Une façon de régler ce problème est de calculer les décisions hors ligne, avant la mise en situation du système. Pour ce faire, on anticipe toutes les situations possibles et on résout le problème pour chacune d’elles ; on peut alors fournir au système une table de décision, contenant un ensemble de « règles de décision » de la forme « dans telle situation, prends telle décision ». Cela garantit une réactivité maximale au système ; en effet l’exploitation en ligne de ce genre de table ne requiert qu’une puissance très limitée.

Concepts et historique

La compilation de connaissances peut être vue comme une forme de «factorisation», la phase hors ligne étant dédiée à l’exécution de calculs à la fois difficiles et communs à plusieurs opérations en ligne. Cette idée n’est pas nouvelle, comme l’illustre l’exemple des tables de logarithmes [Mar08], qui étaient utilisées à une époque où les calculatrices n’étaient pas aussi légères et bon marché qu’aujourd’hui. Elles contenaient des couples ⟨x, log10(x)⟩ pour un grand nombre de valeurs de x, qui pouvaient être utilisées pour faire des calculs complexes, tels l’extraction de racines .

Prenons un autre exemple, plus proche du sujet : dans l’introduction, la première solution que nous proposions pour améliorer la réactivité du système était de résoudre le problème au préalable, pour toutes les situations possibles, de manière à fournir au programme de contrôle une table de règles de décision. Bien que naïve, cette idée relève également de la compilation de connaissances ; les trois aspects principaux de la définition sont en effet présents, à savoir que la phase hors ligne est chargée des calculs difficiles (la résolution du problème pour des situations initiales multiples) et souvent répétés (une même situation peut être rencontrée de nombreuses fois), et la phase en ligne est simple (regarder dans la table la prochaine décision à prendre). Ce que désigne usuellement (et historiquement) le mot compilation est la traduction d’un programme depuis un langage de haut niveau, facilement compréhensible et modifiable par des êtres humains, vers du « langage machine », de bas niveau, beaucoup plus efficace d’un point de vue algorithmique. Il s’agit là encore de pré-traitement — on transforme quelque chose hors ligne pour faciliter son utilisation en ligne. Ce n’est cependant pas à proprement parler de la compilation de connaissances, domaine spécifique qui diffère de l’étude générale du pré-traitement sur deux points. Premièrement, comme le souligne Marquis [Mar08], le nom de la « compilation de connaissances » limite sa portée aux « bases de connaissances », c’est-àdire à des ensembles d’informations généralement représentées par des formules logiques, et à leur exploitation, c’est-à-dire au raisonnement automatisé. La définition reste très générale — le terme « information» peut recouvrir un grand nombre de choses — mais exclut notamment la compilation de programmes au sens classique. La seconde différence entre compilation standard et compilation de connaissances est une conséquence de la précédente [CD97]. Étant liée à la représentation des connaissances et au raisonnement, la compilation de connaissances ne considère la difficulté d’un problème que par le prisme de la théorie de la complexité algorithmique [voir Pap94 pour un survol de la théorie de la complexité]. Ainsi, les auteurs travaillant sur la compilation ne cherchent pas simplement à rendre les problèmes plus faciles, mais drastiquement plus faciles, en les faisant changer de classe de complexité, par exemple de NP-complet à P, de PSPACE-complet à NP, etc.

Un cadre pour la cartographie des langages

Le but de la carte de compilation est de comparer les langages selon leur complexité spatiale et leur efficacité (en termes de complexité au pire cas) pour diverses opérations possibles, comme la requête d’informations sur la forme compilée, ou l’application de transformations. La carte facilite la comparaison des fragments sur le plan de la complexité théorique, permettant ainsi de ne retenir que les meilleurs pour chaque application. L’objectif de cette section est de présenter formellement la carte de compilation, notamment la notion de langage sur laquelle elle repose, et les concepts en permettant la comparaison.

Notations

Avant d’introduire nos conventions de notation, précisons que cette thèse inclut un index des symboles [p. 173]. On note R l’ensemble des nombres réels, Z celui des entiers relatifs, N celui des entiers naturels (y compris 0), N∗ celui des entiers naturels non nuls, et B celui des constantes booléennes. Ces dernières sont notées ⊤ et ⊥ (respectivement pour « vrai » et « faux »), mais sont souvent identifiées aux entiers 1 et 0, de sorte que :

B ⊆ N ⊆ Z ⊆ R

On utilise SA pour l’ensemble des singletons d’un ensemble A. Ainsi, par exemple, SB = { {⊤}, {⊥}} , et SN = ∪ n∈N { {n} } .

Dans une optique de généralisation, nous considérerons des variables de domaine quelconque — discret ou continu, fini ou infini… mais non vide. On note V l’ensemble de toutes les variables possibles ; V est bien sûr non vide, et on le suppose ordonné par un ordre strict total <V. Quand on considérera des ensembles de variables indicées, comme {x1, x2 . . . , xk}, on supposera toujours implicitement que x1 <V x2 <V . . . <V xk.

Comment l’exprimer : les structures de données 

La compilation de connaissances vise à exprimer les fonctions comme des instances de structures de données spécifiques. Une structure de données [voir e.g. CL+01, partie III] est une organisation particulière des informations dans la mémoire d’un ordinateur, munie d’algorithmes de manipulation exploitant les données efficacement, en tirant parti de cette organisation. Parmi les structures de données bien connues, on peut citer les piles, les files, les tables de hachage, les arbres, les graphes… Un objet mathématique comme une fonction est un concept abstrait. Pour le représenter avec une structure de données, il est nécessaire de le modéliser, en identifiant les opérations de base par le biais desquelles il est manipulé ; ainsi, les ensembles sont des « choses » qu’il est possible d’intersecter, d’unir, d’énumérer, etc. Une fois qu’un modèle est décrit, il est possible de définir une structure de donnée l’implantant efficacement. Celle-ci n’est pas nécessairement unique ; diverses structures données peuvent être utilisées pour exprimer un même concept mathématique. Leur efficacité peut varier, mais aucune n’est plus « correcte » qu’une autre. Nous considérons les structures de données d’une manière relativement abstraite, sans nous apesantir sur les détails d’implantation. Nous utiliserons un attribut important des structures de données, la taille mémoire de leurs instances. Pour cela, on munit chaque structure de données d’une fonction de taille caractéristique abstraite, associant à chaque instance φ de la structure de données en question, un entier positif représentatif de la place qu’elle prend en mémoire. La taille caractéristique d’une instance φ, que nous notons ∥φ∥ pour la distinguer du cardinal d’un ensemble (noté |S|), n’est pas directement égale à sa taille mémoire Mem(φ). Le point-clef est que la taille caractéristique doit croître de la même manière que la taille mémoire : ∥φ∥ ∈ Θ(Mem(φ)), c’est-à-dire qu’il existe deux constantes positives k1 et k2 telles que lorsque φ est suffisamment gros, Mem(φ) · k1 ⩽ ∥φ∥ ⩽ Mem(φ) · k2. Par exemple, considérons une structure de données destinée à représenter des listes de nombres réels, et une autre destinée à représenter des listes de nombres entiers. Il est probable que les instances de la première prennent plus de place en mémoire que les instances de la seconde, étant donné que les nombres réels sont plus coûteux que les entiers en termes de mémoire. Pourtant, si on utilise dans les deux cas des structures exactement similaires excepté le type utilisé pour les nombres, elles ont la même taille caractéristique, puisqu’elles sont équivalentes modulo une simple constante multiplicative.

Table des matières

Introduction
Contexte
1 Compilation de connaissances
1.1 Présentation
1.1.1 Concepts et historique
1.1.2 Exemple de langage-cible : OBDDs
1.2 Un cadre pour la cartographie des langages
1.2.1 Notations
1.2.2 Langage de représentation
1.2.3 Comparaison de langages
1.3 Langages booléens
1.3.1 Langages de DAGs
1.3.2 Fragments basé sur des restrictions d’opérateurs
1.3.3 Fragments « historiques »
1.3.4 Fragments basés sur des propriétés des nœuds
1.3.5 La famille des graphes de décision
1.3.6 Ordonner les graphes de décision
1.3.7 Principes de fermeture
1.4 Carte de compilation des langages booléens
1.4.1 Requêtes et transformations booléennes
1.4.2 Résultats de compacité
1.4.3 Satisfaction de requêtes et de transformations
1.5 Compilation
1.5.1 Langage d’entrée
1.5.2 Méthodes exactes de compilation
1.5.3 Méthodes non-exactes de compilation
2 Planification
2.1 Définition générale
2.1.1 Intuition
2.1.2 Description du monde
2.1.3 Définition d’un problème de planification
2.1.4 Solutions d’un problème de planification
2.2 Paradigmes de planification
2.2.1 Planification en avant dans l’espace des états
2.2.2 Planification par satisfiabilité
2.2.3 Planification par model-checking
2.2.4 Planification par processus décisionnels de Markov
2.2.5 Autres paradigmes
2.3 Compilation pour la planification
2.3.1 Planification par satisfiabilité
2.3.2 Planification par recherche heuristique
2.3.3 Planification par model-checking
2.3.4 Planification par MDPs
3 Problématique
3.1 Benchmarks utilisés
3.1.1 Problème de compétition de drones
3.1.2 Problème de gestion de la mémoire d’un satellite
3.1.3 Problème de gestion des connections d’un transpondeur
3.1.4 Problème de rendez-vous en attitude
3.2 Première tentative
3.2.1 Notre approche pour le problème Drone
3.2.2 Résultats pour le problème Drone
3.3 Vers des langages-cibles plus appropriés
3.3.1 Orientation générale
3.3.2 Identification des opérations importantes
3.3.3 Nouvelles requêtes et transformations
Automates à intervalles
Introduction
4 Formalisme des automates à intervalles
4.1 Langage
4.1.1 Définition
4.1.2 Automates à intervalles
4.1.3 Relations avec la famille de BDD
4.1.4 Réduction
4.2 Un sous-langage efficace
4.2.1 Satisfaction d’importantes requêtes sur les automates à intervalles
4.2.2 Convergence
4.3 Carte de compilation d’IA
4.3.1 Préliminaires
4.3.2 Compacité
4.3.3 Requêtes et transformations
Conclusion

Lire le rapport complet