Hostname: page-component-76fb5796d-r6qrq Total loading time: 0 Render date: 2024-04-25T23:05:23.170Z Has data issue: false hasContentIssue false
  • English
  • Français

Commitments and conventions: The foundation of coordination in multi-agent systems

Published online by Cambridge University Press:  07 July 2009

Nick R. Jennings
Nick R. Jennings
Affiliation:
Department of Electronic Engineering, Queen Mary and Westfield College, University of London, Mile End Road, London EI 4NS, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

Distributed Artificial Intelligence systems, in which multiple agents interact to improve their individual performance and to enhance the systems' overall utility, are becoming an increasingly pervasive means of conceptualising a diverse range of applications. As the discipline matures, researchers are beginning to strive for the underlying theories and principles which guide the central processes of coordination and cooperation. Here agent communities are modelled using a distributed goal search formalism, and it is argued that commitments (pledges to undertake a specific course of action) and conventions (means of monitoring commitments in changing circumstances) are the foundation of coordination in multi-agent systems. An analysis of existing coordination models which use concepts akin to commitments and conventions is undertaken before a new unifying framework is presented. Finally, a number of prominent coordination techniques which do not explicitly involve commitments or conventions are reformulated in these terms to demonstrate their compliance with the central hypothesis of this paper.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 8 , Issue 3 , September 1993 , pp. 223 - 250
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aarnts, RP, Corera, J, Perez, J, Gureghian, D, and Jennings, NR, 1991. “Examples of cooperative situations and their implementation”. Vleermuis Journal of Software Research 3 (4) 74–81.Google Scholar
Agha, G, 1986. ACTORS: A Model of Concurrent Computation in Distributed Systems. MIT Press.CrossRefGoogle Scholar
Allen, JF, 1984. “Toward a general theory of time and action”. Artificial Intelligence 23 123–154.CrossRefGoogle Scholar
Audi, R, 1973. “Intending”. The Journal of Philosophy 70 387–403.CrossRefGoogle Scholar
Becker, HS, 1960. “Notes on the concept of commitment”. American Journal of Sociology 66 (1) 32–40.CrossRefGoogle Scholar
Bond, AH, 1989. “Commitment: Some DAI insights from symbolic interactionist society”. In: Proceedings 9th Workshop on Distributed Artificial Intelligence, USA.Google Scholar
Bond, AH and Gasser, L, eds., 1988. Readings in Distributed Artificial Intelligence. Morgan-Kaufmann.Google Scholar
Bratman, ME, 1984. “Two faces of intention” Philosophical Review 93 375–405.CrossRefGoogle Scholar
Bratman, ME, 1990. “What is intention?” In: Cohen, PR, Morgan, J and Pollack, ME (eds.), Intentions in Communication, pp 15–33, MIT Press.CrossRefGoogle Scholar
Bratman, ME, Israel, DJ and Pollack, ME, 1988. “Plans and resource bounded practical reasoning”. Computational Intelligence 4 349–355.CrossRefGoogle Scholar
Burmeister, B and Sundermeyer, K, 1992. “Cooperative problem solving guided by intentions and perception”. In: Werner, E and Demazeau, Y (eds.), Decentralised A.I. 3. pp 77–92, Elsevier.Google Scholar
Cammarata, S, McArthur, D and Steeb, R, 1983. “Strategies of cooperation in distributed problem solving”. In: Proceedings int. Joint Conf. on Artificial Intelligence. pp 767–770, Karlsruhe, Germany.Google Scholar
Clearwater, SH, Huberman, BA and Hogg, T, 1991. “Cooperative solution of constraint satisfaction problems”. Science 254 1181–1183.CrossRefGoogle ScholarPubMed
Chaib-Draa, B, Moulin, B, Mandiau, R and Millot, P, 1992. “Trends in distributed artificial intelligence”. Artificial Intelligence Review 6 35–66.CrossRefGoogle Scholar
Cohen, PR and Levesque, HJ, 1990. “Intention is choice with commitment”. Artificial Intelligence 42 213–261.CrossRefGoogle Scholar
Cohen, PR and Levesque, HJ, 1991 a. “Teamwork”. Nous 25(4) 487–512. (Also appears as SRI Technical Note 504, Menlo Park, CA.)CrossRefGoogle Scholar
Cohen, PR and Levesque, HJ, 1991 b. “Confirmations and joint action”. In: Proceedings Twelfth Int. Joint Conf. on Artificial Intelligence, Sydney, Australia.Google Scholar
Conte, R, Miceli, M and Castelfranchi, C, 1990. “Limits and levels of cooperation: Disentangling various types of prosocial interaction”. In: Proceedings Modelling an Autonomous Agent in a Multi-Agent World. Saint-Quentin en Yvelines, France.Google Scholar
Corkill, DD, 1979. “Hierarchical planning in a distributed environment”. In: Proceedings Sixth Int. Joint Conf. on Artificial Intelligence, pp 168–175, Cambridge, USA.Google Scholar
Corkill, DD and Lesser, VR, 1983. “The use of meta-level control for coordination in distributed problem solving”. In: Proceedings Int. Joint Conf. on Artificial Intelligence, pp 748–756, Karlsruhe, Germany.Google Scholar
Cox, BJ, 1990. “Planning the software industrial revolution”. IEEE Software 11 25–33.CrossRefGoogle Scholar
Davidson, D, 1980. Essays on Actions and Events Oxford University Press.Google Scholar
Decker, KS, 1987. “Distributed problem solving techniques: A survey”. IEEE Transactions on Systems Man and Cybernetics 17(5) 729–740.CrossRefGoogle Scholar
Dennett, DC, 1987. The Intentional Stance. Bradford Books/MIT Press.Google Scholar
Durfee, EH, 1988. Coordination of Distributed Problem Solvers, Kluwer Academic.CrossRefGoogle Scholar
Durfee, EH, Lesser, VR and Corkill, DD, 1987. “Coherent cooperation among communicating problem solvers”. IEEE Transactions on Computers 36 1275–1291.CrossRefGoogle Scholar
Durfee, EH, Lesser, VR, and Corkill, DD, 1989. “Trends in cooperative distributed problem solving”. IEEE Transactions on Knowledge and Data Engineering 1(1) 63–83.CrossRefGoogle Scholar
Durfee, EH and Montgomery, TA, 1991. “Coordination as distributed search in a hierarchical behaviour space”. IEEE Transactions on Systems Man and Cybernetics 21 1363–1378.CrossRefGoogle Scholar
Fikes, RE, 1982. “A commitment-based framework for describing informal cooperative work”. Cognitive Science 6 331–347.Google Scholar
Galbraith, J, 1973. Designing Complex Organizations. Addison-Wesley.Google Scholar
Gailliers, JR, 1988, “A strategic framework for multi-agent cooperative dialogue”. In: Proceedings European Conf. on Artificial Intelligence, pp 415–420, Munich, Germany.Google Scholar
Gasser, L, 1991. “Social conceptions of knowledge and action: DAI foundations and open system semantics”. Artificial Intelligence 47 107–138.CrossRefGoogle Scholar
Gasser, L, 1992 a. “An overview of DAI”. In: Avouris, NM and Gasser, L, (eds.), Distributed Artificial intelligence: Theory and Praxis, pp 9–30, Kluwer Academic.Google Scholar
Gasser, L, 1992 b. “DAI approaches to coordination”. In: Avouris, NM and Gasser, L (eds.), Distributed Artificial Intelligence: Theory and Praxis, pp 31–51, Kluwer Academic.Google Scholar
Gasser, L and Huhns, MN (eds.), 1989. Distributed Artificial Intelligence Vol II. Pitman Publishing.Google Scholar
Georgeff, M, 1983. “Communication and action in multi-agent planning”. In: Proceedings National Conf. on Artificial Intelligence, pp 125–129. Washington, DC.Google Scholar
Gerson, EM, 1976. “On quality of life”. American Sociological Review 41 793–806.CrossRefGoogle Scholar
Gilbert, M, 1989. On Social Facts. Routledge.Google Scholar
Grosz, BJ and Sidner, CL, 1990. “Plans for discourse”. In: Cohen, PR, Morgan, J and Pollack, ME (eds.), Intentions in communication, pp 417–444. MIT Press.CrossRefGoogle Scholar
Halpern, JY, 1986. “Reasoning about knowledge: an overview”. In: Halpern, JY (ed.), Theoretical Aspects of Reasoning About Knowledge, pp 1–17. Morgan Kaufmann.Google Scholar
Halpern, JY and Moses, YO, 1984. “Knowledge and common knowledge in a distributed environment”. In: Proceedings of the Third ACM Conf. on Principles of Distributed Computing, pp 50–61.CrossRefGoogle Scholar
Harel, D, 1984. “Dynamic logic”. In: Gabbay, D and Guenthner, F (eds.), Handbook of Philosophical Logic Vol II, pp 497–604. Reidel Publishing.CrossRefGoogle Scholar
Hayes-Roth, F, 1980. “Towards a framework for distributed AI”. SIGART Newsletter 51–52.Google Scholar
Hern, LEC, 1988. “On distributed artificial intelligence”. The Knowledge Engineering Review 3(1) 21–57.Google Scholar
Hewitt, CE and Kornfield, WA, 1980. “Message passing semantics”. SIGART Newsletter 48.Google Scholar
Hobbs, JR, 1990. “Artificial intelligence and collective intentionality”. In: Cohen, PR, Morgan, J and Pollack, ME (eds.), Intentions in Communication, pp 445–460. MIT Press.CrossRefGoogle Scholar
Huberman, BA and Hogg, T, 1988. “The behaviour of computational ecologies”. In: Huberman, BA (ed.), The Ecology of Computation, pp 77–115. North Holland.Google Scholar
Huhns, MN (ed.) 1988. Distributed Artificial Intelligence. Pitman.Google Scholar
Huhns, MN, Mukhopadhyay, U, Stephens, L and Bonnell, R, 1988. “DAI for document retrieval”. In: Huhns, MN (ed.), Distributed Artificial Intelligence, pp 249–284. Pitman.Google Scholar
Ishida, T, Yokoo, M and Gasser, L, 1990. “An organisational approach to adaptive production systems”. In: Proceedings 8th National Conf. on Artificial Intelligence, pp 52–58. Boston, USA.Google Scholar
Jennings, NR, 1992. “Towards a cooperation knowledge level for collaborative problem solving”. Proceedings 10th European Conf. on Artificial Intelligence, pp 224–228. Vienna, Austria.Google Scholar
Jennings, NR, 1993. “Specification and Implementation of a Belief-Desire-Joint Intention for Collaborative Problem Solving”. International Journal of Intelligent Cooperative Information Systems.CrossRefGoogle Scholar
Jennings, NR and Mamdani, EH, 1992. “Using joint responsibility to coordinate collaborative problem solving in dynamic environments”. In: Proceedings 10th National Conf. on Artificial Intelligence, pp 269–275. San Jose, USA.Google Scholar
Jennings, NR, Mamdani, EH, Laresgoiti, I, Perez, J and Corera, J, 1992. “GRATE: A general framework for cooperative problem solving”. Journal of Intelligent Systems Engineering 1(2) 102–114.CrossRefGoogle Scholar
Jennings, NR and Wittig, T, 1992. “ARCHON: Theory and practice”. In: Avouris, NM and Gasser, L (eds.), Distributed Artificial Intelligence: Theory and Praxis, pp 179–196. Kluwer Academic.Google Scholar
Kambhampati, S and Hendler, JA, 1992. “A validation structure based theory of plan modification and reuse”. Artificial Intelligence 55 193–258.CrossRefGoogle Scholar
Kinny, DN and Georgeff, MP, 1991. “Commitment and effectiveness of situated agents”. In: Proceedings Int. Joint Conf. on Artificial Intelligence, pp 82–88. Sydney, Australia.Google Scholar
Kinny, D, Ljungberg, M, Rao, A, Sonenberg, E, Tidhar, G and Werner, E, 1992. “Planned team activity”. In: Pre-Proceedings of the 4th European Workshop of Modelling Autonomous Agents in a Multi-Agent World. Rome, Italy.Google Scholar
Lenat, DB, 1975. “BEINGS: Knowledge as interacting experts”. Proc. Int. Joint Conf. on Artificial intelligence, pp 126–133. Tblisi, Russia.Google Scholar
Lenat, DB and Feigenbaum, EA, 1991. “On the thresholds of knowledge”. Artificial Intelligence 47 185–250.CrossRefGoogle Scholar
Lesser, VR, 1991. “A retrospective view of FA/C distributed problem solving”. IEEE Transactions on Systems Man and Cybernetics 21 1347–1363.CrossRefGoogle Scholar
Lesser, VR and Corkill, DD, 1983. “The distributed vehicle monitoring testbed: A tool for investigating distributed problem solving networks”. AI Magazine, 15–33.Google Scholar
Lesser, VR and Corkill, DD, 1987. “Distributed problem solving”. In: Shapiro, SC (ed.), Encyclopedia of Artificial Intelligence, pp 245–251. Wiley.Google Scholar
Levesque, HJ, Cohen, PR and Nunes, JH, 1990. “On acting together”. In: Proceedings 8th National Conf. on Artificial Intelligence, pp 94–99. Boston, USA.Google Scholar
Lochbaum, KE, Grosz, BJ and Sidner, CL, 1990. “Models of plans to support communication”. In: Proceedings 8th National Conf. on Artificial Intelligence, pp 485–490. Boston, USA.Google Scholar
Malone, TW, 1987. “Modelling coordination in organizations and markets”. Management Science 33 1317–1332.CrossRefGoogle Scholar
March, JG and Simon, HA, 1958. Organisations. Wiley.Google Scholar
McClelland, JL and Rumelhart, DE, 1986. Parallel Distributed Processing. MIT Press.Google Scholar
McDermott, J, 1990. “Developing software is like talking to Eskimos about snow”. In: Proceedings 8th National Conf. on Artificial Intelligence, pp 1130–1133. Boston, USA.Google Scholar
Mead, OH, 1934. Mind, Self and Society. University of Chicago Press.Google Scholar
Minsky, M, 1985. The Society of Mind. Simon & Schuster.Google Scholar
Neches, R, Fikes, R, Finin, T, Gruber, T, Patil, R, Senator, T and Swartout, T, 1991. “Enabling technology for knowledge sharing”. AI Magazine 36–56.Google Scholar
Pan, JYC and Tenenbaum, JM, 1991. “An intelligent agent framework for enterprise integration”. IEEE Transactions on Systems Man and Cybernetics 21 1409–1419.CrossRefGoogle Scholar
Papazoglou, MP, Laufman, SC and Sellis, TK, 1992. “An organisation framework for cooperating intelligent information systems”. Journal of Intelligent Cooperative Information Systems 1 169–202.CrossRefGoogle Scholar
Pollack, ME, 1990. “Plans as complex mental attitudes”. In: Cohen, PR, Morgan, J and Pollack, ME (eds.). Intentions in Communication, pp 77–105. MIT Press.CrossRefGoogle Scholar
Pollack, ME, 1992. “The uses of plans”. Artificial Intelligence 57 43–68.CrossRefGoogle Scholar
Power, R, 1984. “Mutual intention”. Journal for the Theory of Social Behaviour 14 85–105.CrossRefGoogle Scholar
Rao, AS and Georgeff, MP, 1991. “Modelling rational agents within a BDI architecture”. In: Fikes, R and Sandewall, E (eds.), International Conf. on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann.Google Scholar
Rao, AS, Georgeff, MP and Sonenberg, EA, 1992. “Social plans: A preliminary report”. In: Werner, E and Demazeau, Y (eds.), DecentralisedA13, pp 57–76. North Holland.Google Scholar
Rosenschein, JS and Genesereth, MR, 1985. “Deals among rational agents”. In: Proceedings 9th Int. Joint Conf. on Artificial Intelligence, pp 91–99. Los Angeles, USA.Google Scholar
Sacerdoti, ED, 1977. A Structure for Plans and Behaviour. Elsevier.Google Scholar
Searle, JR, 1983. Intentionality: An essay in the Philosophy of Mind. Cambridge University Press.CrossRefGoogle Scholar
Searle, JR, 1990. “Collective intentions and actions”. In: Cohen, PR, Morgan, J and Pollack, ME (eds.), Intentions in Communication, pp 401–416. MIT Press.CrossRefGoogle Scholar
Shina, SG, 1991. Concurrent Engineering and DFMfor Electronic Design. Van Nostrand Reinhold.Google Scholar
Shoham, Y, 1993. “Agent-oriented programming”. Artificial Intelligence 60 51–92.CrossRefGoogle Scholar
Shoham, Y and Tennenholtz, M, 1992. “On the synthesis of useful social laws for artificial agent societies”. In: Proceedings 10th National Conf. on Artificial Intelligence, pp 276–28?. San Jose, USA.Google Scholar
Simon, HA, 1957. Models of Man. Wiley.CrossRefGoogle Scholar
Singh, MP, 1990. “Group intentions”. In: Proceedings 10th International Workshop on Distributed Artificial Intelligence. MCC Technical Report ACT-AI-355−90.Google Scholar
Singh, MP, 1992. “A critical examination of the Cohen-Levesque theory of intentions”. In: Proceedings 10th European Conf. on Artificial Intelligence, pp 364–368. Vienna, Austria.Google Scholar
Smith, RG and Davis, R, 1981. “Frameworks for cooperation in distributed problem solving”. IEEE Transactions on Systems Man and Cybernetics 11 61–70.CrossRefGoogle Scholar
Stefik, M, 1986. “The next knowledge medium”. Al Magazine 7 (1) 34–46.Google Scholar
Tuomela, R and Miller, K, 1988. “We intentions”. Philosophical Studies 53 367–389.CrossRefGoogle Scholar
Varga, LZ, Jennings, NR and Cockburn, O, 1994. “Integrating intelligent systems into a cooperating community for electricity distribution management. Expert Systems With Applications 7CrossRefGoogle Scholar
Werner, E, 1989. “Cooperating agents: A unified theory of communication and social structure”. In: Gasser, L and Huhns, MN (eds.), Distributed Artificial Intelligence Vol II, pp 3–36. Pitman.CrossRefGoogle Scholar
Wesson, RHayes-Roth, F, Burge, JW, Stasz, C and Sunshine, CA, 1981. “Network structures for distributed situation assessment”. IEEE Transactions on Systems Man and Cybernetics 11 5–23CrossRefGoogle Scholar