HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

Contributor : Daniel Szer Connect in order to contact the contributor
Submitted on : Friday, October 6, 2006 - 3:31:56 PM
Last modification on : Wednesday, February 2, 2022 - 3:51:20 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 6:51:39 PM


  • HAL Id : inria-00104443, version 1



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



Record views


Files downloads