Autómata Celular: ¡Hormiguitas!

HormigasDurante el tiempo que estuve en Alemania de beca Erasmus cursé una asignatura dedicada a los Autómatas Celulares. En principio son construcciones que permiten simular sistemas de una manera concreta:

Se representa un espacio en "celdas" o "células". Cada célula se comporta de un modo relativamente sencillo, y lo que es más importante, solo puede cambiar de estado (entre varios posibles definidos) basándose en los estados de las que la rodean (y de sí misma). Una característica muy importante de estos autómatas es que todas las células cambian de estado al mismo tiempo.

Bueno pues el ejercicio que hice para sacar la asignatura es el que presento en estas páginas: Simulo un campo con comida esparcida aleatoriamente y algunas hormigas que se mueven por el recogiendo y soltando la comida. Implementando reglas verdaderamente sencillas se consiguen comportamientos "globales" bastante interesantes, como por ejemplo, la agrupación de la comida, que inicialmente se encuentra esparcida.

En lo que sigue describo el sistema con detalle. El único inconveniente es que está en inglés (asi se exigía). Si tengo tiempo en un futuro no muy lejano lo traduciré al español.

Para la ejecución de los applets de ejemplo es posible que necesites instalar la Máquina Virtual de Java. Si la necesitas puedes descargarla en la página de Java de Sun.

 

Proposal of Cellular Automata: Introduction

During my studies in the University of Granada (Spain) I have paid special attention to some specific ways to solve some problems using heuristics based in the behaviour of ants and other social insects. In fact I'm making a short investigation about parallel aproaches in Ant Colony Optimization (ACO) algorithms in order to achieve my degree in Computer Science.

This kind of algorithms try to solve some difficult problems in an "easy" and "efficient" way, but I don't think they are easy to transform into a Cellular Automata. But from the bibliography that I have readed about this kind of metaheuristics and the behaviour of social insects I'm trying to develop a small system to simulate some behavior that is asociated with Ants.

As a first global approach the system would try to simulate the way that ants group the food that is dispersed over the ground. One of the important points in this problem is that there are no strict rules about how they make this job of grouping food, but we can have some kind of easy description about what they usually do or not when they find food. Is because of this that I think that an approach using a Cellular Automata could be effective, because it would also give me quite a wide range in order to experiment with it.

Spacial Component

Is very easy to describe what will be the space that the Cellular Automata will simulate. We will have the space where ants and food will be intially randomly situated. In this space ants will have the posibility of moving, probably only to the nearest places in it.

One thing I'm not sure about is what kinf of lattice should I use in order to have a good representation of the ground. Of couse a square one would be very easy to implement, but I think an hexagonal one would be more interesting because it could reflect in a more effective way the great range of directions that ants can take during their walks. Of course in reality they can move in a continuous range of directions, but that should be one discretization for our system.

Time Evolution

The ants will move around the lattice searching food, picking it up and leaving it on the ground. I don't know what would really represent one quantum of time in our system in seconds of "real time", but maybe the easiest assumption that we can do is that one quantum correspond to the time that takes an ant in order to move to an adjacent cell in the lattice. This time would also be equal to the time that they need to pick up food or leave it on the ground, that means that in a single step of our system an ant cannot move to the adjacent cell and pick up food or leave food in the ground, just one of these three actions.

Transition Rules

There are not too much rules directing the behavior of our system, but here I will make a short description in a not very formal way in order to understand them easily.

With this general rules we can construct our first approximation to the Cellular Automata. Of course we should make some other assumtions in order to make the system work fine. For example we should avoid two ants from being in the same cell at the same time, and we should also avoid two pieces of food to be in the same place, except if one is carried by the ant on it and the other is in the ground.

States

The sates of our system are easy to describe. We should take care about two independent kinds of information: The food in the ground and the ants position (and if they are loaded with food or not). We can make a short table to see this posible states of a particular cell:

Food on the Ground There is an ant here? Has the Ant food with it? State number
False False - 0
False True False 1
False True True 2
True False - 3
True True False 4
True True True 5

Watching the table we can see that these states are simple but would make us able to manage our system easily (at least I hope that :-) ).

Parameters

There are too much parameters to play with and experiment beacuse in the description of our transition rules we have talked about "greater or lower possibilities" but we have not discussed an exact way to assign this probabilities, so the ants could be more refractory or not to pick up food or to leave it, depending on the amounts of food sourrounding it, etc.

We can also choose some parameters for the inicialization of our system, because the whole behaviour of the systom will depend very highly on the amount of ants and food in the ground.

Evolution

I think a general idea of how will the automata work has been given in the last paragraphs but here I will try to summarize the way of acting of the ants:

One ant moves randomly in our space. It can casually find food on the ground, so it should take the decision of picking it up to move it or leave it there. To make this decision it "looks" around and if it notices there is not too much food it takes the food, because it is "dispersed". In case the food is sourrounded by too much food the ant will probably "understand" that the food is packed and would continue moving. When an ant has some food and finds an empty place it "thinks" about the posibility of leaving the food or continue moving. For that it also "watchs" at the neighbour places. If there is too much food it would probably leave the food (it will be packed), if there is not it will continue carrying it.

Possible extensions

This is a very simple model that can be "improved" without too much effort in order to take care about other phenomena that take place in the enviroment of ants. For example I think there should not be very difficult to simulate some kind of "wind" that randomly move a little bit some food, or even static obstacles that ants cannot cross. I think if everything goes right with the first little model that I have described I will try to simulate this or other variants in order to see if it is stable when "external forces" play game in our model.ç

 

Description of the Problem

The problem I have chosen to simulate using CA is the way ants collect and group food. We suppose that ants behave in an easy way: they move randomly across the available space, avoiding being two at the same point in the same time, picking up and leaving food.

Their primarily mission is to group the food, and for that they use a very simple rule. If there is too much food surrounding a place and they are carrying food they assume they should leave the food there (there will be a "pile" of food) and if there is food with no other food around they should take it to transport it to some other place where the food is being packed.

I also want to simulate some other easy aspects as "obstacles" in the ground and some kind of wind, that can make the food dissapear or appear randomly at certain points.

There are some facts that we should care about:

C.A. Solution

The solution to the problem using a Cellular Automata was basically described in the previous e-mail, so now I'm going to explain more concrete issues about the automata, and the problems I had when programming it, and also the solutions I have found to them.

The first thing to remark is that we use a hexagonal Lattice to represent the world where ants will be moving. The most important reason for choosing this kind of lattice is that its structure and simetry gives more flexibility to the movement of the ants, which can move in 6 different directions instead of four for easier squared lattices. The type of boundary that I have chosen is periodical (a torus topology), because it gives a better aproximation to a very big field where ants can move, and can always be restricted to a closed area using "obstacles".

Basically one cell in the lattice can be Empty, with Food or be an Obstacle. Also one cell can have an ant or not, and this ant can carry food (is charged) or not. Every cell has also one direction, which represent the direction where an ant wants to move and also the preference in case that more than one ant want to move into an empty cell. This will be explained later.

The rules concerning obstacles are really very easy, one cell will be always an obstacle. On the other hand we should take care that no ant will try to go to an obstacle cell, and also we should take care about counting obstacles or not when an ant should decide to pick up or leave some food on the ground (if we want the ants to pack the food around obstacles they should count the cells with obstacles when choosing the probabilities of picking up or leaving food fron/on the ground).

If we do not look at ants, the rules concerning the food are very easy: One cell with food will have food in the next step, and one cell without food will not contain food after one step. Here I introduce the concept of wind. We will have a certain probability that food gets into an empty cell, or that food is "lost" because of the wind. The probability for both cases is the same, so we can assumme that the average amount of food in the whole lattice will be constant to the initial one. I wanted to simulate this wind to try to see if the systems is capable of reacting when there are external random forces that change the food field in a way that at first sight is not predictable at all.

The more complicated part to simulate in our system is the ants behavior. Since only one ant can be in one cell in a concrete moment we should look at the directions where they wanted to move, if the destination cell is occupied, or if it is not occupied if it is another ant that also wants to go there.

For this purpose we make two different substeps, the first one to determine the directions in which the ants want to move, and the second one where we really move them and solve conflicts when two or more want to go to the same cell.

In the first substep we randomly choose one direction from the six available, but we should avoid that an ant determines to go to an occupied cell. The reason is easy, it does not know if the cell will be empty, because maybe this ant in the destination cell is not going to move (maybe it cannot do it). Also we can think the an ant do not think about going to an occupied cell because the previous one should make there their job, so if it gets there there is no other thing to do. So if the destination cell is occupied we should try to choose another direction. If the six directions are occupied the ant cannot move, and then it gets "sleepy" (that will be represented with a big dot in the program). This situation is very strange, and takes place only when the amount of ants is very big. At the beginning of the simulation every ant is supposed to be sleepy in order to get into this first substep of moving.

This substep also makes another decision. When a cell does not have an ant it chooses one direction randomly. This direction will be necesary in the case that two or more ants want to move into the same cell. The preference will be to the ant which is in that direction (if there is no ant in this direction we choose the first one following the six directions in a concrete order, for example clockwise).

The second substep is a little bit more difficult because we should examine more possibilities.

The first and easiest one is what happens with a cell that does NOT contain an ant. It is obvious that if one of its 6 neighbours has an ant which wants to go into it, it should get occupied by an ant. If none of the neighbors have an ant that wants to move there the cell will remain unoccupied.

If in the cell there is an ant, but it is sleepy, it should remain there, and that is because previously we have realised that there is no free cells surrounding that one.

If the cell has an ant and it wants to move it should realize that will not have a conflict with another ant moving to the same destination cell. The way of assuring that is not very complicated, but should be analyzed carefully. We take our destination cell (which is one of our closest neighbours), and we look if we are the ones with preference for this destination cell. For that we use the direction that was randomly chosen in the first substep. If we have preference we are the ones that have moved, so the cell will have no ant in the next step, and if we don't have the preference, we should remain in our cell, and in the next step the ant will choose another possible direction.

If we look at the source code it is not very complicated since it has some auxiliar functions which calculate the cell that has preference from the neighbours and so one.

Maybe is interesting to remark that in this substep we use a bigger neighborhood that the closest six neighbours. In fact we use the closest neighbors of every neighbor (that sounds tricky, but it is just the cells that are two cells away from the selected cell).

Finally I just want to say that the two substeps must be done in this exact order because the decision for the direction should took place when every ant is in its place. The only problem is that for visualization that is not so good, because if we make the two substeps and then stop to show how the configuration is, we really do not appreciate in which direction are moving the ants and where are the conflicts, so in my program I have divided the substeps and the visualization takes place between them.

The last thing is to decide when an ant takes or leaves food from / to the ground. That is made easily using two little tables of probabilities. We just count the food surrounding a cell and then look the probability of taking or leaving the food (it depends only in if the ant is charged or not and if the cell has food or not on it). This probabilities are adjustable in the program, so you can try different conbinations to see what happens. Of course usually the probability for picking up food when it has no food surrounding should be very high and leaving it when it has too much around. In the following examples we will see how this probabilities really determine the stability and result of the system.

Here is the Pseudo Code description for the transition of one cell:

if there is an ant {
  We choose a direction.
  Until a free destination cell is founded we change de direction.
  If there is not a free cell around {
    the ant gets sleepy.
  } else {
    We choose a direction to give preference in case of conflict.
  }
  If the cell is an obstacle {
    It will be an obstacle (return)
  }
}
If there is NO ant {
  If there is one ant that wants to move here {
    The cell will have an ant
  } else {
    The cell will remain unocuppied
  }
}
If there is an ant and it is SLEEPY {
  The ant stays here
}
If there is an ant but it is NOT SLEEPY {
  If it has the preference to get into de destination cell {
    The ant moves so the cell gets unoccupied
  } else {
    The ant remains here
  }
}
If there is an ANT that is CHARGED and the cell is EMPTY {
  We count food surrounding
  We choose the probability of leaving the food
  We find if the Ant should leave or not the food (random() < selected probability)
} else if there is an ANT that is NOT CHARGED and the cell contains FOOD {
  We count food surrounding
  We choose the probability of leaving the food
  We find if the Ant should pick up the food
}
// WIND!!
If the cell does have NO FOOD {
  If the wind is strong enough (again a random number < prob of wind) {
    The cell gets food from the wind
  }
} else if the cell HAS FOOD {
  If the wind is strong enough (again a random number < prob of wind) {
    The cell looses the food
  }
}

Source Code

Here are the sources for everything in the applets. The really important things concerning CA are in the classes AntCell & HexTorusLattice, the rest are basically supporting classes and interfaces with the user. I hope it is easy to understand. If there is any problem, please let me know and I will explain everything in more detail.

AntCell.java -----------------> Where the steps are made, and everything is calculated
HexTorusLattice.java --------> Facts about the hexagonal latticeand the boundary conditions
AntLattice.java --------------> Basically for initialitations
Cell.java ---------------------> Abstract class for a cell.
FramePrincipal.java ----------> Main class and Applet
GraphicLattice.java ----------> Graphic interface for the lattice.
InitDialog.java ---------------> Dialog to edit options
ProbDialog.java -------------> Dialog to edit the probabilities

Experiments

Here I will present some examples of the CA to show the main characteristics of it. The brown cells are empty cells, the gray cells are obstacles, the green ones are cells with food. The black ants do not carry any food, but the red ones are carrying food. If one ant is a "big dot" means that the ant is "sleepy".

The first example is only to ensure that the ants move correctly and that the boundary conditions work fine. The ants move around the lattice, and they do not appear nor disappear. They also don't have problems with the obstacles, and they solve every possible conflict. It is also interesting to experiment with a very large number of ants in order to see some patological cases, for example when every place is fully occupied and then every ant is sleepy. To change that options you must only click on the Initializing button.

EXPERIMENT 1: OPENS IN A NEW WINDOW

 

The second experiment is an easy one, to show the border and how they pick up food and leave it in the ground. The probabilities are easily assigned as follows:

Food surrounding Pick Up Prob. Leave Prob.
0 6 / 6 = 1.0 0 / 6 = 0.0
1 5 / 6 = 0.83 1 / 6 = 0.16
2 4 / 6 = 0.67 2 / 6 = 0.33
3 3 / 6 = 0.5 3 / 6 = 0.5
4 2 / 6 = 0.33 4 / 6 = 0.67
5 1 / 6 = 0.16 5 / 6 = 0.83
6 0 / 6 = 0.0 6 / 6 = 1.0

In this example there is no wind to see just how the ants work. This simple example do not work as we could expect. The ants move the food, and it looks a little bit more grouped after a few steps, but it really continues very dispersed. That is because the probabilities of picking up food when there are much food surrounding and leaving it when there is not too much are not small enough (and vice versa) and so the ants pick up very frequently packed food and leave food in places where it is not packed very often.

EXPERIMENT 2: OPENS IN A NEW WINDOW

 

The third experiment shows a distribution of probabilities that makes the ants work in a more efficient way:

Food surrounding Pick Up Prob. Leave Prob.
0 1.0 0.0
1 0.99 0.01
2 0.88 0.12
3 0.5 0.5
4 0.12 0.88
5 0.01 0.99
6 0.0 1.0

I have also setted a little wind, so some food will randomly appear and dissapear. In addition to that I have set the flag CountObstacles to TRUE, so usually the groups of food will be surrounding the obstacles.

As we can see the ants work fine and group the food as we expected. Playing a little bit with every parameter show us how they affect in the whole behavior of the system.

EXPERIMENT 3: OPENS IN A NEW WINDOW

 

The last example that I wanted to show is a degeneration of our system. If we use the following probabilities:

Food surrounding Pick Up Prob. Leave Prob.
0 0.0 1.0
1 1.0 0.0
2 1.0 0.0
3 1.0 0.0
4 1.0 0.0
5 1.0 0.0
6 1.0 0.0

With this we are telling that we want the food to be as dispersed as it could be. When the food has surrounding food it is always taken, when it do not have any it is leaved there. Here the obstacles are not counted to select the probabilities, so the food can be near the obstacles.

EXPERIMENT 4: OPENS IN A NEW WINDOW