Javier Morales Matamoros
Published: 2015
Total Pages: 234
Get eBook
Multi Agent Systems (MAS) are computerised systems composed of autonomous software agents that interact to solve complex problems. Within a MAS, agents require some mechanism to coordinate their activities. In the MAS literature, norms have been widely used to coordinate agents' activities. Thus, given a MAS, a major research challenge is how to synthesise a normative system, namely a collection of norms, which supports its agents' coordination. This dissertation focuses on the automated synthesis of norms for open Multi- Agent Systems. In an open MAS, the agent population may change along time, agents may be developed by third parties and their behaviours are not known beforehand. These particular conditions make specially challenging to synthesise a normative system to govern an open MAS. The MAS literature has mainly investigated two general approaches to norm synthesis: off-line design, and on-line synthesis. The first approach aims at synthesising a normative system at design time. With this aim, it assumes that the MAS state space is known at design time and does not change at runtime. This goes against the nature of open MAS, and thus off-line design is not appropriate to synthesise their norms. Alternatively, on-line norm synthesis considers that norms are synthesised at runtime. Most on-line synthesis research has focused on norm emergence, which considers that agents synthesise their own norms, thus assuming that they have norm synthesis capabilities. Again, this cannot be assumed in open MAS. Against this background, this dissertation introduces a whole computational framework to perform on-line norm synthesis for open Multi-Agent Systems. Firstly, this framework provides a computational model to synthesise norms for a MAS at runtime. Such computational model requires neither knowledge about agents' behaviours beforehand nor their participation in the norm synthesis pro- cess. Instead, it considers a regulatory entity that observes agents' interactions at runtime, identifying situations that are undesirable for coordination to sub- sequently synthesise norms that regulate these situations. Our computational model has been conceived to be of general purpose so that it can be employed to synthesise norms in a wide range of application domains by providing little domain-dependent information. Secondly, our framework provides an abstract architecture to implement such regulatory entity (the so-called Norm Synthesis Machine), which observes a MAS and executes a synthesis strategy to synthe- sise norms. Thirdly, our framework encompasses a family of norm synthesis strategies intended to be executed by the Norm Synthesis Machine. Overall, this family of strategies supports multi-objective on-line norm synthesis Our first synthesis strategy, the so-called base, aims at synthesising effective normative systems that successfully avoid situations that are undesirable for a MAS' coordination. Then, two further strategies (called iron and simon) go beyond effectiveness and also consider compactness as a norm synthesis goal. iron and simon take alternative approaches to synthesise compact normative systems that, in addition to effectively achieve coordination, are as synthetic as possible. This allows them to reduce agents' computational efforts when reasoning about norms. A fourth strategy, the so-called lion, goes beyond effectiveness and compactness to also consider liberality as a synthesis goal. lion aims at synthesising normative systems that are effective and compact while preserving agents' freedom to the greatest possible extent. Our final strategy is desmon, which is capable of synthesising norms by considering different degrees of reactivity. desmon allows to adjust the amount of information that is required to decide whether a norm must be included in a normative system or not. Thus, desmon can synthesise norms either by being reactive (i.e., by considering little information), or by being more deliberative (by employing more information). We provide empirical evaluations of our norm synthesis strategies in two application domains: a road traffic domain, and an on-line community domain. In this former domain, we employ these strategies to synthesise effective, compact and liberal normative systems that successfully avoid collisions between cars. In the latter domain, our strategies synthesise normative systems based on users' complaints about inappropriate contents. In this way, our strategies implement a regulatory approach that synthesises norms when there is enough user consensus about the need for norms. Overall, this thesis advances in the state of the art in norm synthesis by providing a novel computational model, an abstract architecture and a family of strategies for on-line norm synthesis for open Multi-Agent Systems.