Communication decisions in multi-agent cooperation: model and experiments

ABSTRACT

In multi-agent cooperation, agents share a common goal, which is evaluated through a global utility function. However, an agent typically cannot observe the global state of an uncertain environment, and therefore they must communicate with each other in order to share the information needed for deciding which actions to take. We argue that, when communication incurs a cost (due to resource consumption, for example), whether to communicate or not also becomes a decision to make. Hence, communication decision becomes part of the overall agent decision problem. In order to explicitly address this problem, we present a multi-agent extension to Markov decision processes in which communication can be modeled as an explicit action that incurs a cost. This framework provides a foundation for a quantified study of agent coordination policies and provides both motivation and insight to the design of heuristic approaches. An example problem is studied under this framework. From this example we can see the impact communication policies have on the overall agent policies, and what implications we can find toward the design of agent coordination policies.

REFERENCES

• 1: M. Aicardi, F. Davoli, and R. Minciardi. Decentralized optimal control of markov chains with a common past information set. IEEE Transactions on Automatic Control, AC-32:1028-1031, 1987.
• 2: Daniel S. Bernstein , Shlomo Zilberstein , Neil Immerman, The Complexity of Decentralized Control of Markov Decision Processes, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.32-37, June 30-July 03, 2000
• 3: Craig Boutilier, Sequential Optimality and Coordination in Multiagent Systems, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.478-485, July 31-August 06, 1999
• 4: Piotr J. Gmytrasiewicz , Edmund H. Durfee, Rational Coordination in Multi-Agent Environments, Autonomous Agents and Multi-Agent Systems, v.3 n.4, p.319-350, December 2000 [doi>10.1023/A:1010028119149]
• 5: Eric A. Hansen, Cost-effective sensing during plan execution, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.1029-1035, October 1994, Seattle, Washington, United States
• 6: E. Hansen, A. Barto, and S. Zilberstein. Reinforcement learning for mixed open-loop and closed-loop control. In Proceedings of the Ninth Neural Information Processing Systems Conference, December 1996.
• 7: E. A. Hansen and S. Zilberstein. Monitoring the progress of anytime problem-solving. In Proceedings of the 13th National Conference onArtificial Intelligence, pages 1229-1234, 1996.
• 8: Y. C. Ho and T. S. Chang. Another look at the nonclassical information problem. IEEE Transactions on Automatic Control, AC-25:537-540, 1980.
• 9: K. Hsu and S. I. Marcus. Decentralized control of finite state markov processes. IEEE Transactions on Automatic Control, AC-27:426-431, 1982.
• 10: M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proc. 11th International Conf. on Machine Learning, pages 157-163, 1994.
• 11: G. M. P. O'Hare , N. R. Jennings, Foundations of distributed artificial intelligence, John Wiley & Sons, Inc., New York, NY, 1996
• 12: Christos Papadimitriou , John N. Tsitsiklis, The complexity of Markov decision processes, Mathematics of Operations Research, v.12 n.3, p.441-450, August 1, 1987 [doi>10.1287/moor.12.3.441]
• 13: N. R. Sandell, P. Varaiya, M. Athans, and M. Safonov. Survey of decentralized control methods for large scale systems. IEEE Transactions on Automatic Control, AC-23:108-128, 1978.
• 14: J. N. Tsitsiklis and M. Athans. On the complexity of decentralized decision making and detection problems. IEEE Transactions on Automatic Control, AC-30:440-446, 1985.
• 15: H. S. Witsenhausen. A counterexample in stochastic optimum control. SIAM Journal on Control, 6(1):138-147, 1968.
• 16: T. Yoshikawa. Decomposition of dynamic team decision problems. IEEE Transactions on Automatic Control, AC-23:443-445, 1978.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory

Keywords:
MDP, coordinating multiple agents, multi-agent communication/collaboration