Optimally Solving Dec-POMDPs as Continuous-State MDPs

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
Abstract : Optimally solving decentralized partially observable Markov decision processes (Dec-POMDPs) is a hard combinatorial problem. Current algorithms search through the space of full histories for each agent. Because of the doubly exponential growth in the number of policies in this space as the planning horizon increases, these methods quickly become intractable. However, in real world problems, computing policies over the full history space is often unnecessary. True histories experienced by the agents often lie near a structured, low-dimensional manifold embedded into the history space. We show that by transforming a Dec-POMDP into a continuous-state MDP, we are able to find and exploit these low-dimensional representations. Using this novel transformation, we can then apply powerful techniques for solving POMDPs and continuous-state MDPs. By combining a general search algorithm and dimension reduction based on feature selection, we introduce a novel approach to optimally solve problems with significantly longer planning horizons than previous methods.
Type de document :
Communication dans un congrès
IJCAI - 23rd International Joint Conference on Artificial Intelligence, Aug 2013, Pékin, China. 2013, Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence
Liste complète des métadonnées

https://hal.inria.fr/hal-00907338
Contributeur : Olivier Buffet <>
Soumis le : jeudi 21 novembre 2013 - 10:28:16
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : samedi 22 février 2014 - 04:32:54

Fichier

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

Identifiants

  • HAL Id : hal-00907338, version 1

Collections

Citation

Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, François Charpillet. Optimally Solving Dec-POMDPs as Continuous-State MDPs. IJCAI - 23rd International Joint Conference on Artificial Intelligence, Aug 2013, Pékin, China. 2013, Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. 〈hal-00907338〉

Partager

Métriques

Consultations de la notice

369

Téléchargements de fichiers

79