Knowledge compilation for online decision-making : application to the control of autonomous system
Alexandre Niveau · OpenGrey (Institut de l'Information Scientifique et Technique) · 2012
La conduite de systemes autonomes necessite de prendre des decisions en fonction des observations et des objectifs courants : cela implique des tâches a effectuer en ligne, avec les moyens de calcul embarques. Cependant, il s'agit generalement de tâches combinatoires, gourmandes en temps de calcul et en espace memoire. Realiser ces tâches integralement en ligne degrade la reactivite du systeme ; les realiser integralement hors ligne, en anticipant toutes les situations possibles, nuit a son embarquabilite. Les techniques de compilation de connaissances sont susceptibles d'apporter un compromis, en deportant au maximum l'effort de calcul avant la mise en situation du systeme. Ces techniques consistent a traduire un probleme dans un certain langage, fournissant une forme compilee de ce probleme, dont la resolution est facile et la taille aussi compacte que possible. La traduction peut etre tres longue, mais n'est effectuee qu'une seule fois, hors ligne. Il existe de nombreux langages-cible de compilation, notamment le langage des diagrammes de decision binaires (BDDs), qui ont ete utilises avec succes dans divers domaines (model-checking, configuration, planification). L'objectif de la these etait d'etudier l'application de la compilation de connaissances a la conduite de systemes autonomes. Nous nous sommes interesses a des problemes reels de planification, qui impliquent souvent des variables continues ou a grand domaine enumere (temps ou memoire par exemple). Nous avons oriente notre travail vers la recherche et l'etude de langages-cible de compilation assez expressifs pour permettre de representer de tels problemes.