Le cadre de ce projet est relié au logiciel open source Marmote qui est dédié à la modélisation et au calcul autour des Chaine de Markov et plus précisément à sa bibliothèque de résolution des Processus de Décision Markovien (PDM). Cette bibliothèque est développée en C++ et contient déjà des algorithmes classiques de résolution. Cependant la version actuelle nécessite un certain nombre d’évolutions pour pouvoir être utilisée par un public ayant une connaissance des Processus de Décision Markoviens et cherchant un solveur facile à mettre en oeuvre.
Les évolutions à réaliser vont être de plusieurs types et vont permettre d’appréhender les principaux aspects du développement d’une bibliothèque scientifique en s’intégrant dans un code déjà existant.
Ce projet va se diviser en plusieurs phases :
- a) Appréhender et comprendre le cadre des PDM et des algorithmes de résolution associés.
- b) Conceptualiser et réfléchir à une architecture de code à partir du code existant. Entre autre, on chercher à utiliser quelques-uns des concepts de la programmation orientée objets pour définir les différents PDM selon leurs caractéristiques et leur résolution. Ceci permettra une utilisation plus souple de la bibliothèque.
-c) Ajout de fonctionnalités supplémentaires simples pour élargir le champ des modèles traités. On ajoutera notamment la possibilité de travailler avec des espaces d’état (espace dans lequel évolue le processus) multidimensionnels et non plus monodimensionnels.
-d) Faciliter la prise en main et l’utilisation. Ceci passe par la création d’exemple jouets facile à comprendre et à faire évoluer. Ils permettront aussi de comparer et de tester le code développé.
-e) Développement, test, et évolution d’une méthode de résolution des PDM basée sur l’algorithme de Newton Raphson. Cette partie vise à implémenter une méthode classique mais peut répandue et à la comparer avec les méthodes déjà implémentées. C’est une des partie conséquente du projet et nécessite d’avoir traité les points précédents. On testera aussi sa convergence, sa stabilité et sa vitesse et on sera peut être amené à la modifier pour la rendre plus fiable.
[1] W.B Powell, chapter 3 « Introduction to Markov Decision Processes » in Approximate Dynamic Programming: Solving the Curses of Dimensionality, 2nd Edition, 2011.
[2] Masamitsu Ohnishi, « Policy iteration and Newton-Raphson methods for Markov decision processes under average cost criterion », Computers & Mathematics with Applications, Pages 147-155, 1992.