Incremental Policy Generation for Finite-Horizon DEC-POMDPs

Chistopher Amato, Jilles Steeve Dibangoye, and Shlomo Zilberstein. Incremental Policy Generation for Finite-Horizon DEC-POMDPs. Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), Thessaloniki, Greece, 2009.

Abstract

Decentralized partially observable MDPs (DEC-POMDPs) provide a rich framework for modeling decision making by a team of agents. Despite rapid progress in this area, the limited scalability of solution techniques has restricted the applicability of the model. To overcome this computational barrier, research has focused on restricted classes of DEC-POMDPs, which are easier to solve yet rich enough to capture many practical problems. We present CBDP, an efficient and scalable point-based dynamic programming algorithm for one such model called ND-POMDP (Network Distributed POMDP). Specifically, CBDP provides magnitudes of speedup in the policy computation and generates better quality solution for all test instances. It has linear complexity in the number of agents and horizon length. Furthermore, the complexity per horizon for the examined class of problems is exponential only in a small parameter that depends upon the interaction among the agents, achieving significant scalability for large, loosely coupled multi-agent systems. The efficiency of CBDP lies in exploiting the structure of interactions using constraint networks. These results extend significantly the effectiveness of decision-theoretic planning in multi-agent settings.

Bibtex entry:

@inproceedings{ADZicaps09,
  author	= {Chistopher Amato and Jilles Steeve Dibangoye and Shlomo Zilberstein},
  title		= {Incremental Policy Generation for Finite-Horizon {DEC-POMDP}s},
  booktitle     = {Proceedings of the International Conference on Automated Planning
                   and Scheduling},
  year		= {2009},
  pages		= {2-9},
  address       = {Thessaloniki, Greece},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/ADZicaps09.html}
}

shlomo@cs.umass.edu