MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
Daniel Szer
Francois Charpillet
Shlomo Zilberstein
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 trafic 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.
Download
[pdf]