Contributions à la résolution des processus décisionnels de Markov centralisés et décentralisés (Algorithmes et Théorie)

Cette thèse porte sur les aspects calculatoires des problèmes de prise de décisions sous diverses sources d'incertitude de systèmes munis d'un ou de plusieurs agents. En particulier, nous aborderons des problèmes pouvant être modélisés sous forme de processus décisionnels de Markov. De plus, nous étudions également les extensions des processus décisionnels de Markov, notamment ceux incorporant l'incertitude résultant soit des autres agents du système, soit des informations sur l'état du système. Nous présentons des stratégies permettant d'améliorer les performances des techniques de l'état de l'art de la résolution des processus décisionnels de Markov. Nous suggérons tout d abord une méthode générale, nommée programmation dynamique topologique, qui exploite les dépendances causales entre états du système afin de faire face à deux problématiques. D'une part, elle détecte la structure du problème, comme un moyen de surmonter à la fois la malédiction de la dimension et celle de l'historique. D'autre part, elle contourne le problème lié aux mises à jour redondantes et construit des solutions optimales ou approximatives suivant un ordre topologique induit par la structure sous-jacente du problème. En outre, nous introduisons la planification centralisée pour le contrôle distribué des processus décisionnels de Markov. Nous offrons les bases théoriques utiles pour des travaux futurs dans cette direction. Cette analyse formelle a débouché sur bon nombre d'algorithmes exacts et approximatifs pour la résolution centralisée des processus décisionnels de Markov décentralisés. Parmi tous ces algorithmes figure, l'algorithme d'élagage incrémental à base de croyances, qui s'est révélé le meilleur algorithme approximatif à ce jour. La planification centralisée pour le contrôle distribué ouvre un certain nombre de perspectives, y compris celle d'une statistique suffisante bornée pour le contrôle distribué des processus de Markov.This thesis addresses the computational issues in sequential decision-making under various sources of uncertainty for either single or multi-agent systems. In particular, we will be concerned in problems that can be modeled as Markov decision processes. In addition, we address extensions of Markov decision process, which involve uncertainty resulting from other agents in the world, and partial observability. We present several strategies that improve the performances of state-of-the-art techniques for solving Markov decision processes. We suggest a general method, namely topological dynamic programming, that exploits the causal relation between states to deal with two key issues. First, it detects the structure of the problem as a means of overcoming both dimensionality and history curses. Secondly, it circumvents the problem of unnecessary backups and builds optimal and approximate solutions based on a topological order induced by the underlying problem structure. Moreover, we introduce the centralized planning for distributed control of Markov decision processes. We provide theoretical basis for further work in that direction. This analysis results in a number of efficient exact as well as approximate algorithms for solving decentralized Markov decision processes. Among many, point-based incremental pruning algorithm turns out to be the most efficient so far. The centralized planning for distributed control opens a number avenues, including a bounded sufficient statistic for a general model of decentralized Markov decision processes.CAEN-BU Sciences et STAPS (141182103) / SudocSudocFranceF