Distributed Evolution of Swarms

This page is a short summary of my diploma thesis (equivalent to master's thesis).

Throughout the thesis, a generic software infrastructure was developed for performing experiments in swarm evolution. Given this infrastructure, new experiments can be implemented in a very efficient way. Additionally, the software is capable of parallelizing experiments on a heterogeneous computer cluster in an efficient and robust way, thus enabling large scale evolution experiments with less restrictions in swarm behavior evolution than related work.

Different to related work, in my experimental setup, the evolution of behaviors was much less narrowed down by common constraints. For instance, parameters of sensors and acting elements were evolved, extensive simulations were performed following realistig physical laws, the swarmer controllers were growing, recurrent, evolvable neural nets, and much more.

Furthermore, efficient physics simulation techniques were implemented and used. To distribute the simulations on many computers using local area networks as well as the internet, a client-server protocol stack was implemented.

After the implementation period, a family of nature-inspired evolution experiments with different environments and appropriately modeled swarmers was performed (10 experiments with 10 evolutions each). Evolved swarms were first tested by an automated testsuite to decide whether detailed analysis and visual observation is applicable. How behavior is elicited using evolutions, is shown in the following Youtube-Video.

Throughout the original work, 10 experiments including 100 evolutions have been performed, and a vast variety of behaviours was elicited. Thus, it is presented, how volatile behavior patterns can be, that result from less constrained evolutions. Elicited patterns were discussed and extensively and presented in text, image and video material.

Given the presented artificial ecology and free evolutions, it seemed remarkably easy to evolve mechanisms that can be seen as cooperation among the swarm. Capabilities were measured to be of significant importances, that make no sense in individual behaviour (such as several communicational capabilities or social interaction forces).

The variety of evolved behaviours includes several behavioural patterns observed in nature, such as mutual inhibition of reproduction in order to budget food, sophisticated aggregation behaviour, marking food sources with pheromones, and exploration. Forms of communication were evolved, simple, though essential for the swarm. Behaviours were evolved which can be observed everywhere in nature – however, in a synthetical and, therefore, completely transparent analyzable way. Even though the experimental swarms were assembled using fictional individuals, the results exhibit the vast, inspiring potential of such free experiments in the field of synthetical biology. This potential is also shown throughout the following talk trailer on YouTube.

SwarmWorld is capable of thousands of simulation steps a second on a single CPU with possibly thousands of static objects in the simulated world, as well as (in this work) 15 to 50 swarmers. To the current extent, sensoric perceptions of each swarmer are handled by collision-detection mechanisms applied on sensoric areas and emitters contained in specific sensor domains (for instance, a sensoric domain “vision” would contain all visible objects as emitters and all visual fields of swarmers as sensoric areas).

The evaluations were distributed via TCP/IP and therefore carried out on a variable number of heterogeneous multi-CPU-computers in parallel. During peak periods, about 100 CPUs were used in parallel. Performance comparisons between multi agent simulation frameworks are difficult because of their dependence on both the different features every single system possesses and the kind of experiment to perform. Also, it is not the purpose of this paper to analyze the performance of our framework. In so far, we just constitute that the 70000 * 25000 * 10 = 1,75 * 10^{10} simulation steps per experiment (remember: one experiment contained 10 evolution runs), continuously simulating approx. 10 to 50 swarmers and possibly thousands of objects, could be carried out within 0.5 to 4 days. This represents an effective simulation speed of 50000 to 400000 simulation steps a second with realistic 2d rigid body physics taken into account. It is to note in this context, that both the number of PCs was fluctuating during runtime and most of the evolution time the calculation was slowed down to keep the calculating PCs available for daily work, so significantly higher speeds will be possible in the future.

Advanced experiments are planned to re-evolve beings known from nature and take the evolutionary timeline into account, which could shed light on how to really follow the paradigm of artificial life: to localize life as it is in its vast context of life as it could be.