Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis

Abstract

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 characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.

References in corpus (4)

• The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
• Learning to Cooperate via Policy Search
• Distributed Planning in Hierarchical Factored MDPs
• General Principles of Learning-Based Multi-Agent Systems

Cited by in corpus (22)

• Optimal and Approximate Q-value Functions for Decentralized POMDPs
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• ACCNet: Actor-Coordinator-Critic Net for "Learning-to-Communicate" with Deep Multi-agent Reinforcement Learning
• Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
• A Multi-UAV System for Exploration and Target Finding in Cluttered and GPS-Denied Environments
• Scaling Up Decentralized MDPs Through Heuristic Search
• Multi-Agent Algorithms for Collective Behavior: A structural and application-focused atlas
• An Action Language for Multi-Agent Domains: Foundations
• Learning Multi-agent Communication under Limited-bandwidth Restriction for Internet Packet Routing
• Communication-Based Decomposition Mechanisms for Decentralized MDPs
• Sharing Rewards in Cooperative Connectivity Games
• Modelling Multi-Agent Epistemic Planning in ASP
• Message-Dropout: An Efficient Training Method for Multi-Agent Deep Reinforcement Learning
• A Coordinated MDP Approach to Multi-Agent Planning for Resource Allocation, with Applications to Healthcare
• Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments
• Loss Bounds for Approximate Influence-Based Abstraction
• Human and Multi-Agent collaboration in a human-MARL teaming framework
• Self-Fulfilling Signal of an Endogenous State in Network Congestion Games
• Design of a Solver for Multi-Agent Epistemic Planning
• Balancing Performance and Human Autonomy with Implicit Guidance Agent
• Comprehensive Multi-Agent Epistemic Planning
• Multiagent Conflict Resolution for a Specification Network of Discrete-Event Coordinating Agents