25 holonomic circular robots of radius 0.25 m with 360-degree field of view sensors of range 50 m must form a flock and move together through a marked course to a goal location with minimal collisions between each other. Assume that the sensing of each robot is perfect, that they all may home toward both the line through the course and the goal location, but that each robot may not explicitly communicate with any other robot. The goal of robots is to minimize the average distance of each robot from the centroid of the distribution of robots without colliding and minimize the distance of the centroid from the closest point on the line at each time step while making progress toward the goal location.
Implementing algorithm from Matarić, “From Local Interactions to Collective Intelligence,” The Biology and Technology of Intelligent Autonomous Agents, NATO ASI Series 144, 275:295, Springer, Berlin, 1995.
2.2 Simulation Environment
Unity Engine is used as the tool for simulation the behavior of this collective behaviors task. Figure 1 (right) basically shows the simulation environment. In Figure 1 (right), the left-side window, which is the Scene View, shows that models while the left-side window, which is the Game View, is the simulation "playground". Figure 1 (left) is a theoretical diagram of this task. First, 25 robots will appear randomly inside of a circle with a radius of 50 meters (green circle in the right figure). Then these robots need to form a flock and move along the two courses (magenta lines in the right figure) until finding the goal.
Figure 1 (left) Theoretical diagram; (right) Simulation environment (i.e. Unity3D Engine editor interface).
2.3 Component Behaviors
In Matarić's paper, in order to achieve the goal of flocking, 4 behaviors are integrated. They are (1) collision avoidance, (2) following, (3) aggregation and (4) dispersion. In the writer's understanding, however, dispersion, which basically lets robot avoid another "too close" robot and move forward to the local centroid, can be treated as a combination of collision avoidance and aggregation. By this reason, there is no such a dispersion behavior in the writer's code. Besides the three behaviors from flocking (which are collision avoidance, following, and aggregation), another behavior called homing is also included to simulate whole states of robots. These behaviors will be further explained and discussed later.
Before diving into details of each behavior, first, please talk a look at a one-line code above. A net vector is used to determine the heading of each robot and is calculated based on the four behaviors. The four behaviors (collision avoidance, following, aggregation and homing) are accomplished by four separate functions, which will return a vector respectively. The four factors before each function are the corresponding factor for each behavior for easily controlling the whole system. For instance, if one wants to see the single homing behavior, just set the homing vector non-zero and other factors to be zeros, which you will see in a second. Similarly, any other behaviors could be observed in this way.
The actual body of robot (radius = 0.25 m) is denoted by a small black dot in the center of light blue circle. The white-blue circle shows a "safe" region (diameter = 5 m) and provides a better visual indication of where each robot is.
Robot will calculate and move forward to a local centroid within its sensing range. This is the key for forming a flock. Without consideration of collision avoidance, all robots will finally merge into one.
After including the collision avoidance, robots will not collide with each other due to the aggregation. They will keep a "safe" distance with each other, which is 2.5 m in this case denoted by white-blue circles.
Robot will be attracted by the points on the two courses and can be dragged to the most closest (to the goal) point. This is the reason that all robots choose to bypass the corner instead of go along the lines.
Following will let robots to get an attractive force by nearby robots (those outside its "safe" region). It behaves pretty like aggregation so will not show separately.
The left video shows an integration of all the four behaviors.
Changes of behaviors as vary number of robots from 25 through 100 were observed. Four scenarios (25 robots, 50 robots, 75 robots and 100 robots) were simulated during the experiment. Here are four videos for each scenarios. The videos were accelerated to be viewed within 15 seconds while their actual durations are between 7 minutes and 13 minutes.
Two metrics are used to analyze the system, (1) average distance of each robot from centroid of distribution of robots for numbers and (2) average distance of centroid from closest point on line through course. These two metrics were calculated and recorded per second during the experiment for every scenario. Based on that, time versus average distance of each robot from centroid of distribution of robots for numbers and time versus average distance of centroid from closest point on line through course are plotted in Figure 2 and 3, respectively.
Figure 2 Time versus average distance of each robot from centroid of distribution of robots for numbers.
Figure 3 Time versus average distance of centroid from closest point on line through course.
This metric (average distance of each robot from the centroid of distribution of robots for numbers) actually describes how close (or dense) robots are with each other. Hence, the lower the metric, the denser the robots. Robots first were generated in the start region randomly so all four curves almost start from similar positions. Then the curves drop rapidly because of the aggregation and following behaviors as shown in previous videos. The metric stops as a constant afterward because all robots obtain a steady-state distance with each other as a whole flock. Thus, the metric increases with the number of robots linearly.
Another interesting observation could be seen through this figure. The time spent to let all robots arrive the goal increases with the number of robots as well. This may be caused by the doubled results of moving forward (by homing) and dragged by robots (by aggregation, which will be increased by the number of robots) behind of the robots who are in the front of the flock. On the other side, the robots in the back of the flock are obstructed by those front robots. However, a possible explanation would be the downside of this simulation design - no acceleration was included in the physical engine so the speed of robot can be changed instantly. By this reason, robots could not achieve their full speed (i.e. 2 m/s) when rapidly changing heading direction by algorithms. This problem should be definitely fixed to fully represent the behaviors of robots.
Fortunately, this task shows no apparent relation with the speed of the robots, so the results can show the collective behaviors of robots as its initial goal.
The other metric (average distance of centroid from closest point on line through course) basically indicates how close the flock is to the courses. A peak in the metric exists in every curve in Figure 3, which is the moment when the flock bypasses the corner between the two courses. This could be seen in the "Homing" video and any other videos in the experiment section. The cause of this peak is because the way of writer tried to achieve homing behavior is to set up a series of points on the courses first and check in a reverse order (the goal will be the first point to check). So when robots moves to the corner of the courses, they will find the point on the second course and directly go to that point and ignore the points on the corner. This peak could be fixed by changing the way of homing or just set up fewer points to achiever the same purpose.
Unlike the previous metric, this metric is decreased when increases the number of robots.
* 2.6 Further study
If assume that a fixed ratio (e.g. 50% in the video above, denoted by darker blue) of robots cannot move towards courses (i.e. without homing behavior), some interesting results could be observed. These non-homing robots can finally reach the goal as the other homing robots thanks to the aggregation/following behavior, which lets them to follow the robots who can detect the courses.
Based on the former video, if the aggregation/following behavior of the non-homing robots is removed as well. In this case, these robots will only avoid other robots who are too close to them without any other behaviors. As shown in the video above, these robots quickly disperse and homing robot flock will be affected by these dispersing robots so cannot reach the goal as normal.
There are several things could be done to make these "sheep" robots (only with collision avoidance behavior) herded by other "herding dog" robots (cannot detect courses and have homing behavior). First, the "herding dog" robots could try to form a circle for trying to cover as many the "sheep" robots as possible for preventing them from dispersing. Then, the "herding dog" robots need to drive the "sheep" robots to reach the goal without losing them during migration. With this kind of algorithm, hopefully, all the robots could reach the goal, which can be done in future works.
Figure 4 Comparison between all homing scenario (base case, black lines) and 50% non-homing scenario (video above, red lines): (1) solid lines: Time versus average distance of each robot from centroid of distribution of robots for numbers; (2) dashed lines: Time versus average distance of centroid from closest point on line through course.
In Figure 4, two black lines denote the scenario that all robots have homing behavior, in which solid line is time versus average distance of each robot from the centroid of distribution of robots for numbers and dashed line is time versus average distance of the centroid from the closest point on line through courses. Red lines represent the scenario that 50% robots do not have homing behavior so they can either follow other robots or move with the local centroid.
Removing homing behavior from half of the robots almost has no influence on the first metric - average distance of each robot from the centroid of distribution of robots for numbers. Because all robots regardless homing or non-homing are pretty close to each other at the "safe" distance as shown in the videos above due to aggregation/following. Thus, the average distance of each robot from the centroid of distribution of robots for numbers becomes invariant when a flock formed.
However, the second metric (average distance of the centroid from the closest point on line through courses) in the 50% non-homing scenario varies a lot compared with the base case since the overall dragging produce by homing behavior is reduced by removing the homing behavior from half of the robots. By this reason, the time spent on reaching the goal increases in the 50% non-homing scenario.