MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs

Daniel Szer, Francois Charpillet, and Shlomo Zilberstein. MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs. Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI), 576-583, Edinburgh, Scotland, 2005.

Abstract

We present multi-agent A* (MAA*), the first complete and optimal heuristic search algorithm for solving decentralized partially-observable Markov decision problems (DEC- POMDPs) with finite horizon. The algorithm is suitable for computing optimal plans for a cooperative group of agents that operate in a stochastic environment such as multi-robot coordination, network traffic control, or distributed resource allocation. Solving such problems effectively is a major challenge in the area of planning under uncertainty. Our solution is based on a synthesis of classical heuristic search and decentralized control theory. Experimental results show that MAA* has significant advantages. We introduce an anytime variant of MAA* and conclude with a discussion of promising extensions such as an approach to solving infinite-horizon problems.

Bibtex entry:

@inproceedings{SCZuai05,
  author	= {Daniel Szer and Francois Charpillet and Shlomo Zilberstein},
  title		= {{MAA}*: A Heuristic Search Algorithm for Solving Decentralized 
                   {POMDP}s},
  booktitle     = {Proceedings of the Twenty-First Conference on Uncertainty in
                   Artificial Intelligence},
  year		= {2005},
  pages		= {576-583},
  address       = {Edinburgh, Scotland},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/SCZuai05.html}
}

shlomo@cs.umass.edu