Point-based Dynamic Programming for DEC-POMDPs

Daniel Szer 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We introduce point-based dynamic programming (DP) for decentralized partially observable Markov decision processes (DEC-POMDPs), a new discrete DP algorithm for planning strategies for cooperative multi-agent systems. Our approach makes a connection between optimal DP algorithms for partially observable stochastic games, and point-based approximations for single-agent POMDPs. We show for the first time how relevant multi-agent belief states can be computed. Building on this insight, we then show how the linear programming part in current multi-agent DP algorithms can be avoided, and how multi-agent DP can thus be applied to solve larger problems. We derive both an optimal and an approximated version of our algorithm, and we show its efficiency on test examples from the literature.
Type de document :
Communication dans un congrès
21st National Conference on Artificial Intelligence - AAAI'2006, Jun 2006, Boston/USA, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00104443
Contributeur : Daniel Szer <>
Soumis le : vendredi 6 octobre 2006 - 15:31:56
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50
Document(s) archivé(s) le : mardi 6 avril 2010 - 18:51:39

Fichier

Identifiants

  • HAL Id : inria-00104443, version 1

Collections

Citation

Daniel Szer, François Charpillet. Point-based Dynamic Programming for DEC-POMDPs. 21st National Conference on Artificial Intelligence - AAAI'2006, Jun 2006, Boston/USA, 2006. 〈inria-00104443〉

Partager

Métriques

Consultations de la notice

152

Téléchargements de fichiers

110