A rule language for modelling and monitoring social expectations in multi-agent systems
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1659-1659.
© 2005 International Joint Conferences on Artificial Intelligence
Abstract
This paper proposes a rule language for defining social expectations based on a metric interval temporal logic with past and future modalities and a current-time binding operator. An algorithm for run-time monitoring compliance of rules in this language based on formula progression is also outlined.
- [Alur et al., 1996] R. Alur, T. Feder, and T. A. Henzinger. The benefits of relaxing punctuality. Journal of the ACM, 43(1):116-146, 1996.
- [Bacchus and Kabanza, 1998] F. Bacchus and F. Kabanza. Planning for temporally extended goals. Annals of Mathe- matics and Artificial Intelligence, 22(1-2):5-27, 1998.
- [Blackburn et al., 2001] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic, chapter 7, pages 436-447. Cam- bridge University Press, 2001.
- [Cortés, 2004] U. Cortés. Electronic institutions and agents. AgentLink News, 15:14-15, September 2004.
- [Cranefield, 2005] S. Cranefield. A rule language for modelling and monitoring social expectations in multi- agent systems. Discussion Paper 2005/01, Depart- ment of Information Science, University of Otago, 2005. http://www.otago.ac.nz/informationscience/pubs/ papers/papers/dp2005-01.pdf. Link
- [Verdicchio and Colombetti, 2003] M. Verdicchio and M. Colombetti. A logical model of social commitment for agent communication. In Proc. of AAMAS 2003, pages 528-535. ACM Press, 2003.
- [Verdicchio and Colombetti, 2004] M. Verdicchio and M. Colombetti. Dealing with time in content language expressions. In Proc. of the AAMAS 2004 Workshop on Agent Communication, pages 90-104, 2004.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
The study of electronic institutions-explicit declarative models of the rules governing particular open systems of autonomous agents-has gained much recent attention [Cort´es, 2004]. There has been a significant amount of research on statically verifying properties of institutions as well as interpreting institutions to manage or guide agent interaction. However, there has been little attention paid to mechanisms for run-time compliance checking, i.e. monitoring events in a running agent system, determining the future expectations of agents' behaviour according to norms of the institution, and checking if these are fulfilled or violated. This paper focuses on this issue by presenting (i) a logic named hyMITL± that combines CTL± [Verdicchio and Colombetti, 2003] with Metric Interval Temporal Logic (MITL) [Alur et al., 1996], as well as features of hybrid logics [Blackburn et al., 2001], and (ii) a subset of hyMITL± that provides a rule language for defining social expectations. We have implemented an algorithm for monitoring social expectations encoded in this language, based on the technique of formula progression from the planning system TLPlan [Bacchus and Kabanza, 1998].
2 Syntax of hyMITL◦
The syntax of hyMITL± is defined as follows:
where
- p is an atomic formula from a first order language L.
- φx denotes a formula φ in which variable x is free (i.e. not bound by ∀ or ↓).
- a and d are terms, possibly containing variables, that denote (respectively) absolute points in time and durations (e.g. using the language proposed by Verdicchio and Colombetti [2004]).
- u is a unit selector on the ↓ binding operator, referring to the desired granularity of time (e.g. year or minute) for binding x to the current time (with default value now).
We constrain the use of variables within interval bounds b: any such variables must be bound by an enclosing ↓ operator.
In this logic, the temporal operators X+ and X- mean "in the next state" and "in the previous state" respectively. φU+I ψ asserts that φ will remain true from the current state for some (possibly empty) sequence of consecutive future states, followed by a state that is within the time interval I and for which ψ holds. X- and U-I are defined similarly, but in the past direction.
The bounds of intervals can be specified either relatively or absolutely-a prefix of "+" or "-" indicates a relative time value. When qualifying U-, the interval bounds are written in the reverse order from usual, e.g. [-2hours,-3hours].
A and E are temporal path quantifiers. They assert that the formula that follows the operator applies to all, or respectively at least one, of the possible sequences of states passing through the current state.
The ↓ operator is based on the "binder" operator used in hybrid logics [Blackburn et al., 2001]. It binds a variable to a term denoting the current date/time, possibly 'rounded down' to a particular degree of precision, e.g. to the start of the current year, month or day, depending on the unit indicated by the superscript u.
We use the usual derived operators of first order predicate logic, as well as the standard abbreviations for existential and universal quantification over states in a path: F+I φ ≡ trueU+I φ and G+I φ ≡ ¬F+I ¬φ, with similar definitions for F-I and G-I . We define future and past "weak until" operators in the following way:
with similar definitions for intervals with open bounds and for W-.
AG+ (Done(c, make payment(c, p, amount, prod num)) ∧ [t, t +1week) → ↓week w.((¬F-[-0↪w]Done(p, send report(c, prod num,w)) →F+(+0↪ w+1week)Done(p, send report(c, prod num,w))) W+[+0↪ w+52 weeks] Done(c, cancel order(c, p, prod num)))
the progression step as it is performed in the current statebefore a new state is created by a new event occurrence, and therefore before formula progression can be done (this needs the time difference between the old and new state as an input).
5 Conclusion
This paper has defined a rule language for defining social expectations based on a metric interval temporal logic and has outlined an algorithm that can be used at run time in a multiagent system to monitor when expectations are generated, fulfilled and violated. A prototype implementation of the compliance testing algorithm has been implemented using SWI Prolog. Most of the features described here have been implemented, although currently the system is not connected to an agent-it uses a static database of states and their facts-and integers are used to represent times.
The semantics for hyMITL±, the algorithms used, a discussion of related work and future extensions to this work, and acknowledgements can be found in the full version of this paper [Cranefield, 2005].
@inproceedings{ijcai2005p248,
title = {A rule language for modelling and monitoring social expectations in multi-agent systems},
author = {Cranefield, Stephen},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Leslie Pack Kaelbling and Alessandro Saffiotti},
pages = {1659--1659},
year = {2005},
url = {https://ijcai.org/proceedings/2005/248},
}
TY - CPAPER TI - A rule language for modelling and monitoring social expectations in multi-agent systems AU - Cranefield, Stephen T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1659 EP - 1659 UR - https://ijcai.org/proceedings/2005/248 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: