Laboratory of Intelligent Systems - Evolution of cooperation and division of labour



Evolution of Cooperation in Artificial Ants



*** This project was completed in October 2007. ***

Please have a look at current follow-up projects on the
Evolution of Division of Labour and on the Evolution of Communication



Understanding the sociobiology of
social insects using mathematical
models, computer simulations and
collective evolutionary robotics.



Markus Waibel,
Danesh Tarapore,
Prof. Dario Floreano,
Prof. Laurent Keller




Ants compose about 15% of the animal bio-mass in most terrestrial environments. Two key features of the enormous success of ants and other social insects (e.g., termites or honey bees) are the ability to cooperate and to perform efficient division of labor. These features, which allow social insects to perform complex tasks in a variety of different environments, can be of great benefit for artificial intelligent systems, such as software agents and autonomous robots.

Genetic relatedness is known to have played a major role in favoring the evolution of cooperation in social insects and in the evolution of complex life in general (JM Smith, E. Szathmary 1995). The biological theory of kin selection, formalized by JBS Haldane (1955) and W. D. Hamilton (1963), explains how individuals can exhibit strategies that favor the reproductive success of genetic relatives, even at a cost to their own survival and/or reproduction. One part of this project is concerned with comparing the evolution of cooperation in highly related, i.e homogeneous agents vs. different, i.e. heterogeneous agents.

The high levels of cooperation found in social insects have given rise to the idea that colonies can be viewed as "super-organisms", operating as a single functional unit. This raised an important question about the functioning of evolution: the question of the 'Level of Selection'.
The process of evolution can be understood as a procession of ever more complex replicators: simple molecules -> molecular compartements -> independent replicators -> chromosomes -> RNA -> DNA -> prokaryotes -> eukaryotes -> asexual clones -> sexual populations -> protists -> animals/plants/fungi -> solitary individuals -> colonies/castes (JM Smith, E. Szathmary 1995). This suggests that selection always acts at the highest level, i.e. at the level of the "super-organism" for colonies of ants. However, such claims have been challenged both on theoretical grounds and on the observation that life within a colony is not always as harmonious as it may appear.



In 1976 R. Dawkins advanced the theory of the 'selfish gene', and today the 'gene' is recognized as the most important unit of selection in evolution. However, selection acting at the colony level leads to suppression of individual conflict and to an overall increase in group productivity in ants. Understanding exactly how and to what degree actual conflict is suppressed and how this influences group performance is the key to understanding the functioning of social insect societies.

The goals of this project were twofold: On the one hand, we studied the role of relatedness and levels of selection on the evolution of cooperation and labour division in ants, on the other hand we were interested in bio-inspired methods for automatic generation of cooperation and division of labour in artificial multi-agent systems.



Methods

This project investigated the role of relatedness and levels of selection on evolution of cooperation and labour division in ant colonies. Experiments were carried out in simulation and on groups of real Alice micro-robots on four test cases, (1) heterogeneous colonies with individual level selection, (2) heterogeneous colonies with colony level selection, (3) homogeneous colonies with individual level selection and (4) homogeneous colonies with colony level selection.

During the first stage of experiments, we implemented and used a very fast probabilistic simulator to conduct an initial analysis of these four cases. In this simulation, decisions were not based on individual controllers, but instead on a probabilistic model. Probabilities were estimated in test runs with the real robotic setup. The advantage of such an approach is its simplicity and speed, allowing for a fast evaluation of the parameter ranges and yielding a very complete picture of the space of possible solutions. Part of these results were published in Perez-Uribe et al., 2003 (see link at bottom of page).

In the second stage, we have finished the implementation of a physics-based, 2D simulator (available online here). Work on the simulator was conducted in cooperation with the ECAgents project.
As opposed to the probabilistic simulator, decision making was based on individual controllers, which allowed a transfer of behavior evolved in simulation to the real Alice micro-robots. Direct evolution of the desired behaviors on real robots is far too time consuming for tasks with a high number of parameters. Benchmarks of our simulator at the start of this project showed that its simulation speed compared very favorably to commercially available alternatives less adapted to the specific needs of our project.

Work on the real robotic setup was carried out in parallel to the simulations. A video of the simulation and the results of a transfer to hardware can be seen at the right.

Sim1.avi (17.8 MB)

Real1.avi (6.1 MB)


Hardware

Our experiments with colonies of Alice micro-robots led to the development of a setup that allows for fully automated evolution of robot controllers in hardware. We have constructed an arena equipped with a real-time tracking system and a robotic x-y table equipped with a magnetic arm to reposition foraging tokens in the robot arena. Further work included the development of a new extension module for the Alice micro-robots, including a linear camera, 2 infra-red sensors at the back of the robot, a long range infrared sensor as well as an additional battery module, boosting robot autonomy to about 20 hours. For more information on the micro-robots, please visit the Alice homepage. The automated hardware setup has been used for a first set of evolutionary experiments in hardware and is ongoing research at the end of this project.



Results of probabilistic simulations

So far, we have found that altruist behaviors are favored by colony-level selection and that altruistic behaviors have low probability of emerging in heterogeneous colonies evolving under individual-level selection. Concerning the prediction, made by some biologists, that groups should be more efficient when selection acts at the level of the colony and when there is higher relatedness within groups, we have so far found that homogeneous colonies, indeed, performed better than heterogeneous ones. Part of our results with the probabilistic simulator were published in Perez-Uribe et al., 2003 (see link below).

Results of physics based simulations

Preliminary tests with the physics-based simulator verify the results found with the probabilistic simulator. Homogeneous groups (3, 4) outperform heterogeneous groups (1, 2) in tasks that benefit from cooperation, with homogeneous groups with colony level selection (4) having the highest performance. This is in accord with our initial hypothesis for an overall group efficiency ranking of 4<3<2<1.

A video of the evolution of robot behavior over 150 generations can be downloaded at the right.

EvoShort-lowres.mpg (9.8 MB)

EvoLong.mpg (28.0 MB)