An investigation into Mathematical Programming for Finite Horizon Decentralized POMDPs

Raghav Aras 1, 2 Alain Dutech 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Decentralized planning in uncertain environments is a complex task generally dealt with by using a decision-theoretic approach, mainly through the framework of Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs). Although DEC-POMDPS are a general and powerful modeling tool, solving them is a task with an overwhelming complexity that can be doubly exponential, using either Dynamic Programming or Forward Search methods. In this paper, we study an alternate formulation of DEC-POMDPs relying on a sequence form representation of policies. From this formulation, we show how to derive Mixed Integer Linear Programming (MILP) problems that, once solved, give exact optimal solutions to the DEC-POMDPs. We show that these MILPs can be derived either by using some combinatorial characteristics of the optimal solutions of the DEC-POMDPs or by using concepts borrowed from game theory. Through an experimental validation on classical test problems from the DEC-POMDP literature, we compare our approach to existing algorithms. Results show that mathematical programming outperforms dynamic programming but is less efficient than forward search, except for some particular problems. The main contributions of this work are the use of mathematical programming for DEC-POMDPs and a better understanding of DEC-POMDPs and of their solutions. Besides, we argue that our alternate representation of DEC-POMDPs could be helpful for designing novel algorithms looking for approximate solutions to DEC-POMDPs.
Type de document :
Article dans une revue
Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2010, 37, pp.329-396. 〈http://www.jair.org/media/2915/live-2915-4898-jair.pdf〉. 〈10.1613/jair.2915〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00439627
Contributeur : Alain Dutech <>
Soumis le : mardi 8 décembre 2009 - 09:19:09
Dernière modification le : jeudi 29 mars 2018 - 11:06:04
Document(s) archivé(s) le : jeudi 17 juin 2010 - 23:25:42

Fichier

aras09_mathProgPOMDP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Raghav Aras, Alain Dutech. An investigation into Mathematical Programming for Finite Horizon Decentralized POMDPs. Journal of Artificial Intelligence Research, Association for the Advancement of Artificial Intelligence, 2010, 37, pp.329-396. 〈http://www.jair.org/media/2915/live-2915-4898-jair.pdf〉. 〈10.1613/jair.2915〉. 〈inria-00439627〉

Partager

Métriques

Consultations de la notice

360

Téléchargements de fichiers

94