# Optimizing information exchange in cooperative multi-agent systems

@inproceedings{Goldman2003OptimizingIE, title={Optimizing information exchange in cooperative multi-agent systems}, author={Claudia V. Goldman and Shlomo Zilberstein}, booktitle={AAMAS '03}, year={2003} }

Decentralized control of a cooperative multi-agent system is the problem faced by multiple decision-makers that share a common set of objectives. The decision-makers may be robots placed at separate geographical locations or computational processes distributed in an information space. It may be impossible or undesirable for these decision-makers to share all their knowledge all the time. Furthermore, exchanging information may incur a cost associated with the required bandwidth or with the risk… Expand

#### 264 Citations

Computing effective communication policies in multiagent systems

- Computer Science
- AAMAS '07
- 2007

This work presents a decision theoretic approach for computing optimal communication policies in stochastic environments which uses a branching future representation and evaluates only those decisions that an agent is likely to encounter. Expand

The Information Flow Problem in multi-agent systems

- Computer Science
- Eng. Appl. Artif. Intell.
- 2018

This paper presents a formalization of this problem, which has been coined as the Information Flow Problem, and also presents a complete case study with an empirical evaluation involving four well-known communication strategies and eight typical multi-agent systems. Expand

Balancing Coordination and Synchronization Cost in Cooperative Situated Multi-Agent Systems with Imperfect Communication

- Computer Science
- ECAI
- 2004

A new Markov team decision model is presented, based on a off-line centralized team plan, that provides a quantitative solution to the problem of balancing coordination and synchronization cost in cooperative domains, but its exact solution is computationally infeasible. 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

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

Reward shaping for valuing communications during multi-agent coordination

- Computer Science
- AAMAS
- 2009

This research presents a novel model of rational communication, that uses reward shaping to value communications, and employs this valuation in decentralised POMDP policy generation and an empirical evaluation of the benefits is presented in two domains. Expand

Communication based on Interactive Dynamic Influence Diagrams in cooperative multi-agent systems

- Computer Science
- 2013 8th International Conference on Computer Science & Education
- 2013

A heuristic algorithm is presented to compute communication policies by evaluating the trade-off between the cost of communication and the value of the information received, and experimental results show the impact of communication policies have on the overall agent policies in the context of Multiagent tiger problem. Expand

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

Execution-time communication decisions for coordination of multi-agent teams

- Computer Science
- 2007

Decentralized Partially Observable Markov Decision Processes is employed, an extension of single-agent POMDPs that can be used to model and coordinate teams of agents and provides algorithms that address the questions of when and what agents should communicate. Expand

#### References

SHOWING 1-10 OF 18 REFERENCES

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

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

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

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

Emergent Coordination through the Use of Cooperative State-Changing Rules

- Computer Science
- AAAI
- 1994

It is shown that a relatively simple, easily calculated rule can sometimes improve global system performance in the Tileworld, and is presented a way of characterizing domains as multi-agent deterministic finite automata, and characterizing cooperative rules as transformations of these automata. Expand

The Dynamics of Reinforcement Learning in Cooperative Multiagent Systems

- Computer Science
- AAAI/IAAI
- 1998

This work distinguishes reinforcement learners that are unaware of (or ignore) the presence of other agents from those that explicitly attempt to learn the value of joint actions and the strategies of their counterparts, and proposes alternative optimistic exploration strategies that increase the likelihood of convergence to an optimal equilibrium. Expand

Mutual online concept learning for multiple agents

- Computer Science
- AAMAS '02
- 2002

A specific MOCL algorithm is presented, called the mutual perceptron convergence algorithm, which can converge within a finite number of mistakes under some conditions and shows that the possibility of convergence depends on the quality of the instances they produce. Expand

Markov Games as a Framework for Multi-Agent Reinforcement Learning

- Computer Science
- ICML
- 1994

A Q-learning-like algorithm for finding optimal policies and its application to a simple two-player game in which the optimal policy is probabilistic is demonstrated. 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

Learning to Cooperate via Policy Search

- Computer Science, Mathematics
- UAI
- 2000

This paper provides a gradient-based distributed policy-search method for cooperative games and compares the notion of local optimum to that of Nash equilibrium, and demonstrates the effectiveness of this method experimentally in a small, partially observable simulated soccer domain. Expand