Une contribution à la résolution des Processus Décisionnels de Markov Décentralisés avec contraintes temporelles
Institution:
CaenDisciplines:
Directors:
Abstract EN:
This thesis deals with distributed multiagent decision-making under uncertainty. We formalize this problem with Decentralized Markov Decision Processes (DEC-MDP) which extends Markov Decision Processes (MDP) to multi-agent settings. Even if DEC-MDPs describe an expressive framework for cooperative multiagent decision, they suffer from a high complexity and fail to formalize constraints on task execution. Despite the wide variety of approaches to solve DEC-MDPs, computing a solution for large problems remains a serious challenge even for approximation approaches. We develop an approach that can solve large problems, and that can deal with more complex time and action representations. We therefore define a class of DEC-MDP, OC-DEC-MDP, that allows us to consider several possible durations for each task taking into account constraints on task execution. Having considered the representation of the problems we deal with, we turn to OC-DEC-MDP resolution. Our purpose is to develop an efficient planning approach that computes each agent's policy even for large missions. Given the high complexity of finding an optimal solution, we aim at computing an approximate solution. We also split the multiagent decision problem into a set of MDPs. For purposes of coordinating the agents, we then introduce the notion of Opportunity Cost.
Abstract FR:
Cette thèse porte sur la prise de décision distribuée dans des systèmes multi-agents agissant sous incertitude (les colonies de robots autonomes par exemple). Les processus décisionnels de Markov Décentralisés décrivent un formalisme mathématique permettant de modéliser et de résoudre de tels problèmes. Leur utilisation pour la planification des tâches dans des applications réelles pose toutefois quelques difficultés. Le modèle usuel des DEC-MDPs ne permet par exemple pas la prise en compte de contraintes sur l'exécution des tâches. De plus, la complexité de leur résolution est telle qu'il est difficile de déterminer une solution optimale excepté pour de petits problèmes. Le travail que nous présentons dans cette thèse a pour premier objectif d'adapter le modèle des DEC-MDPs afin de proposer une modélisation adéquate du temps et des actions, et de permettre la représentation de problèmes réels. Nous décrivons ainsi une nouvelle classe de DEC-MDPs : les OC-DEC-MDPs (DEC-MDP avec Coût Occasionné). Dans un second temps, nous nous intéressons à leur résolution. Nous proposons différents algorithmes procédant à la planification des tâches de chaque agent en vue d'une prise de décision décentralisée et autonome, en accord avec les contraintes du problème. Afin de développer des algorithmes efficaces et de traiter des problèmes de taille importante, nous recherchons une approximation de la solution optimale. Nous procédons également à un découpage du problème initial en un ensemble de MDPs, et introduisons la notion de coût occasionné afin de tenir compte des interactions entre les agents et de calculer des politiques coopératives.