Qualitative Planning under Partial Observability in Multi-Agent Domains

Ronen I. Brafman, Guy Shani, and Shlomo Zilberstein. Qualitative Planning under Partial Observability in Multi-Agent Domains. Proceedings of the Twenty-Seventh Conference on Artificial Intelligence (AAAI), 130-137, Bellevue, Washington, 2013.

Abstract

Decentralized POMDPs (Dec-POMDPs) provide a rich, attractive model for planning under uncertainty and partial observability in cooperative multi-agent domains with a growing body of research. In this paper we formulate a qualitative, propositional model for multi-agent planning under uncertainty with partial observability, which we call Qualitative Dec-POMDP (QDec-POMDP). We show that the worst-case complexity of planning in QDec-POMDPs is similar to that of Dec-POMDPs. Still, because the model is more "classical" in nature, it is more compact and easier to specify. Furthermore, it eases the adaptation of methods used in classical and contingent planning to solve problems that challenge current Dec-POMDPs solvers. In particular, in this paper we describe a method based on compilation to classical planning, which handles multi-agent planning problems significantly larger than those handled by current Dec-POMDP algorithms.

Bibtex entry:

@inproceedings{BSZaaai13,
  author	= {Ronen I. Brafman and Guy Shani and Shlomo Zilberstein},
  title		= {Qualitative Planning under Partial Observability in
                   Multi-Agent Domains},
  booktitle     = {Proceedings of the Twenty-Seventh Conference on
		   Artificial Intelligence},
  year		= {2013},
  pages		= {130-137},
  address       = {Bellevue, Washington},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/BSZaaai13.html}
}

shlomo@cs.umass.edu