Antennae - Python implementation of ant trail networks

Ants are funny creatures. In spite of their (seemingly) limited cognitive and sensory abilities, they are able to build large complex structures, fight off enemy colonies, and collectively carry large objects.

Ants are able to communicate by giving off pheromones, a chemical that triggers a reaction once picked up by another ant. One of the ways pheromones come into play is when ants spread out to forage for food. Once they find a food source, they carry it back to the nest, all the while leaving a pheromone trail that will lead other ants to the same location. Because of the way the pheromone is deposited, ants are able to construct the shortest route to the food source without prior information about the layout of their environment.

Although inherently a biological question, various mathematicians have tried to express this behaviour in mathematical structures, and not without success. I implemented one of these concepts in Python. You can download it here.

Mathematical framework

We model the space the ants move in with a graph. A graph is a collection of nodes and edges that represents a network. An illustration is included below.

An example of the ant network as a graph. Edges are in black, the source node is in red and the food node is in yellow.

The path an ant travels is represented by a sequence of edges. The length of an edge is precisely the distance between the nodes it connect. Edges can hold pheromone: the more pheromone an edge has, the more likely an ant wants to travel it. The amount of pheromone and the probability of choosing a certain edge are related as follows. Say an ant has the opportunity to choose between the three edges \(e_1\), \(e_2\) and \(e_3\) with respectively pheromone amounts \(a_1\), \(a_2\), \(a_3\). Then the probability of choosing \(e_1\) (which we will denote with \(P(e_1)\)) is equal to

\[P(e_1) = \frac{a_1}{a_1 + a_2 + a_3}\]

The ants are modelled as independent units (also called agents) that travel from node to node using the available edges. They start at the nest node, randomly choosing edges to arrive at new nodes, until (hopefully) finally arriving at the food node. All the ants travel at the same fixed speed.

Each ant has a memory that holds the edges they visited from the nest node up until their current location. In addition, they are able to determine the amount of pheromone on an edge, as well as add deposit new pheromone after having found a food source.

Pheromone trails decays with a certain rate, so that as time passes, lesser used paths lose their attractiveness. This process can be described as follows. If between time 0 to time \(t\) an edge does not gain any new pheromone deposits, but is only subject to the decay process with rate \(d\), then its pheromone level \(a(t)\) at time \(t\) is determined as follows:

\[a_1(t) = a_1(0) * (1-d)^t\]

Implementation

When the script is executed, a new random graph is created. This graph is given a nest node, a food node, and a path connecting the two (consisting of at least one edge). The ants are initialised in the nest node and the simulation starts. Each time step the ants progress on their edge. When they reached the node, they determine their next edge by weighing the probabilities with the pheromone on the edges. This makes the path having the most pheromone the most likely option, but gives the other edges also a chance.

When the edges reach the food source, they backtrace to take the exact same path back to the nest (minus any loops they might have made). While they are on their way back, they drop pheromone on the edges as a signal to the other ants that this road might lead to food. The more pheromone an edge contains, the thicker it is drawn. You can see that over time, the quickest route becomes the most popular one.

All the parameters are present in the file params.py.

Interesting parameters include

• pheromone_decay: setting this to higher levels increases the volatility of the ants.
• min_path_length: represents the number of edges that must be between the nest node and the food node. Setting this to higher numbers increases the work the ant colony has to perform to find a stable route.
• edge_probability: increases the number of edges and the possibility for ants to get lost.

Feel free to play around and extend it!