Computer Science Department
School of Computer Science, Carnegie Mellon University


Local Multiagent Coordination in
Decentralized MDPS with Sparse Interactions

Francisco S. Melo, Manuela Veloso

July 2010


Keywords: Decentralized Markov decision process, sparse interaction, multiagent planning

Creating coordinated multiagent policies in environments with uncertainty is a challenging problem, which can be greatly simplified if the coordination needs are known to be limited to specific parts of the state-space. In this work, we explore how such local interactions can simplify coordination in multiagent systems. We focus on problems in which the interaction between the agents is sparse, exploiting this property to minimize the coupling of the decision processes for the different agents. We contribute a new decision-theoretic model for multiagent systems, Dec-SIMDPs, that explicitly distinguishes the situations in which the agents in the team must coordinate from those in which they can act independently. We relate our new model to other existing models from the literature, such as MMDPs and Dec-MDPs. We then propose a solution method that takes advantage of the particular structure of Dec-SIMDPs and provide theoretical error bounds on the quality of the obtained solution. Finally, we illustrate the performance of our method in several simulated navigation problems.

41 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by