Ping Xuan
Shlomo Zilberstein
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.
- 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.Google Scholar
Cross Ref
- 2.D. S. Bernstein, S. Zilberstein, and N. Immerman. The complexity of decentralized control of markov decision processes. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI-2000), 2000. Google ScholarDigital Library
- 3.C. Boutilier. Sequential optimality and coordination in multiagent systems. In Proceedings of the Sixteenth International Joint Conferences on Artificial Intelligence (IJCAI-99), July 1999. Google ScholarDigital Library
- 4.P. J. Gmytrasiewicz and E. H. Durfee. Rational interaction in multiagent environments: Coordination. Autonomous Agents and Multi-Agent Systems Journal, 1999. Google ScholarDigital Library
- 5.E. Hansen. Cost-effective sensing during plan execution. In Proceedings of the Twelth National Conference onArtificial Intelligence, 1994. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 9.K. Hsu and S. I. Marcus. Decentralized control of finite state markov processes. IEEE Transactions on Automatic Control, AC-27:426-431, 1982.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 11.G. O'Hare and N. Jennings, editors. Foundations of Distributed Artificial Intelligence. John Wiley, 1996. Google ScholarDigital Library
- 12.C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of markov decision processes. Mathematics of Operations Research, 12(3):441-450, 1987. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 15.H. S. Witsenhausen. A counterexample in stochastic optimum control. SIAM Journal on Control, 6(1):138-147, 1968.Google ScholarCross Ref
- 16.T. Yoshikawa. Decomposition of dynamic team decision problems. IEEE Transactions on Automatic Control, AC-23:443-445, 1978.Google Scholar
Index Terms
- Communication decisions in multi-agent cooperation: model and experiments
Recommendations
Congregation Formation in Multiagent Systems
We present congregating both as a metaphor for describing and modeling multiagent systems (MAS) and as a means for reducing coordination costs in large-scale MAS. When agents must search for other agents to interact with, congregations provide a way for ...
How communication can improve the performance of multi-agent systems
AGENTS '01: Proceedings of the fifth international conference on Autonomous agentsWe analyze a general model of multi-agent communication in which all agents learn to communicate simultaneously to a message board. We show that the communicating multi-agent system is equivalent to a Mealy finite state machine whose states are ...
Comments