The simple rules that govern the interactions between the different components of a complex system often lead to interesting behaviour that are unexpected, emergent or serendipitous. This thesis proposes a new approach using compression for the automatic discovery of interesting behaviour that occurs in complex systems. In order to evaluate the new approach, three different types of complex systems are examined experimentally:one dimensional cellular automata, flocking and a variation of Braitenberg Vehicles.
In the first experiment, a novel approach has been developed to examine one dimensional cellular automata, where the output is compressed using the text compression scheme Prediction by Partial Matching (PPM) to generate the code length differences of the output with respect to time. Several clustering algorithms, such as k-means and Hierarchical Agglomerative Clustering, were then used to group cellular automata which show similar behaviour together into clusters, thus making interesting behaviours much more accessible in comparison to results produced in related studies. Various types of interesting behaviour were then found by analysing the graphs of the code length
differences, where jagged peaks in the graphs, high variance in the data, and large gradients were good indicators of interesting patterns in cellular automata. Rare or unusual behaviour were also classed as being interesting, which could easily be found by examining for small clusters.
In the second experiment, a similar strategy was taken when analysing a flocking
behaviour model. By combining Run Length Encoding with PPM compression of the output produced over the course of the simulation, and using multi-stage clustering it was possible to cluster similar flocking behaviours together. To test the quality of these clusters, an innovative algorithm was devised to determine the distance between different behaviours. It was noticed that tightly bound flocks had much smaller compression code lengths (highly compressed) overall in the spatial domain. When examining the compressed trajectory data, it was noted that the highest compression code length (i.e.least compressed) values belonged to flocking behaviours with circling or a large number of twists and turns.
A third experiment involved creating variations of traditional Braitenberg Vehicles,by placing sensors on ten different possible locations on the simulated vehicle, and incorporating Brooks’ subsumption architecture, which resulted in different unusual behaviours being produced. The vehicle was allowed to explore a simulated environment with walls on the border which contained a single bright light in the centre. With a search space of over 10,000 simulations, by using PPM compression, clustering was able to effectively discover interesting emergent behaviour produced from a simple interaction of light and proximity sensors on a vehicle and a single light source.
From the three sets of complex systems examined, it is evident that the novel
compression-based algorithms created were capable of automatically clustering similar behaviours together and, from that, interesting behaviours were automatically retrieved from those systems. These novel algorithms and techniques have useful potential in the science of complex systems and modelling to help expedite the exploration of a substantial search space of simulations in order to automatically discover interesting behaviours.