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

https://hal.inria.fr/inria-00000204
Contributor : Daniel Szer <>
Submitted on : Monday, September 12, 2005 - 10:13:06 AM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM
Long-term archiving on: : Thursday, April 1, 2010 - 10:23:05 PM

Identifiers

  • HAL Id : inria-00000204, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

1163

Files downloads

634