Internationalof Computational
Intelligence
Systems
Journal ofJournal
Robotics,
Networking andArtificial Life
Vol.
XX(Z);Month(Year),xx–yyVol.
6(1); June(2019),
pp.pp.
60–65
DOI: 10.1080/XXXXXXXXXXXXXX; ISSN
online
DOI: https://doi.org/10.2991/jrnal.k.190602.002;
ISSNXXXX–XXXX
2405-9021; eISSN
2352-6386
https://www.atlantis-press.com/journals/ijndc
https://www.atlantis-press.com/journals/jrnal

Research Article

Design and Analysis of Multi-robot Grouping
Aggregation Algorithm
Huailin Zhao1,*, Zhen Nie1, Xiaoxing Wang2
School of Electrical and Electronic Engineering, Shanghai Institute of Technology, No. 100, Haiquan Road, Fengxian District, Shanghai 201418, China
College of Engineering, University of Massachusetts Amherst, Amherst, MA 01003, USA

1
2

ARTICLE INFOABSTRACT

Article History

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 thatcan determine the number of groups and complete the grouping task autonomously was designed. Aiming at the problemof aggregation, three kinds of aggregation algorithms are proposed. Taking the center aggregation control as an example, thecooperation and control of each group of robots are studied. Finally, the simulation results of MATLAB show that the multirobot grouping and aggregation algorithm is effective.

Received 30 September 2018
Accepted 15 November 2018
Keywords
Multi-robot
clusteringgrouping aggregation
swarm intelligence© 2019 The Authors. Published by Atlantis Press SARL.
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION
The multi-robot collaboration system is a frontier topic in the field ofartificial intelligence [1]. From the control point of view, the multi-robot collaboration system is a typical distributed control system [2–4],
and its goal is to build large complex systems which included softwareand 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 ofrobots 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 inspace, which are divided into many groups according to a specificgrouping rule, and then each group of robots adjust the motion
states through communication and cooperation between eachother, finally they gather together, or in the desired area to complete
the aggregation. In the end, all the robots formed a multi-groupgathering 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 ofCorresponding author. Email: zhao_huailin@yahoo.com*

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.

2. ANALYSIS AND DESIGN OF GROUPINGALGORITHM
Grouping aggregation is divided into two steps, grouping task andaggregation 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 eachcluster were randomly selected.
In the Euclid space, a set of n-dimensional samples X = {x1, x2, x3… xi … xn} (representing n robots) is given, where xi ∈ Rn. 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.
		    d(xi , x j ) = xi − x j (1)where xi, xj represents two points in the Euclid space, which are twon-dimensional data.

H. Zhao et al. / Journal of Robotics, Networking and Artificial Life 6(1) 60–65

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).
2

k

		 
ci = arg min ∑ ∑ x j − mi (2)i =1 x ∈XCjwhere mi is the center of ith cluster.
			 mi =1∑ x (3)N i x ∈ci

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, theK-means algorithm ends. The equation of square fitting error sum
is given bykn		    J = ∑ ∑ dij x j − mii =1 j =1

2

(4)

61

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 usedas the initial cluster center.
After the initial clustering center is selected, clustering is carriedout according to formula (2). If the number of samples in any groupis less than qn, 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 andthe total average distance D of all samples were calculated.
		 Di =

1∑ x − mi , i = 1, 2,, k (5)N i x ∈ci

		 D =1 n∑ N D , i = 1, 2, , k (6)n i =1 i i

ì1, x Î cwhere dij = í j i .
î0, x j Ï ci

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

3. IMPROVED GROUPING ALGORITHM

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 isaccording to the following conditions.

There are two limitations [10,11] of K-means algorithm. Firstly, thevalue 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-meansis 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 numberof groups based on the K-means algorithm. For the problem thatthe k-value is difficult to estimate, we have added two processesof “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 thegroup 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, qN, qc, qs, L, I). Where K is the expected
number of groups. k is the initial number of groups. qn is theminimum number of samples in each group. If the samples areless than this number, the group will be removed. qs is the maximum standard deviation of the sample features in a group. If it isgreater than this value, the group may be split. qc 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.

1(1) If the number of iterations is odd or k ≤ K , that is, the2number of cluster centers is less than half of the expected
number of groups, splitting the existing clusters;(2) If the number of iterations is even or k ≥ 2K, that is, thenumber 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 isdefined as formula (7):		 s in =1
2∑ ( x − min ) (7)N i xi ∈ci lnwhere Ni is the number of samples in ith group, xln is the nth component of the lth in the group ci, mln is the nth component of the centerof the group ci.
Find the largest standard deviation of component in each group:
dimax, i = 1, 2, 3, …, k, if dimax > qs, and the group satisfy one of thefollowing two conditions, split the group into two groups.
(1)

D j > D and Ni > 2qn+1(2) k <K2

H. Zhao et al. / Journal of Robotics, Networking and Artificial Life 6(1) 60–65

62

The center after splitting is recorded as mi+ and mi−, mi+ and mi−
are given byin the complicated reality environment. The aggregation task
failed.

mi+ = mi + hd i
(8)mi+ = mi − hd i(2) Selecting the neighboring robot as the reference point, asshown 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 isthat a large amount of communications is required, and eachrobot needs to spend more time for communication, and theresult of the formation control is not satisfactory.

			
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.
			 Dij = mi − m j (9)where mi is the center of the ith group and mj is the center of thejth group.
Comparing Dij with qc, and arranging all Dij that smaller than qc
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:	   ml =1(N i mi + N j m j ), l = 1, 2, ¼ L (10)Ni + N j

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

(3) Selecting the center of group as the reference point, as shownin 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 geometriccenter is calculated. Each robot uses takes the center as a reference point to adjust the direction and speed, and move to thereference point. During the aggregation movement, the systemconstantly 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.
Comparing the three aggregation algorithms, this study intends touse the center algorithm for aggregation control. The center calculation equations are expressed as follows:nxiy, yc = ∑ i (11)ni =1i =1 nn

4. ANALYSIS AND DESIGN OF
AGGREGATION ALGORITHM
As mentioned earlier, the aggregation problem is that multi-robots
randomly distributed in the space adjust the motion states throughcommunication and cooperation between each other, finally theygather together, or in the desired area to complete the aggregation.
Aiming at the aggregation task requirements of this topic, threeaggregation control algorithms were designed and analyzed in thispaper:(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, andthe 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 theadvantages 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, thefollower or leader robot may be lost in the process of motion
(a)

(b)

(c)

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

xc = ∑
		 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 thecenter 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:
		 Xi (k + 1) = Xi (k) + vi (k + 1) ⋅ T (12)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 andcollision 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:Tcos(± (q m + a )) − sin(± (q m + a ))  xd 
vavoid =    (13)sin(± (q m + a ))cos (± (q m + a ))   yd 
where qm is the angle between the motion direction of the robot andthe 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x of obstacle area.  d  is the direction of obstacle motion predicted
 yd 
by the robot, and a is a given constant.

H. Zhao et al. / Journal of Robotics, Networking and Artificial Life 6(1) 60–65

5. CALCULATION PROCESS OF GROUPINGAGGREGATION ALGORITHM
As mentioned earlier, to complete the grouping aggregation task,
the first thing should be done is grouping operation, and the next isthe 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 groupingaccording to the splitting merging principle mentioned. The specific algorithm flow is as follows:(1) Set the seven control parameters of grouping, and select k initial centroids according to the principle of maximum distance.
(2) The Euclidean distance between each robot and the group
center are calculated, and assign them to the group with theclosest center according to the nearest distance principle.
(3) Splitting: If the samples distribution in the same group is
too dense or the number of samples is too small, the groupneeds to be split. If the sample distance in the same groupexceeds a given limit, it will be split, otherwise it will be
retained. After the splitting, a new center is obtained, andthen repeat from step 2.
(4) Merging: If the two groups are too close to each other, or thenumber of samples in a group is too small, the groups are
merged according to the merge rule. And then repeat fromstep 2.
(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 andnew center position, then moves to the center. The specific algorithm flow is as follows:63

of 100 and a width of 100 was first configured. About 60 robots
were randomly set up in the grid. The initial parameters of thegroup 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.
After the simulation starts, the multi-robot system automaticallygroups according to the grouping algorithm we designed before.
The grouping process is shown in Figures 3a and 3b. Figure 3ashows the results of the first grouping, in which the stars show
the first four initial centers selected according to the principle ofmaximum distance, and the diamonds show the new centers after
the first grouping is completed. Figure 3b shows the result after thegrouping 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 inreal time during the grouping process.
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 toa sampling period in the aggregation process, respectively. Figure 4dshows that the robots have gathered within a small range. Figure 4eshows that the motion state of the robots was slightly adjusted relative to Figure 4d, but it was still within a small range, so that theaggregation task was completed.
Table 1 | The robot group initial parameters
The expected number of clusters: K
The number of initial cluster centers: k
The minimum number of samples in each group: qn
The maximum standard deviation among each sample
characteristics: qs
The minimum distance between each group: qc
The number of groups that can be merged in one merge process: L
The maximum number of iterations: I

4
4
3
1
10
1
200

(1) Each robot initializes its position, and reads and saves the current position.
(2) The robots in the group communicate with each other toinform the position information. The center coordinates arecalculated 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) Repeat from step 1 until all robots in each group enter a small
range.

6. SIMULATION ANALYSIS
According to the grouping aggregation control algorithm, theresearch group carried out simulation analysis on the MATLAB.
In order to facilitate the observation of the simulation results andanalysis, the simulation environment which is a 2-D with a length

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

H. Zhao et al. / Journal of Robotics, Networking and Artificial Life 6(1) 60–65

64

(a)

(b)

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 firstgrouping is completed are shown as diamonds. (b) The result after the grouping is completed.
(a)

(c)

(b)

(d)

(e)

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.

7. CONCLUSIONREFERENCES

This topic takes multi-robot system as the research object, andtakes grouping aggregation as the main task, and realizes thegrouping 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.

[1] H. Zhao, Y. Guo, M. Sugisaka, Design of the multi-car collaboration system, The 2017 International Conference on Artificial
Life and Robotics (ICAROB), A Life Robotics Corporation Ltd,
Seagaia Convention Center, Miyazaki, Japan, 2017, pp. 186–190.
[2] W. Tingting, Research on the surround control problem of multiagent system, University of Electronic Science and Technology ofChina, dissertation, 2014.
[3] S. Xiaoxing, Research on formation and coordination of grouprobots, Lanzhou University of Technology, dissertation, 2011.
[4] D.V. Dimarogonas, K.J. Kyriakopoulos, Connectedness preserving distributed swarm aggregation for multiple kinematic robots,
IEEE Trans. Robot. 24 (2008), 1213–1223.
[5] H. Zhao, W. Ren, Consensus problem of distributed multi-agent
systems, The 2015 International Conference on Artificial Lifeand Robotics (ICAROB), A Life Robotics Corperation Ltd, Japan,
2015, pp. 201–206.

CONFLICTS OF INTEREST
There is no conflicts of interest.

H. Zhao et al. / Journal of Robotics, Networking and Artificial Life 6(1) 60–65[6] H. Zhao, Z. Wu, X. Wang. A multi-robot rescuing system, The 2018
International Conference on Artificial Life and Robotics (ICAROB),
A Life Robotics Corperation Ltd, Japan, 2018, pp. 582–586.
[7] Z. Guoqing, Study on Control on strategy for self-organized formation of swarm robotics systems, Shandong University, dissertation, 2017.
[8] Q. Wang, C. Wang, Z.Y. Feng, Y.E. Jin-Feng, Review of K-meansclustering algorithm, Electron. Des. Eng. 7 (2012), 21–24.
[9] P. Yang, C. Guo, C. Li, Swarm robots aggregation formation control based on K-means clustering algorithm, Mod. Mach. Tool
Autom. Manuf. Technol. 8 (2012), 89–92.

65[10] Z. Wang, G. Li, Z. Han, X. Zheng, Research and implementation based on K-medoids clustering algorithm, Silicon Valley 1(2011), 80–81.
[11] N.X. Xia, Y.D. Su, X. Qin, Efficient K-medoids clustering algorithm, Appl. Res. Comput. 27 (2010), 4517–4519.
[12] W.M. Wang, S. Zhou, Research on multi-robot cooperative
control and formation method, Netinfo Security 6 (2014),
59–66.
[13] L. Jing, L. Chenglin, L. Fei, Pilot-following formation and obstacle avoidance control of multi-mobile robots, CAAI Trans. Intell.
Syst. 12 (2017), 202–212.

Authors Introduction
Mr. Xiaoxing Wang

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

Mr. Zhen Nie
He received the B.S. degree from
Shanghai Institute of technology,
Shanghai, China, in 2017. He is amaster course student at Shanghai
Institute of Technology, and his
major is bionic equipment and control engineering. His main researchinterests are robotics and multiagent system.

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