Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
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 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.
Keywords:
Pages: 576-583
PS Link:
PDF Link: /papers/05/p576-szer.pdf
BibTex:
@INPROCEEDINGS{Szer05,
AUTHOR = "Daniel Szer and Francois Charpillet and Shlomo Zilberstein",
TITLE = "MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs",
BOOKTITLE = "Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2005",
PAGES = "576--583"
}


hosted by DSL   •   site info   •   help