contribution à la résolution des processus décisionnels de markov : applications à la robotique

Abstract

Cette thèse porte sur les Processus Décisionnels de Markov (PDM) qui offrent un modèle mathématique simple et un ensemble d’algorithmes permettant de résoudre des problèmes de décisions séquentielles dans l’incertain. La complexité de ces algorithmes croît exponentiellement en fonction de la taille de l’espace d’états, ce qu’on appelle en littérature la malédiction de la dimension, cela limite grandement l’utilisation des PDM dans la plupart des problèmes réels. En outre, pour le problème du plus court chemin stochastique avec des impasses, qui est modélisé sous forme d’un PDM, la convergence de ses algorithmes de résolution ne peut être assurée. En littérature, les techniques les plus utilisées pour remédier au problème des PDM de grandes dimensions, sont les méthodes hiérarchiques (ou topologiques) qui consistent à : (i) décomposer l’espace d’états en Composantes Fortement Connexes (CFC), (ii) résoudre les PDM restreints correspondants à chaque CFC et combiner leurs solutions pour obtenir une solution globale. Néanmoins, la procédure de décomposition risque lui aussi de croître exponentiellement en fonction de la taille de l’espace d’états. À travers nos contributions, nous proposons une nouvelle technique de décomposition optimisée basée sur l’algorithme de Tarjan, qui nous a permis de réduire l’espace d’états de chaque PDM restreint et de construire de nouveaux algorithmes hiérarchiques pour les PDM actualisés à espaces d’états et d’actions finis. En outre, nous considérons la classe des PDM orientés but, à savoir le problème du plus court chemin stochastique avec des impasses. Nous présentons, d’une part, une transformation de son modèle PDM permettant de résoudre le problème de divergence des algorithmes de résolution et de répondre à la question d’insuffisance de ressources pour atteindre le but. D’autre part, nous proposons une nouvelle méthode de partition de l’espace d’états en niveaux d’accessibilité aux états buts, à chaque niveau correspondra un ou plusieurs PDM restreints dont les solutions seront combinées pour fournir une heuristique admissible du problème initial. Enfin, dans l’application de la couverture de zone par un robot démineur ou robot nettoyeur, etc., nous présentons un modèle PDM et un algorithme de résolution en ligne orienté but, offrant la possibilité de choisir le mode de balayage adéquat. Par ailleurs, nous considérons les PDM inconnus. Nous proposons, tout d’abord, un nouvel algorithme d’apprentissage par renforcement (AR) guidé pour le problème de la navigation robotique dans un environnement inconnu. Ensuite, nous présentons deux nouveaux algorithmes d’AR pour la classe des PDM déterministes ayant une fonction de II Résumé récompenses inconnue. Ces algorithmes peuvent être utilisés dans différentes applications en robotique, telle que l’apprentissage à la marche robotique. Enfin, nous proposons deux nouveaux modèles d’AR, le premier appliqué au robot suiveur de ligne et le deuxième modèle appliqué au robot auto-balancé. Finalement, des simulations et des expérimentations seront présentées pour montrer les performances des algorithmes proposés et leurs compétitivités avec les algorithmes de résolution classiques.