Task partitioning in a robot swarm:
retrieving objects by transferring them directly between sequential sub-tasks.

Supplementary material

by Giovanni Pini, Arne Brutschy, Alexander Scheidler, Marco Dorigo, and Mauro Birattari
DATE: May 2012


Table of Contents
  1. Dead-reckoning noise model
  2. Video material
  3. Real robot experiments
  4. Validation experiments
  5. Environment and swarm size
  6. Effect of the number of sub-tasks

DEAD-RECKONING NOISE MODEL

To implement the noise model, we collected samples of the robots' dead-reckoning errors when trying to reach the source position estimate. We sample data from four of the runs in which the object retrieval task is not partitioned. Each sample records the error in the two dimensions X and Y on a trip from the source to the nest and back. The floor of the arena is covered by tiles that are used as a reference to calculate the error. The samples are collected manually from videos of the robots performing the experiment described here.

A total of 61 samples were collected from the videos of the experiments. These samples are reported in this figure; the closer a point to the origin, the smaller the dead-reckoning error for the corresponding trip. In the figure, the origin marks the position at which the object was gripped (which becomes the source position estimate of the robot). The bias towards the left-hand side (see this video) can be clearly seen in the plot (the nest is located at the top of the figure). This figure reports 77 error points taken in simulation with experimental conditions analogous to those in which the real-robot noise samples where taken.


TOP

VIDEO MATERIAL

This section contains miscellaneous videos. Two videos, rendered from the simulation, illustrate the behavior of the robots using the non-partitioning and the partitioning strategy (see Section 3 of the paper). A third video shows the trajectory followed by a foot-bot when moving straight. Figure 8 of the paper has been created using snapshots taken from the video. The last two video report complete experimental runs performed with the real robots, in one case the robots employ the non-partitioning strategy, in the other the partitioning strategy.
The video illustrates the behavior of the robots using the two strategies.
The video shows the trajectory of a foot-bot when both wheel speeds are set to 10 cm/s. In the first part of the video the robots goes backwards, in the second part it goes forwards. The video shows that the trajectory is curved towards the left-hand side with respect to the direction of motion.
The video shows a foot-bot gripping an object. The foot-bot initially approaches the object using the information from the omnidirectional camera. Once close to the object, the robot uses its prozimity sensors to refine the alignment and to determine when it is time to open the gripper. Once the object is gripped, the robot turns the turret in both directions, to check whether the object is already gripped by another robot.
The video shows two foot-bots transferring an object
The video shows a complete experimental run with the real robots employing the non-partitioning strategy. The experiment is divided into two phases of 15 minutes each. At the end of each phase, the robots' positions are marked on the arena floor, the batteries are changed, and the controller state is recorded so that it can be used to initialize the robots for the following phase. This is due to the high power consumption due to the extensive usage, made in the experiment, of the sensors and actuators available on the foot-bot. This causes the battery to drain quickly with a consequent increase of hardware failures, which hinder the integrity of the experiments. Limiting the duration of each phase decreases considerably the frequency of failures due to low battery.
The video shows a complete experimental run with the real robots employing the partitioning strategy. The experiment is divided into two phases of 15 minutes each. At the end of each phase, the robots' positions are marked on the arena floor, the batteries are changed, and the controller state is recorded so that it can be used to initialize the robots for the following phase. This is due to the high power consumption due to the extensive usage, made in the experiment, of the sensors and actuators available on the foot-bot. This causes the battery to drain quickly with a consequent increase of hardware failures, which hinder the integrity of the experiments. Limiting the duration of each phase decreases considerably the frequency of failures due to low battery.


TOP

REAL ROBOT EXPERIMENTS

The real robot experiments are carried out with a swarm of 6 robots in a 4.5 X 6.7 meters arena. The source to nest distance D is 4 meters. Each experimental run starts with 3 robots in proximity of the object source, the remaining in the center of the arena. The experiment lasts 30 minutes, divided into 2 phases of 15 minutes each. We run a total of 12 runs, 6 for the non-partitioning strategy and 6 for the partitioning strategy. For more details about the real robot experiments refer to section 5.1 of the paper. A summary of the retuls of each experimental run can be found here. Two videos showing complete runs can be found in the video section of this page.

PLOT - Empirical distribution of the object transfer and object grip times

The following plot reports the empirical distribution function of the time samples used in simulations. The samples are collected in real-robot experimental runs and used to simulate object transfer and object gripping in ARGoS (refer to Section 4.4 of the paper).

The plot is available here.

TOP

VALIDATION EXPERIMENTS

The goal of the validation experiments is to replicate the setup of the real robot experiments in simulation and validate the simulation of the studied system. For more details about the validation experiments refer to section 5.2 of the paper.

PLOT V1 - Validation, througput plot

The plot reports the value of the throughput in time for the validation experiments. The throughput is expressed as amount of objects delivered to the nest in a time window of 15 minutes, divided by the number of robots (6 in the experiments presented here). The value of the throughput is sampled every 2 simulated minutes. The figure reports the throughput for the partitioning strategy (top) and the non-partitioning strategy (bottom). The median (black line), the 25-75% (blue) and the 5-95% quantiles (red) are reported.

TOP

PLOTS V2 - Simulation and real robot experiments - probability of getting lost, QQ plots

Each file reports the QQ plot of the probability of getting lost, computed in simulation and with the real robot experiments. In case the partitioning strategy is employed, the data is divided into two sets. One set is relative to the probability of getting lost when searching the object source (i.e., the source position estimate of the robot is relative to the source). The other set is relative to the probability of getting lost when searching other robots (i.e., the source position estimate of the robot is relative a transfer location).

Click on a link to see the corresponding plot:

Simulation, non-partitioning strategy
Simulation, partitioning strategy - search source
Simulation, partitioning strategy - search other robots
Real robots, non-partitioning strategy
Real robots, partitioning strategy - search source
Real robots, partitioning strategy - search other robots

TOP

TABLE 1 - Simulation and real robot experiments - comparison figures

The tables compare simulation and real robot experiments. For each statistic, the mean and 95% confidence interval on the value of the mean are reported. The first table reports the data collected in the experiments in which the swarm employs the non-partitioning strategy, the second table the data collected in the experiments in which the swarm employs the partitioning strategy.




Non-partitioning strategy

STATISTICREAL ROBOTSIMULATIONDESCRIPTION
Get lost frequency - objects source70.93 / 77.16 / 85.2276.66 / 77.91 / 79.1 Frequency at which the robot do not locate the source during neighborhood exploration and gets lost.
Source found during exploration - %70.47 / 77.85 / 85.2376.66 / 77.91 / 79.1 % of time the source is found during exploration (instead of during neighborhood exploration)
Source found directly - %23.81 / 43.53 / 60.47 37.67 / 41.77 / 45.63 % of time the source is directly found: the duration of neighborhood exploration is zero.
Exit arena - num times0 / 0 / 0 0 / 0.01 / 0.025 Number of times the robot tried to reach a position outside the boundaries of the arena



Partitioning strategy

STATISTICREAL ROBOTSIMULATIONDESCRIPTION
Get lost frequency - objects source6.31 / 11.37 / 17.1613.29 / 14.05 / 14.81 Frequency at which the robot do not locate the source during neighborhood exploration and gets lost.
Source found during exploration - %11.42 / 16.92 / 22.321.51 / 22.29 / 23.04 % of time the source is found during exploration (instead of during neighborhood exploration)
Source found directly - %59.66 / 73.94 / 87.05 63.55 / 64.88 / 66.15 % of time the source is directly found: the duration of neighborhood exploration is zero.
Get lost frequency - transfer locations11.48 / 14.14 / 17.65 11.35 / 11.94 / 12.56Frequency at which the robot do not locate the position where it received an object and gets lost.
Transfer partner found during exploration - %10.05 / 12.88 / 16.92 8.87 / 9.46 / 10.04 % of time a transfer partner is found during exploration (instead of during neighborhood exploration)
Transfer partner found directly - %28.52 / 31.73 / 35.2 14.24 / 15.23 / 16.19 % of time a transfer partner is directly found: the duration of neighborhood exploration is zero.
Abandon transfer0.33 /0.83 / 1.33 0.7 / 0.83 / 0.95 Number of times the robots abandoned trying to transfer the object (timeout)
Exit arena - num times0 / 0.16 / 0.5 0 / 0 / 0 Number of times the robot tried to reach a position outside the boundaries

TOP

ENVIRONMENT SIZE AND NUMBER OF ROBOTS

The goal of the experiments described here is to evaluate the effect of the size of the environment and of the number of robots on the behavior of the system. More details and results about these experiments can be foudn in section 5.4 of the paper.

TABLE 2 - Probability of getting lost in relation to the number of robots and the size of the environment

The following table reports the probability of getting lost for different environment and swarm sizes. The percentage summarize, for each environment/swarm size, the data collected in the corresponding 200 experimental runs. The table shows that, for a given swarm size, the probability of getting lost does not depend on the specific environment. It is instead linked to the distance D between source and nest (4.0 m in this experiments). The table also shows that the percentage grows with the swarm size, this is a consequence of physical interference between the robots. Notice that the cases in which the mechanism that checks if the robot is trying to exit the arena (desribed in Section 4.4 of the paper) is counted in the percentages as a case in which the robot got losts.

SMALL ENVIRONMENTNORMAL ENVIRONMENTLARGE ENVIRONMENTHUGE ENVIRONMENT
2 robots 76.71 % 76.63 % 77.04 % 78.20 %
4 robots 76.59 % 76.25 % 77.54 % 77.29 %
6 robots 77.54 % 76.85 % 78.19 % 78.22 %
8 robots 78.38 % 77.42 % 78.61 % 77.83 %
10 robots 78.22 % 78.01 % 78.66 % 78.31 %
15 robots 79.85 % 78.27 % 79.22 % 78.37 %
20 robots 80.85 % 79.78 % 80.07 % 79.09 %
30 robots 83.44 % 80.66 % 81.29 % 80.34 %

TOP

TABLE 3 - Probability of getting lost for different sizes of the swarm and strategy - Small environment

The following table reports the probability of getting lost (get lost %) computed in the small environment for the two strategies and the for the different swarm sizes. The table also reports the percentage of times in which the robot detected it was trying to exit the arena (exit arena %), expressed with respect to the total number of times the robots got lost. Exit arena % is therefore computed as:

 exit arena % = number of times the robot tried to exit the arena / (number of times the robot got lost + number of times the robot tried to exit the arena) 


The data in the table highlights two aspects. First, it confirms that the partitioning strategy improves the localization capabilities of the robots with respect to the non-partitioning strategy. Second, the performance degrades for an increasing swarm size (refer to the paper) mostly because the robots perceive that they are exiting the arena. As mentioned in the paper, the mechanism that checks whether a robot is trying to exit the arena, is based on the perception of obstacles. Overcrowding increases the number of false positives detected by the mechanism. The partitioning strategy is more sensitive to this phenomenon, given that robots concentrate on the path between nest and source and form groups that impede the movements and are perceived as obstacles.

NO PARTITION - get lost %NO PARTITION - exit arena %PARTITION - get lost %PARTITION - exit arena %
2 robots 76.71 % 21.54 % 13.32 % 14.15 %
4 robots 76.59 % 22.61 % 15.05 % 10.53 %
6 robots 77.54 % 23.95 % 17.81 % 14.56 %
8 robots 78.38 % 23.86 % 21.58 % 19.68 %
10 robots 78.22 % 25.90 % 24.92 % 24.78 %
15 robots 79.85 % 27.75 % 33.86 % 36.53 %
20 robots 80.85 % 29.44 % 42.17 % 44.97 %
30 robots 83.44 % 35.05 % 56.68 % 56.98 %

TOP

PLOT E1 - Empirical distribution of time needed to find the source

The plots report the empirical distribution of the time it takes to find the source, in the 4 different environments. The data reported accounts for the time it takes the robots to find the source, after neighborhood exploration failed (i.e., after a robot got lost). The graph on top of each figure reports the data for the non-partitioning strategy, the one at the bottom for the partitioning strategy. The graphs show that a bigger environment results, in general, in a longer average time required to find the source. This is not the case of the normal and large environments. In this case the large arena requires a (slighly) shorter time for finding the source. This is because in the normal arena the source is very close to a wall, and it is harder to find it by random walk, despite the smaller area. The graphs also highlight that the robots take less time in finding the source when the partitioning strategy is employed, compared to the time needed when the non-partitioning strategy is employed. This indicates that the robots get lost in positions that are closer to the source (i.e., the localization error is smaller).

Click on a link to see the plot for the corresponding environment:

SMALL ENVIRONMENT
NORMAL ENVIRONMENT
LARGE ENVIRONMENT
HUGE ENVIRONMENT

TOP

EFFECT OF THE NUMBER OF SUBTASKS

In these experiments we study different ways for partitioning the task in terms of number of sub-tasks. We test partitioning strategies that partition the task in 1 (i.e., without partitioning) to 8 sub-tasks. We test two settings that differ in the value of the source to nest distance D: in one case it is set to 4 meters, in the other case it is set to 6 meters. The experiments are run in the huge environment.

PLOTS B1 - Performance plots for different number of sub-tasks and swarm sizes

The following plots report the performance of swarms of different size and for different number of sub-tasks in which the object retrieval task is partitioned. In the first set of plots, the source to nest distance D is 4 meters, in the second set it is 6 meters. The performance is reported as total amount of objects retrieved by the swarm at the end of the experiment. Click on a link to see the correpsponding plot:

D = 4 meters: 4 robots, 6 robots, 8 robots, 10 robots, 15 robots, 20 robots, 30 robots
D = 6 meters: 4 robots, 6 robots, 8 robots, 10 robots, 15 robots, 20 robots, 30 robots

TOP