Specifying norm-governed computational societies

ABSTRACT

Electronic markets, dispute resolution and negotiation protocols are three types of application domains that can be viewed as open agent societies. Key characteristics of such societies are agent heterogeneity, conflicting individual goals and unpredictable behavior. Members of such societies may fail to, or even choose not to, conform to the norms governing their interactions. It has been argued that systems of this type should have a formal, declarative, verifiable, and meaningful semantics. We present a theoretical and computational framework being developed for the executable specification of open agent societies. We adopt an external perspective and view societies as instances of normative systems. In this article, we demonstrate how the framework can be applied to specifying and executing a contract-net protocol. The specification is formalized in two action languages, the C+ language and the Event Calculus, and executed using respective software implementations, the Causal Calculator and the Society Visualizer. We evaluate our executable specification in the light of the presented case study, discussing the strengths and weaknesses of the employed action languages for the specification of open agent societies.

REFERENCES

• 1: Varol Akman , Selim T. Erdoǧan , Joohyung Lee , Vladimir Lifschitz , Hudson Turner, Representing the zoo world and the traffic world in the language of the causal calculator, Artificial Intelligence, v.153 n.1-2, p.105-140, March 2004 [doi>10.1016/j.artint.2003.08.002]
• 2: Artikis, A. 2003. Executable specification of open norm-governed computational systems. Ph.D. thesis, University of London. http://www.iit.demokritos.gr/~a.artikis/publications/artikis-phd.pdf (also available from the author).
• 3: Alexander Artikis , Jeremy Pitt , Marek Sergot, Animated specifications of computational societies, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545070]
• 4: Artikis, A., Sergot, M., and Pitt, J. 2003. Specifying electronic societies with the Causal Calculator. In Proceedings of Workshop on Agent-Oriented Software Engineering III (AOSE), F. Giunchiglia, J. Odell, and G. Weiss, Eds. Lecture Notes in Computer Science, vol. 2585, Springer-Verlag, Brlin Germany. 1--15.
• 5: Alexander Artikis , Marek Sergot , Jeremy Pitt, An executable specification of a formal argumentation protocol, Artificial Intelligence, v.171 n.10-15, p.776-804, July, 2007 [doi>10.1016/j.artint.2007.04.008]
• 6: Bing, J. 1998. Managing copyright in a digital environment. In The Impact of Electronic Publishing on the Academic Community, I. Butterworth, Ed. Portland Press, 52--62.
• 7: J. Bradshaw , A. Uszok , R. Jeffers , N. Suri , P. Hayes , M. Burstein , A. Acquisti , B. Benyo , M. Breedy , M. Carvalho , D. Diller , M. Johnson , S. Kulkarni , J. Lott , M. Sierhuis , R. Van Hoof, Representation and reasoning for DAML-based policy and domain services in KAoS and nomads, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860709]
• 8: Brewka, G. 2001. Dynamic argument systems: A formal model of argumentation processes based on situation calculus. J. Logic Comput. 11, 2, 257--282.
• 9: Kathleen M. Carley , Les Gasser, Computational organization theory, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 10: Chittaro, L. and Montanari, A. 1996. Efficient temporal reasoning in the cached event calculus. Comput. Intell. 12, 3, 359--382.
• 11: Alessandro Cimatti , Edmund M. Clarke , Enrico Giunchiglia , Fausto Giunchiglia , Marco Pistore , Marco Roveri , Roberto Sebastiani , Armando Tacchella, NuSMV 2: An OpenSource Tool for Symbolic Model Checking, Proceedings of the 14th International Conference on Computer Aided Verification, p.359-364, July 27-31, 2002
• 12: Clark, K. 1978. Negation as failure. In Logic and Databases, H. Gallaire and J. Minker, Eds. Plenum Press, New York, 293--322.
• 13: Clarke, E. M., Grumberg, O., and Peled, D. A. 2000. Model Checking. MIT Press, Cambridge, MA.
• 14: Derek Coleman , Patrick Arnold , Stephanie Bodoff , Chris Dollin , Helena Gilchrist , Fiona Hayes , Paul Jeremaes, Object-oriented development: the fusion method, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 15: Colombetti, M. 2000. A commitment-based approach to agent speech acts and conversations. In Proceedings of Workshop on Agent Languages and Communication Policies. 21--29.
• 16: Craven, R. 2006. Execution mechanisms for the action language C+. Ph.D. dissertation, University of London, London, UK.
• 17: Craven, R. and Sergot, M. 2005. Distant causation in C+. Studia Logica 79, 1, 73--96.
• 18: Davis, R. and Smith, R. 1983. Negotiation as a metaphor for distributed problem solving. AI 20, 63--109.
• 19: Marc Esteva , David de la Cruz , Carles Sierra, ISLANDER: an electronic institutions editor, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545069]
• 20: Marc Esteva , Julian A. Padget , Carles Sierra, Formalizing a Language for Institutions and Norms, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.348-366, August 01-03, 2001
• 21: Institutionalizing Open Multi-Agent Systems, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.381, July 10-12, 2000
• 22: Marc Esteva , Juan A. Rodríguez-Aguilar , Carles Sierra , Pere Garcia , Josep Lluís Arcos, On the Formal Specifications of Electronic Institutions, Agent Mediated Electronic Commerce, The European AgentLink Perspective., p.126-147, January 2001
• 23: Farrell, A., Sergot, M., Sallé, M., and Bartolini, C. 2005. Using the event calculus for tracking the normative state of contracts. Int. J. Coop. Informa. Syst. 4, 2--3, 99--129.
• 24: J. Ferber , O. Gutknecht, A Meta-Model for the Analysis and Design of Organizations in Multi-Agent Systems, Proceedings of the 3rd International Conference on Multi Agent Systems, p.128, July 03-07, 1998
• 25: Jacques Ferber , Olivier Gutknecht, Operational Semantics of Multi-agent Organizations, 6th International Workshop on Intelligent Agents VI, Agent Theories, Architectures, and Languages (ATAL),, p.205-217, July 15-17, 1999
• 26: David Fitoussi , Moshe Tennenholtz, Choosing social laws for multi-agent systems: minimality and simplicity, Artificial Intelligence, v.119 n.1-2, p.61-101, May 2000 [doi>10.1016/S0004-3702(00)00006-0]
• 27: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 28: Mark S. Fox , Mihai Barbuceanu , Michael Gruninger , Jinxin Lin, An organizational ontology for enterprise modeling, Simulating organizations: computational models of institutions and groups, MIT Press, Cambridge, MA, 1998
• 29: Gelati, J., Governatori, G., Rotolo, A., and Sartor, G. 2002a. Declarative power, representation, and mandate. A formal analysis. In Proceedings of Conference on Legal Knowledge and Information Systems (JURIX).
• 30: Gelati, J., Rotolo, A., and Sartor, G. 2002b. Normative autonomy and normative co-ordination: declarative power, representation, and mandate. In Proceedings of Workshop on the Law of Electronic Agents (LEA). 133--149.
• 31: Michael Gelfond, Representing Knowledge in A-Prolog, Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II, p.413-451, January 2002
• 32: Enrico Giunchiglia , Joohyung Lee , Vladimir Lifschitz , Norman McCain , Hudson Turner, Nonmonotonic causal theories, Artificial Intelligence, v.153 n.1-2, p.49-104, March 2004 [doi>10.1016/j.artint.2002.12.001]
• 33: Giunchiglia, E., Lee, J., Lifschitz, V., and Turner, H. 2001. Causal laws and multi-valued fluents. In Proceedings of Workshop on Nonmonotonic Reasoning, Action and Change (NRAC).
• 34: Governatori, G., Gelati, J., Rotolo, A., and Sartor, G. 2002. Actions, institutions, powers: Preliminary notes. In Proceedings of Workshop on Regulated Agent-Based Social Systems: Theories and Applications (RASTA). 69--79.
• 35: Martin Hardwick , Richard Bolton, The industrial virtual enterprise, Communications of the ACM, v.40 n.9, p.59-60, Sept. 1997 [doi>10.1145/260750.260770]
• 36: Carl Hewitt, Open information systems semantics for distributed artificial intelligence, Artificial Intelligence, v.47 n.1-3, p.79-106, Jan. 1991 [doi>10.1016/0004-3702(91)90051-K]
• 37: Jones, A. 2001. Roles. In Deliverable D2 of ALFEBIITE EU-Project (IST-1999-10298), A. Jones and C. Krogh, Eds. 52--55. http://alfebiite.ee.ic.ac.uk/docs/Deliverables/D2.pdf.
• 38: Andrew J. I. Jones , Marek Sergot, On the characterization of law and computer systems: the normative systems perspective, Deontic logic in computer science: normative system specification, John Wiley and Sons Ltd., Chichester, UK, 1994
• 39: Jones, A. and Sergot, M. 1996. A formal characterisation of institutionalised power. J. IGPL 4, 3, 429--445.
• 40: Henry Kautz , Bart Selman, Planning as satisfiability, Proceedings of the 10th European conference on Artificial intelligence, p.359-363, August 1992, Vienna, Austria
• 41: Nihan Kesim , Marek Sergot, Implementing an object-oriented deductive database using temporal reasoning, Journal of Database Management, v.7 n.4, p.21-34, Fall 1996
• 42: Mark Klein , Juan-Antonio Rodriguez-Aguilar , Chrysanthos Dellarocas, Using Domain-Independent Exception Handling Services to Enable Robust Open Multi-Agent Systems: The Case of Agent Death, Autonomous Agents and Multi-Agent Systems, v.7 n.1-2, p.179-189, July-September 2003 [doi>10.1023/A:1024145408578]
• 43: R Kowalski , M Sergot, A logic-based calculus of events, New Generation Computing, v.4 n.1, p.67-95, 1986 [doi>10.1007/BF03037383]
• 44: Lee, J., Lifschitz, V., and Turner, H. 2001. A representation of the zoo world in the language of the Causal Calculator. In Proceedings of Symposium on Formalizations of Commonsense Knowledge.
• 45: Lifschitz, V. 2000. Missionaries and cannibals in the Causal Calculator. In Proceedings of Conference on Principles of Knowledge Representation and Reasoning (KR), A. Cohn, F. Giunchiglia, and B. Selman, Eds. Morgan Kaufmann, San Francisco, CA, 85--96.
• 46: Vladimir Lifschitz , Norman McCain , Emilio Remolia , Armando Tacchella, Getting to the airport: the oldest planning problem in AI, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
• 47: Vladimir Lifschitz , Hudson Turner, Representing Transition Systems by Logic Programs, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, p.92-106, December 02-04, 1999
• 48: Makinson, D. 1986. On the formal representation of rights relations. J. Philos. Logic 15, 403--425.
• 49: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 50: Zohar Manna , Amir Pnueli, Temporal verification of reactive systems: safety, Springer-Verlag New York, Inc., New York, NY, 1995
• 51: Naftaly H. Minsky, The Imposition of Protocols Over Open Distributed Systems, IEEE Transactions on Software Engineering, v.17 n.2, p.183-195, February 1991 [doi>10.1109/32.67599]
• 52: Naftaly H. Minsky, Law-governed systems, Software Engineering Journal, v.6 n.5, p.285-302, Sept. 1991
• 53: Naftaly H. Minsky , Victoria Ungureanu, Law-governed interaction: a coordination and control mechanism for heterogeneous distributed systems, ACM Transactions on Software Engineering and Methodology (TOSEM), v.9 n.3, p.273-305, July 2000 [doi>10.1145/352591.352592]
• 54: Moses, Y. and Tennenholtz, M. 1992. On computational aspects of artificial social systems. In Proceedings of Workshop on Distributed Artificial Intelligence (DAI). 267--284.
• 55: Moses, Y. and Tennenholtz, M. 1995. Artificial social systems. Computers AI 14, 6, 533--562.
• 56: Erik T. Mueller, Event Calculus Reasoning Through Satisfiability, Journal of Logic and Computation, v.14 n.5, p.703-730, October 2004 [doi>10.1093/logcom/14.5.703]
• 57: Noda, I., Matsubara, H., Hiraki, K., and Frank, I. 1998. Soccer server: a tool for research on multi-agent systems. App. AI 12, 2--3, 233--250.
• 58: Javier Pinto , Raymond Reiter, Temporal reasoning in logic programming: a case for the situation calculus, Proceedings of the tenth international conference on logic programming on Logic programming, p.203-221, August 1993, Budapest, Hungary
• 59: Jeremy Pitt , Lloyd Kamara , Alexander Artikis, Interaction patterns and observable commitments in a multi-agent trading scenario, Proceedings of the fifth international conference on Autonomous agents, p.481-488, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376422]
• 60: Pörn, I. 1977. Action theory and social science: some formal models. In Synthese Library Number 120. D. Reidel Publishing Company.
• 61: Henry Prakken, Coherence and Flexibility in Dialogue Games for Argumentation, Journal of Logic and Computation, v.15 n.6, p.1009-1040, December 2005 [doi>10.1093/logcom/exi046]
• 62: Henry Prakken , Thomas F. Gordon, Rules of Order for Electronic Group Decision Making - A Formalization Methodology, Collaboration between Human and Artificial Societies, Coordination and Agent-Based Distributed Computing, p.246-263, January 1999
• 63: Juan A. Rodríguez‐Aguilar , Francisco J. Martín , Pablo Noriega , Pere Garcia , Carles Sierra, Towards a test‐bed for trading agents in electronic auction markets, AI Communications, v.11 n.1, p.5-19, January 1998
• 64: Rodriguez-Aguilar, J. and Sierra, C. 2002. Enabling open agent institutions. In Socially Intelligent Agents: Creating Relationships with Computers and Robots, K. Dautenhahn, A. Bond, L. Canamero, and B. Edmonds, Eds. Kluwer Academic Publishers, 259--266.
• 65: Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
• 66: Sadighi, B. and Sergot, M. 2002. Contractual access control. In Proceedings of Workshop on Security Protocols. Leature Notes in Computer Science, vol. 2845. Springer-Verlag, New York. 96--102.
• 67: Action Concepts for Describing Organised Interaction, Proceedings of the 30th Hawaii International Conference on System Sciences: Advanced Technology Track, p.373, January 03-06, 1997
• 68: Searle, J. 1969. Speech Acts. Cambridge University Press, Cambridge, UK.
• 69: Marek Sergot, A computational theory of normative positions, ACM Transactions on Computational Logic (TOCL), v.2 n.4, p.581-622, Oct. 2001 [doi>10.1145/383779.383786]
• 70: Sergot, M. 2004a. (C+)⁺⁺: An action language for modelling norms and institutions. Tech. rep. 2004/8, Department of Computing, Imperial College London, London, UK. http://www.doc.ic.ac.uk/research/technicalreports/2004/DTR04-8.pdf.
• 71: Sergot, M. 2004b. Modelling unreliable and untrustworthy agent behavior. In Proceedings of Workshop on Monitoring, Security, and Rescue Techniques in Multiagent Systems (MSRAS), B. Dunin-Keplicz, A. Jankowski, A. Skowron, and M. Szczuka, Eds. Advances in Soft Computing. Springer-Verlag, New York, 161--178.
• 72: Sergot, M. and Craven, R. 2006. The deontic component of action language nC+. In Deontic Logic and Artificial Normative Systems. Proceedings of the 8th International Workshop on Deontic Logic in Computer Science (DEON'06), L. Goble and J.-J. C. Meyer, Eds. Lecture Notes in Artificial Inteligence, vol. 4048. Springer-Verlag, New York, 222--237.
• 73: Shanahan, M. 1999. The event calculus explained. In Artificial Intelligence Today, M. Wooldridge and M. Veloso, Eds. Lecture Notes in Artificial Inteligence, vol. 1600. Springer-Verlag, New York, 409--430.
• 74: Shanahan, M. 2000. An abductive event calculus planner. J. Logic Program. 44, 207--239.
• 75: Murray Shanahan , Mark Witkowski, Event Calculus Planning Through Satisfiability, Journal of Logic and Computation, v.14 n.5, p.731-745, October 2004 [doi>10.1093/logcom/14.5.731]
• 76: Shoham, Y. and Tennenholtz, M. 1992. On the synthesis of useful social laws for artificial agent societies. In Proceedings of Conference on Artificial Intelligence (AAAI), W. Swartout, Ed. The AAAI Press/The MIT Press, Cambridge, MA, 276--281.
• 77: Yoav Shoham , Moshe Tennenholtz, On social laws for artificial agent societies: off-line design, Artificial Intelligence, v.73 n.1-2, p.231-252, Feb. 1995 [doi>10.1016/0004-3702(94)00007-N]
• 78: Munindar P. Singh, Agent Communication Languages: Rethinking the Principles, Computer, v.31 n.12, p.40-47, December 1998 [doi>10.1109/2.735849]
• 79: Munindar P. Singh, A Social Semantics for Agent Communication Languages, Issues in Agent Communication, p.31-45, January 2000
• 80: Marvin A. Sirbu, Credits and debits on the Internet, IEEE Spectrum, v.34 n.2, p.23-29, Feb. 1997 [doi>10.1109/6.570823]
• 81: R. G. Smith, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on Computers, v.29 n.12, p.1104-1113, December 1980 [doi>10.1109/TC.1980.1675516]
• 82: Smith, R. and Davis, R. 1978. Distributed problem solving: the contract-net approach. In Proceedings of Conference of Canadian Society for Computational Studies of Intelligence. 217--236.
• 83: Tennenholtz, M. 1995. On computational social laws for dynamic non-homogeneous social structures. J. Exper. Theor. AI 7, 379--390.
• 84: Eric Werner, Cooperating agents: a unified theory of communication and social structure, Distributed Artificial Intelligence (Vol. 2), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 85: Werner, E. 1992. The design of multi-agent systems. In Decentralized A.I., Vol. 3. E. Werner and Y. Demazeau, Eds. Elsevier Science Publishers, 3--30.
• 86: Michael Wooldridge , Nicholas R. Jennings , David Kinny, A methodology for agent-oriented analysis and design, Proceedings of the third annual conference on Autonomous Agents, p.69-76, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301165]
• 87: Michael Wooldridge , Nicholas R. Jennings , David Kinny, The Gaia Methodology for Agent-Oriented Analysis and Design, Autonomous Agents and Multi-Agent Systems, v.3 n.3, p.285-312, September 2000 [doi>10.1023/A:1010071910869]
• 88: Pinar Yolum , Munindar P. Singh, Flexible protocol specification and execution: applying event calculus planning using commitments, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544867]
• 89: Pınar Yolum , Munindar P. Singh, Reasoning about Commitments in the Event Calculus: An Approach for Specifying and Executing Protocols, Annals of Mathematics and Artificial Intelligence, v.42 n.1-3, p.227-253, September 2004 [doi>10.1023/B:AMAI.0000034528.55456.d9]
• 90: Franco Zambonelli , Nicholas R. Jenning , Andrea Omicini , Michael J. Wooldridge, Agent-oriented software engineering for Internet agents, Coordination of Internet agents: models, technologies, and applications, Springer-Verlag, London, 2001
• 91: Zambonelli, F., Jennings, N., and Wooldridge, M. 2001b. Organisational rules as an abstraction for the analysis and design of multi-agent systems. Int. J. Softw. Engin. Knowl. Engin. 11, 3, 303--328.
• 92: Franco Zambonelli , Nicholas R. Jennings , Michael Wooldridge, Organizational abstractions for the analysis and design of multi-agent system, First international workshop, AOSE 2000 on Agent-oriented software engineering, p.235-251, January 2001, Limerick, Ireland
• 93: Franco Zambonelli , Nicholas R. Jennings , Michael Wooldridge, Developing multiagent systems: The Gaia methodology, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.3, p.317-370, July 2003 [doi>10.1145/958961.958963]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages

General Terms:
Theory

Keywords:
Action language, agent, contract-net, event calculus, executable specification, norm, policy