Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs

Abstract

Memory-Bounded Dynamic Programming (MBDP) has proved extremely effective in solving decentralized POMDPs with large horizons. We generalize the algorithm and improve its scalability by reducing the complexity with respect to the number of observations from exponential to polynomial. We derive error bounds on solution quality with respect to this new approximation and analyze the convergence behavior. To evaluate the effectiveness of the improvements, we introduce a new, larger benchmark problem. Experimental results show that despite the high complexity of decentralized POMDPs, scalable solution techniques such as MBDP perform surprisingly well.

Appears in Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007)

References in corpus (3)

• The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
• The Complexity of Decentralized Control of Markov Decision Processes
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs

Cited by in corpus (5)

• Rollout Sampling Policy Iteration for Decentralized POMDPs
• Uncertain Congestion Games with Assorted Human Agent Populations
• Distribution over Beliefs for Memory Bounded Dec-POMDP Planning
• Team Behavior in Interactive Dynamic Influence Diagrams with Applications to Ad Hoc Teams
• Partially Observed, Multi-objective Markov Games