Computer Science – Artificial Intelligence
Scientific paper
2011-10-31
Journal Of Artificial Intelligence Research, Volume 32, pages 169-202, 2008
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.2466
Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and information gathering scenarios can be formalized using this framework. However, finding the optimal solution in the general case is hard, limiting the applicability of recently developed algorithms. This paper provides a practical approach for solving decentralized control problems when communication among the decision makers is possible, but costly. We develop the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems. In this framework, referred to as decentralized semi-Markov decision process with direct communication (Dec-SMDP-Com), agents operate separately between communications. We show that finding an optimal mechanism is equivalent to solving optimally a Dec-SMDP-Com. We also provide a heuristic search algorithm that converges on the optimal decomposition. Restricting the decomposition to some specific types of local behaviors reduces significantly the complexity of planning. In particular, we present a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. The paper concludes with an additional tractable algorithm that enables the introduction of human knowledge, thereby reducing the overall problem to finding the best time to communicate. Empirical results show that these approaches provide good approximate solutions.
Goldman Claudia V.
Zilberstein Shlomo
No associations
LandOfFree
Communication-Based Decomposition Mechanisms for Decentralized MDPs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Communication-Based Decomposition Mechanisms for Decentralized MDPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication-Based Decomposition Mechanisms for Decentralized MDPs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-466845