Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms

Jilles Steeve Dibangoye 1 Christopher Amato 2 Olivier Buffet 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Résumé : Les processus de décision markoviens partiellement observables décentralisés (Dec-POMDP) fournissent un modèle général pour la prise de décision dans l'incertain dans des cadres coopératifs décentralisés. En guise de nouvelle approche de résolution de ces problèmes, nous introduisons l'idée de transformer un Dec-POMDP en un MDP déterministe à espace d'états continu dont la fonction de valeur est linéaire par morceaux et convexe. Cette approche exploite le fait que la planification peut être effectuée d'une manière centralisée hors ligne, alors que l'exécution peut toujours être distribuée. Cette nouvelle formulation des Dec-POMDP, que nous appelons un occupancy MDP, permet pour la première fois d'employer de puissantes méthodes de résolution de POMDP et MDP à états continus. La malédiction de la dimensionalité devenant prohibitive, nous raffinons cette approche basique et présentons des façons de combiner la recherche heuristique et des représentations compactes qui exploitent la structure présente dans les domaines multi-agents, sans perdre la capacité de converger à terme vers une solution optimale. En particulier, nous introduisons une recherche heuristique qui repose sur des représentations compactes fondées sur des features, sur des mises-à-jour à base de points, et une sélection d'action efficace. Une analyse théorique démontre que nos algorithmes de recherche heuristique fondés sur des features se terminent en temps fini avec une solution optimale. Nous incluons une analyse empirique extensive utilisant des bancs d'essai bien connus, démontrant ainsi que notre approche améliore significativement le passage à l'échelle en comparaison de l'état de l'art.
Type de document :
Rapport
[Research Report] RR-8517, INRIA. 2014, pp.77
Liste complète des métadonnées

Littérature citée [67 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00975802
Contributeur : Olivier Buffet <>
Soumis le : mercredi 9 avril 2014 - 11:38:06
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : mercredi 9 juillet 2014 - 11:50:54

Fichier

RR-8517.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00975802, version 1

Citation

Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, François Charpillet. Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms. [Research Report] RR-8517, INRIA. 2014, pp.77. 〈hal-00975802〉

Partager

Métriques

Consultations de la notice

358

Téléchargements de fichiers

326