# Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis

@article{Goldman2004DecentralizedCO, title={Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis}, author={Claudia V. Goldman and Shlomo Zilberstein}, journal={ArXiv}, year={2004}, volume={abs/1107.0047} }

Decentralized control of cooperative systems captures the operation of a group of decision-makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems… Expand

#### 268 Citations

Complexity analysis and optimal algorithms for decentralized decision making

- Mathematics
- 2005

Coordination of distributed entities is required for problems arising in many areas, including multi-robot systems, networking applications, e-commerce applications, and the control of autonomous… Expand

A Rich Communication Model in Opportunistic Decentralized Decision Making

- Computer Science
- 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology
- 2010

This paper proposes an approach that allows to formalize more complex and realistic communication decisions in DEC-MDPs with interaction graph, and extends one of the most scalable decentralized decision model, the DEC- MDP with opportunity cost (OC-DEC-M DP). Expand

Formal models and algorithms for decentralized decision making under uncertainty

- Computer Science
- Autonomous Agents and Multi-Agent Systems
- 2007

Five different formal frameworks, three different optimal algorithms, as well as a series of approximation techniques are analyzed to provide interesting insights into the structure of decentralized problems, the expressiveness of the various models, and the relative advantages and limitations of the different solution techniques. Expand

Formal Models and Algorithms for Decentralized Control of Multiple Agents Technical Report UM-CS-2005-068

- 2005

Over the last five years, the AI community has shown considerable interest in decentralized control of multiple decision makers or “agents” under uncertainty. This problem arises in many application… Expand

The Value of Communication in Decentralized Planning and Control

- Computer Science
- 2006

This project produced a mathematical approach to the design and analysis of decentralized control with particular focus on management of communication in an uncertain environment, developing the first policy iteration algorithm for solving general problems formalized as decentralized POMDPs and laying the foundations for developing learning techniques for communication. Expand

Agent interactions in decentralized environments

- Computer Science
- 2009

This thesis unifies a range of existing work, extending analysis to establish novel complexity results for some popular restricted-interaction models and identifies new analytical measures that apply to all Dec-POMDPs, whatever their structure. Expand

Communication-Based Decomposition Mechanisms for Decentralized MDPs

- Computer Science
- J. Artif. Intell. Res.
- 2008

This paper develops the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems, and presents a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. Expand

Solving efficiently Decentralized MDPs with temporal and resource constraints

- Computer Science
- Autonomous Agents and Multi-Agent Systems
- 2010

A new model is presented that allows for large multi-agent decision problems with temporal and precedence constraints to be represented and polynomial algorithms to efficiently solve problems formalized by OC-DEC-MDPs are proposed. Expand

A polynomial algorithm for decentralized Markov decision processes with temporal constraints

- Computer Science
- AAMAS '05
- 2005

This paper presents a class of Decentralized MDPs, OC-DEC-MDP, that can handle temporal and precedence constraints, and introduces an opportunity cost to allow the agents to coordinate. Expand

Solving Efficiently DEC-MDPs with Temporal Constraints

Optimizing the operation of cooperative multi-agent systems that can deal with large and realistic problems has become an important focal area of research in the multi-agent community. In this paper… Expand

#### References

SHOWING 1-10 OF 40 REFERENCES

Optimizing information exchange in cooperative multi-agent systems

- Computer Science
- AAMAS '03
- 2003

This paper develops a decision-theoretic solution to centralized control of a cooperative multi-agent system, treating both standard actions and communication as explicit choices that the decision maker must consider, and presents an analytical model to evaluate the trade-off between the cost of communication and the value of the information received. Expand

The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models

- Computer Science
- J. Artif. Intell. Res.
- 2002

A unified framework for multiagent teamwork, the COMmunicative Multiagent Team Decision Problem (COM-MTDP), which combines and extends existing multiagent theories, and provides a basis for the development of novel team coordination algorithms. Expand

The Complexity of Decentralized Control of Markov Decision Processes

- Computer Science, Mathematics
- UAI
- 2000

This work considers decentralized control of Markov decision processes and gives complexity bounds on the worst-case running time for algorithms that find optimal solutions and describes generalizations that allow for decentralized control. Expand

Communication decisions in multi-agent cooperation: model and experiments

- Computer Science
- AGENTS '01
- 2001

A multi-agent extension to Markov decision processes in which communication can be modeled as an explicit action that incurs a cost is presented, which provides a foundation for a quantified study of agent coordination policies and provides both motivation and insight to the design of heuristic approaches. Expand

Transition-independent decentralized markov decision processes

- Computer Science
- AAMAS '03
- 2003

A novel algorithm is presented that is the first effective technique to solve optimally a class of transition-independent decentralized MDPs and lays the foundation for further work in this area on both exact and approximate solutions. Expand

Sequential Optimality and Coordination in Multiagent Systems

- Mathematics, Computer Science
- IJCAI
- 1999

This work proposes an extension of value iteration in which the system's state space is augmented with the state of the coordination mechanism adopted, allowing agents to reason about the short and long term prospects for coordination, the long term consequences of (mis)coordination, and make decisions to engage or avoid coordination problems based on expected value. Expand

General principles of learning-based multi-agent systems

- Computer Science, Physics
- AGENTS '99
- 1999

This paper presents a summary of a mathematical framework for COINs, and investigates the real-world applicability of the core concepts of that framework via two computer experiments: theCOINs perform near optimally in a difficult variant of Arthur’s bar problem, and they avoid the tragedy of the commons for that problem. Expand

Generalizing the Partial Global Planning Algorithm

- Computer Science
- Int. J. Cooperative Inf. Syst.
- 1992

The coordination problem as it was viewed by the PGP algorithm is described, and a new model of task structures and coordination relationships is described that has less communication overhead and can be more easily adapted and extended to new styles of problem solving and new multi-agent environments that have different characteristics from the original DVMT. Expand

On the Complexity of Designing Distributed Protocols

- Computer Science
- Inf. Control.
- 1982

It is shown that deciding whether two distant agents can arrive at compatible decisions without any communication can be done in polynomial time if there are two possible decisions for each agent, but is NP-complete if one agent has three or more alternatives. Expand

Multiagent Planning with Factored MDPs

- Computer Science
- NIPS
- 2001

This work presents a principled and efficient planning algorithm for cooperative multiagent dynamic systems that avoids the exponential blowup in the state and action space and is an efficient alternative to more complicated algorithms even in the single agent case. Expand