A real-time semantics for norms with deadlines

ABSTRACT

Norms have been proposed as a way to regulate multi-agent systems. In order to operationalize norms, several computational frameworks have been proposed for programming norm-governed agent organizations. It has been argued that in such systems it is essential that norms, in particular those giving rise to achievement obligations, have deadlines. In this paper we propose a novel semantic framework that takes into account and formalizes real-time aspects of such norms with deadlines. The framework introduced provides a semantics for norms with real-time deadlines that is a conservative extension of more traditional transition systems semantics that has been used for specifying multi-agent systems. Our framework thus provides a natural extension for formalizing multi-agent systems with norms that have real-time deadlines. We address several important aspects of semantics of norms with deadlines such as deadline termination and, in particular, investigate the issue of deadline shifting that arises naturally in a real-time setting as a result of interactions between norms. A new normative model is presented for handling such interactions. We present several formal results showing that our semantics corresponds with basic intuitions that any operational semantics for norms with (real-time) deadlines should satisfy, and that it is well-defined.

References

1. R. Alur and T. A. Henzinger. Logics and models of real time: A survey. In Real-Time: Theory in Practice, volume 600 of LNCS, pages 74-106. Springer, 1992.
2. L. Astefanoaei, F. de Boer, and M. Dastani. Strategic executions of choreographed timed normative multi-agent systems. In Proceedings of the nineth international joint conference on autonomous agents and multiagent systems (AAMAS'10), pages 965--972. IFAAMAS, 2010.
3. G. Boella, J. Broersen, and L. van der Torre. Reasoning about constitutive norms, counts-as conditionals, institutions, deadlines and violations. In T. D. Bui, T. V. Ho, and Q.-T. Ha, editors, Proceedings of the 11th Pacific Rim International Conference on Multi-Agents (PRIMA'08), volume 5357 of LNCS, pages 86--97. Springer, 2008.
4. J. Broersen. Issues in designing logical models for norm change. In G. Vouros, A. Artikis, K. Stathis, and J. Pitt, editors, Proceedings of the First International Workshop on Organized Adaption in Multi-Agent Systems (OAMAS'08), volume 5368 of LNCS, pages 1--17, 2009.
5. S. Cranefield. A rule language for modelling and monitoring social expectations in multi-agent systems. In Coordination, Organizations, Institutions, and Norms in Multi-Agent Systems (ANIREM'05 and OOOP'05), volume 3913 of LNCS, pages 246--258, 2006.
6. M. Dastani, N. Tinnemeier, and J.-J. Ch. Meyer. A programming language for normative multi-agent systems. In V. Dignum, editor, Multi-Agent Systems: Semantics and Dynamics of Organizational Models. IGI Global, 2009.
7. F. Dignum and R. Kuiper. Specifying deadlines with dense time using deontic and temporal logic. International Journal of Electronic Commerce, 3(2):67--86, 1998.
8. G. Governatori, J. Hulstijn, R. Riveret, and A. Rotolo. Characterising deadlines in temporal modal defeasible logic. In Proceedings of the 20th Australian joint conference on Advances in artificial intelligence, pages 486--496. Springer-Verlag, 2007.
9. G. Governatori, A. Rotolo, and G. Sartor. Temporalised normative positions in defeasible logic. In Procedings of the 10th International Conference on Artificial Intelligence and Law, pages 25--34. ACM Press, 2005.
10. T. Henzinger, Z. Manna, and A. Pnueli. Timed transition systems. In Proceedings of the Real-Time: Theory in Practice, REX Workshop, volume 600 of LNCS, pages 226--251. Springer, 1991.
11. T. A. Henzinger, Z. Manna, and A. Pnueli. An interleaving model for real time. Technical Report STAN-CS-90-1329, Stanford University, 1990.
12. A. Hoare. Communicating Sequential Procresses. Prentice-Hall, 1985.
13. J. Hübner, O. Boissier, and R. Bordini. A normative programming language for multi-agent organisations. Annals of Mathematics and Artificial Intelligence, 62:27--53, 2011.
14. J. F. Hübner, O. Boissier, and R. H. Bordini. From organisation specification to normative programming in multi-agent organisations. In J. Dix, J. A. Leite, G. Governatori, and W. Jamroga, editors, Proceedings of the eleventh international workshop on computational logic in multi-agent systems (CLIMA'10), volume 6245 of LNCS, pages 117--134, 2010.
15. K. Irwin, T. Yu, and W. H. Winsborough. On the modeling and analysis of obligations. In Proceedings of the 13th ACM conference on Computer and communications security (CCS'06), pages 134--143. ACM, 2006.
16. R. Koymans. Specifying real-time properties with metric temporal logic. Real-Time Systems, 2:255--299, 1990.
17. M. B. van Riemsdijk, K. V. Hindriks, C. M. Jonker, and M. Sierhuis. Formalizing organizational constraints: A semantic approach. In Proceedings of the nineth international joint conference on autonomous agents and multiagent systems (AAMAS'10), pages 823--830. IFAAMAS, 2010.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Context specific languages