Journal of Robotics, Networking and Artificial Life

Volume 6, Issue 1, June 2019, Pages 60 - 65

Design and Analysis of Multi-robot Grouping Aggregation Algorithm

Huailin Zhao1, *, Zhen Nie1, Xiaoxing Wang2
1School of Electrical and Electronic Engineering, Shanghai Institute of Technology, No. 100, Haiquan Road, Fengxian District, Shanghai 201418, China
2College of Engineering, University of Massachusetts Amherst, Amherst, MA 01003, USA
*Corresponding author. Email:
Corresponding Author
Huailin Zhao
Received 30 September 2018, Accepted 15 November 2018, Available Online 25 June 2019.
10.2991/jrnal.k.190602.002How to use a DOI?
Multi-robot; clustering; grouping aggregation; swarm intelligence

In this paper, the grouping aggaregation problem of multi-robot in simple environment is studied. The grouping algorithm and aggregation algorithm are mainly discussed. Based on K-means clustering algorithm, a grouping control algorithm that can determine the number of groups and complete the grouping task autonomously was designed. Aiming at the problem of aggregation, three kinds of aggregation algorithms are proposed. Taking the center aggregation control as an example, the cooperation and control of each group of robots are studied. Finally, the simulation results of MATLAB show that the multi-robot grouping and aggregation algorithm is effective.

© 2019 The Authors. Published by Atlantis Press SARL.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (


The multi-robot collaboration system is a frontier topic in the field of artificial intelligence [1]. From the control point of view, the multi-robot collaboration system is a typical distributed control system [24], and its goal is to build large complex systems which included software and hardware systems into small, easy-to-manage systems that communicate and coordinate with each other. The research of multi-robot collaboration system involves the knowledge, goals, skills, planning of robots and how to make robots coordinate actions to solve problems, and the idea of swarm intelligence is emphasized. The multi-robot collaboration system forms a complex system through communication, coordination, and cooperation among autonomous robots. The major applications include formation flying of multi-unmanned aerial vehicle (UAV), clusters of warehousing logistics robot, competitions of robot team, large-scale robotic rescue systems, etc. Some examples in nature are dancing fish, flying birds, and so on.

Aggregation is the basic problem of multi-robot system consistency [5,6], and it is also an optimizing measure [7], and the grouping aggregation is a special case of aggregation problem. Group aggregation is a motion planning of the robots randomly distributed in space, which are divided into many groups according to a specific grouping rule, and then each group of robots adjust the motion states through communication and cooperation between each other, finally they gather together, or in the desired area to complete the aggregation. In the end, all the robots formed a multi-group gathering situation, the idea of swarm intelligence is emphasized.

After analyzing the K-means algorithms, an efficient grouping aggregation algorithm that can automatically select the number of groups is designed based on K-means. The feasibility of multi-robot grouping aggregation is verified by MATLAB (Mathworks Inc., United States) simulation experiment. And the multi-robot distributed coordination and grouping aggregation control are realized.


Grouping aggregation is divided into two steps, grouping task and aggregation task. The grouping task is to complete the group division of each robot according to a specific grouping rule. This study designed and analyzed a grouping algorithm based on K-means algorithm.

The K-means algorithm is a clustering algorithm which is the simplest and most commonly used in unsupervised learning. It is a center-based clustering algorithm [8,9]. The K-means algorithm completes the grouping task by minimizing the distance between each sample and the center of the cluster. The initial centers of each cluster were randomly selected.

In the Euclid space, a set of n-dimensional samples X = {x1, x2, x3xixn} (representing n robots) is given, where xiRn. The K-means algorithm divides all samples into k clusters C = {ci, i = 1, 2, …, k}. The Euclidean distance is chosen as the criterion for the distance, the equation is expressed as follows.

where xi, xj represents two points in the Euclid space, which are two n-dimensional data.

In determining the similarity of the samples, the samples are divided into the clusters with the highest similarity according to the following equation (the similarity is based on the distance between the samples and the centers, and the smaller the distance, the higher the similarity).

where μi is the center of ith cluster.
where Ni is the number of samples in group i.

The K-means algorithm needs to re-divide the cluster and update the centers iteratively. When the square error sum is converged, the K-means algorithm ends. The equation of square fitting error sum is given by

where dij={1,xjci0,xjci .


There are two limitations [10,11] of K-means algorithm. Firstly, the value of the k needs to be specified by the users in advance. But the value of k is difficult to estimation, which may result in unreasonable grouping. Secondly, the biggest disadvantage of K-means is that the selection of initial clustering centers has a great influence on the results, which can easily lead to the increase of iteration times and fall into local optimum. Therefore, we have improved the grouping algorithm that can automatically select the number of groups based on the K-means algorithm. For the problem that the k-value is difficult to estimate, we have added two processes of “merging” and “split” in the process of grouping, so that it can automatically adjust the number of groups in the grouping process. Merging means that merge the two groups into one group when the number of samples in one group is too small or the distance between the two groups is too close. Splitting refers to splitting the group into two groups when the variance in one group is too large. For the initial center problem, we select the initial cluster center by the maximum distance.

The grouping algorithm can complete the grouping by seven initial parameters (K, k, θN, θc, θs, L, I). Where K is the expected number of groups. k is the initial number of groups. θn is the minimum number of samples in each group. If the samples are less than this number, the group will be removed. θs is the maximum standard deviation of the sample features in a group. If it is greater than this value, the group may be split. θc is the minimum distance between the centers of the two groups. If it is less than this value, the two groups need to be merged. L is the maximum number of groups that can be merged in a merge operation. I is the number of iterations.

The idea of the grouping algorithm is as follows:

After seven initial parameters are given, K initial clustering centers must be determined first. And the initial clustering centers are selected according to the maximum distance. The specific operation is to calculate the distance between any two points according to formula (1), and find the two points x1 and x2 with the largest distance. Then with x1 and x2 as references, search for x3 so that the distance from x3 to x1 and x2 is the largest at the same time. Repeat this operation until k points are selected, and the k points are used as the initial cluster center.

After the initial clustering center is selected, clustering is carried out according to formula (2). If the number of samples in any group is less than θn, the group will be cancelled, and the value of k is subtracted by 1. Then the clustering is carried out again. The average distance Di¯ from each group of samples to the group center and the total average distance D¯ of all samples were calculated.

where Ni is the number of samples in ith group; μi is the center of ith group, and n is the number of all samples.

After each clustering is completed, the obtained clustering results are split and merged according to a given requirement, thereby a new clustering center will be obtained. Split, merge or iterate is according to the following conditions.

  1. (1)

    If the number of iterations is odd or k12K , that is, the number of cluster centers is less than half of the expected number of groups, splitting the existing clusters;

  2. (2)

    If the number of iterations is even or k ≥ 2K, that is, the number of cluster centers is more than twice the number of expected groups, the existing clusters are not split.

The split operation is as follows:

First, the standard deviation of all components in each group (also known as features of each dimension) is calculated, which is defined as formula (7):

where Ni is the number of samples in ith group, xln is the nth component of the lth in the group ci, μln is the nth component of the center of the group ci.

Find the largest standard deviation of component in each group: δimax, i = 1, 2, 3, …, k, if δimax > θs, and the group satisfy one of the following two conditions, split the group into two groups.

  1. (1)

    Dj¯>D¯ and Ni > 2θn+1

  2. (2)


The center after splitting is recorded as μi+ and μi , μi+ and μi are given by

where 0 < h < 1.

The merge operation is as follows:

Firstly, the distance Dij of each cluster center is calculated. The Dij is expressed as follows.

where μi is the center of the ith group and μj is the center of the jth group.

Comparing Dij with θc, and arranging all Dij that smaller than θc from small to large. Then merging the group ci and cj start from who has the smallest Dij. The new center is expressed as follows:

where Ni and Nj are the number of samples of the groups ci and cj.


As mentioned earlier, the aggregation problem is that multi-robots randomly distributed in the space adjust the motion states through communication and cooperation between each other, finally they gather together, or in the desired area to complete the aggregation. Aiming at the aggregation task requirements of this topic, three aggregation control algorithms were designed and analyzed in this paper:

  1. (1)

    Selecting a robot from each group as leaders, as shown in Figure 1a. The basic idea of this algorithm is to pre-set a leader robot, and other robots are called followers [12,13]. In the process of aggregation, the leader controls the motion path, and the followers keep a certain angle and distance with the leader, finally all robots aggregate at the position of the leader. After careful analysis, the aggregation has some defects. On the one hand, because the algorithm does not make full use of the advantages of distributed systems, when the leader robot goes wrong, it will cause all robots fail to aggregate. On the other hand, because the control of the system is relatively simple, the follower or leader robot may be lost in the process of motion in the complicated reality environment. The aggregation task failed.

  2. (2)

    Selecting the neighboring robot as the reference point, as shown in Figure 1b. Each robot finds its own target position in the whole aggregation movement through the position information of neighboring robots. The limitation of this method is that a large amount of communications is required, and each robot needs to spend more time for communication, and the result of the formation control is not satisfactory.

  3. (3)

    Selecting the center of group as the reference point, as shown in Figure 1c. This selection method is called center algorithm. During the aggregation process, multiple robots form a geometric figure. According to the geometric figure, the geometric center is calculated. Each robot uses takes the center as a reference point to adjust the direction and speed, and move to the reference point. During the aggregation movement, the system constantly updates the reference points, and finally all robots reach a same point. The aggregation task is end. This algorithm is simple and practical. The system is convergent. The advantages of the distributed control system are fully reflected.

Figure 1

Three different aggregation algorithms: (a) Selecting a robot from each group as leaders. (b) Selecting the neighboring robot as the reference point. (c) Selecting the center of group as the reference point.

Comparing the three aggregation algorithms, this study intends to use the center algorithm for aggregation control. The center calculation equations are expressed as follows:

where (xi, yi) is the 2-D coordinate of the current position for the ith robot, and (xc, yc) is the center coordinate.

During the aggregation process, the system periodically updates the center position and notifies all robots. Each robot makes motion planning according to its current position and new center position. The motion planning equation is given by:

where T is the sampling period, Xi is the motion state of ith robot, vi is the velocity of ith robot.

In the later stage of aggregation, the robot is close to each other and collision may occur. So the dynamic obstacle avoidance of robots is studied. When the robot finds that other robots may affect its motion, the robot produces an obstacle area according to the current position and predicted position of the obstacle. Then the robot turns left or right at a certain angle to avoid collision. The output vector formula of robot avoiding dynamic obstacles is defined as follows:

where θm is the angle between the motion direction of the robot and the line connecting the robot and the obstacle robot. ± indicates the direction of the robot’s rotation, which is determined according to the predicted direction of obstacle motion and the relative position of obstacle area. [xdyd] is the direction of obstacle motion predicted by the robot, and α is a given constant.


As mentioned earlier, to complete the grouping aggregation task, the first thing should be done is grouping operation, and the next is the aggregation operation. The specific process is as follows.

According to the grouping requirements, the robot updates the position of the center of the group in real time, and grouping according to the splitting merging principle mentioned. The specific algorithm flow is as follows:

  1. (1)

    Set the seven control parameters of grouping, and select k initial centroids according to the principle of maximum distance.

  2. (2)

    The Euclidean distance between each robot and the group center are calculated, and assign them to the group with the closest center according to the nearest distance principle.

  3. (3)

    Splitting: If the samples distribution in the same group is too dense or the number of samples is too small, the group needs to be split. If the sample distance in the same group exceeds a given limit, it will be split, otherwise it will be retained. After the splitting, a new center is obtained, and then repeat from step 2.

  4. (4)

    Merging: If the two groups are too close to each other, or the number of samples in a group is too small, the groups are merged according to the merge rule. And then repeat from step 2.

  5. (5)

    Repeated grouping, judgment, splitting or merging until the expected grouping effect is reached, or the number of operations has reached the upper limit.

After the grouping operation is completed, the aggregation operation is started. According to the requirements of center algorithm, the center position of each group should be real-time updated and notified each robot in the group. Each robot adjusts the speed and direction according to its current position and new center position, then moves to the center. The specific algorithm flow is as follows:

  1. (1)

    Each robot initializes its position, and reads and saves the current position.

  2. (2)

    The robots in the group communicate with each other to inform the position information. The center coordinates are calculated according to the position coordinates of all robots. Then each robot calculates its own speed and direction of motion based on its own coordinate and center coordinate. Finally, the robots move to the center of the group.

  3. (3)

    Repeat from step 1 until all robots in each group enter a small range.


According to the grouping aggregation control algorithm, the research group carried out simulation analysis on the MATLAB. In order to facilitate the observation of the simulation results and analysis, the simulation environment which is a 2-D with a length of 100 and a width of 100 was first configured. About 60 robots were randomly set up in the grid. The initial parameters of the group are configured. The specific parameters are as shown in Table 1. The specific 2-D grid and the initial position of the robot are shown in Figure 2.

The expected number of clusters: K 4
The number of initial cluster centers: k 4
The minimum number of samples in each group: θn 3
The maximum standard deviation among each sample characteristics: θs 1
The minimum distance between each group: θc 10
The number of groups that can be merged in one merge process: L 1
The maximum number of iterations: I 200
Table 1

The robot group initial parameters

Figure 2

The specific two-dimensional grid and the initial position of the robot.

After the simulation starts, the multi-robot system automatically groups according to the grouping algorithm we designed before. The grouping process is shown in Figures 3a and 3b. Figure 3a shows the results of the first grouping, in which the stars show the first four initial centers selected according to the principle of maximum distance, and the diamonds show the new centers after the first grouping is completed. Figure 3b shows the result after the grouping is completed. The stars show the centers of each group. In each grouping process, splitting, merging, or iteration is judged according to the given parameter, and the centers are updated in real time during the grouping process.

Figure 3

The simulation of grouping process: (a) The results of the first grouping. The initial centers are shown as stars and the new centers after the first grouping is completed are shown as diamonds. (b) The result after the grouping is completed.

The aggregation movement begins after the grouping is completed. In the process of aggregation control, the robots of each group moved from the initial position to the center of each group. During the aggregation motion, the centers were updated in each sampling period (the sampling period T was set 1 s). Figures 4a–4e correspond to a sampling period in the aggregation process, respectively. Figure 4d shows that the robots have gathered within a small range. Figure 4e shows that the motion state of the robots was slightly adjusted relative to Figure 4d, but it was still within a small range, so that the aggregation task was completed.

Figure 4

The simulation of aggregation process: (a) The initial position of four groups of robots. (b) and (c) Two processes of robot aggregation. (d) The robots have aggregated within a small range. (e) The result of aggregation.


This topic takes multi-robot system as the research object, and takes grouping aggregation as the main task, and realizes the grouping and aggregation control of multi-robot in simple environment. Based on the K-means algorithm, the research group designed a grouping algorithm that can automatically complete the grouping, and designed the centroid aggregation control algorithm. The MATLAB simulation analysis shows the detailed process of grouping operation and aggregation operation, which verifies the feasibility of the grouping aggregation algorithm. The algorithm embodies the swarm intelligence in a certain degree.


There is no conflicts of interest.

Authors Introduction

Dr. Huailin Zhao

He received his PhD from Oita University, Japan in 2008. He is a professor in the School of Electrical and Electronic Engineering, Shanghai Institute of Technology, China. His main research interests are robotics, multi-agent system and artificial intelligence. He is the member of both IEEE and Sigma Xi.

Mr. Zhen Nie

He received the B.S. degree from Shanghai Institute of technology, Shanghai, China, in 2017. He is a master course student at Shanghai Institute of Technology, and his major is bionic equipment and control engineering. His main research interests are robotics and multi-agent system.

Mr. Xiaoxing Wang

He graduated from Shanghai Insitute of Technology in 2017. He is now a graduate student of University of Massachusetts Amherst for the master of science electrical and computer engineering degree. His main research interests include embedded system, internet of things and multi-agent system.


[2]W Tingting, Research on the surround control problem of multi-agent system, University of Electronic Science and Technology of China, 2014. dissertation
[3]S Xiaoxing, Research on formation and coordination of group robots, Lanzhou University of Technology, 2011. dissertation
[5]H Zhao and W Ren, Consensus problem of distributed multi-agent systems, in The 2015 International Conference on Artificial Life and Robotics (ICAROB) (A Life Robotics Corperation Ltd, Japan, 2015), pp. 201-206.
[7]Z Guoqing, Study on Control on strategy for self-organized formation of swarm robotics systems, Shandong University, 2017. dissertation
[8]Q Wang, C Wang, ZY Feng, and YE Jin-Feng, Review of K-means clustering algorithm, Electron. Des. Eng, Vol. 7, 2012, pp. 21-24.
[9]P Yang, C Guo, and C Li, Swarm robots aggregation formation control based on K-means clustering algorithm, Mod. Mach. Tool Autom. Manuf. Technol., Vol. 8, 2012, pp. 89-92.
[10]Z Wang, G Li, Z Han, and X Zheng, Research and implementation based on K-medoids clustering algorithm, Silicon Valley, Vol. 1, 2011, pp. 80-81.
[11]NX Xia, YD Su, and X Qin, Efficient K-medoids clustering algorithm, Appl. Res. Comput., Vol. 27, 2010, pp. 4517-4519.
[12]WM Wang and S Zhou, Research on multi-robot cooperative control and formation method, Netinfo Security, Vol. 6, 2014, pp. 59-66.
[13]L Jing, L Chenglin, and L Fei, Pilot-following formation and obstacle avoidance control of multi-mobile robots, CAAI Trans. Intell. Syst., Vol. 12, 2017, pp. 202-212.
Journal of Robotics, Networking and Artificial Life
6 - 1
60 - 65
Publication Date
ISSN (Online)
ISSN (Print)
10.2991/jrnal.k.190602.002How to use a DOI?
© 2019 The Authors. Published by Atlantis Press SARL.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (

Cite this article

AU  - Huailin Zhao
AU  - Zhen Nie
AU  - Xiaoxing Wang
PY  - 2019
DA  - 2019/06/25
TI  - Design and Analysis of Multi-robot Grouping Aggregation Algorithm
JO  - Journal of Robotics, Networking and Artificial Life
SP  - 60
EP  - 65
VL  - 6
IS  - 1
SN  - 2352-6386
UR  -
DO  - 10.2991/jrnal.k.190602.002
ID  - Zhao2019
ER  -