Telecom Paris
Dep. Informatique & Réseaux

J-L. Dessalles Home page

November 2019



Module Athens TPT-09

    Emergence in Complex Systems      From nature to engineering
                                other AI courses

Contents


Please answer in English!
    This Lab work is based on the use of Evolife. If necessary, install it.

Emergent phenomena

Heterocline cycle

After Sigmund, K. (1998). The population dynamics of conflict and cooperation. In Proceedings of the International Congress of Mathematicans, Documenta Mathematica 1, 487-506. (Link)

We suppose that we observe three species, such as bacteria in the gut. Suppose that species B dominates A, that C dominates B and that A dominates C. For example, species B develops both a substance that is poisonous for A and a substance that makes itself immune to the poison. Species C develops the antidote but avoids the burden of synthesizing the poison. Species A devotes no energy to synthesizing either the poison or the antidote.

The purpose of the study is to observe the dynamics of three species that are playing a rock-paper-scissors game. You may see an external demo.

You can study the phenomenon using Evolife. Launch Evolife from the Evolife directory with ‘Starter’. Load the Heterocline Cycle scenario and run it. You should observe the characteristic alternation between species.

Open the scenario file: S_HeteroclineCycle.py located in the directory Scenarii. Locate the function Species and read it. Explain why it takes some time, when one of the three species is dominant, for another species to overthrow it. You may look at the Genome windows when running the simulation. It displays the genome of all individuals horizontally. The vertical stripes result from the fact that individuals are similar. The first gene, which determines the species, corresponds to the first three bits on the left. The two other genes are not used at this point and are therefore neutral.


HeteroclineSpecies
What is the effect of a large mutation rate (e.g. 10‰)? Explain why.


    
Find he relevant parameters in the configuration editor, in the section: Scenarios/BehaviouralEcology/HeteroclineCycle. They are:
HeteroclineValues
Verify that the circular dominance is robust w.r.t. these values. Give an example of values that are significantly different from the ones given, and yet preserve the phenomenon.


    

Suggestions for further work

Cellular automata

Each cell in a cellular automaton changes its state depending on the current state of the neighbouring cells. There are various nice implementations of C.A. on the Web. For example this one (or that one if the latter does not run on your browser). You may also have a look at the cellular automaton page in Wolfram’s math world.
Evolife offers an implementation in the directory Other/CellularAutomata. You can run it by executing the local command Starter. Play with the cellular automaton and try to obtain:
Each cell in a cellular automaton takes the decision of changing its state or not, depending on its current state and the state of its neighbours. All cells apply the same rule. With two neighbours (left and right), there are 8 possible configurations (if states are binary), from 000 to 111. Each rule associates a new state to each configuration. This means that a rule can be defined by eight bits. There are therefore 256 different rules, that are conventionally numbered from 0 to 255. Rule 32 corresponds to the binary sequence 00000100 ( = 32 in reverse binary representation). This rules says that the fifth configuration (starting from 0), 101 ( = 5 in binary coding) is the only configuration that generates 1 as new state.

Define a rule that keeps any state constant. To do so, complete the association table:
000 → 0
001 → 0
010 → 1
. . .
Then read the last column bottom up. This gives you the rule number in binary form.

Similarly, find a rule that checks for parity (parity of the number of ones within the neighbourhood, including the cell itself).

Try rule 30. Observe that the rule is quite ‘interesting’.
(Note that if you start with a different pattern such as P='01'*128, the results is no longer interesting.)

CellularAutomaton
Play with the cellular automaton and mention another rule that you find interesting.


    

Suggestions for further work

Paths

Path formation

The program Walker.py (in the directory Other/PathFinder) implements the process of path formation. Individuals are attracted to their target, but they also move more easily when following existing tracks.

The ground displayed on the image shows a path (white line) getting around hills (white zones) and depressions (dark zones). Run the program by executing the local command Starter. The Configuration Editor allows you to change parameter values. Several configuration are pre-stored. The one named geodesic shows how the path finder can find the shortest path to the target. Other configurations illustrate the fact that paths may share parts instead of being shortest. These experiments illustrate the exploration/exploitation dilemma.

Load these various scenarios in turn. You may change the number of starting points (located on the left of the landscape). You may also vary the number of agents that walk simultaneously.


PathFinder 1


    
What happens if you increase the pheromone attractiveness (e.g. 25) and diminish the target attractiveness (e.g. 0.1)?
PathFinder 2
The parameter slope aversion controls the avoidance to slope (both negative and positive). You may edit the file Walker.py and change this to avoid only positive slopes. Copy the new code line in the box below.


    

PathFinder 3
What happens?


    

Paterson’s Worm

    [by Félix Richart]

The Paterson’s Worm experiment is an attempt to model the behaviour of prehistoric worms, and especially their foraging patterns.
The simulated worm moves on a triangular grid. Each time it passes on a segment, it eats every food on it. A path on which the food has already been eaten will never be visited again.
The worm doesn’t move randomly. When on a node, it analyses paths that have not yet been eaten to decide where to go next. If the worm already encountered the same distribution of eaten and non-eaten paths, it will take the same decision as when it encountered the pattern first.

To access the Evolife implementation of paterson’s worm, go to the directory Other/Worm, and run it with the command Starter.
The 6 directions the worm can take are numbered from 0 to 5, where 3 is always the direction from where the worm comes, and 0 the direction in front of it.

A rule for the worm is a list of digits between 0 and 5. It works this way:

The simplest rule is the rule "0". The worm initially goes to the right. It encounters the following distribution: only direction "3" is eaten (the one it came from). Since it is a new distribution, it reads the rule and chooses path "0". It moves straight ahead on path "0" and finds the same distribution as before: no direction is eaten, except for direction "3" (the one it came from). So it copies its previous decision and goes straight ahead again. And so on indefinitely.


Paterson Worm 1
Try the rule "0" (you can set it up in the parameters). Then try the rule "1051". What is the main difference between the two rules?


    

Some rules gives eternal worms, other ones give finite ones. Among the 412 possible rules (excluding the symetric ones), 73 are eternal, 336 are finite. 3 of them are uncertain, which means that no one knows whether they end, even if they have been tested up to very large numbers of steps.

Set the size of the grid to 100 and the speed of the worm to 1000. Try the rules

(Do not wait until the end because it might take eternity)
These three rules lead to apparently complex behaviour. The worm that follows the first one is infinite. The second worm dies after more than 3 billion steps, and the third one is one of the uncertain cases.

You can find on the french wikipedia page of the Paterson’s Worm the duration of each rule. Interesting rules are also indicated in the file possible_worms.txt. Try some of them. You may also run the Evolife Algorithm with a random rule by writing "random" as a parameter instead of a rule.

Paterson Worm 2
Can you find a simple rule that leads to a complex pattern?
Indicate a rule you consider interesting. Explain why.


    

Suggestions for further work

Morphogenesis

You may watch this video (in French) showing the complexity of nest building by ants.

(click on image to animate)    

Evolife offers currently only a sketch implementation of Turing’s Reaction-Diffusion model, using the Gray-Scott implementation (see animation). You’ll find it in the directory Other/Morphogenesis. You can run it by executing the local command Starter. As its stands, the program offers a basic implementation of the Gray-Scott reaction. You may play with the parameters that are accessible through Starter. Don’t change them too abruptly, as the Gray-Scott model is quite sensitive to slight deviations.

Suggestions for further work

Emerging patterns

Physical phenomena offer a variety of situations in which patterns are observed to emerge in an unexpected way. This video (signalled by Félix Richart, thank you!) shows how a vibrating metallic plate may generate a whole gamut of stationary waves, depending on the frequency.

Chaos

Some deterministic dynamical systems exhibit behaviour that is apparently random. Chaos theory is concerned with such systems. Many of them obey simple generative rules.
For instance, the Mandelbrot set (right) is generated by the iterated application for the function f(z) = z2 + c, where z is a geometrically interpreted complex number and c is a constant (starting from z=0).

Note that these systems look random, but are not random. By definition, random objects cannot be compressed. Chaotic systems can be defined by their generated procedure, which correspond to huge compression if the procedure is simple.

Chaotic systems may be highly sensitive to initial conditions (this is the so-called butterfly effect). The complexity of the initial conditions has to be counted when considering compression; it may impact (if high precision is required) the complexity of the chaotic system.

Emergence of Fractals

    [by Félix Richart]

Fractal forms may emerge from a simplistic non-deterministic procedure. Consider a real coefficient c between 0 and 100 and k points in the plane (vertices). Draw an additional random point P0. Take a random integer i between 1 and k. Draw a new point P1 at c% of the distance from P0 to the ith vertex. Repeat the procedure endlessly. If c is not too large, a fractal shape repeating the initial shape should emerge.

See this video for a detailed demo.

Go to the Evolife/Other/ChaosFractals folder and run the local command starter. Load the Chaos_triangle configuration. Run the program and observe the emergence of a dotted fractal triangle.
Here, in "Shape/InitialDots", you put a list of cartesian coordinates of the intial dots to generate the fractal. You can put any number of dots in the list. The "Shape/Coef" parameter sets the distance ratio between your current dot and the initial dots and the next one.

First try with 3 initial dots and a coef of 0.5 to see the fractal appear.

ChaosFractals
Start from a square: [(10,10),(10,90),(90,90), (90,10)].
What is the max value of the coefficient that leads to a fractal ?


    

You can now play with the program, try various coefficient values and initial dots to see fractals emerging.

Suggestions for further work


            

Back to the main page