Project for "System Modelling and Simulation" ("Modelowanie i Symulacja Systemów") course of Computer Science Master's major in AGH Academy of Science and Technology.
Ant colonies use the sense of smell to coordinate tasks such as foraging for food, defense or brood care.
Trail pheromone signals are particularly important in the context of foraging. When a forager has located a profitable food source and then returns to her nest, she deposits trail pheromones that guide nest mates to the same resource[1].
There are other types of "smells", such as "death pheromone", "home pheromone", "danger pheromone" and even some to differentiate between two different colonies of the same species of ants.
Ant colony optimization algorithm tries to solve computational problems of "finding the best path". It's a probabilistic technique, so in comparison to stochastic algorithms like Breadth-first search (BFS) or Depth-first search (DST) in large graphs it should prove to be much faster.
It's modeled around simplified colony simulation of "ants," that is, agents with very simple basic capabilities which, to some extent, mimic the
behavior of real ants[2].
- The world is rectangular and two dimensional 🌍
- Each ant is a standalone agent, that thinks for itself and acts depending on: it's own state, the strength and type of pheromones in its viscinity and the random factor. 🧠
- The ants target is to find food and get it back to their nest. 🍕
- The ants leave traces of pheromones wherever they go ("return to base" or "food source" pheromones). 🧭
- When an ant finds food source, it leaves traces of a different pheromone ("food source" pheromone). 🐜
graph LR;
A(Choose your direction) --> B{Are you holding <br/> food right now?};
B --->|YES| C(Track<br/><br/>HOME<br/><br/>pheromone)
B --->|NO| D(Track<br/><br/>FOOD<br/><br/>pheromone)
C --->E(Divide your field of view into<br/>three circular sectors)
D ---> E
E ---> F(Perform a move towards <br/>the sector with the<br/>strongest pheromone track<br/>with a random variation)
classDef orange fill:#fb8,stroke:#d74,stroke-width:2px, color:black;
class sq,e green
class B orange
Examle simulation explained
 |
 |
|---|---|
| 1. Initial chaos | 2. First track forming |
 |
 |
| 3. First track is self-optimizing to get shorter. More paths are forming but they are not leading to the nest yet |
4. All the paths got connetced to the nest |
 |
 |
| 5. Paths keep getting straigher and shorter | 6. Paths are almost ready but since some ants are still walking free their location is not stable yet. |
 |
 |
| 7. Pheromne map significantly more stable and durable. | 8. Loop o rightgot slower to optimize distance |
 |
 |
| 9. The loop on righis at the point of the collapse | 10.The whole food is collected |
Post-simulation ants behaviour
Once all the food is collected the path are becoming forgotten starting with the longest one. If we keep the simmulation running we may even observe forming of so called "ant mill" (wikipeda) which is apperaing close to the place of the picked loot - so in an area filled densly with pheromonses.
In this case the distance travelled by ants is self-optimizing too, so the circle is collapsing towards ts center and then disapperaing
The main goal of the project has been accomplished. In most common use cases the swarm behaviour is modeled using one AI unit ("swarm leader"). We achieved analogous result in the environment, where each unit makes their own decisions based on their surroundings.
The performance of the simulation leaves a lot to be desired. The amount of ants on the screen as well as the lifespan of the pheromones directly influence the speed of acquiring more food. Dynamic structures used by Python make it difficult to create a multi-threaded version of the algorithm. Also the pygame engine unfortunately brings even more performance overhead. Nevertheless the simulation takes acceptable amount of time.
- The world is 3D. It has depth and depending on this depth the ants go slower/faster.
- The world has obstacles that ants can't get through.
- The pheromones change their position based on the wind.
- The pheromones diffuse faster or slower depending on the temperature.
- There are multiple nests (factions) of ants that don't cooperate with each other and prefer to stay separate.
- Ants die when they're not in their nest for too long. They also change their choices depending on their own health.
- New ants are born if the situation is
- Language:
3.10.3 - Game engine:
- Used libraries:
-
Morgan E.D. Trail pheromone of ants. Physiol. Entomol. 2009;34:1–17. doi: 10.1111/j.1365-3032.2008.00658.x.
-
M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man and Cybernetics, Part B, 26(1):29-42, 1996.