Mixed Integer Linear Programming For Exact Finite-Horizon Planning In Decentralized Pomdps

Raghav Aras 1 Alain Dutech 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We consider the problem of finding an n-agent joint-policy for the optimal finite-horizon control of a decentralized Pomdp (Dec-Pomdp). This is a problem of very high complexity (NEXP-hard in n >= 2). In this paper, we propose a new mathematical programming approach for the problem. Our approach is based on two ideas: First, we represent each agent's policy in the sequence-form and not in the tree-form, thereby obtaining a very compact representation of the set of joint-policies. Second, using this compact representation, we solve this problem as an instance of combinatorial optimization for which we formulate a mixed integer linear program (MILP). The optimal solution of the MILP directly yields an optimal joint-policy for the Dec-Pomdp. Computational experience shows that formulating and solving the MILP requires significantly less time to solve benchmark Dec-Pomdp problems than existing algorithms. For example, the multi-agent tiger problem for horizon 4 is solved in 72 secs with the MILP whereas existing algorithms require several hours to solve it.
Type de document :
Communication dans un congrès
The International Conference on Automated Planning and Scheduling - ICAPS 2007, Sep 2008, Providence / Rhode Island, United States. pp.18-25, 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00163372
Contributeur : Alain Dutech <>
Soumis le : mardi 17 juillet 2007 - 13:32:37
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : jeudi 8 avril 2010 - 23:26:42

Fichiers

raw-milp-icap-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00163372, version 1
  • ARXIV : 0707.2506

Collections

Citation

Raghav Aras, Alain Dutech, François Charpillet. Mixed Integer Linear Programming For Exact Finite-Horizon Planning In Decentralized Pomdps. The International Conference on Automated Planning and Scheduling - ICAPS 2007, Sep 2008, Providence / Rhode Island, United States. pp.18-25, 2007. 〈inria-00163372〉

Partager

Métriques

Consultations de la notice

222

Téléchargements de fichiers

118