Skip to main content
Unpublished Paper
MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
  • Daniel Szer
  • Francois Charpillet
  • Shlomo Zilberstein, University of Massachusetts - Amherst
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.
Publication Date
This is the pre-published version harvested from arXiv.
Citation Information
Daniel Szer, Francois Charpillet and Shlomo Zilberstein. "MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs" (2012)
Available at: