MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
arXiv:1207.1359
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.
Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)
References in corpus (7)
- Value-Function Approximations for Partially Observable Markov Decision Processes
- The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
- Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
- Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis
- Learning to Cooperate via Policy Search
- Solving POMDPs by Searching in Policy Space
- Solving POMDPs by Searching the Space of Finite Policies
Cited by in corpus (18)
- Optimal and Approximate Q-value Functions for Decentralized POMDPs
- Partially Observable Markov Decision Processes in Robotics: A Survey
- Game-Theoretic Multiagent Reinforcement Learning
- Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs
- Policy Iteration for Decentralized Control of Markov Decision Processes
- Optimizing Memory-Bounded Controllers for Decentralized POMDPs
- Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
- Mixed Integer Linear Programming For Exact Finite-Horizon Planning In Decentralized Pomdps
- An Investigation into Mathematical Programming for Finite Horizon Decentralized POMDPs
- Approximate information state for approximate planning and reinforcement learning in partially observed systems
- Distributed Heuristic Forward Search for Multi-Agent Systems
- Influence-Optimistic Local Values for Multiagent Planning --- Extended Version
- Distribution over Beliefs for Memory Bounded Dec-POMDP Planning
- Online Planning for Decentralized Stochastic Control with Partial History Sharing
- On Bellman's Optimality Principle for zs-POSGs
- A Framework for Rate Efficient Control of Distributed Discrete Systems
- Optimal decentralized control of coupled subsystems with control sharing
- Multi-Robot Active Information Gathering with Periodic Communication