Specialization in Swarm Robotics using Local Interactions

Specialization in Swarm Robotics using Local Interactions

Kazuaki Yamada

Department of Mechanical Engineering Toyo University

Saitama, Japan

Abstract This paper proposes the use of a novel response threshold model to implement autonomous specialization in swarm robotics. The response threshold model mimics the sensitivity of ants to external stimuli. An ant can specialize either as a worker or as a non-worker. This specialization is conducted autonomously, using the different sensitivity of different ants to external stimuli. The conventional response threshold model has used the ratio of workers in the colony as an external stimulus. However, individual agents cannot know the overall ratio because only local communication through pheromones is available. In contrast, the proposed response threshold model used the ratio of workers that an agent touched in a short term as the external stimulus. We investigated the efficiency of the proposed response threshold model through simulations of ant foraging behavior and verified that it allowed agents to effectively collect food by statistically adjusting the worker to non-worker ratio.

Keywords Swarm robotics, Social insects, Specialization, Response threshold model, Foraging problem

1. INTRODUCTION

   Multi-robot systems coordinate the actions of many autonomous robots, forming orderly systems through interactions between nearby robots, and can complete tasks that are difficult for a single robot to achieve. Multi-robot systems are also potentially robust against changes in their environment. However, the dynamics of multi-robot systems are complex, requiring interactions between many autonomous agents, and pre-programming of the appropriate action rules has proved challenging. Promising approaches include multi-agent reinforcement learning, evolutionary robotics, and swarm robotics [1-3]. Multi-agent reinforcement learning and evolutionary robotics address robot control using algorithms such as reinforcement learning and evolutionary computation, without the pre-programming of a controller with detailed rules. These approaches allow for discovery of design solutions that exceed the expectations of the designers [4,5]. However, they require appropriate evaluation functions to be designed for each problem, and therefore, they still depend on the skills of the designers. Swarm robotics, in contrast, is an approach that applies the mechanisms of social insects, such as ants and bees, to engineering problems. For example, the mechanisms of the foraging behavior of ants and bees have been applied to the optimization method [6-10] and have demonstrated their usefulness in traveling problems like the traveling salesman problem.

   Many studies in swarm robotics have applied the mechanisms of ant systems to engineering technologies [11,12]. Ants sustain large colonies using a social system that assigns different roles by social class [13]. The ant's perception

   functions and action rules are limited, and communication between them can only be conducted through chemical signals. The queen ant cannot monitor everything happened in a colony, and cannot give instructions to each ant directly. Yet, ants successfully allocate different roles, such as a care of larvae, colony protection, exploration for food, and foraging, without any centralized management system [14]. This division of labor allows for the adaptation of the colony to changing circumstances. For example, a colony needs to increase the number of ants exploring for new food sources when food becomes scarce and to increase the number of ants collecting food once a new source has been discovered. Rather than allocating roles in a top-down manner, ants assign roles strictly through local communication using pheromones. Bonabeau et al. [15] have modeled this autonomous specialization using a response threshold model. The response threshold model is an equation that describes the sensitivity of ants to pheromones. It is known that there are two types of ants [16]: one with high sensitivity to pheromones and the other with low sensitivity. The different sensitivities are thought to contribute to an autonomous specialization. However, the conventional model used the ratio of workers in an ant colony as the external stimulus, ignoring the crucial factor that social insects can assign roles through local communication.

   This paper proposes a new response threshold model that uses the ratio of workers as an external stimulus. We apply the proposed model to an ant foraging problem and show that the model can successfully mimic the assignment of roles in an ant colony by switching between the exploring and foraging behaviors. We show how ants assign roles strictly through local communication.

   This paper is organized as follows. Section 2 explains how to model an ant foraging problem. Section 3 shows the new response threshold model. Section 4 demonstrates the efficiency of the proposed method through simulation. Conclusions and future work are discussed in Section 5.

2. FORAGING PROBLEM

   This section models the ant foraging problem as a multi- agent simulation following previous studies [17-20]. In this model, an ant is modeled as an agent. An agent has the following three functions:

   • Exploring behavior/foraging behavior

   An agent performs either an exploring behavior or a foraging behavior. When an agent discovers food, the agent performs a foraging behavior and carries the food to a nest. Otherwise, the agent explores for food.

   • Homing pheromone/trail-marking pheromone

     An agent has homing and trail-marking pheromones. The agent lays homing pheromone while exploring for food, and trail-marking pheromone while carrying food back to the nest. Both pheromones are volatile substances and quickly diffuse and evaporate.

   • Worker/non-worker

   An agent can either be a worker or a non-worker. While exploring, an agent can perceive trail-marking pheromones if it is a worker but not if it is a non-worker. While carrying food, the agent can perceive homing pheromones in both worker and non-worker rules.

   TABLE 1. RELATIONSHIP AMONG BEHAVIORS, PHEROMONES, AND WORKER/NON-WORKER.

   	worker	non-worker
   exploring behavior	Able to perceive the trail- marking pheromone	not able to perceive the trail-marking pheromone
   	laying the homing pheromone
   foraging behavior	able to perceive the homing pheromone
   	laying the trail-marking pheromone

   TABLE 2. THE RELATIONSHIP BETWEEN WORKER/NON-WORKER AND BEHAVIOR RULES.

   	worker	non-worker
   exploring behavior	Rule 1 Rule 2	Rule 2
   foraging behavior	Rule 3 Rule2

   Table 1 shows the relationship among exploring behavior/foraging behavior, worker/non-worker, and homing pheromone/trail-marking pheromone. Next, we describe the modeling of perception and action. As shown in Fig. 1, an agent can perceive the pheromone level in three adjacent cells and can select one of three action rules before moving to the next cell. The three action rules are as follows:

   1. Pheromone trail

      An agent moves forward when it detects pheromone on the front cell (Fig. 1(a)). When the agent detects pheromoneson the right front and the left front cell, it moves to the cell with highest pheromone level (Fig. 1(b)).

      (2) ( + 1) = () Random walk

      When an agent can perceive no pheromones, it randomly selects one cell from three cells and moves to that cell.

      1. (b)

   Fig. 1. Pheromone follow behavior rules.

   Rule 1. If it detects no homing pheromone, it moves according to Rule 2.

3. RESPONSE THRESHOLD MODEL

   This section describes the proposed response threshold model, which uses the state of neighborhood agents as external stimuli. First, we explain the role that a response threshold model plays in autonomous specialization and introduce a conventional response threshold model. Next, we describe the proposed response threshold model. It is known that there are two types of ants: those sensitive to external stimuli and those insensitive to external stimuli. Sensitivity to external stimuli can be modeled using a parameter called a response threshold. An agent with a low response threshold becomes a worker with high probability even if external stimuli are weak, whereas an agent with a high response threshold does not become a worker even if external stimuli are strong. Thus, a response threshold can prevent outcomes in which all agents are workers or all agents are non-workers. In a conventional response threshold model, an agent changes from a worker to a non-worker with probability p and changes from a non-worker to a worker with a probability described by the following equation:

   ()2

   = ()2 + ()2

   , (1)

   where and s show a response threshold and an external stimulus at time t, respectively. The response threshold is updated using (2-a) if the agent is a worker and using (2-b) if the agent is a non-worker. If the agent is a worker, the response threshold decreases and the sensitivity of the agent to external stimuli increases. If the agent is a non-worker, the response threshold increases and the sensitivity of the agent to external stimuli decreases.

   1. Turn around

      ( + 1) = ()

      (2-a)

      When an agent cannot perceive a colony ahead, the agent turns through 180°.

      ( + 1) = () An agent can perform an exploring behavior or a foraging behavior by changing the combination of rules (Table 2). During the exploring behavior, an agent moves according to Rule 1 if it is a worker and can detect the trail-marking pheromone, but an agent moves randomly according to Rule 2 if it is a non-worker. During the foraging behavior, both worker and non-worker agents follow Rule 3. If an agent detects a homing pheromone, it moves according to

      ( + 1) = () . (2-b)

      In the conventional model, a stimulus s is updated by the ratio of the number of workers n(t) to the total number of ants m(t) in an agent group, as in the following equation:

      ()

      ( + ) = () + () . (3)

      Fig. 2. An ant system simulator.

      However, ants cannot know the state of all other ants. The above equation cannot therefore represent that the mechanism by which ants are able to form orderly groups through local interactions. We therefor propose a novel equation as follows:

      ( + 1) = ()

      () , (4)

      where N(t) is the number of foraging agents that an agent has touched during the steps up to time t, and M(t) is the total number of agents that the agent has touched during the steps up to time t.

4. SIMULATION

   We applied the proposed response threshold method to a foraging problem to investigate the effectiveness of the proposed model. The simulation results revealed the mechanisms that allow the appropriate ratio of workers to be maintained across fluctuations in food availability using only local information shared between adjacent agents.

   1. Simulation Setting

      As shown in Fig. 2, the experimental environment was a two dimensional grid space of 100×100 cells. The colony was placed at the center of the environment. In the initial state, food areas were randomly placed at two of the four corners. When the food in one area had been exhausted, the next food area was randomly placed in one of the corners. The two hundred agents were used in the simulation. A red cell showed a worker agent, and a blue cell showed a non-worker agent. When an agent touched food, it started to carry the food to the colony. A yellow cell contained a trail-marking pheromone. As the pheromone evaporated, and the level of the pheromone decreased, the color of the cell became lighter. The homing pheromone and the trail- marking pheromone did not merge. Fig. 2 omits the homing

      Fig. 3. The relationship between the ratio of workers and the quantity of

      obtained food.

      Fig. 4. The transition of the ratio of workers.

      Fig. 5. The relationship between the transition of the ratio of workers and

      the quantity of obtained food.

      pheromone for clarity. The initial pheromone level was set at five hundred, with the level reducing as the pheromones evaporated. The pheromones spread to an adjacent cell by diffusion, reducing by half in the process. If pheromones were already present in the cell when the diffusion took place, the strongest level of pheromone was selected. The simulation halted after 10000 steps.

      In the response threshold model, the probability with which an agent changed from worker to non-worker was step at p =

      0.001. Both stimulus and response threshold ranged from 0 to 1000. The initial response threshold was set at 500. The coefficients in (2) were = 10.0 and = 1.0. The coefficient in

      1. were = 1000. The number of steps across which an agent could retain a memory of touching another agent was set at =10.

   2. Simulation Results

      • Specialization using a response threshold model

        To determine the best ratio of workers, we fixed the ratio of workers before starting the experiment. Fig. 3 shows that agents obtained the most food when the ratio of workers was about 60%. Fig. 4 shows the transition of the ratio of workers when agents changed roles by using the proposed response threshold model. The ratio of workers converged to approximately 60%, regardless of the initial ratio. Fig. 5 shows the transition in the ratio of workers and the quantity of food obtained. As can be seen, the ratio of workers decreased with the amount of food. The discovery of a new food area led to increases in both the food obtained and the ratio of workers. Using the proposed response threshold model, agents could adapt robustly to the fluctuation of food supplies, by switching roles.

      • Specialization process using the response threshold model

        In this section, we first explain the process by which an agent switched roles in the response threshold model. Fig. 6(a) shows the transition in the ratio of workers. Fig.6(b)6(c), and

        6(d) show the strength of external stimuli, response thresholds, and the probability with which an agent switched roles, respectively. In Fig. 6(d), the red line shows the probability of switching from worker to non-worker, while the blue line shows the probability of switching from non-worker to worker. From Fig. 6(a) and 6(b), we can see that an agent received mor external stimuli when the ratio of workers was high. In Fig. 6(c), the agent became a non-worker after about 3500 steps, the response threshold increased, and the sensitivity of the agent to external stimuli decreased. Between about 3500 steps and 5800 steps, the probability that an agent switched from non-worker to worker was zero (Fig. 6(d)). However, as shown in Fig. 6(b), the frequency with which an agent touched a worker increased at about 5800 steps. At this point, the probability that the agent switched from non-worker to worker was 50%. The probability of an agent switching from worker to non-worker was always p

        = 0.001. As shown in Fig. 6(d), the agent became a non-worker after about 6200 steps. We can see that an agent switched roles stochastically based on the ratio of neighboring workers that the agent touched.

        Next, we explain how agents could assign roles appropriately, based on the short term ratio of workers touched, without requiring a centralized administrative system. Fig. 7 shows the relationship between the ratio of workers in an agent group and the mean of the ratio of foraging agents that an agent touched during ten steps. We can see that there is a correlation between the two, suggesting that the agents could assign roles appropriately against the fluctuation of food supplies.

      • The influence of different parameters on autonomous specialization

      This section repots how the number of agents and the length of memory affect autonomous specialization. First, to investigate the effect of the number of agents, we modeled the transition of the ratio of workers when the number of agents was 80, 100, 120, 140, and 200 (Fig. 8), from an initial ratio of 50%. We can see that the ratio of workers converged to about 60% when the number of agents was 140 and 200. When the number of agents was smaller than 120, the fluctuations in the ratio became bigger. This suggests that agents could not assign roles appropriately when the number of agents because the frequency with which agents touched each other was too low.

      1. The ratio of workers.

      2. External stimulus s.

      3. Response threshold .

      4. Probability q.

   Fig. 6. The relationship between the ratio of workers and the quantity of

   obtained food.

   Next, we investigated how the number of agents and the length of memory affected autonomous specialization. Fig. 9 shows the mean of the ratio of workers when changing the two parameters. In practice, we used the mean of the ratio of workers after 5000 steps as the analysis data because the fluctuation in the ratio of workers was large in the early steps. When the number of agents was over 180, agents successfully maintained the ratio of workers at about 60%. When the number of agents was 120 to 160, the ratio of workers decreased as the length of memory was shorter. When the number of agents was

   120 and the length of memory was one, the ratio of agents decreased to about 50%. When the number of agents was less than 120, the ratio of agents decreased below 50% even if when the length of memory was extended. Population density was critical to the maintenance of an appropriate ratio of workers. This was because the increase in the number of times that agents touched neighboring workers was more significant than the shorter length of memory. When the population density was low, the agents could not maintain an appropriate ratio of workers. These results demonstrate that if the population density is sufficiently high, the proposed response threshold model is robust, regardless of the length of memory.

5. CONCLUSIONS

This paper proposed a novel response threshold model to implement autonomous specialization in swarm robotics. The response threshold model is the computational model that represents the sensitivity of social insects to pheromone signals. An ant with high sensitivity becomes a worker, even if external stimuli are low. Conversely, an ant with low sensitivity does not become a worker, even if external stimuli are high. The difference in sensitivity prevents outcomes wherein all ants are workers or all ans are non-workers. The conventional response threshold model uses the ratio of workers in the group as external stimuli. However, individual ants cannot know the overall ratio of workers in the colony because only local communication through pheromones is

Fig. 7. The relationship between the ratio of workers in the colony and the ratio of foraging agents that an agent touched during ten step.

available. In contrast, the proposed response threshold model

used the ratio of foraging agents that an agent touched in a short term as an external stimulus.

Our simulations confirmed that, by using the proposed method, agents could maintain an appropriate ratio of workers and could collect food effectively. Based on the ratio of foraging agents that an agent touched in the short term, we analyzed the autonomous specialization process of an agent

and revealed the mechanisms through which agents could assign roles adaptively during fluctuations in the food supply. We further investigated how the number of agents and the length of memory affect the autonomous specialization of agents, showing that the proposed method was robust against environmental changes, regardless of the length of memory.

In future studies, we will investigate whether the proposed response threshold model can be adapted to fluctuations in the number of agents. We will also apply the proposed method to crowdsourcing [21], to investigate its efficiency.

Fig. 8. The relationship between the ratio of workers and the number of

agents.

Fig. 9. The relationship between the ratio of workers and the length of

memory.

REFERENCES

1. S. Nolfi, D. Floreano, Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines, MIT Press, 2000.

2. M. Tan, Multi-Agent Reinforcement Learning: Independent vs. Cooperative Agents, Proceedings of the 10th international Conference on Machine Learning, pp.330-337, 1993.

3. Tamer Abukhalil, Madhav Patil, and Tarek Sobh, Survey on Decentralized Modular Swarm Robots and Control Interfaces, International Journal of Engineering (IJE), Vol.7, No.2, pp.44-60, 2013.

4. Toshiyuki Yasuda, Kazuhiro Ohkura, and Kazuaki Yamada, Multi- Robot Cooperation Based on Continuous Reinforcement Learning with Two State Space Representations, Proceedings of 2013 IEEE International Conference on Systems, Man, and Cybernetics, pp.4470- 4475, 2013.

5. Kazuhiro Ohkura, Toshiyuki Yasuda, and Yoshiyuki Matsumura, Generating Cooperative Collective Behavior in Swarm Robotic Systems, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.17, No.5, pp.699-706, 2013.

6. Bonabeau, E., Dorigo, M., and Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999.

7. M. Dorigo and T. Stutzle, Ant Colony Optimaization, MIT Press, 2004.

8. Li-Pei Wong, Malcolm Yoke Hean Low, and Chin Soon ChongAn, Efficient Bee Colony Optimization Algoritm for Traveling Salesman Problem using Frequency-based Pruning, Proceedings of the 7th IEEE International Conference on Industrial Informatics (INDIN 2009), pp.775-782, 2009.

9. Nishant Pathak, Sudhanshu, and Prakash Tiwari, Travelling Salesman Problem Using Bee Colony With SPV, International Journal of Soft Computing and Engineering (IJSCE), Vl.2, No.3, pp.2231-2307, 2012.

10. Sonam Mittal, Neha Nirwal, and Harsh Sardana, Enhanced Artificial Bees Colony Algorithm for Travelling Salesman Problem, Journal of Advanced Computing and Communication Technologies, Vol.2, No.2, pp.2347-2804, 2014.

11. Guanjun Ma, Haibin Duan, and Senqi Liu, Improved Ant Colony Algorithm for Global Optimal Trajectory Planning of UAV under Complex Environment, International Journal of Computer Science & Applications, Vol.4, No.3, pp.57-68.

12. Ratan Mishra and Anant Jaiswal, Ant colony Optimization: A Solution of Load balancing in Cloud", {International Journal of Web $\&$ Semantic Technology (IJWesT)}, Vol.3, No.2, pp.33-50, 2012.

13. V. Ramos and J. J. Merelo, Self-Organized Stigmergic Document Maps: Environment as a Mechanism for Context Learning, Proceedings of 1st Spanish Conference on Evolutionary and Bio- Inspired Algorithms (AEB'02), pp.284-293, 2002.

14. Peter Miller, The Smart Swarm, Avery, 2010.

15. E. Bonabeau, A. Sobkowski, G. Theraulaz, and J. L. Deneubourg, Adaptive Task Allocation Inspired by a Model of Division of Labor in Social Insects, Proceedings of BCEC97, pp.36-45, 1997.

16. E. Hasegawa, Y. Ishii, K. Tada, K. Kobayashi and J. Yoshimura, Lazy workers are necessary for long-term sustainability in insect societies, Scientific Reports 6:20846, 2016.

17. Liviu A. Panait and Sean Luke, Ant Foraging Revisited, Artificial Life IX:Proceedings of the 9th International Conference on the Simulation and Synthesis of Living Systems, pp. 569-574, 2004.

18. Liviu A. Panait and Sean Luke, A Pheromone-Based Utility Model for Collaborative Foraging, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent System (AAMAS '04), Vol.1, pp.36-43, 2004.

19. Yuichiro Sueoka, Takuto Kita, Masato Ishikawa, Yasuhiro Sugimoto and Koichi Osuka, Distributed control of the number of clusters in obstacle collecting by swarm agents, Nonlinear Theory and Its Applications, Vol.5, No.4, pp.476-486, 2014.

20. Kazuki Nakayama, Yuichiro Sueoka, Masato Ishikawa, Yasuhiro Sugimoto and Koichi Osuka, Control of transportation trails by distributed autonomous agents inspired by the foraging behavior of ants, Nonlinear Theory and Its Applications, Vol.5, No.4, pp.487-498, 2014.

21. Thierry Buecheler, Rocky Lonigro, Rudolf M. Füchslin, and Rolf Pfeifer, Modeling and Simulating Crowdsourcing as a Complex Biological System: Human Crowds Manifesting Collective Intelligence on the Internet, Proceedings of the Eleventh European Conference on the Synthesis and Simulation of Living Systems (ECAL 2011), pp.109- 116, 2011.