Publication - Decomposing Centralized Multiagent Policies

Authors: Xuan, P.; Lesser, V
Title: Decomposing Centralized Multiagent Policies
Abstract: Using or extending Markov decision processes (MDPs) or partially observable Markov decision processes (POMDPs) to model multi-agent decision problems has become an important trend. Generally speaking, there are two types of models: centralized and decentralized. The centralized ones focus on finding the best joint action given any global state, while the decentralized ones try to find that for each agent, what is the best local action given all the partial information available in that agent. Although decentralized models better capture the nature of decentralization in multi-agent systems, they are much harder to solve compared to centralized models. In this paper, we show that, by studying the communication needs of the centralized models, we can establish a connection between the two models, and the solutions to centralized models (i.e. centralized policies) can be used to derive solutions to decentralized models (i.e. decentralized policies) -- a process we call plan decomposition. We show that the amount of communication needed could be greatly reduced during the decomposition, and there are techniques that could be applied to produce a set of decentralized policies based on the same centralized policy. While this method does not solve decentralized models optimally, it does offer a great deal of flexibility and allows us to trade off the quality of the policies with the amount of communication needed, and gives us better insights about the need and timing for effective coordination in multi-agent planning.
Publication: University of Massachusetts Amherst, Computer Science Technical Report
Date: 2007
Sources: PDF: /Documents/Xuan_TR0752.pdf
Reference: Xuan, P.; Lesser, V. Decomposing Centralized Multiagent Policies. University of Massachusetts Amherst, Computer Science Technical Report. 2007.
  author    = "P. Xuan and V Lesser",
  title     = "{Decomposing Centralized Multiagent Policies}",
  year      = "2007",
  url       = "",