Social norms are powerful formalism in coordinating autonomous agents' behaviour to achieve certain objectives. In this paper, we propose a dynamic normative system to enable the reasoning of the changes of norms under different circumstances, which cannot be done in the existing static normative systems. We study two important problems (norm synthesis and norm recognition) related to the autonomy of the entire system and the agents, and characterise the computational complexities of solving these problems.
Norm synthesis for static normative systems. As stated, most current formalisms of normative systems are static. @cite_7 shows that this norm synthesis problem is NP-complete. @cite_3 proposes a norm synthesis algorithm in declarative planning domains for reachability objectives, and @cite_8 considers the on-line synthesis of norms. @cite_10 considers the norm synthesis problem by conditioning over agents' preferences, expresses as pairs of LTL formula and utility, and a normative behaviour function.
@cite_3 @cite_10 @cite_7 @cite_8
81435041 2204084130 1986112535 1703978911
Norms and social laws are one of the key mechanisms used to facilitate coordination in multiagent systems. In existing approaches the process of designing useful norms has to either be performed by a human expert, or requires a full enumeration of the state space which is bound to cause tractability problems in non-trivial domains. In this paper we propose a novel automated synthesis procedure for prohibitive norms in planning-based domains that disallow access to a set of predefined undesirable states. Our method performs local search around declarative specifications of states using AI planning methods. Using this approach, norms can be synthesised in a generalised way over incomplete state specifications to improve the efficiency of the process in many practical cases, while producing concise, generalised, social norms that are applicable to entire sets of system states. We present an algorithm that utilises traditional planning techniques to ensure continued accessibility under the prohibitions introduced by norms. An analysis of the computational properties of our algorithm is presented together with a discussion of possible heuristic improvements. The environment is an essential component of multi-agent systems and is often used to coordinate the behaviour of individual agents. Recently many languages have been proposed to specify and implement multi-agent environments in terms of social and normative concepts. In this paper, we first introduce a formal setting of multi-agent environment which abstracts from concrete specification languages. We extend this formal setting with norms and sanctions and show how concepts from mechanism design can be used to formally analyse and verify whether specific normative behaviours can be enforced (or implemented) if agents follow their subjective preferences. We also consider complexity issues of associated problems. Abstract We are concerned with the utility of social laws in a computational environment, laws which guarantee the successful coexistence of multiple programs and programmers. In this paper we are interested in the off-line design of social laws, where we as designers must decide ahead of time on useful social laws. In the first part of this paper we suggest the use of social laws in the domain of mobile robots, and prove analytic results about the usefulness of this approach in that setting. In the second part of this paper we present a general model of social law in a computational system, and investigate some of its properties. This includes a definition of the basic computational problem involved with the design of multi-agent systems, and an investigation of the automatic synthesis of useful social laws in the framework of a model which refers explicitly to social laws. Normative systems (norms) have been widely proposed as a technique for coordinating multi-agent systems. The automated synthesis of norms for coordination remains an open and complex problem, which we tackle in this paper. We propose a novel mechanism called IRON (Intelligent Robust On-line Norm synthesis mechanism), for the on-line synthesis of norms. IRON aims to synthesise conflict-free norms without lapsing into over-regulation. Thus, IRON produces norms that characterise necessary conditions for coordination, without over-regulation. In addition to defining the norm synthesis problem formally, we empirically show that IRON is capable of synthesising norms that are effective even in the presence of non-compliance behaviours in a system.