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

Abstract

Despite the significant progress in multiagent teamwork, existing research does not address the optimality of its prescriptions nor the complexity of the teamwork problem. Without a characterization of the optimality-complexity tradeoffs, it is impossible to determine whether the assumptions and approximations made by a particular theory gain enough efficiency to justify the losses in overall performance. To provide a tool for use by multiagent researchers in evaluating this tradeoff, we present a unified framework, the COMmunicative Multiagent Team Decision Problem (COM-MTDP). The COM-MTDP model combines and extends existing multiagent theories, such as decentralized partially observable Markov decision processes and economic team theory. In addition to their generality of representation, COM-MTDPs also support the analysis of both the optimality of team performance and the computational complexity of the agents' decision problem. In analyzing complexity, we present a breakdown of the computational complexity of constructing optimal teams under various classes of problem domains, along the dimensions of observability and communication cost. In analyzing optimality, we exploit the COM-MTDP's ability to encode existing teamwork theories and models to encode two instantiations of joint intentions theory taken from the literature. Furthermore, the COM-MTDP model provides a basis for the development of novel team coordination algorithms. We derive a domain-independent criterion for optimal communication and provide a comparative analysis of the two joint intentions instantiations with respect to this optimal policy. We have implemented a reusable, domain-independent software package based on COM-MTDPs to analyze teamwork coordination strategies, and we demonstrate its use by encoding and evaluating the two joint intentions strategies within an example domain.

References in corpus (3)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• The Complexity of Decentralized Control of Markov Decision Processes
• Learning to Cooperate via Policy Search

Cited by in corpus (28)

• Optimal and Approximate Q-value Functions for Decentralized POMDPs
• Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis
• $QD$-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations
• MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs
• Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs
• CM3: Cooperative Multi-goal Multi-stage Multi-agent Reinforcement Learning
• Multi-Agent Reinforcement Learning Based on Representational Communication for Large-Scale Traffic Signal Control
• Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
• An Investigation into Mathematical Programming for Finite Horizon Decentralized POMDPs
• Resilient robot teams: a review integrating decentralised control, change-detection, and learning
• Task-Oriented Data Compression for Multi-Agent Communications Over Bit-Budgeted Channels
• Learning Multi-agent Communication under Limited-bandwidth Restriction for Internet Packet Routing
• Communication-Based Decomposition Mechanisms for Decentralized MDPs
• An ASP-Based Architecture for Autonomous UAVs in Dynamic Environments: Progress Report
• Scalable Anytime Planning for Multi-Agent MDPs
• Towards an ASP-Based Architecture for Autonomous UAVs in Dynamic Environments (Extended Abstract)
• Scalable Planning and Learning for Multiagent POMDPs: Extended Version
• Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games
• Team Behavior in Interactive Dynamic Influence Diagrams with Applications to Ad Hoc Teams
• Multi-Agent Decentralized Belief Propagation on Graphs
• Interactive AI with a Theory of Mind
• Multi-Robot Active Information Gathering with Periodic Communication
• Optimal Decision-Making in Mixed-Agent Partially Observable Stochastic Environments via Reinforcement Learning
• The Power of Communication in a Distributed Multi-Agent System
• Emergence of Roles in Robotic Teams with Model Sharing and Limited Communication
• Experiments with Tractable Feedback in Robotic Planning under Uncertainty: Insights over a wide range of noise regimes (Extended Report)
• Decoupling stochastic optimal control problems for efficient solution: insights from experiments across a wide range of noise regimes
• A Framework for Rate Efficient Control of Distributed Discrete Systems