ТЕОРЕТИЧЕСКАЯ И ЧИСЛЕННАЯ ОЦЕНКА КОЛЛЕКТИВНОГО ПОВЕДЕНИЯ МУРАВЬЁВ

DOI: https://doi.org/10.23670/IRJ.2018.75.9.013

ТЕОРЕТИЧЕСКАЯ И ЧИСЛЕННАЯ ОЦЕНКА КОЛЛЕКТИВНОГО ПОВЕДЕНИЯ МУРАВЬЁВ

Научная статья

Свистова С.Ф.*

Российский Технологический Университет, Москва, Россия

* Корреспондирующий автор (svistova.s[at]mail.ru)

Аннотация

Известно, что колонии насекомых, особенно муравьи, действуют и решают различные задачи очень распределённым образом, сохраняя высокий уровень надежности. Алгоритмы колоний насекомых, основанные на поведении насекомых, получили большое внимание в различных приложениях, таких как распределение задач, поиск дома для жизни и т. д., демонстрируя очень хорошие результаты в решении конкретных проблем NP-сложности. В этой статье мы анализируем вариант алгоритма кормления, основывающегося на поведении колонии муравьёв. Мы находим, как теоретически, так и с помощью численных симуляций, такие условия, которые ведут к известную самоуничтожающему поведению, называемому “муравьиная спираль смерти”.

Ключевые слова: распределённые алгоритмы, случайное блуждание моделирование, численная симуляция.

 

THEORETICAL AND NUMERICAL EVALUATION OF COLLECTIVE ANT BEHAVIOUR

Research article

Svistova S.F.*

Russian Technological University, Moscow, Russia

* Corresponding author (svistova.s[at]mail.ru)

Abstract

It is known that insect colonies, especially ants, act and solve various necessary tasks in a very distributed manner, keeping high level of robustness. Insect colony algorithms, based on the insects’ behaviour, have received large attention in various applications such as task allocation, house hunting, etc., showing very good results in solving particular NP-Hard problems. In this paper we analyse a variation of foraging algorithm that originates from the ant colonies behaviour. We discover theoretically and using the numerical simulations the conditions, which lead to a known self-destructive behaviour, also referred as the Ant Spiral of Death.

Keywords: distributed algorithms, random walk, modelling, numerical simulation.

Introduction

Basic ant colony foraging problem on the grid can be described as the problem of finding target cells (sources of food) given starting cell (anthill) and number of independent agents (ants) with limited resources [2, P. 575]. Some species of ants may have very limited amount of short-term memory and extensively rely on the pheromones for navigation. I.e. each walked path is marked with some amount of pheromone, which tells other ants whether path is walked already and/or source of food is found. Each ant that walks "food" path adds it’s own pheromones to existing amount to increase attractiveness of the path and pull more ants into the process. Pheromones are tended to dissipate and diffuse, thus, decreasing influence over time [10, P. 123].

One of the algorithms that models and solves foraging problem is called Pheromones Algorithm. It imposes no obstacles, no dissipation, no direct communication and centralised starting point. Group of ants starts from given cell and randomly explore surroundings, avoiding already marked cells. More complicated foraging model may include obstacles and rely on more probabilistic navigation, for instance, whenever ant tries to find an anthill it will more probable to move in the direction with larger pheromones density, but it can still perform random walks. This problem is experimentally covered in [3, P. 56] with discussion on the different parameters that leads to convergence.

We, in turn, want to discuss modification of the pheromone algorithm in no-food environment in order to simulate phenomenon of Ant Spiral of Death. It is observed, that some warrior colonies of ants, with bad eye-vision, can form a moving spiral "flock" (size can vary up to 1200 feet), and if it is not broken down somehow, then, whole colony can die because of exhaustion. It is, usually, explained by the looped pheromone paths which are followed by the blind ants that do not have other methods for orientation. It can be easily reproduced in handicraft conditions by placing sufficient amount of ants into bounded space. In the following sections we will describe the model of ants behaviour, derive some theoretical results and prove them experimentally.

Model

Informally, ant behaviour in our model can be described as following:

1. N ants start randomly in a bounded grid space and act synchronously.
2. Each ant places portion of pheromones  at its starting point.
3. Environment does not contain food cells.
4. At each round:
   1. If ant stands at non-marked with pheromone cell, then it places there amount of pheromone equal to the maximum amount from the neighbourhood (cells that can be reached within one round) of this cell, multiplied by the uncertainty factor . If cell is marked (i.e. ant previously moved to, probably, other’s ant path), then it adds  to the existing amount (increases attention to the path).
   2. Ant randomly chooses whether to perform chaotic move with some fixed probability p or to move to the cell with larger amount of pheromones (with respect to distance):
      • ant can move in 8 directions by one cell during one round;
      • tie-breaking is done randomly;
      • each ant has limited memory and can remember up to last cells it visited;
      • ant prefers not to visit cells that are in the neighbourhood of the last visited (tries to explore broader).
   3. Pheromone Φ evaporate over time with rate ∈, i.e. 

Theory

Given the model description we can do some theoretical suggestions regarding the possibility of the Spiral of Death formation. For ease, let consider the above model with number of ants N = 1.

Assumption 1. For small chaotic move probability  an ant, starting from the closed trail of pheromones is more likely to stay on it.

Proof. Since ants have 8 degrees of freedom, then, probability to chaotically move from the trail at the step 0 is . WLOG at the step 1, there are only 3 ways to move strictly out from the trail, thus, the probability is . At the step 3, assuming trail is not in the neighbourhood anymore, ant will choose direction randomly and uniformly. Thus, 1D random-walk can be applied in order to find probability that ant will not chaotically come back to the trail. From the theory it is known that this probability is proportional to , where  is the number of steps. Total probability, that an ant leaves the trail is

For a sufficiently small p and large n this probability is small.

Assumption 2. For ant memory  and number of steps , following equations give conditions on parameters n, m, u and ∈ that, if satisfied, lead to creation of "Spiral of Death".

                                                           (1), (2)

where n* is solution to 1, δ - some threshold, may considered as machine precision.

Proof

To prove this assumption we need to find probability that path of the ant have intersections after n steps. First, we consider easier problem of finding probability that ant returns to it’s starting point. We can consider creation of such closed loop as 2D random-walk with return. However, finite ant memory m and respective behaviour imply following restriction: random-walk started at step i can not return at steps less than i+m. From the theory it is known, that for 2D case probability of return in k steps is proportional to . Then, mathematical expectation of the number of returns after s steps is [1]

where  -  harmonic number.

Thus, ant returns to it’s starting point after n steps  times. However, to solve original problem, we also need to consider intersections with each following point of random-walk 2 ... n. Hopefully, intersection with point  can be considered as the return after i - n steps of the random-walk started at i, because random-walk is, essentially a Markov Process. Thus, number of intersections is

adding memory restriction:

Finally, closed loop creation, or, equivalently having at least one intersection in  a random-walk is given by setting number of intersections I∼1, from which (1) immediately follows. This is qualitative estimate that describes the relations between the model parameters. To obtain particular solution n* given some m, one should numerically solve the particular equation.

If, after n steps, trail completely dissipated, then, random-walk would not intersect the trail whatsoever. Therefore, we need to require the pheromone not to dissipate completely at any trail point i before the closed-loop is created. From 1 for fixed m, particular n* steps, that are needed for closed-loop creation can be obtained. Thus, using evaporation and uncertainty laws, we see, that for each trail point i after n steps

Immediately follows (2).

In this section we provided some theoretical results showing how different parameters of our model must be set with respect to each other in order to create or avoid "Spiral of Death" in the case of N=1. Extension to N>1 does not seem trivial for general case, but can be roughly done using the results on multiple random-walk intersections.

Experiments

In this section we provide some experimental results obtained from the simulation of the described model. For implementation, we used Multiagent Simulation Toolkit MASON, which provides easy way to model synchronous systems using Java programming language. As well, it has in-built screen-capture tools, which allows to record and take snapshots of the simulation. We conducted several experiments on the bounded square grid of size 50*50 cells. Starting points of ants were placed uniformly. We varied model parameters N, m, ∈, p to see how they affect the results. For all experiments we put .

First, we decided to reproduce theoretical results for N=1 and see if our assumptions are reasonable. For large chaotic movement probability p we have got expectable results, that ant can not create stable loop, hence, we set p=1% for the experiments described below:

• Small memory m=5, moderate evaporation ∈=0.8 lead to small loop size as expected. See FIG. 1 a).
• Small memory m=5, intensive evaporation ∈=0.3 lead to loop impossibility as random-walk can’t end before Φ=0.002  See FIG. 1 b).
• Very large memory  m=10, moderate evaporation  ∈=0.8 lead to loop impossibility, as ant is very unlikely to return to the trail. See FIG. 1 c).
• Large memory m=50, slow evaporation ∈=0.99 lead to large loops as expected. See FIG. 1 d).

Second, we observed behaviour patterns for N>1. Now, we varied , fixing memory to moderate value m=20.

• N=100, tiny probability , fast evaporation lead ∈=0.6 to small/medium loops. See FIG. 1 f).
• N=100, large probability p=10%, moderate evaporation lead ∈=0.8 to no loops, mostly chaotic movement. See FIG. 1 e).
• N=100, tiny probability , moderate evaporation lead  ∈=0.8 to large loop. See FIG. 1 g).

Summary

In this paper we showed the behaviour of an ant colony in specific environment, which could lead to an interesting natural glitch/phenomenon known as "Ant Spiral of Death”. We described simple model with several parameters that could be varied. After that, for simple case of unit size ant colony we derived theoretical predictions on the relations between parameters that lead to larger possibility of "spiral behaviour". Further, we implemented our model using multi-agent simulation toolkit and conducted experiments that, overall, were consensual with theoretical results. Finally, we empirically picked up suitable parameters and verified, that "Ant Spiral of Death" can be produced in our model with colony of larger size N>1.

Fig. 1 – Obtained results

Конфликт интересов Не указан.

Conflict of Interest None declared.

Список литературы / References

1. Van den Berg M. Exit and return of a simple random walk // Potential Analysis. – 2005. – Т. 23. – №. 1. – P. 45-53.
2. Panait L. A. Learning ant foraging behaviours / Panait L. A., Luke S. // Artificial Life XI Ninth International Conference on the Simulation and Synthesis of Living Systems. – 2004. – P. 575-580.
3. Panait L. Ant foraging revisited / Panait L., Luke S. // proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9). – 2004. – P. 14-37.
4. Afek Y. Optimal pheromone utilization / Afek Y., Kecher R., Sulamy M. // 2nd Workshop on Biological Distributed Algorithms (BDA), Austin, Texas, USA. – 2014. – P. 13-27.
5. Afek Y. Idle Ants Have a Role / Afek Y., Gordon D. M., Sulamy M. // arXiv preprint arXiv:1506.07118. – 2015. – P. 1-20.
6. Afek Y. Optimal and Resilient Pheromone Utilization in Ant Foraging / Afek Y., Kecher R., Sulamy M. //arXiv preprint arXiv:1507.00772. – 2015. – P. 10-23.
7. Chircop J. A multiple pheromone ant clustering algorithm / Chircop J., Buckingham C. D. // Nature Inspired Cooperative Strategies for Optimization (NICSO 2013). – Springer, Cham, 2014. – P. 13-27.
8. Chircop J. A multiple pheromone algorithm for cluster analysis / Chircop J., Buckingham C. D. // International Conference on Swarm Intelligence (ICSI), Cergy, France. – 2011. – P. 1-14.
9. Chircop J. The Multiple Pheromone Ant Clustering Algorithm and its application to real world domains / Chircop J., Buckingham C. D. // Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on. – IEEE, 2013. – P. 1-22.
10. Hoff N. R. Two foraging algorithms for robot swarms using only local communication // Robotics and Biomimetics (ROBIO), 2010 IEEE International Conference on. – IEEE, 2010. – P. 123-130.