Skip to main content
SpringerLink
Log in

Learning Communication Strategies in Multiagent Systems

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

In this paper we describe a dynamic, adaptive communication strategy for multiagent systems. We discuss the behavioral parameters of each agent that need to be computed, and provide a quantitative solution to the problem of controlling these parameters. We also describe the testbed we built and the experiments we performed to evaluate the effectiveness of our methodology. Several experiments using varying populations and varying organizations of agents were performed and are reported. A number of performance measurements were collected as each experiment was performed so the effectiveness of the adaptive communications strategy could be measured quantitatively.

The adaptive communications strategy proved effective for fully connected networks of agents. The performance of these experiments improved for larger populations of agents and even approached optimal performance levels. Experiments with non-fully connected networks showed that the adaptive communications strategy is extremely effective, but does not approach optimality. Other experiments investigated the ability of the adaptive communications strategy to compensate for “distracting” agents, for systems where agents are required to assume the role of information routers, and for systems that must decide between routing paths based on cost information.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. W.A. Kornfeld, “ETHER: A parallel problem solving system,” in Proc. of IJCAI-79, 1979, pp. 490- 492.

  2. Alan H. Bond and L. Gasser (Eds.), Readings in Distributed Artificial Intelligence, Morgan Kaufmann: San Mateo, CA, pp. 3- 35, 1988.

    Google Scholar 

  3. Ronald Fagin and Moshe Y. Vardi, “Knowledge and implicit knowledge in a distributed environment: Preliminary report,” in Proceedings of the Conference on the Theoretical Aspects of Reasoning about Knowledge, edited by Joseph Y. Halpern, 1986, pp. 187- 206.

  4. Jeffery S. Rosenschein, “Synchronization of multiagent plans,” in Proceedings of the National Conference of the American Association for Artificial Intelligence, Pittsburgh, PA, 1982, pp. 115- 119.

  5. Reid G. Smith, “The contract net protocol: High level communication and control in a distributed problem solver,” IEEE Transactions on Computers, vol. C-29, no.12, pp. 1104- 1113, 1980.

    Google Scholar 

  6. Reid G. Smith and Randal Davis, “Frameworks for cooperation in distributed problem solving,” IEEE Transactions on Systems, Man and Cybernetics, vol. SMC-11, no.1, pp. 61- 70, 1981.

    Google Scholar 

  7. Edmund H. Durfee, V.R. Lesser, and Daniel D. Corkill, “Coherent cooperation among communicating problem solvers,” IEEE Transactions on Computers, vol. C-36, no.11, pp. 1275- 1291, 1987.

    Google Scholar 

  8. Edmund H. Durfee and V.R. Lesser, “Incremental planning to control a time-constrained, blackboard-based problem solver,” IEEE Transactions on Aerospace and Electronic Systems, vol. 24, no.5, pp. 647- 662, 1988.

    Google Scholar 

  9. Michael Georgeff, “Communication and interaction in multi-agent planning,” in Proc. of the 8th International Joint Conference on Artificial Intelligence, Karlsruhe, Germany, 1983, pp. 125- 129.

  10. V.R. Lesser and Lee D. Erman, “Distributed interpretation: A model and experiment,” IEEE Transactions on Computers, vol. C-29, no.12, pp. 1144- 1163, 1980.

    Google Scholar 

  11. V.R. Lesser and Daniel D. Corkill, “Functionally accurate, cooperative distributed systems,” IEEE Transactions on Systems, Man and Cybernetics, vol. SMC-11, no.1, pp. 81- 96, 1981.

    Google Scholar 

  12. Edmund H. Durfee and V.R. Lesser, “Using partial global plans to coordinate distributed problem solvers,” in Proc. of IJCAI-87, Milan, Italy, 1987, pp. 875- 883.

  13. Edmund H. Durfee and V.R. Lesser, “Negotiating tasking decomposition and allocation using partial global planning,” in Distributed Artificial Intelligence, edited by L. Gasser and M. Huhns, Morgan Kaufmann, pp. 229- 243, 1989.

  14. Edmund H. Durfee and V.R. Lesser, “Partial global planning: A coordination framework for distributed hypothesis formation,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 21, no.5, pp. 1167- 1183, 1991.

    Google Scholar 

  15. K.S. Decker, “Distributed artificial intelligence testbeds,” in Foundations of Distributed Artificial Intelligence, edited by G. O'Hare and N. Jennings, Wiley Inter-Science, 1994.

  16. S.E. Conry, R.A. Meyer, and R.P. Pope, “Mechanisms for assessing nonlocal impact of local decisions in distributed planning,” in Distributed Artificial Intelligence, edited by L. Gasser and M. Huhns, Morgan Kaufmann, pp. 245- 257, 1989.

  17. Robert J. Ensor and John D. Gabbe, “Transaction blackboards,” in Proc. of IJCAI-85, 1985, pp. 340- 344.

  18. Lee D. Erman, Frederick A. Hayes-Roth, V.R. Lesser, and D. Raj Reddy, “The hearsay-II speech-understanding system: Integrating knowledge to resolve uncertainty,” Computing Surveys, vol. 12, no.2, pp. 213- 253, 1980.

    Google Scholar 

  19. Barbara Hayes-Roth, “A blackboard architecture for control,” Artificial Intelligence, vol. 26, pp. 251- 321, 1985.

    Google Scholar 

  20. Y. Shoham and M. Tennenholtz, “On the synthesis of useful social laws for artificial agent societies (preliminary report),” in Proc. of AAAI-92, 1992, pp. 704- 709.

  21. M. Fenster, S. Kraus, and J.S. Rosenschein, “Coordination without communication: Experimental validation of focal point techniques,” in Proc. First Int. Conf. on Multiagent Systems, AAAI Press, 1995, pp. 102- 108.

  22. Y. Shoham and M. Tennenholtz, “On social laws for artificial agent societies: Off-line design,” Artificial Intelligence, vol. 73, no.1- 2, pp. 231- 252, 1995.

    Google Scholar 

  23. Mark S. Fox, “An organizational view of distributed systems,” IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-11, no.1, pp. 70- 80, 1981.

    Google Scholar 

  24. R. Wesson, Fredrick Hayes-Roth, John W. Burge, Cathleen Stasz, and Carl A. Sunshine, “Network structures for distributed situation assessment,” IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-11, no.1, pp. 5- 23, 1981.

    Google Scholar 

  25. Thomas W. Malone, “Modeling coordination in organizations and markets,” Management Science, vol. 33, no.10, pp. 1317- 1332, 1987.

    Google Scholar 

  26. Randal Steeb, Stephanie Cammarata, Fredrick A. Hayes-Roth, Perry W. Thorndyke, and Robert B. Wesson, “Architectures for distributed air-traffic control, “Technical Report” R-2728-ARPA, pp. 9- 30, 1981.

  27. S. Cammarata, D. McArthur, and R. Steeb, “Strategies of Cooperation in Distributed Problem Solving,” in Proc. of IJCAI-83, 1983, pp. 767- 770.

  28. Michael J. Shaw and Andrew B. Whinston, “Learning and adaptation in distributed artificial intelligence systems,” in Distributed Artificial Intelligence, edited by L. Gasser and M.N. Huhns, Pitman Publishing/Morgan Kaufmann Publishers, vol. II, pp. 413- 429, 1990.

  29. P. Brazdil, M. Games, S. Sian, L. Torgo, and W. van de Velde, “Learning in distributed systems and multiagent environments,” in Proceedings of the European Working Session on Learning, Porto, Portugal, 1991, pp. 413- 423.

  30. P. Brazdil and S. Muggleton, “Learning to relate terms in a multiple agent environment,” in Proceedings of the European Working Session on Learning, Porto, Portugal, 1991, pp. 424- 439.

  31. S. Gallant, “Connectionist expert systems,” Communications of ACM, vol. 31, pp. 152- 168, 1988.

    Google Scholar 

  32. Barbara Hayes-Roth, “An architecture for adaptive intelligent systems,” Artificial Intelligence, vol. 72, nos.1- 2, pp. 329- 365, 1995.

    Google Scholar 

  33. K.S. Decker and V.R. Lesser, “Analyzing the need for meta-level communication,” in Proc. of IJCAI-94, 1994.

  34. Daniel E. Neiman, David W. Hildum, and V.R. Lesser, “Exploiting meta-level information in a distributed scheduling system,” in Proc. of IJCAI-94, 1994.

  35. Elise H. Turner, “Exploiting problem solving to select information to include dialogues between cooperating agents,” in Proc. of Sixteenth Annual Conference of the Cognitive Science Society, 1994, pp. 882- 886.

  36. K.S. Decker and V.R. Lesser, “Designing a family of coordination algorithms,” in Proc. First Int. Conf. on Multiagent Systems, AAAI Press, 1995, pp. 73- 80.

  37. M. Prasad, V. Nagendra, V.R. Lesser, and S. Lander, “Learning organizational roles in a heterogeneous multi-agent system,” in AAAI Symposium on Adaptation, Coevolution and Learning in Multiagent Systems, AAAI Technical Report SS-96-01, pp. 73- 77, 1996.

  38. R. Whitehair and V.R. Lesser, “A framework for the analysis of sophisticated control in interpretation systems, “Computer Science Technical Report” 93-53, University of Massachusetts, 1993.

  39. T. Ohkno, K. Hiraki, and Y. Anzai, “Reducing communication load on contract net by case-based reasoning—Extension with directed contract and forgetting,” in Proc. Second Int. Conf. on Multiagent Systems, AAAI Press, 1996, pp. 244- 251.

  40. R. Foisel, V. Chevrier, and J.-P. Haton, “Improving global coherence by adaptive organization in a multi-agent system,” in Proc. Second Int. Conf. on Multiagent Systems, AAAI Press, 1996, p. 435.

  41. D. Carmel and S. Markovitch, “Learning models of intelligent agents,” in Proc. of AAAI-96, 1996, pp. 62- 67.

  42. H.H. Bui, D. Kieronska, and S. Venkatesh, “Learning other agents' preferences in multiagent negotiation,” in Proc. of AAAI-96, 1996, pp. 114- 119.

  43. Walter Jacobs, “A structure for systems that plan abstractly,” in Proceedings of the AFIPS Conference, Spring Joint Computer Conference, vol. 38, 1971, pp. 357- 364.

    Google Scholar 

  44. C. Tsatsoulis and G. Yee, “Learning reliability models of other agents in a multiagent system,” AAAI Workshop on Intelligent Adaptive Agents, AAAI Technical Report, 1996.

  45. C.L. Forgy “RETE: A fast algorithm for the many pattern/many pattern object matching problem,” Artificial Intelligence, vol. 19, pp. 17- 37, 1982.

    Google Scholar 

  46. Michael D. Kinney, “A multi-agent communications tool using remote procedure calls,” CECASE-TR-8640-12, Center for Excellence in Computer Aided Systems Engineering, The University of Kansas, 1992.

  47. NASA COSMIC, CLIPS Advanced Programming Guide, Version 4.1, 1989.

  48. Michael D. Kinney, “A testbed for an adaptive communications strategy for multi-agent systems,” CECASE-TR-8640-27, Center for Excellence in Computer Aided Systems Engineering, The University of Kansas, 1992.

  49. Y. Shoham, “Agent-oriented programming,” Artificial Intelligence, vol. 60, pp. 51- 92, 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering and Computer Science, The University of Kansas, Lawrence, KS, 66045

    Michael Kinney & Costas Tsatsoulis

Authors
  1. Michael Kinney
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Costas Tsatsoulis
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kinney, M., Tsatsoulis, C. Learning Communication Strategies in Multiagent Systems. Applied Intelligence 9, 71–91 (1998). https://doi.org/10.1023/A:1008251315338

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008251315338

Search

Navigation