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 o-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 rst synthesis strategy, the so-called base, aims at synthesising
eective 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 eectively achieve coordination, are as synthetic
as possible. This allows them to reduce agents' computational eorts 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 eective and compact while
preserving agents' freedom to the greatest possible extent. Our nal strategy is
desmon, which is capable of synthesising norms by considering dierent 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 trac domain, and an on-line community domain.
In this former domain, we employ these strategies to synthesise eective, 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.