MAGNAN Jean-Christophe

Docteur
Équipe : DECISION
Date de départ : 29/02/2016
https://lip6.fr/Jean-Christophe.Magnan

Direction de recherche : Christophe GONZALES

Co-encadrement : WUILLEMIN Pierre-Henri

Représentations Graphiques de Fonctions et Processus Décisionnels Markoviens Factorisés

En planification théorique de la décision, le cadre des Processus Décisionnels Markoviens Factorisés (Factored Markov Decision Process, FMDP) a produit des algorithmes efficaces de résolution des problèmes de décisions séquentielles dans l'incertain. L'efficacité de ces algorithmes repose sur des structures de données telles que les Arbres de Décision ou les Diagrammes de Décision Algébriques (ADDs). Ces techniques de planification sont utilisées en Apprentissage par Renforcement par l'architecture SDYNA afin de résoudre des problèmes inconnus de grandes tailles. Toutefois, l'état-de-l'art des algorithmes d'apprentissage, de programmation dynamique et d'apprentissage par renforcement utilisés par SDYNA, requière que le problème soit spécifié uniquement à l'aide de variables binaires et/ou utilise des structures améliorables en termes de compacité. Dans ce manuscrit, nous présentons nos travaux de recherche visant à élaborer et à utiliser une structure de donnée plus efficace et moins contraignante, et à l'intégrer dans une nouvelle instance de l'architecture SDYNA.
Dans une première partie, nous présentons l'état-de-l'art de la modélisation de problèmes de décisions séquentielles dans l'incertain à l'aide de FMDP. Nous abordons en détail la modélisation à l'aide de DT et d'ADDs. Puis nous présentons les ORFGs, nouvelle structure de données que nous proposons dans cette thèse pour résoudre les problèmes inhérents aux ADDs. Nous démontrons ainsi que les ORFGs s'avèrent plus efficaces que les ADDs pour modéliser les problèmes de grandes tailles.
Dans une seconde partie, nous nous intéressons à la résolution des problèmes de décision dans l'incertain par Programmation Dynamique. Après avoir introduit les principaux algorithmes de résolution, nous nous attardons sur leurs variantes dans le domaine factorisé. Nous précisons les points de ces variantes factorisées qui sont améliorables. Nous décrivons alors une nouvelle version de ces algorithmes qui améliore ces aspects et utilise les ORFGs précédemment introduits.
Dans une dernière partie, nous abordons l'utilisation des FMDPs en Apprentissage par Renforcement. Puis nous présentons un nouvel algorithme d'apprentissage dédié à la nouvelle structure que nous proposons. Grâce à ce nouvel algorithme, une nouvelle instance de l'architecture SDYNA est proposée, se basant sur les ORFGs : l'instance SPIMDDI. Nous testons son efficacité sur quelques problèmes standards de la littérature. Enfin nous présentons quelques travaux de recherche autour de cette nouvelle instance. Nous évoquons d'abord un nouvel algorithme de gestion du compromis exploration-exploitation destiné à simplifier l'algorithme F-RMax. Puis nous détaillons une application de l'instance SPIMDDI à la gestion d'unités dans un jeu vidéo de stratégie en temps réel.

Soutenance : 02/02/2016

Membres du jury :

M. Régis Sabbadin, Directrice de recherche, INRIA, Toulouse [Rapporteur]
M. Abdel-Illah Mouaddib, Professeur, GREYC, Université de Caen [Rapporteur]
M. Olivier Sigaud, Professeur, ISIR, UPMC
M. Florent Teichteil-Koenigsbuch, Docteur, Airbus Group Innovations, Toulouse
M. Christophe Gonzales, Professeur, LIP6, UPMC
M. Pierre-Henri Wuillemin, Maitre de Conférence, LIP6, UPMC

Date de départ : 29/02/2016

Publications 2013-2017

Mentions légales
Carte du site