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

Decentralized POMDPs provide an expressive frameworkfor sequential multi-agent decision making. Despite theirhigh 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 showthat even a single backup step in the multi-agent settingis NP-Complete. Despite this negative worst-case result, wepresent an efficient and scalable optimal algorithm as well asa principled approximation scheme. The optimal algorithmexploits recent advances in the weighted CSP literature toovercome 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 approachprovides 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 of3. The approximation scheme also works well in practice, providing near-optimal solutions to the backup problem.

Authors

• Akshat Kumar Singapore Management University
• Shlomo Zilberstein University of Massachusetts Amherst

Keywords

• Multiagent planning
• DEC-POMDPs