CELLULAR AUTOMATA EXPLORATIONS

Ant Colony Activity

by Richard J. Gaylord and Kazume Nishidate

In this column, we continue our exploration of the biological world. In the previous column,  we modeled the use of chemical scents  (pheromones) by ants to lay down trails which can be followed by other ants. Here, we will look at the activity (working and sleeping behavior) of ants in an ant colony.

While an individual ant is considered by many people to have no significance (hence the phrase 'crush like an ant'), the complex behavior of a 'society' of ants is rather fascinating (the so-called ant farm has long been popular among scientifically inclined young people). Various studies [Goodwin 1994, Gordon 1995] have shown that an individual ant cannot be trained to perform even the simplest of tasks and that groups of ants have no hierarchical order or 'chain of command' by which one ant directs the action of another ant. In the absense  of native intelligence and social control, the question is: How does the collective behavior carried out in a colony of ants emerge from the activity of the individual ants in the colony? It has been suggested [Goodwin 1994, Gordon 1995] that local interactions between ants, of the sort found in a cellular automaton, suffice to produce the observed organizational features of an ant colony. We will develop a CA which models the activity level of an ant colony over time as a function of the size of the colony.

The Ant Colony CA

The model employs a square lattice with reflecting boundary conditions whose interior sites are either empty or occupied by an ant which is in either an active or inactive state. The following statement describes how the sites in the lattice evolve over time [Goodwin 1994]:

"When in an active state, individuals move from one site to any adjacent, unoccupied site on a
lattice that defines the territory of the colony. If an individual moves to a site adjacent to one occupied by an inactive ant, the latter is stimulated to become active, but its activity will cease after a time unless it becomes spontaneously active or is simulated by another ant."

Unfortunately, this description is rather vague and it is necessary to be more precise in specifiying the rules of an ant colony cellular automaton.

In developing our ant colony CA program, we assume (based on what seems physically reasonable) that the lattice sites in the system are updated according to the following rules (it is  straightforward to modify our program for an alternative interpretation of the ant colony model): 

- an active ant moves to the adjacent empty site it faces, unless the move will result in a
  collision with another active ant.

- an active ant facing an adjacent site that is either on the border or is occupied by another ant
  stays put. 
  
- an active ant, whether it moves or not, randomly picks a direction to face in each time step and
  increments its 'activity time clock' (which keeps track of how many time steps have elapsed
  since the ant became active) by one.

- an active ant becomes inactive after s time steps. 

- an inactive ant becomes active either spontaneously or when an active ant is on an adjacent 
  site.

The system

The system consists of an 'n by n' square lattice whose sites have values which are ordered pairs, {x, y}.

The first component of the ordered pair is either the symbol, b, or an integer ranging from -1 to 4 where the values have the following meanings:

b  - a border site
0  - an empty site
-1 - a site occupied by an inactive ant
1  - a site occupied by a north-facing active ant 
2  - a site occupied by a east-facing active ant 
3  - a site occupied by a south-facing active ant 
4  - a site occupied by a west-facing active ant 

The second component of the ordered pair is an integer ranging from 0 to s where the value is an 'activity time clock' indicating the number of time steps that the ant has been in the active state. A site that is empty, on the border, or has an inactive ant on it, has an activity time clock value of 0. A site with an active ant on it has a value of 1, 2, .., s.

We start by randomly placing inactive and active ants on the sites of a (n - 1) by (n - 1) lattice, with a probability p. If the ant is active, it faces a randomly chosen direction and its time clock is randomly set between 1 and s.

antPopulation = 
    Table[{{-1, 1, 2, 3, 4}[[Random[Integer, {1, 5}] ]], 
             Random[Integer, {1, s}] }* Floor[Random[] + p], {n - 1}, {n - 1}] /. {-1, _} -> {-1, 0}

We decorate the antPopulation lattice with a border of sites having value {b, 0} on the left and bottom sides of the lattice using

antFarm = border[antPopulation]

where

border = Append[Map[Append[#, {b, 0}]&, #], Table[{b, 0}, {Length[#] + 1}]]&

Note: It's not necessary to place borders along all four sides of the lattice [this is  analogous to the use of one rather than two borders in the interfacial diffusion front CA]. The choice of which column (left or right) and which row (top or bottom) are decorated with a border is irrelevant.

The ant density on the ant farm is conserved in the system over time. It can be calculated using

antDensity = N[Apply[Plus, Abs[Sign[Transpose[Flatten[antPopulation, 1]][[1]]]]]/n^2]

When the system is large,  the ant density approaches the value of p.

The rules

The rules for the behavior of an ant during a time step, take thirteen arguments

ant[site, N, E, S, W, NE, SE, SW, NW, Nn, Ee, Ss, Ww]

The arguments represent the value of the site and the values of 12 neighbor sites : the nearest neighbors in the N, E, S, W directions, the nearest neighbors in the NE, SE, SW, NW directions, and the next nearest neighbors in the N, E, S, W directions (these values are needed to implement the 'excluded volume' constraint ).

The following rules describe the behavior of sites during a time step:

The function RND is a  random number generator used to determine the direction faced by an active ant .

RND := Random[Integer, {1, 4}]

For an inactive ant (a site whose value is {-1, 0}):

- An inactive ant adjacent to an active ant becomes active, randomly chooses a direction to face, and resets its activity time clock to 1.

ant[{-1,  0}, {x_?Positive, _}, _, _, _, _, _, _, _, _, _, _, _] := {RND, 1}
ant[{-1,  0},  _, {x_?Positive,_}, _, _, _, _, _, _, _, _, _, _] := {RND, 1}
ant[{-1,  0},  _, _, {x_?Positive,_}, _, _, _, _, _, _, _, _, _] := {RND, 1}
ant[{-1,  0},  _, _, _, {x_?Positive,_}, _, _, _, _, _, _, _, _] := {RND, 1}

- An inactive ant becomes active with probability r, randomly chooses a direction to face, and resets its activity time clock to 1.

ant[{-1, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := 
                            { -1 + # * Random[Integer, {2, 5}], #}&[Floor[Random[] + r] ]

For an active ant (a site whose value is an ordered pair whose first component is 1, 2, 3 or 4):

- An active ant become inactive after s time steps and resets its activity time clock to 0.

ant[{x_?Positive, s}, _, _, _, _, _, _, _, _, _, _, _, _] := {-1, 0}

- An active ant facing an adjacent site that is either on the border or is occupied by another ant, stays put, randomly chooses a direction to face, and increments its activity time clock by 1.

ant[{1, y_}, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{2, y_}, _, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{3, y_}, _, _, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{4, y_}, _, _, _, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _] := {RND, y + 1}

- An active ant facing an empty adjacent site that is also faced by another active ant (eg., an active right-facing ant that lies to the left of an empty site that is faced by an active left-facing ant lying to the right of the empty site) stays put, randomly chooses a direction to face, and increments its activity time clock by 1

ant[{1, y_}, {0, 0}, _, _, _, {4, _}, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{1, y_}, {0, 0}, _, _, _, _, _, _, {2, _}, _, _, _, _] := {RND, y + 1}
ant[{1, y_}, {0, 0}, _, _,_ ,_ ,_ ,_ , _, {3, _}, _, _, _] := {RND, y + 1}
ant[{2, y_}, _, {0, 0}, _, _, {3, _}, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{2, y_}, _, {0, 0}, _, _, _, {1, _}, _, _, _, _, _, _] := {RND, y + 1}
ant[{2, y_}, _, {0, 0}, _, _, _, _, _, _, _, {4, _}, _, _] := {RND, y + 1}
ant[{3, y_}, _, _, {0, 0}, _, _, {4, _}, _, _, _, _, _, _] := {RND, y + 1}
ant[{3, y_}, _, _, {0, 0}, _, _, _, {2, _}, _, _, _, _, _] := {RND, y + 1}
ant[{3, y_}, _, _, {0, 0}, _, _, _, _, _, _, _, {1, _}, _] := {RND, y + 1}
ant[{4, y_}, _, _, _, {0, 0}, _, _, {1, _}, _, _, _, _, _] := {RND, y + 1}
ant[{4, y_}, _, _, _, {0, 0}, _, _, _, {3, _}, _, _, _, _] := {RND, y + 1}
ant[{4, y_}, _, _, _, {0, 0}, _, _, _, _, _, _, _, {2, _}] := {RND, y + 1}

- An active ant facing an empty adjacent site vacates the site it is on.

ant[{1, _}, {0, 0}, _, _, _, _, _, _, _, _, _, _, _] := {0, 0}
ant[{2, _}, _, {0, 0}, _, _, _, _, _, _, _, _, _, _] := {0, 0}
ant[{3, _}, _, _, {0, 0}, _, _, _, _, _, _, _, _, _] := {0, 0}
ant[{4, _}, _, _, _, {0, 0}, _, _, _, _, _, _, _, _] := {0, 0}

For an empty site (a site having an ordered pair {0, 0}):

- An empty site faced by two or more active ants remains empty.

ant[{0, 0}, {3, _}, {4, _}, _, _, _, _, _, _, _, _, _, _] := {0, 0}
ant[{0, 0}, {3, _}, _, {1, _}, _, _, _, _, _, _, _, _, _] := {0, 0}
ant[{0, 0}, {3, _}, _, _, {2, _}, _, _, _, _, _, _, _, _] := {0, 0}
ant[{0, 0}, _, {4, _}, {1, _}, _, _, _, _, _, _, _, _, _] := {0, 0}
ant[{0, 0}, _, {4, _}, _, {2, _}, _, _, _, _, _, _, _, _] := {0, 0}
ant[{0, 0}, _, _, {1, _}, {2, _}, _, _, _, _, _, _, _, _] := {0, 0}

- An empty site faced by one ant that has been active less than s time steps beomes occupied by the ant which randomly chooses a direction to face and increments its activity time clock by 1.

ant[{0, 0}, {3, y_?(# < s &)}, _, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1} 
ant[{0, 0}, _, {4, y_?(# < s &)}, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{0, 0}, _, _, {1, y_?(# < s &)}, _, _, _, _, _, _, _, _, _] := {RND, y + 1}
ant[{0, 0}, _, _, _, {2, y_?(# < s &)}, _, _, _, _, _, _, _, _] := {RND, y + 1}

- An empty site remains unchanged.

ant[{0, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := {0, 0}

- A border site remains unchanged.

ant[{b, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := {b, 0}

Note: While it may be off-putting to see the large number of rules (thirty eight, to be exact), these rules are very simple to read and understand (which is helpful). Moreover, the use of rules in a CA program offers a substantial benefit: it is quite easy to add, delete or modify the rules to obtain variations of the model (decreasing the time that we have to spend developing a program is quite important to us ).

Applying the rules

The following anonymous function is used to apply the rule function to the thirteen arguments representing a site and its neighbors:

MvonN[ant, #]&

where

MvonN[func__, lat_] :=   
  MapThread[func, 
                     Map[RotateRight[lat, #]&, {{0, 0}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}, 
                                                                  {1,  -1}, {-1, -1}, {-1, 1}, {1, 1}, 
                                                                  {2, 0}, {0, -2}, {-2, 0}, {0, 2}}], 2]

The ant farm evolves over t time steps by repeatedly applying the anonymous update function to the antColony lattice representing the configuration of the ant colony using the NestList function.

evolve = NestList[MvonN[ant, #]&, initConf, t]

We can strip off the activity time clock from each lattice site, leaving a list of the lattice configurations over time by mapping the anonymous function

latticeConfig = Function[y, Map[#[[1]]&, y, {2}]]

onto the list given in evolve.

Map[latticeConfig, evolve]

The Ant Colony Program

maggiesFarm[n_, p_, s_, r_, t_]:=
   Module[{antPopulation, antFarm, border, ant},

antPopulation = 
    Table[{{-1, 1, 2, 3, 4}[[Random[Integer, {1, 5}] ]], 
           Random[Integer, {1, s}] }* Floor[Random[] + p], {n - 1}, {n - 1}] /.  {-1, _} -> {-1, 0}; 
                       
border = Append[Map[Append[#, {b, 0}]&, #], Table[{b, 0}, {Length[#] + 1}]]&;                                                                                  
                                                                                               
antFarm = border[antPopulation];

RND := Random[Integer, {1, 4}];

ant[{-1,  0}, {x_?Positive, _}, _, _, _, _, _, _, _, _, _, _, _] := {RND, 1};
ant[{-1,  0},  _, {x_?Positive,_}, _, _, _, _, _, _, _, _, _, _] := {RND, 1};
ant[{-1,  0},  _, _, {x_?Positive,_}, _, _, _, _, _, _, _, _, _] := {RND, 1};
ant[{-1,  0},  _, _, _, {x_?Positive,_}, _, _, _, _, _, _, _, _] := {RND, 1};
ant[{-1, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := 
                            { -1 + # * Random[Integer, {2, 5}], #}&[Floor[Random[] + r] ];
ant[{x_?Positive, s}, _, _, _, _, _, _, _, _, _, _, _, _] := {-1, 0};
ant[{1, y_}, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{2, y_}, _, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{3, y_}, _, _, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{4, y_}, _, _, _, {-1 | x_?Positive | b, _}, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{1, y_}, {0, 0}, _, _, _, {4, _}, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{1, y_}, {0, 0}, _, _, _, _, _, _, {2, _}, _, _, _, _] := {RND, y + 1};
ant[{1, y_}, {0, 0}, _, _,_ ,_ ,_ ,_ , _, {3, _}, _, _, _] := {RND, y + 1};
ant[{2, y_}, _, {0, 0}, _, _, {3, _}, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{2, y_}, _, {0, 0}, _, _, _, {1, _}, _, _, _, _, _, _] := {RND, y + 1};
ant[{2, y_}, _, {0, 0}, _, _, _, _, _, _, _, {4, _}, _, _] := {RND, y + 1};
ant[{3, y_}, _, _, {0, 0}, _, _, {4, _}, _, _, _, _, _, _] := {RND, y + 1};
ant[{3, y_}, _, _, {0, 0}, _, _, _, {2, _}, _, _, _, _, _] := {RND, y + 1};
ant[{3, y_}, _, _, {0, 0}, _, _, _, _, _, _, _, {1, _}, _] := {RND, y + 1};
ant[{4, y_}, _, _, _, {0, 0}, _, _, {1, _}, _, _, _, _, _] := {RND, y + 1};
ant[{4, y_}, _, _, _, {0, 0}, _, _, _, {3, _}, _, _, _, _] := {RND, y + 1};
ant[{4, y_}, _, _, _, {0, 0}, _, _, _, _, _, _, _, {2, _}] := {RND, y + 1};
ant[{1, _}, {0, 0}, _, _, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{2, _}, _, {0, 0}, _, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{3, _}, _, _, {0, 0}, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{4, _}, _, _, _, {0, 0}, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, {3, _}, {4, _}, _, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, {3, _}, _, {1, _}, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, {3, _}, _, _, {2, _}, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, _, {4, _}, {1, _}, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, _, {4, _}, _, {2, _}, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, _, _, {1, _}, {2, _}, _, _, _, _, _, _, _, _] := {0, 0};
ant[{0, 0}, {3, y_?(# < s &)}, _, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1}; 
ant[{0, 0}, _, {4, y_?(# < s &)}, _, _, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{0, 0}, _, _, {1, y_?(# < s &)}, _, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{0, 0}, _, _, _, {2, y_?(# < s &)}, _, _, _, _, _, _, _, _] := {RND, y + 1};
ant[{0, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := {0, 0};
ant[{b, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := {b, 0};

MvonN[func__, lat_] :=   
  MapThread[func, 
                     Map[RotateRight[lat, #]&, {{0, 0}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}, 
                                                                  {1,  -1}, {-1, -1}, {-1, 1}, {1, 1}, 
                                                                  {2, 0}, {0, -2}, {-2, 0}, {0, 2}}], 2];

evolve = NestList[MvonN[ant, #]&, antFarm, t]
  ]

"Go to the ant thou sluggard; consider her ways"

The activity of the ant colony as a function of time is obtained by mapping an anonymous function which counts the number of active ants (given by the number of ordered pairs having a first component  of 1, 2, 3 or 4) onto the matrices produced by the maggiesFarm program.

activityHistory  = Map[Count[Flatten[#, 1], {x_?Positive, _}]& , evolve]

A plot of the ant colony activity over time is then obtained using

ListPlot[activityHistory]

Below we compare the behavior of an ant colony in which active ants become inactive after ten time steps at a low density (p = 0.1) and high density (p = 0.9).

SeedRandom[8]
activityHistory = 
   Map[Count[Flatten[#, 1], {x_?Positive, _}]&, 
              Drop[maggiesFarm[10, 0.1, 10, 0.15, 250], 50]];

ListPlot[activityHistory, 
         PlotJoined -> True, 
         PlotRange -> {{0, 200}, {0, 10}},
         AxesLabel -> {FontForm["time step", {"Helvetica", 12}],
         FontForm["activity", {"Helvetica", 12}]}
        ];

SeedRandom[8]
activityHistory = 
   Map[Count[Flatten[#, 1], {x_?Positive, _}]&, 
              Drop[maggiesFarm[10, 0.9, 10, 0.15, 250], 50]];

ListPlot[activityHistory, 
         PlotJoined -> True, 
         PlotRange -> {{0, 200}, {0, 100}},
       AxesLabel -> {FontForm["time step", {"Helvetica",12}],
         FontForm["activity", {"Helvetica", 12}]}
        ];

Comparing the two plots, we see that the chaotic activity pattern at low ant density is replaced by a periodic rhythm at high ant density.  

The periodicity displayed by the ant colony is characteristic of an excitable medium system [see [Gaylord and Nishidate 1996] and Gaylord and Wellin 1995, chapter 11], which consists of spatially distributed elements that undergo an 'excited-refractory-receptive' cycle, becoming 'excited' as a result of interacting with neighboring elements, and subsequently returning incrementally to the quiescent state in which they are again 'receptive' to being excited. In the ant colony model, the activated ant , {x_Positive, 1}, represents the excited state, the active ant, {x_Positive, y_?( # > 1 &)}, represents the refractory state, and the inactive ant, {-1, 0}, represents the receptive state.

Computer Simulation Projects

1. Harvester ants are extremely industrious (hence the biblical quote from Solomon used in the title of the previous section) and they carry out a number of tasks. Four chores that take place outside the nest have been identified:  foraging (retrieving food from a region around the nest), patrolling (responding to damage to the nest or invasion by alien ants and choosing the direction taken by foragers), nest maintenance (modifying the chambers of the nest and carrying away dirt from the nest entrance, and midden work (building and sorting the colony refuse pile and collecting and piling stones on the nest surface). 

Each ant is able to carry out any of these tasks and when performing a task, each ant can be in either an active or inactive state. At a given time, the task performed by a particular ant (and hence the number of ants engaged in a particular task) depends on the number of ants that are engaged in the various tasks. 

Create an ant colony CA where an ant determines at each time step, which of eight states (inactive forager, active forager, inactive patroller, active patroller, inactive nest maintenance, active nest maintenance, inactive midden work, active midden work) to be in, using a two-step process:

First, an ant in a given task category (forager, patroller, nest maintenance, midden work) becomes or remains active (inactive) if the the majority of the ants performing the same task in its immediate neighborhood (nearest neighbor sites), excluding itself, are inactive (active).

Second, an active ant switches from the task it is doing to another task if the majority of the active ants in its enlarged neighborhood (nearest neighbor and next nearest neighbor sites) are performing the same task as the ant.

General References

Holldobler, Bert and and Wilsob, Edward O. "Journey to the Ants", Belknap/Harvard University Press (1994).

Goodwin, Brian. 1994. "How The Leopard Changed Its Spots", Weidenfeld & Nicolson, UK. Chapter 3 "Life, an excitable medium ".

Gordon, Deborah M. "The Development of Organization in an Ant Colony", American Scientist, 83 (Jan.-Feb.), (1995), 50-57.

Gaylord, Richard J. and Wellin, Paul R. "Excursions in Programming. Contagious Spreading", Mathematica in Education and Research, Vol. 5, No 2, 31-36.

Gaylord, Richard J. and Nishidate, Kazume, "Computer Simulations with Mathematica: Explorations in Complex Physical and Biological Systems", TELOS/Springer-Verlag (1994).