Optimally Solving Dec-POMDPs as Continuous-State MDPs

Abstract : Decentralized partially observable Markov decision processes (Dec-POMDPs) provide a general model for decision-making under uncertainty in decentralized settings, but are difficult to solve optimally (NEXP-Complete). As a new way of solving these problems, we introduce the idea of transforming a Dec-POMDP into a continuous-state deterministic MDP with a piecewise-linear and convex value function. This approach makes use of the fact that planning can be accomplished in a centralized offline manner, while execution can still be decentralized. This new Dec-POMDP formulation , which we call an occupancy MDP, allows powerful POMDP and continuous-state MDP methods to be used for the first time. To provide scalability, we refine this approach by combining heuristic search and compact representations that exploit the structure present in multi-agent domains, without losing the ability to converge to an optimal solution. In particular, we introduce a feature-based heuristic search value iteration (FB-HSVI) algorithm that relies on feature-based compact representations, point-based updates and efficient action selection. A theoretical analysis demonstrates that FB-HSVI terminates in finite time with an optimal solution. We include an extensive empirical analysis using well-known benchmarks, thereby demonstrating that our approach provides significant scalability improvements compared to the state of the art.
Type de document :
Article dans une revue
Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2016, 55, pp.443-497. 〈http://www.jair.org/〉. 〈10.1613/jair.4623〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01279444
Contributeur : Jilles Steeve Dibangoye <>
Soumis le : mardi 1 mars 2016 - 08:34:11
Dernière modification le : mardi 2 octobre 2018 - 14:46:01
Document(s) archivé(s) le : mardi 31 mai 2016 - 10:53:28

Fichier

dibangoye16a.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Domaine public

Identifiants

Citation

Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, François Charpillet. Optimally Solving Dec-POMDPs as Continuous-State MDPs. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2016, 55, pp.443-497. 〈http://www.jair.org/〉. 〈10.1613/jair.4623〉. 〈hal-01279444〉

Partager

Métriques

Consultations de la notice

647

Téléchargements de fichiers

145