Control >> Adaptive division of labour

Adaptive division of labour

The final scenario of the project involves the use of many s-bots to perform different and concurrent tasks. It would be desirable to design control policies for the s-bots to be capable of automatically allocating resources (i.e., the minimal amount of agents necessary for each task) with respect to the nature of the task in which they currently engage. The issue we investigate in this section concerns the nature of these mechanisms for allocating resources. In particular, we are interested in having the swarm itself to adapt to the environment in which it is working. The means by which the swarm can itself allocate s-bots to one task or the other is called division of labour.

We first studied a simple case, where there is only one task. We implemented an algorithm inspired by the division of labour observed in ants, and we present here a study of its characteristics.

The test application we chose to work with is a prey retrieval task. The s-bots have to look for objects, which are also called prey, and retrieve them to a particular place of the environment, called nest.

Experiments were done both in simulation and with real robots. At the time of experiments with the robots, no prototype of the s-bots were available, therefore we used some built with LEGO Mindstorm©

We simulated the robots in a circular arena, 2.40 m of diameter (see Figure 1). The nest is signalled by a light in the centre of the arena. Prey are black cylinders which appear randomly. In simulation, the probability with which it happens each second, which we refer to as prey density, is a parameter and varies from 0.005 s^-1 to 0.04 s^-1. The number of s-bots in the group, sometime also referred to as colony, varied from 2 to 8. We had not been able to use more s-bots because there would have been no space for them in the nest. With the real robot, given that the experiments were very time consuming, we test only a group of 4 robots with prey size of 0.006.

Figure 1. Left and center: real and simulated arena. The nest in placed in the centre and is signalled by a light right above it. S-bots are looking for prey, which are black cylinders. Right: simulated model of an s-bot.

The s-bots are controlled as depicted in Fig. 2. They all start resting in the nest. Each robot start searching with a probability P_l each second. If a prey is found before a timeout is reached, the prey is retrieved, otherwise the robots come back to the nest.

Figure 2. Schema of the s-bots' control algorithm.

The s-bots modify their value of P_l according to the following algorithm:

• initialisation at the beginning of the experiment:
  
  • failures = 0
  • successes = 0
  • P_l = P_init
• if a prey is retrieved:
  • failures = 0
  • successes = successes + 1
  • P_l = min{P_l + successes * D, P_max}
• if the s-bot returns without prey in the nest:
  • failures = failures + 1
  • successes = 0
  • P_l = max{P_l - failures * D, P_min}

At any given instant t after the beginning of the experiment, the value of P_l in an s-bot is a random variable which has different values for every robot and every experiment. The occurrence of division of labour can be observed in the distribution of P_l. The result for the real robots can be seen in Fig. 3 (data refers to 10 experiments, 4 robots for experiment). We noticed that the s-bots still tend to have either low or high value of P_l, but seldom in between. We classified the s-bots into three classes: foragers, loafers and undecided. Foragers have P_l is bigger than 0.042, loafers have P_l lower than 0.007, and the rest are undecided (notice that this last group spans over a range of values for P_l that is five times bigger than the others).

Figure 3. Distribution of P_l among the robots after 2400 s after the beginning of the experiments. The U-shape shows that the robots tend to have either high or low P_l. Colours identify three classes: loafers, undecided and foragers

In simulation, we performed 50 experiments for prey density 0.005 s^-1, 0.01 s^-1, 0.02 s^-1 and 0.04 s^-1 and for colonies of 2, 4, 6 and 8 s-bots. We recorded the final value of P_l for each robot after 2400 s and estimated its distribution. Figure 4 reports the percentage of s-bots in each class for each combination of prey density/group size.

(a) Prey density = 0.005	(b) Prey density = 0.01
(c) Prey density = 0.02	(d) Prey density = 0.04

Figure 4. Percentage of observed s-bots that were forager, undecided or loafers at the end of the experiments in simulation. Note that the percentage of foragers increases with the prey density and that decreases with the colony size.

The data shows that the control algorithm described above can effectively adapt the colony to different environments, reducing the number of active robots if they are more than needed and increasing it otherwise.

The mechanism of division of labour that we are studying is based only on individual successes or failures. If one s-bot, for any reason, is better than the others for the task of retrieving, then it will be more successful and therefore it will always become a forager. Generally speaking, the differences can be artificially created or intrinsic in the robots. In the first case, for instance, some robots can be intentionally designed for the task of retrieving while the others are designed to explore the environment to find and mark dangerous spots. In the second case, the differences come from the imperfections of the robots' components, which can never be identical, e.g., one motor that is less powerful than another. Any mechanism for division of labour should take into account the heterogeneity of the colony.

We could proove that differences among real robots make some of them more likely of becoming foragers. You can read more details in our paper. In simulation, given that the s-bots are completely identical, we artificially introduced some differences that might make one better than the other in retrieving. We created six different s-bots that differ in their maximum speed. More precisely, the maximum speed of the first s-bot, named s-bot1, was equal to the one in the previous experiments multiplied by 0.5. The speeds of the other fives robots were scaled respectively by 0.7, 0.9, 1.1, 1.3, 1.5. The six robots were combined into all possible colonies of four robots, creating fifteen different groups. Each group was tested in the same set of fifty randomly generated environments where prey appeared with probability 0.01 s^-1. The groups were simulated for 2400\,s and we counted how many times each s-bot became a forager (P_l bigger than 0.043). The results are reported in Table 1.

Statistical tests show that the probability to become a forager increases with the maximum speed of the individual.

The s-bots are also able, using the control algorithm illustrated above, to adapt to dynamic environments. If the prey density increased, some s-bots in the nest would eventually joint the nest-mates in retrieving. If the prey density decreased, some unsuccessful s-bot would decrease its P_l till it becomes a loafer.

We simulated what happens when the prey density increase while a group of s-bots is at work. What follows refers only to work done in simulation. The group started with prey density equal to 0.005 s^-1. After 3600 s (that is, 20 minutes after the end of the previous experiments) prey density changed to 0.04 s^-1, and the s-bots worked for other 3600 s. Therefore the total experiment lasted 7200 s. We refer to this set-up as dynamic environment. We tested then the same colony starting from the same initial conditions and working for 3600 s with prey density directly set to 0.04 s. We refer to this set-up as static environment. The results are reported in Fig. 5.

(a) Group size = 2	(b) Group size = 4
(c) Group size = 6	(d) Group size = 8

Figure 5. Percentage of observed s-bots that were forager, undecided or loafers in dynamic and static environments. The distribution of the robots after the change of prey density in a dynamic environment is different from the static one.

The interesting result that we obtained is that the distribution at the end of an experiment in a dynamic environment differs from the distribution obtained in a static environment. We observed that these distributions have not changed for a long time (more than 1000 s) before the reported times, therefore can be considered stable. Thus, the cause of the differences should rely in the sensibility of the group to different initial conditions. Future work will try to identify the interactions and the mechanisms that lead to this phenomenon.

References

• Labella T.H., Dorigo M., Deneubourg J.-L. Self-Organised Task Allocation in a Group of Robots. In R. Alami, editor, Proceedings of the 7th International Symposium on Distributed Autonomous Robotic Systems (DARS04). Toulouse, France, June 23-25, 2004.
• Labella T.H., Dorigo M., Deneubourg J.-L. Efficiency and Task Allocation in Prey Retrieval. In A.J. Ijspeert, D. Mange, M. Murata, and S. Nishio, editors, Proceedings of the First International Workshop on Biologically Inspired Approaches to Advanced Information Technology (Bio-ADIT2004), Lecture Notes in Computer Science, pages 32-47. Springer Verlag, Heidelberg, Germany.
• Labella T.H. Prey Retrieval by a Swarm of Robots. Technical Report TR/IRIDIA/2003-16, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, May 2003. DEA thesis.

Control >> Adaptive division of labour