"Mathematica in Education and Research" COLUMN

CELLULAR AUTOMATA EXPLORATIONS

by

Richard J. Gaylord and Kazume Nishidate

In our previous two columns we looked at the application of cellular automata to the modeling of physical phenomena, specifically phase segregation and phase transfomation in materials. In the next two columns we will turn from the material world to the biological world. We will  explore the behavior of social insects, specifically ants. In the first part, we will look at how ants lay down and follow trails (this is important in the foraging of food for the ant colony). In the second part, we will examine the synchronization of activity levels (sleeping and working) in an ant colony.

Chemotaxis

Introduction

Chemical signaling plays a major role in communications amongst the members of animal, bird, insect, and even bacterial societies (it has also been speculated that  some sort of chemical signaling occurs between humans) and these signals influence various sorts of social behavior (eg., mating and aggression) in these systems [Pennisi 1995]. Movement, in particular, is often governed by chemicals. For example, the production and emission of cAMP by slime mold amoeba and the attraction of the amoeba to this chemical brings about their aggregation into clusters when there is a scarcity of food, while the mass recruitment of ants to the collective task of food foraging employs the emission of pheromones by those ants carrying food, to lead other ants to the food source [Resnick 1994].

We will present a simple random walkers CA model [Resnick 1994] of chemotaxis, the movement in response to a chemical gradient, for the case where the chemical which attracts the walkers is emitted by each walker as it moves, and is dissipated into the environment in the absense of a walker.

The chemotaxis CA

The system

The  system consists of an 'n by n' square lattice with periodic boundary conditions. Each lattice site has a value which is an ordered pair. The first component of the ordered pair is a non-negative integer which represents the level of chemical attractant on the site. The second component of the ordered pair is an integer between 0 and 4 where the values have the following meanings:

0 - an empty site 
1 - a north-facing ant
2 - an east-facing ant
3 - a south-facing ant
4 - a west-facing ant

Initially, all of the sites have a zero level of chemical attractant and the sites are randomly occupied with probability p by random walkers facing randomly chosen directions.

initConf  = Table[{0, Random[Integer, {1, 4}] } * Floor[Random[] + p], {n}, {n}]

The update rules

A simple way to combine the effect of an 'active landscape' on the movement of random walkers is to first apply the rules for orienting the walkers and then apply the rules for diffusing the particles on the lattice, on each time step.

Orienting the walkers

The rules for orienting a walker take five arguments:

sniff[site, N, E, S, W]

where the five arguments represent the value of the site and the values of the four nearest neighbors in the North, East, South, and West directions, respectively.

rule #1 - an empty site remains unchanged

sniff[{a_, 0}, _, _, _, _] := {a, 0}

rule #2 - An ant orients itself so as to face the nearest neighbor site that has the highest chemical attractant level. If two or more nearest neighbor sites have the highest level of chemical attractant, the ant randomly chooses one of these sites to face.

sniff[{a_, _}, {n_, _}, {e_, _}, {s_, _}, {w_, _}] := 
           {a, #[[Random[Integer, {1, Length[#]}] ]]&[Flatten[Position[#, Max[#]]]&[{n, e, s, w}] ] }

Taking a step

The rules for surface diffusion take thirteen arguments:

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

where the thirteen arguments represent the value of the site, the values of the four nearest neighbors in the N, E, S, W directions, the values of the four nearest neighbors in the NE, SE, SW, NW directions, and the values of four next nearest neighbors in the N, E, S, W directions.

When an ant moves, it leaves behind a chemical scent to attract other ants. In the absence of an ant, the chemical scent that has been laid down dissipates.

These changes in the strength of the chemical scent are easily expressed in rewrite rules by using the twentyeight update rules of the multiple walkers CA with minor modifications.

In the following rules, the chemical scent on an occupied site that is vacated by an ant is increased by 1, while the chemical scent on an unoccupied site that remains empty is reduced by 1.

walk[{a_, 1}, {_, 0}, _, _, _, {_, 4}, _, _, _, _, _, _, _] := {a, 1}
walk[{a_, 1}, {_, 0}, _, _, _, _, _, _, {_, 2}, _, _, _, _] := {a, 1}
walk[{a_, 1}, {_, 0}, _, _, _, _, _, _, _, {_, 3}, _, _, _] := {a, 1}
walk[{a_, 1}, {_, 0}, _, _, _, _, _, _, _, _, _, _, _] := {a + 1, 0}
walk[{a_, 2}, _, {_, 0}, _, _, {_, 3}, _, _, _, _, _, _, _] := {a, 2}
walk[{a_, 2}, _, {_, 0}, _, _, _, {_, 1}, _, _, _, _, _, _] := {a, 2}
walk[{a_, 2}, _, {_, 0}, _, _, _, _, _, _, _, {_, 4}, _, _] := {a, 2}
walk[{a_, 2}, _, {_, 0}, _, _, _, _, _, _, _, _, _, _] := {a + 1, 0}
walk[{a_, 3}, _, _, {_, 0}, _, _, {_, 4}, _, _, _, _, _, _] := {a, 3}
walk[{a_, 3}, _, _, {_, 0}, _, _, _, {_, 2}, _, _, _, _, _] := {a, 3}
walk[{a_, 3}, _, _, {_, 0}, _, _, _, _, _, _, _, {_, 1}, _] := {a, 3}
walk[{a_, 3}, _, _, {_, 0}, _, _, _, _, _, _, _, _, _] := {a + 1, 0}
walk[{a_, 4}, _, _, _, {_, 0}, _, _, {_, 1}, _, _, _, _, _] := {a, 4}
walk[{a_, 4}, _, _, _, {_, 0}, _, _, _, {_, 3}, _, _, _, _] := {a, 4}
walk[{a_, 4}, _, _, _, {_, 0}, _, _, _, _, _, _, _, {_, 2}] := {a, 4}
walk[{a_, 4}, _, _, _, {_, 0}, _, _, _, _, _, _, _, _] := {a + 1, 0}
walk[{a_, b_}, _, _, _, _, _, _, _, _, _, _, _, _] := {a, b}
walk[{a_, 0}, {_, 3}, {_, 4}, _, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}
walk[{a_, 0}, {_, 3}, _, {_, 1}, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}
walk[{a_, 0}, {_, 3}, _, _, {_, 2}, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}
walk[{a_, 0}, _, {_, 4}, {_, 1}, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}
walk[{a_, 0}, _, {_, 4}, _, {_, 2}, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}
walk[{a_, 0}, _, _, {_, 1}, {_, 2}, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}
walk[{a_, 0}, {_, 3}, _, _, _, _, _, _, _, _, _, _, _] := {a, 3}
walk[{a_, 0}, _, {_, 4}, _, _, _, _, _, _, _, _, _, _] := {a, 4}
walk[{a_, 0}, _, _, {_, 1}, _, _, _, _, _, _, _, _, _] := {a, 1}
walk[{a_, 0}, _, _, _, {_, 2}, _, _, _, _, _, _, _, _] := {a, 2}
walk[{a_, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0}

Note: We have arbitrarily chosen to assume (in those walk rules that have a non-zero second component in the ordered pair on the rhs of the rule) that an ant retains its orientation when it attempts to move. However, the specific non-zero value that is used for the second component of the ordered pair is irrelevant since, as we will show in the next section, each ant chooses its orientation (using the sniff rules) immediately after attempting a move.

Applying the update rules

In a given time step, the sniff rules are first applied to the CA lattice, which we'll call lat, using

VonNeumann[sniff, #]&[mat]

where

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

and then we apply the diffusion rules once, using

MvonN[walk, #]&[VonNeumann[sniff, #]&[mat]]

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 sites in the lattice are updated over t time steps, starting with the initial lattice configuration, using the following operation.

NestList[MvonN[walk, #]&[VonNeumann[sniff, #]]&, initConf, t]

Note: It is also permissible to apply the walk rules before the sniff rules.

The program

chemotaxis[m_, p_, t_] := 
  Module[{initConf, sniff, RND, walk, sniffUpdate, walkUpdate},

   initConf  = Table[{0, Random[Integer, {1, 4}] } * Floor[Random[] + p], {m}, {m}];
               
   sniff[{a_, 0}, _, _, _, _] := {a, 0};
   sniff[{a_, _}, {n_, _}, {e_, _}, {s_, _}, {w_, _}] := 
           {a, #[[Random[Integer, {1, Length[#]}] ]]&[Flatten[Position[#, Max[#]]]&[{n, e, s, w}] ] };
   
      
   walk[{a_, 1}, {_, 0}, _, _, _, {_, 4}, _, _, _, _, _, _, _] := {a, 1};
   walk[{a_, 1}, {_, 0}, _, _, _, _, _, _, {_, 2}, _, _, _, _] := {a, 1};
   walk[{a_, 1}, {_, 0}, _, _, _, _, _, _, _, {_, 3}, _, _, _] := {a, 1};
   walk[{a_, 1}, {_, 0}, _, _, _, _, _, _, _, _, _, _, _] := {a + 1, 0};
   walk[{a_, 2}, _, {_, 0}, _, _, {_, 3}, _, _, _, _, _, _, _] := {a, 2};
   walk[{a_, 2}, _, {_, 0}, _, _, _, {_, 1}, _, _, _, _, _, _] := {a, 2};
   walk[{a_, 2}, _, {_, 0}, _, _, _, _, _, _, _, {_, 4}, _, _] := {a, 2};
   walk[{a_, 2}, _, {_, 0}, _, _, _, _, _, _, _, _, _, _] := {a + 1, 0};
   walk[{a_, 3}, _, _, {_, 0}, _, _, {_, 4}, _, _, _, _, _, _] := {a, 3};
   walk[{a_, 3}, _, _, {_, 0}, _, _, _, {_, 2}, _, _, _, _, _] := {a, 3};
   walk[{a_, 3}, _, _, {_, 0}, _, _, _, _, _, _, _, {_, 1}, _] := {a, 3};
   walk[{a_, 3}, _, _, {_, 0}, _, _, _, _, _, _, _, _, _] := {a + 1, 0};
   walk[{a_, 4}, _, _, _, {_, 0}, _, _, {_, 1}, _, _, _, _, _] := {a, 4};
   walk[{a_, 4}, _, _, _, {_, 0}, _, _, _, {_, 3}, _, _, _, _] := {a, 4};
   walk[{a_, 4}, _, _, _, {_, 0}, _, _, _, _, _, _, _, {_, 2}] := {a, 4};
   walk[{a_, 4}, _, _, _, {_, 0}, _, _, _, _, _, _, _, _] := {a + 1, 0};
   walk[{a_, b_}, _, _, _, _, _, _, _, _, _, _, _, _] := {a, b};
   walk[{a_, 0}, {_, 3}, {_, 4}, _, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   walk[{a_, 0}, {_, 3}, _, {_, 1}, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   walk[{a_, 0}, {_, 3}, _, _, {_, 2}, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   walk[{a_, 0}, _, {_, 4}, {_, 1}, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   walk[{a_, 0}, _, {_, 4}, _, {_, 2}, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   walk[{a_, 0}, _, _, {_, 1}, {_, 2}, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   walk[{a_, 0}, {_, 3}, _, _, _, _, _, _, _, _, _, _, _] := {a, 3};
   walk[{a_, 0}, _, {_, 4}, _, _, _, _, _, _, _, _, _, _] := {a, 4};
   walk[{a_, 0}, _, _, {_, 1}, _, _, _, _, _, _, _, _, _] := {a, 1};
   walk[{a_, 0}, _, _, _, {_, 2}, _, _, _, _, _, _, _, _] := {a, 2};
   walk[{a_, 0}, _, _, _, _, _, _, _, _, _, _, _, _] := {Max[a - 1, 0], 0};
   
   VonNeumann[func__, lat_] :=   
        MapThread[func, Map[RotateRight[lat, #]&, {{0, 0}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}}], 2]; 

    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];
                                                                  
NestList[MvonN[walk, #]&[VonNeumann[sniff, #]]&, initConf, t]
   ]

Following the trail

As the ants move, they will tend to follow trails laid down by other ants. This can result in the 'clustering' together of the ants. We can look at the paths taken by the ants using a RasterArray graphics whose elements are colored according to the amount of chemical attractant on the CA lattice site. Below are shown the results obtained for various densities of ants on a 50 by 50 lattice over 300 time steps.

SeedRandom[7]
(attractantMap = chemotaxis[50, 0.05, 300] /. {x_Integer, _} -> x);

Show[GraphicsArray[
  Partition[Map[Show[Graphics[
	RasterArray[# /. Thread[Range[0, Max[#]] ->
	Map[Hue, Table[Random[], {Max[#] + 1}]]]],
   DisplayFunction -> Identity, AspectRatio -> Automatic] ]&, 
	attractantMap[[Range[1, 301, 100 ] ]]], 2] ]];

SeedRandom[7]
(attractantMap = chemotaxis[50, 0.10, 300] /. {x_Integer, _} -> x);

Show[GraphicsArray[
  Partition[Map[Show[Graphics[
	RasterArray[# /. Thread[Range[0, Max[#]] -> 
	Map[Hue, Table[Random[], {Max[#] + 1}]]]],
   DisplayFunction -> Identity, AspectRatio -> Automatic] ]&,
	attractantMap[[Range[1, 301, 100 ] ]]], 2] ]];

SeedRandom[7]
(attractantMap = chemotaxis[50, 0.25, 300] /. {x_Integer, _} -> x);

Show[GraphicsArray[
  Partition[Map[Show[Graphics[
	RasterArray[# /. Thread[Range[0, Max[#]] ->
	Map[Hue, Table[Random[], {Max[#] + 1}]]]],
   DisplayFunction -> Identity, AspectRatio -> Automatic] ]&,
	attractantMap[[Range[1, 301, 100 ] ]]], 2] ]];

Computer Simulation Projects

1. Modify the sniff rules so that an ant faces the empty nearest neighbor site with the highest level of chemical attractant, and when there are no empty nearest neighbor sites, the ant retains its current orientation.

General References

Pennisi, E., "The Secret Language of Bacteria". The New Scientist. September 16, 30-33 (1995)

Resnick, M., Turtles, Termites, and Traffic Jams. MIT Press, (1994), pp. 50-68.

Lam, L. and Pochy, R., "Active-Walker Models: Growth and Form in Nonequilibrium Systems", Computers in Physics, 7, (1993) 534-541.

Freund, Harald and Grassberger, Peter. "The Red Queen's walk". Physica A 190, 218-237 (1992).