Executable specification of adaptive open norm-governed computational systems

Abstract

Ad hoc networks may be characterised as volatile systems of agents which collaborate to achieve a common goal, be that the fair use of a common pool resource, the minimisation of packet collisions or efficient data routing. Early approaches to these problems take inspiration from emergent systems, characterised in terms of a population governed by a fixed specification, and out of which arises a relatively sophisticated set of global properties. However, the features of open ad hoc networks necessitate an approach in which participating agents agree to conform to a mutable set of rules (permissions, powers and obligations), which are conventionally rather than physically binding. We are concerned with the development of open agent societies, in which a heterogeneous set of norm-aware agents with conflicting goals can produce similar emergent global properties by introspectively modelling system change. In this thesis we present norm-governed systems spaces, in which the `organised adaptation' of a specification is defined in terms of a finite number of adaptations and environmental states. These two elements are unified in a statistical framework which models an agent's motivation for system change as a set of Markov chains, mapped to a representation of utility. This arrangement allows participants to calculate the total expected utility of any deterministic adaptation strategy, wherein policy changes are chosen for the complete set of environmental fluctuations. We demonstrate this architecture in Matlab with a resource allocation example, in the context of which a norm-governed systems space is trained. Analytic models of agent societies are often idealised, and must be deployed in an experimental test bed to ensure the assumptions remain valid. We present the novel platform PreSage-NGS which constitutes a subsumption of the norm-governed systems space framework into a multi agent system simulation environment. We illustrate an application of this software in the same resource allocation scenario, identifying agent goal conflicts by inferring the alignment of private utility models through the evaluation of publicly expressed strategy proposals. This thesis explores how norm-governed systems spaces may be rapidly trained using lightweight approximations of agent populations in Matlab, which may be verified experimentally to ensure predictions translate to the reality of an open agent society. PreSage-NGS represents a means of exploring the strength of social models for system change in agent societies, in which bounded rationality may create unforeseen interaction dynamics.