arXiv (Cornell University) · 2012 · 157 citations · 20 references
ComputingAutonomous SystemsComputer ScienceAlgorithmsMarkov Decision ProcessesRoboticsDecentralized ControlDecentralized PlanningHeuristic SearchMulti-agent SystemsOptimal ControlPartially Observable Markov Decision ProcessesAnytime Heuristic SearchDecentralized PomdpsFinite Horizon AnalysisFinite-horizon OptimizationHeuristic Search PlanningMulti-agent Decision MakingMultiagent PomdpsPomdp Solvers
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.
20
The Complexity of Decentralized Control of Markov Decision Processes
Daniel S. Bernstein, Robert Givan, Neil Immerman et al. · Mathematics of Operations Research · 2002 · 1.2K citations