Formicarium

This article is about swarm intelligence , and how we can try to simulate it to show how collective behavior can unlock better solutions to problems that may otherwise remain unsolved.

From Wikipedia, we can define Swarm Intelligence (SI) as:

SI systems consist typically of a population of simple agents or boids interacting locally with one another and with their environment … The agents follow very simple rules, and although there is no centralized control structure dictating how individual agents should behave, local, and to a certain degree random, interactions between such agents lead to the emergence of “intelligent” global behavior, unknown to the individual agents.

One of the most common examples of swarm intelligence systems are ant colonies, and this is what formicarium tries to simulate.

The purpose is to show how the collective behavior of decentralized and self-organized artificial systems allows multiple organism to perform better when working together to achieve the same goal, compared with a single organism, given the same set of skills and the same environment.

Overview

The formicarium emulator is a project written in Rust, using the semeion engine †.

Formicarium is a zero-player game where you are in control of the initial environment configuration, and the only rule is that your ants need to collect all the food they find on the environment and bring it back to their nest.

The simulation runs on a 2D environment of fixed size, which is initially populated with the following (passive or active) entities:

• Nest: A single ant nest that represents the place where all the ants are born (spawned) at the beginning of the simulation, and where all the food needs to be collected.

• Morsels: One or multiple locations in the environment where a fixed amount of food can be found.

• Ants: The entities that can freely move within the environment to collect the food from the morsels and bring it back to the nest.

• Pheromones: Dynamic entities that are created by the ants and used as a communication mechanism to allow other ants to take educated decisions. There are 2 types of pheromones:

  • Colony: used to reinforce a path that can lead to the Nest.
  • Food: used to reinforce a path that can lead to a Morsel.

Each of these entities is represented with basic geometric shapes when drawn into the screen, and their color and size is used to represent concentration or scope.

The simulation starts with a fixed set of parameters that determine the environment’s initial configuration. The goal is for the ants to collect all the food in the environment as fast as possible (lowest number of generations) and bring it back to their nest. When all the food is found and collected, the simulation is over.

The faster the ants can bring back the food the better and, more importantly, the number of generations required with the same configuration should decrease faster than linearly as the number of ants increases, showing that even the most basic forms of swarm intelligence can give significant advantages when multiple organisms work together.

This is what the main loop of the simulation looks like:

use formicarium::*;

let conf = game::Conf::parse("conf.json")?;
let context = game::Context::new(conf);
let mut state = game::State::new(&context)?;

while !state.is_simulation_over() {
    let generation = state.env.nextgen()?;
    if generation > MAX_GENERATIONS_COUNT {
        panic!("Timeout!");
    }
}

println!("Simulation over after {} generations", state.env.generation());

† If you want to know more about semeion, please have a look at this post .

The Ants

The ants are the only active entities that take part in the simulation, where all the ants have a determined and equal set of skills, and they can make decisions that will affect their actions (such as movement) according to the portion of the environment they can see and interact with.

Each ant can either be looking for food (foraging) or, having already collected the food from a morsel, be bringing the food back to the nest (carrying).

According to the current ant task, its single goal is to find a specific target in the environment where:

• Foraging targets any Morsel.
• Carrying food targets the Nest.

Once the ant reaches its target, it simply switches its task.

In order to find their target, each ant can rely on the information retrieved by the area of the environment that immediately surrounds the ant and, in particular, each ant can take its own decisions according to the entities that currently populate the visible portion of this environment subset.

The main idea is that each ant can either reinforce the information found, by trusting the trail of pheromones left previously by other ants (or itself) in order to find its target, or cancel it out by rejecting the information found because it’s misleading and thought to possibly lead to a dead end.

Ants cannot communicate directly with each other†, therefore this information can only be exchanged by leaving pheromone entities in the environment, where each pheromone has an intrinsic property of concentration that can be increased or reduced by the ants (and decreases over time to simulate evaporation). The stronger the pheromone concentration, the higher the chance to be in proximity of a target.

When no information is available in the surrounding environment, the ant can still rely on a sense of direction, by knowing the approximate direction of its nest. Moreover, each ant has the ability to remember a configurable number of previous steps (representing its short-term memory), which allows the ant to not end up in local minima or maxima by returning to locations that were thought to be close to its target.

If no educated action can be taken, the ant will simply try a random step.

Given this behavior, the higher the number of ants, the stronger the pheromone trails will be reinforced (or weakened), giving numerous groups of ants advantages over smaller ones.

† There are some circumstances where direct communication is required, such as when two or more ants occupy the same morsel location that contains a single portion of food. In that case only a single ant can take the food; this is solved by building consensus so that all the ants elect a leader between them that will be in charge of bringing the food found back to the colony nest, while the other ants will continue in their search for other morsels.

Running the simulation

If you want to run formicarium , the first thing to do is to install Rust , clone the repository

git clone https://github.com/gliderkite/formicarium.git

and finally run with:

cargo run --release -- conf.json

where the last argument is the path to the configuration file that you are free to edit to see how different parameters can affect the behavior of the ants.

The main configuration arguments are:

• The dimension of the environment (as the size in number of columns and rows).
• The location of the nest.
• The number of ants.
• The ants’ memory span (as number of previous locations they can remember).
• The quantity of pheromone the ants can leave, expressed by the initial quantity that gets reset every time the ant reaches its target, and by the amount the pheromone left decreases at each step (the farthest from the origin the smaller the amount of pheromone left).
• The strength of the pheromone paths that are reinforced by the ants (in percentage, relative to the current concentration).
• The number of morsels, and the amount of food each of them will contain when the simulation starts.

All the other configuration values are mostly related to the graphics settings, so that you can control which entities are going to be visible, as well as the desired FPS.

You can also specify an optional seed value that will be used to place the morsels in the environment.

Let’s try to make sense of the above image with less ants, in a smaller environment:

The blue static square represents the nest, while the green squares represent the morsels (and they disappear when the amount of food in them reaches zero).

The red circles are the ants when foraging, and they become blue when carrying the food back to the nest.

Finally, the black-to-white smaller circles represent the food pheromone, where the brighter the color the stronger its concentration, and they disappear when completely evaporated (the colony pheromone has been omitted for clarity).

It looks clear how, once a path to the morsel is formed, it becomes stronger and stronger, due to the always increasing number of ants following the same path. It’s a reinforcing circle that often terminates with all the ants following the same path until all the food in the morsel is gone, and a new path needs to be established.

Results

For this post I decided to run a simulation with a relatively small environment, using always the same configuration parameters but changing the number of ants, to see how effectively the increase in the number of ants would reflect in the number of generations needed to collect all the food and terminate the simulation.

You can find the simulation configuration, as well as the code to run the simulation, in the formicarium repository .

The simulation was run 10 times per number of ants, and what I show here are the mean values.

As you can see on the x-axis, we plot the number of ants, while on the y-axis the (mean) number of generations it took to complete the simulation for the given number of ants.

The red line represents instead a hypothetical trend of linear generations decrease, computed as interpolations of the plotted generations values.

We can try to make sense of these data by observing that the number of generations follows a decreasing trend when the number of ants increases, which is what we were expecting. Moreover, it looks like when the number of ants is relatively small, we gain considerable advantage (be able to collect all the food faster) by adding a few more ants (although this is a significant increase in the number of ants in relative terms). Then, we can observe a period where the ants perform better than the plotted linear interpolation (where the blue bars are below the red line). Finally, the number of generations starts to converge to a value that doesn’t seem to decrease independently of how many ants we keep introducing to the environment (that can signify we have saturated the environment).