HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs

Daniel Szer 1 François Charpillet 1 Shlomo Zilberstein 2
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Complete list of metadata

Contributor : Daniel Szer Connect in order to contact the contributor
Submitted on : Monday, September 12, 2005 - 10:13:06 AM
Last modification on : Wednesday, February 2, 2022 - 3:51:34 PM
Long-term archiving on: : Thursday, April 1, 2010 - 10:23:05 PM


  • HAL Id : inria-00000204, version 1



Daniel Szer, François Charpillet, Shlomo Zilberstein. MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs. 21st Conference on Uncertainty in Artificial Intelligence - UAI'2005, Jul 2005, Edinburgh/Scotland. ⟨inria-00000204⟩



Record views


Files downloads