Modelling Ant Nest Construction
Wonder of small actions collectively in massive scale
Self organising nature of ants has attractive properties such as the resilience through redundancies, and versatility across wide range of problems. They are more scalable, less costly because of the simplicity and more robust as the work of the defective agent can be readily be taken over by another agent. In this post I model and analyse ant nest building with a live simulation.
Disclosure: This was a part of my academic work in the module of Intelligence in Animals and Machines, during my MSc in Evolutionary and Adaptive Systems, at University of Sussex
Introduction
Among animal nest building, insects display an amazing ability to construct large and complex structures without any central ability to architect, plan or manage the construction. For example with termites, relative to their body size, scale of their structures are only rivalled by man made constructions \cite{1}. This decentralised construction is achieved as a result of a combination of self-organisation, interacting & modifying the immediate environment, and guiding & influencing the fellow ants through extensive use of pheromones (stigmergy).
Self organising nature of operation has attractive properties such as the resilience through redundancies, and versatility across wide range of problems. They are more scalable, less costly because of the simplicity and more robust as the work of the defective agent can be readily be taken over by another agent. Studying this type of behaviour is of particular interest in robotics where derived algorithms could be used for tasks of varying degree of complexity by deploying a large number of simple agents. They could be an attractive solution in space exploration where large number of inexpensive autonomous bots can carryout construction of essential structures as well as site preparation before human landings on Mar \cite{7}. Much closer to earth and with immediate usefulness they could also be used in software agents managing resource allocations in large data centres \cite{3}.
Leptothorax tuberointerruptus are a species of rock dwelling ants which are about 2.5mm in length. They live and build their nests in natural rock crevices with simple operations like pushing sand granules (or debri). They do not have to construct a roof or a floor for their nest because of their choice of nest sites (i.e. flat rock crevices). Therefore the building is essentially two-dimensional and quite conducive to laboratory experimentation \cite{5}.
In the paper titled Controlling Ant-Based Construction, by Pitonakova L., Bullock S. \cite{8} investigates the dynamics of nest construction of this ant species using an agent based model of the ant's behaviour. It consists of a continuous-space model where ants can have a higher degree of freedom of movement (i.e. not grid based). They modelled three types of ants (Internal, External and Passive or the brood) capable of pushing sand particles. They also modelled a limited physical properties such as friction where these features were not present in previous attempts at modelling.
With this model, they investigated a few properties such as:
- Whether the nest size depend on the ratio between internal and external ant numbers
- Whether using a pheromone building template will lead to more regular structures
- Whether the spontaneous nest entrance formation was facilitated by pheromone template and internal ant density.
- Whether the same behaviour algorithm is capable of generating an alternative architectures.
In their implementation, nest construction by the simulated ants was achieved by carefully programming the behaviours such as the sand drop probability. The drop probability was calculated using the following formula
\begin{equation} P_{drop} = f \times|log(1-\alpha \times(\Sigma R + \epsilon))| \end{equation} where $$f = 0.625, \alpha = 0.8, \epsilon = 10^{-11}, \Sigma R = TotalFeltResistance$$
The Total Felt Resistance was proportional to the number of items carried by an ant as well as the number of collisions with sand.
Further modelling
Taking inspiration from this, we implemented a similar agent based model, capable of real-time depiction of ant behaviour. Our implementation used a simpler model for drop probability by using the concept of energy expenditure, without resorting to an exponential equation based on total felt resistance as above. The aim was to have the drop probability emerge from the interaction with the environment, ant's energy level, and the expenditure of energy when pushing stones. This is a more natural way to model it, specially in robotics, as the expense of energy can be measured and managed directly. Also we investigated the emergence of 'extending of walls' without specifically modelling it, as done in the paper. In their implementation, ants' drop behaviour was dependant on the kind of the ant. For example, internal ants could drop the carrying items at any point where as the external ants could drop on collision with sand. We removed this conditionally programmed behaviour and controlled their actions with parameterisation.
Methods
The simulation consisted of sand and ants as distinct situated objects that interacted with each other. It also contained a simulated static pheromone cloud that was emanating from the centre of the brood. On each cycle, object positions were updated according to their internal states, the external influences such as pheromone level detected, or collisions with other objects.
We modelled three types of ants (Internal, External,Passive), each of them were configurable from a common template. Their behaviour was defined by the relative values of the parameters used. Ants moved in a correlated random fashion. The range of movement of the ants was dependent on the pheromone level detected. Each type of an ant had a pheromone threshold level such that once the local pheromone level was below it, the ant traversed back in the direction of the location with last known highest pheromone level. Internal and external ants differed only by their carry direction and threshold levels, where it was higher for internal ants, such that they stayed close to the brood (cluster of Passive ants) and the threshold level was lower for external ants, such that they roamed the neighbourhood. Internal ants carried sand outwards in the direction of decaying pheromone levels and External ants carried in the opposite direction.
Passive ants had a very high level of pheromone threshold and they clustered together in the middle of the nest.
Each ant had an inherent energy level. They expended the energy in moving, dragging objects and turning. We didn't model a specific energy acquisition model, such as seeking food, instead each ant in each simulation cycle got a parameterised amount of energy, to be expended on activities. When the energy level dropped below parameterised levels, ants were not able to perform activities, for example, walking, carrying etc.
Each ant had a variable speed. They could randomly speed up and slow down, turn a small angle or stop briefly. This formed a realistic movement model for ants.
Ants could detect collisions with other objects such as sand or other ants taking the body morphology into account. Ants' direction, speed and object carrying behaviours were affected accordingly as a result of a collision.
We also modelled a basic memory of the location of maximum pheromone location, and the ant was capable of navigating towards that direction.
All simulations were performed in an arena the size of 660 x 660 px and an ant was modelled as a 10 x 2 px rectangle. A sand granule was of the size 2 x 2 px. These dimensions were used in the Controlling Ant-Based Construction paper and in turn were given by Franks and Deneubourg (1997) \cite{4}. For all experiments (unless otherwise stated) we used a static pheromone template, which was a gaussian dispersion (mean of 0 and standard deviation of 100) of simulated pheromone, normalised to 1, situated at the centre of the arena emanating from the brood.
In general, simulation was done as described in pseudo code in the Listing 1. All objects in the simulation, such as ants, sand were situated objects in the simulated world. The basic algorithm worked for all situated objects, but polymorphism ensured each action was specialised for each derived object.
For each situated object,
update state (in the case of an ant)
check pheromone seek behaviour
if current pheromone level is below threshold
turn in the direction of detected max pheromone
level location
move in the 2D world
bounce off walls
change speed
change direction
detect collisions
If collided with an ant
decide whether to drop carried sand
change direction
if collided with sand particle
decide whether to drop carried sand
change direction
decide whether to pick up sand
if picked up sand,
if internal ant
change direction away from nest
if external ant
change direction towards nest
move carried items
replenish energy
render ant to canvas
Listing 1 : Simulation pseudo code
We had implemented the simulation with an object oriented programming language called Typescript which cross compiled to Javascript. This made it possible for any browser to run the simulation without having to set up software or run a server.
A Typescript implementation (as.ts) and compiled Javascript (as.js) with HTML file (index.html) that is runnable by loading HTML file in a web browser, are attached as supplemental material.
Experiments & Results
General observations
We randomly placed ants in the simulated world. External ants were randomly dispersed throughout the arena; Internal ants were randomly dispersed inside the pheromone cloud and Passive ants were placed in the middle of the arena.
Internal ants navigated outwards until they reach the perimeter established by the pheromone sensitivity threshold. When they picked up a sand granule, they push it outwards. As such, internal ants, initially worked to establish the rough perimeter, clearing sand outwards, in. External ants brought in the sand towards the brood as much as possible. But initially they tended to be closer to or be inside the perimeter as they were more likely to encounter sand close by. Only when the immediate vicinity inside the perimeter was cleared, they tended to venture outside.
When the external ants brought in sand, and encountered the perimeter wall they tended to drop the sand at the perimeter. The external ants, who were inside the perimeter tended to move sand even further in to the middle where the brood resides. In some occasions, they moved the sand from the perimeter wall itself. This caused the openings to form after sometime.
With the change of sand dropping algorithm, the behaviour observed had changed. We no longer saw that the internal and the external ant counts contribute to the size of the nest built, but rather it's speed.
Effects of internal and external ant counts on the speed of nest building
We experimented with a range of internal and external ant counts. Figure 1 shows the results of those experiments. Actual nest perimeter was constructed about 160px from the centre of the nest. When the mean distance to the sand converges on the distance to the perimeter, we considered that the perimeter was well established using all available sand (Figure 1a).
When the ant counts were 50/10 (Internal/External), the perimeter was quickly established, but clearing out the neighbourhood sand took a very long time. This was expected as the number of external ants were relatively small. With increasing external ant counts, the perimeter establishment was quicker, as evidenced by 50/30 and 50/50 in Figure 1a. Further relative increase in external ant counts were detrimental as most of the sand was piled in the centre rather than at the perimeter. Figure 1b shows the standard deviations of the sand particles from the centre. Higher value means, the sand was spread out and lower value means they were piled together. This is a measure of how well the ants were building the nest.
With 50/10 ratio, as mentioned above, perimeter was quickly established, as evidenced by the initial drop, but further reduction took a long while as there were only a relatively small number of external ants.
With 50/30 ratio, after building the initial perimeter ants took a while start collecting more sand. This could be explained by external ants spending more time inside the perimeter moving sand about. After this phase, the perimeter establishment was roughly linear.
When there were an equal number of ants (50/50) the disorder increased quickly. This was due to an equal number of ants moving sand back and forth, until eventually internal ants established the perimeter, while the external ants brought in more sand from surroundings.
When the external ant count was relatively higher, the amount of sand piled in the centre of the nest tended to become higher. This was due to the small number of internal taking longer to move that sand back towards the perimeter.
 |
 |
| Figure 1a | Figure 1b |
Effects of the pheromone threshold level of internal ants on the size of the nest.
Each kind of ant had a different pheromone threshold level. While roaming, when the currently detected pheromone level fell below the threshold level, an ant turned to the direction of its last known maximum pheromone level location. In order for the external ants to be able to roam in the whole arena, we had set their threshold level to zero. In a larger arena or out in the field, it's more likely that there would be some threshold level, which keeps the ants restricted to the vicinity of their nest. By controlling the threshold level of the internal ants, we were able to control the diameter of the nest perimeter wall.
 |
 |
 |
| Threshold = 0.8 | Threshold = 0.7 | Threshold = 0.1 |
Figure 2 shows three pheromone threshold levels we used. Higher the threshold level, constructed nest wall diameter was smaller. We experimented with various ant counts and within first few simulation iterations, wall formation was visible. Then we chose an appropriate number of internal ants, according to the formed nest sizes such that they could move. With large number of internal ants inside a small nest, it took longer to form the perimeter wall as they couldn't move as effectively as they could, inside a larger nest.
Constructing different shapes with pheromone cloud configurations
We were able to construct different shapes by placing a few pheromone clouds in formation. We constructed three shapes, a heart shape, a square and an oval by placing: (a) Two clouds of diameter 50, 150px apart and a third in between and below with half the intensity. (b) Four clouds of diameter 50 at the corners of a square of 100px sides. (c) Two clouds of diameter 50, 100px apart. These are shown in Figure 3 and the corresponding nests created are shown in Figure 4.
The heart shaped perimeter was constructed not only by placement, but also varying the intensity of the 3rd pheromone site. Its perimeter walls had mostly regular distributions of sand, apart from the openings on the top. The walls on the top were never fully formed, as the external ants kept bringing in sand from that side.
Square shaped perimeter was open on the left side and most of the sand on that side was used. The wall on the right side was established but only weakly but the construction hasn't exhausted all the sand available.
Oval shaped perimeter exhibited similar properties. Most of the sand on the left had been used up in creating the bottom walls. This happened when the external ants pushed the sand into the centre first and then internal ants pushed them back on to the perimeter.
In all these cases, reason for some walls not appearing was because of insufficient sand or external ants kept breaking down the weakly formed perimeter not giving internal ants enough time to rebuild it.
 |
 |
 |
| Heart shaped | Square | Oval |
 |
 |
 |
| Heart shaped | Square | Oval |
Constructing with asymmetric distribution of building material
We also investigated the ability of the ants to build perimeter walls when the sand is not uniformly randomly dispersed in the arena. For these experiments, we created sand granules of various random sizes of width and height differing from 2px to 10 px. We dispersed the sand on (a) only on left half of the arena. (b) only on the left quarter of the arena. Internal ants' movement was confined by the pheromone cloud, while external ants could roam through out the arena.
Figure 5 shows that ants were capable of building the perimeter even when immediate surroundings didn't contain the building materials. Initially, internal ants pushed the sand outwards to the left to establish half the perimeter, at the same time, external ants brought in sand into the centre. These sand were in turn pushed towards the right half circle by the internal ants to construct that side of the perimeter. This was accomplished without changing any behaviour parameters of the ants.
 |
 |
 |
 |
| Frame 1 | Frame 10k | Frame 100k | Frame 600k |
We performed a very similar experiment as above, but after introducing a weight property to sand particles. The weight property was proportional to its size. This in combination with energy consumption model we used through out, it was possible for the ants to avoid heavier sand and only use lighter material, essentially categorising sand according to weight. Figure 6 shows the construction using only the lighter material. Similar binary clustering had been achieved by Holland O. et al. in their experiments, using small buggy like autonomous robots with grippers clustering coloured objects \cite {6}.
These two experiments show that the perimeter building is a collective effort coordinated between internal ants and external ants by gradually modifying the environment using simple clues (Pheromone template) and simple internal rules governing them.
 |
 |
 |
 |
| Frame 1 | Frame 10k | Frame 40k | Frame 90k |
Discussion
With this simulation, we have shown how nest construction can be controlled by varying a few simple properties of the system. The speed of the construction can be controlled by varying the relative numbers of agents. The shape of the construction can be controlled by varying the pheromone template. We can also use the agents to perform simple classification or filtering of objects by dependent on the properties of the building materials. Investigating the behaviour of the ants with dynamic deposition of pheromone would be an interesting future experiment.
Our model is grounded in biology and we extended it somewhat beyond the biological characteristics. Using an energy based model to govern the ant's behaviour has very close applications to robotics as opposed to the friction based model used in the paper by Pitonakova et al. For example there's a considerable morphological changes needed to measure the friction when the problem domain changes from, ground based robot to an airborne drone unlike an algorithm based on energy expenditure.
The implementation of the simulation yields a platform where ant behaviour can be visualised in real-time. It is versatile in being able to configure large number of properties to conduct a variety of experiments. More sophisticated physics and collision detection methods can be incorporated as required as further extensions.
The ants only have reactive behaviours and they are not managed in any direct way, nor have they any knowledge of an overall plan of the construction. They follow a simple set of rules, interacting and changing the environment and are able to exhibit a variety of complex behaviours that are seemingly intelligent. Braitenberg characterised similar behaviours with his array of increasingly sophisticated vehicles showing variety of complex interactions with its environment \cite{2}. Their collective behaviour emerges from the interaction with the environment (sand), other agents and guiding elements (pheromone cloud) with minimal intelligence built into the agents themselves.
Appendix
Code for the simulation can be found here
References
[1] Eric Bonabeau, Guy Theraulaz, J Deneubourg, Nigel R Franks, Oliver Rafelsberger, J Joly, and Stephane Blanco. A model for the emergence of pillars, walls and royal chambers in termite nests. Philosophical Transactions of the Royal Society B: Biological Sciences, 353(1375):1561–1576, 1998.
[2] Valentino Braitenberg. Vehicles: Experiments in synthetic psychology. MIT press, 1986.
[3] Rajarshi Das, Ian Whalley, and Jeffrey O Kephart. Utility-based collaboration among autonomous agents for resource allocation in data centers. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pages 1572–1579. ACM, 2006.
[4] Nigel R Franks and Jean-Louis Deneubourg. Self-organizing nest construction in ants: individual worker behaviour and the nest’s dynamics. Animal Behaviour, 54(4):779–796, 1997.
[5] NR Franks, Andy Wilby, Bernard Walter Silverman, and C Tofts. Self-organizing nest construction in ants: sophisticated building by blind bulldozing. Animal behaviour, 44:357–375, 1992.
[6] Owen Holland and Chris Melhuish. Stigmergy, self-organization, and sorting in collective robotics. Artificial life, 5(2):173–202, 1999.
[7] Chris AC Parker and Hong Zhang. Collective robotic site preparation. Adaptive Behavior, 14(1):5–19, 2006.
[8] Lenka Pitonakova and Seth Bullock. Controlling ant-based construction. In Advances in Artificial Life, ECAL, volume 12, pages 151–158, 2013.