Animated specifications of computational societies

ABSTRACT

E-markets and negotiation protocols are two types of application domains that can be viewed as open computational societies. Key characteristics of such societies are agent heterogeneity, conflicting individual goals and limited trust. The risk that members of such societies will not conform to specifications imposes the need for a framework that will facilitate the designers to determine to what extent it is desirable to deploy their agents in such societies. We address this need by presenting a formal framework for specifying, animating, and ultimately reasoning about and verifying the properties of open computational systems. We view computational systems from an external perspective, aiming to account for the institutional and social aspects of these systems. We identify the key concepts and illustrate how they are used by formalising an example employing the contract net protocol. The framework and associated logical inferences have been implemented as a software platform that provides automated animation of the global states of an open system (society) during its execution. Simulations have demonstrated that the implementation of the framework establishes a foundation for a rich, formal representation of open computational societies.

REFERENCES

• 1: Kathleen M. Carley , Les Gasser, Computational organization theory, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 2: 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
• 3: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 4: J. Ferber and O. Gutknecht. Operational semantics of multi-agent organisations. In Intelligent Agents IV. 2000.
• 5: 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]
• 6: 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
• 7: A. Jones and M. Sergot. A formal characterisation of institutionalised power. IGPL, 4(3), 1996.
• 8: 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]
• 9: Y. Moses and M. Tennenholtz. Artificial social systems. Computers and AI, 14(6):533--562, 1995.
• 10: 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]
• 11: 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, Sept. 1997
• 12: F. Santos, A. Jones, and J. Carmo. Action concepts for describing organised interaction. In HICSS, 1997.
• 13: J. Searle. What is a speech act? In Philosophy of Language, pages 130--141. 1965.
• 14: 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]
• 15: M. Shanahan. The event calculus explained. Artificial Intelligence Today, pages 409--430, 1999.
• 16: Munindar P. Singh, A Social Semantics for Agent Communication Languages, Issues in Agent Communication, p.31-45, January 2000
• 17: R. Smith and R. Davis. Distributed problem solving: The contract-net approach. In 2nd Conference of Canadian Society for CSI, pages 217--236, 1978.
• 18: M. Wooldridge. The Logical Modelling of Computational Multi-Agent Systems. PhD thesis, UMIST, 1992.
• 19: Michael Wooldridge, This is MYWORLD: the logic of an agent-oriented DAI testbed, Proceedings of the workshop on agent theories, architectures, and languages on Intelligent agents, p.160-178, March 1995, Amsterdam, The Netherlands
• 20: 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design, Experimentation

Keywords:
formal specification, norm-governed multi-agent systems