FSE 2016 All Events

24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2016), November 13–18, 2016, Seattle, WA, USA

Desktop Layout

Session 1: Specification
Research Papers
Emerald 1, Chair: Mike Whalen
Designing Minimal Effective Normative Systems with the Help of Lightweight Formal Methods
Jianye Hao, Eunsuk Kang, Jun Sun, and Daniel Jackson
(Tianjin University, China; University of California at Berkeley, USA; Singapore University of Technology and Design, Singapore; Massachusetts Institute of Technology, USA)
Publisher's Version
Abstract: Normative systems (i.e., a set of rules) 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. 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.


Time stamp: 2019-06-18T22:41:30+02:00