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 overconstrain the behaviors of agents). Designing or even automatically synthesizing minimal effective normative systems is highly nontrivial. 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. 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.
Hao et al. REF propose a method for designing minimal effective normative models to coordinate agents in an open system.
Designing minimal effective normative systems with the help of lightweight formal methods
FSE 2016
Computer Science