Stochastic modelling of spatial collective adaptive systems
Collective Adaptive Systems (CAS) are composed of individual agents with internal knowledge and rules which organize themselves into ensembles. These ensembles can often be observed to exhibit behaviour resembling that of a single entity with a clear goal and a consistent internal knowledge, even when the individual agents within the ensemble are not managed by any outside, globally-accessible entity. Because of their lack of a need for centralized control which results in high robustness, CAS are commonly observed in nature – and for similar reasons are often reflected in human engineered systems. Researching the patterns of operation observed in such systems provides meaningful insight into how to design and optimise stable multiagent systems capable of withstanding adverse conditions. Formal modelling provides valuable intellectual tools which can be applied to the problem of analysis of systems by means of modelling and simulation. In this thesis we explore the modelling of CAS in which space (topology and distances) plays a significant role. Working with CARMA (Collective Adaptive Resource-sharing Markovian Agents) a formal feature-rich language for modelling stochastic CAS, we investigate a number of spatial CAS scenarios from the realm of urban planning. When components operate in a spatial context, their behaviour can be affected by where they are located in that space. For example, their location can influence the speed at which they move, and their ability to communicate with other components. Components in CARMA have internal store, and behaviour expressed by Markov processes. They can communicate with each other through sending messages on state transitions in a unicast or broadcast fashion. Simulation with pseudo-random events can be used to obtain values of measures applied to CARMA models, providing a basis for analysis and optimisation. The CARMA models developed in the case studies are data-driven and the results of simulating these models are compared with real-world data. In particular, we explore two scenarios: crowd-routing and city transportation systems. Building on top of CARMA, we also introduce CGP (CARMA Graphical Plugin), a novel graphical software tool for graphically specifying spatial CAS systems with the feature of automatic translation into CARMA models. We also supply CARMA with additional syntax structures for expressing spatial constructs.