Skip to main content

Research Repository

Advanced Search

Norm approximation for imperfect monitors

Alechina, Natasha; Dastani, Mehdi; Logan, Brian

Authors

Natasha Alechina

Mehdi Dastani

Brian Logan



Abstract

In this paper, we consider the runtime monitoring of norms with imperfect monitors. A monitor is imperfect for a norm if it has insufficient observational capabilities to determine if a given execution trace of a multi-agent system complies with or violates the norm. One approach to the problem of imperfect monitors is to enhance the observational capabilities of the normative organisation. However this may be costly or in some cases impossible. Instead we show how to synthesise an approximation of an 'ideal' norm that can be perfectly monitored given a monitor, and which is optimal in the sense that any other approximation would fail to detect at least as many violations of the ideal norm. We give a logical analysis of (im)perfect monitors. We state the computational complexity of the norm approximation problem, and give an optimal algorithm for generating optimal approximations of norms given a monitor.

Citation

Alechina, N., Dastani, M., & Logan, B. (2014). Norm approximation for imperfect monitors

Conference Name 13th International Conference on Autonomous Agents & Multiagent Systems AAMAS 2014
End Date May 9, 2014
Publication Date May 5, 2014
Deposit Date Sep 21, 2015
Publicly Available Date Sep 21, 2015
Peer Reviewed Peer Reviewed
Public URL http://eprints.nottingham.ac.uk/id/eprint/30181
Publisher URL http://dl.acm.org/citation.cfm?id=2615753
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf
Additional Information ISBN 9781450327381

Files


eprints-mehdi14.pdf (338 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations