MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
This addresses the challenge of computing optimal plans for cooperative agents in stochastic environments like multirobot coordination, but it is incremental as it builds on existing heuristic search and decentralized control theory.
The authors tackled the problem of solving decentralized partially-observable Markov decision problems (DEC-POMDPs) with finite horizon by introducing MAA*, the first complete and optimal heuristic search algorithm, which shows significant advantages in experimental results.
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 multirobot coordination, network traffic control, `or distributed resource allocation. Solving such problems efiectively 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.