Automated norm synthesis in planning environments
View/Open
Date
24/11/2011Author
Christelis, George Dimitri
Metadata
Abstract
Multiagent systems offer a design paradigm used to conceptualise and implement systems
composed of autonomous agents. Autonomy facilitates proactive independent
behaviour yet in practice agents are constrained in order to ensure the system satisfies
a desired social objective. Explicit constraints on agent behaviour, in the form of social
norms, encourage this desirable system behaviour, yet research has largely focused on
norm representation languages and protocols for norm proposal and adoption. The fundamental
problem of how to automate the process of norm synthesis has largely been
overlooked with norms assumed provided by the designer. Previous work has shown
that automating the design of social norms is intractable in the worst case. Existing
approaches, relying on state space enumerations, are effective for small systems but
impractical for larger ones. Furthermore, they do not produce a set of succinct, general
norms but rather a large number of state-specific restrictions.
This work presents conflict-rooted synthesis, an automated norm synthesis approach
that utilises a planning-based action schemata to overcome these limitations.
These action schemata facilitate localised searches around specifications of undesirable
states, using representations of sets of system states to avoid a full state enumeration.
The proposed technique produces concise, generalised social norms that are applicable
in multiple system states while also providing guarantees that agents are still able to
achieve their original goals in the constrained system. To improve efficiency a set of
theoretically sound, domain-independent optimisations are presented that reduce the
state space searched without compromising the quality of the norms synthesised.
A comparison with an alternative model checking based technique illustrates the
advantages and disadvantages of our approach, while an empirical evaluation highlights
the improved efficiency and quality of norms it produces at the cost of a less
expressive specification of undesirable states. We empirically investigate the effectiveness
of each of the proposed optimisations using a set of benchmark domains, quantifying
how successful each of them is at reducing search complexity in practice. The
results show that, with all optimisations enabled, conflict-rooted synthesis produces
more generally applicable and succinct norms and consumes fewer system resources.
Additionally, we show that this approach synthesises norms in systems where the competing
approach is intractable. We provide a discussion of our approach, highlighting
the impact our abstract search approach has on the fields of multiagent systems and
automated planning, and discuss the limitations and assumptions we have made. We
conclude with a presentation of future work.
Collections
The following license files are associated with this item: