Point-Based Backup for Decentralized POMDPs: Complexity and New Algorithms

Akshat Kumar and Shlomo Zilberstein. Point-Based Backup for Decentralized POMDPs: Complexity and New Algorithms. Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1315-1322, Toronto, Canada, 2010.

Abstract

Decentralized POMDPs provide an expressive framework for sequential multi-agent decision making. Despite their high complexity, there has been significant progress in scaling up existing algorithms, largely due to the use of point-based methods. Performing point-based backup is a fundamental operation in state-of-the-art algorithms. We show that even a single backup step in the multi-agent setting is NP-Complete. Despite this negative worst-case result, we present an efficient and scalable optimal algorithm as well as a principled approximation scheme. The optimal algorithm exploits recent advances in the weighted CSP literature to overcome the complexity of the backup operation. The polytime approximation scheme provides a constant factor approximation guarantee based on the number of belief points. In experiments on standard domains, the optimal approach provides significant speedup (up to 2 orders of magnitude) over the previous best optimal algorithm and is able to increase the number of belief points by more than a factor of 3. The approximation scheme also works well in practice, providing near-optimal solutions to the backup problem.

Bibtex entry:

@inproceedings{KZaamas10,
  author	= {Akshat Kumar and Shlomo Zilberstein},
  title		= {Point-Based Backup for Decentralized {POMDP}s:
                   Complexity and New Algorithms},
  booktitle     = {Proceedings of the Ninth International Conference on Autonomous
                   Agents and Multiagent Systems},
  year		= {2010},
  pages		= {1315-1322},
  address       = {Toronto, Canada},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KZaamas10.html}
}

shlomo@cs.umass.edu