Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
11-2016
Abstract
Normative systems are an important approach to achieving effective coordination among (often an arbitrary number of) agents in multiagent systems. A normative system should be effective in ensuring the satisfaction of a desirable system property, and minimal (i.e., not containing norms that unnecessarily over-constrain the behaviors of agents). Designing or even automatically synthesizing minimal effective normative systems is highly non-trivial. Previous attempts on synthesizing such systems through simulations often fail to generate normative systems which are both minimal and effective. In this work, we propose a framework that facilitates designing of minimal effective normative systems using lightweight formal methods. Given a minimal effective normative system which coordinates many agents must be minimal and effective for a small number of agents, we start with automatically synthesizing one such system with a few agents using Alloy Analyzer. We then increase the number of agents so as to check whether the same design remains minimal and effective. If it is, we manually establish an induction proof so as to lift the design to an arbitrary number of agents. We show the effectiveness of the framework by using it to design road junction traffic rules and population protocols. The protocols designed using our framework are shown to be as good as those manually designed and published ones.
Keywords
Lightweight formal methods, Minimal effective, Norm Synthesis
Discipline
Computer and Systems Architecture | Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
FSE 2016: Proceedings of the 24th ACM SIGSOFT Symposium on the Foundations of Software Engineering, Seattle, November 13-18, 2016
First Page
50
Last Page
60
ISBN
9781450342186
Identifier
10.1145/2950290.2950307
Publisher
IEEE
City or Country
USA
Citation
HAO, Jianye; KANG, Eunsuk; SUN, Jun; and JACKSON, Daniel.
Designing minimal effective normative systems with the help of lightweight formal methods. (2016). FSE 2016: Proceedings of the 24th ACM SIGSOFT Symposium on the Foundations of Software Engineering, Seattle, November 13-18, 2016. 50-60.
Available at: https://ink.library.smu.edu.sg/sis_research/4947
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1145/2950290.2950307