Sage Journals: Discover world-class research

Abstract

Spatial formations of swarm robots are increasingly applied in many domains in which the environments are dynamic and unpredictable. The autonomy of the individual robots and decentralization of the entire system increase the complexity of the response to environmental changes, which could prolong the formation convergence and significantly increase the communication cost. To address these issues, we propose an adaptive mechanism with three basic behaviours for each individual robot and design a grouping-based spatial formation algorithm for swarm robots to respond to changes and accomplish shape formation. Specifically, the robots are automatically partitioned into several groups based on their spatial neighbours. In this manner, the interactions and self-organization of robots are primarily performed at the intra-group rather than inter-group level, leading to decreased communication costs. Furthermore, this grouping mechanism naturally supports parallel formation and therefore improves the convergence speed. Our simulation and experimental results demonstrate that the proposed method significantly improves the convergence speed and decreases the communication cost, thus validating the effectiveness of the proposed adaptive mechanism.

Keywords

Swarm robots spatial formation grouping self-organization dynamic environment

Introduction

The swarm robotic system is essentially a self-organizing multi-agent system in which the individual is autonomous in behaviour and the entire system is decentralized in control. The local interactions of robots and their behaviours are expected to self-organize the system for orderly behaviour in space. Swarm robots are used to study how systems composed of multiple autonomous robots (agents) can be applied to accomplish collective tasks where the tasks either cannot be achieved by each robot alone or are performed more efficiently by robots as a group.¹ Swarm robotic systems offer certain distinct advantages over traditional single robot systems such as robustness, flexibility and adaptability to spatial and temporal distribution tasks.² Examples of practical applications for swarm robotic systems include formation^3,4; collaborative search and rescue^5,6; nuclear, chemical and biological attack detection⁷; battlefield surveillance⁸; space exploration⁹; and target tracking and observation,¹⁰ among others.

One common task of the swarm robotic system is to form complex shapes in space to accomplish the given task. Evidence has shown that the success of swarm robots in performing a task depends on the ability to generate and maintain the appropriate formation. For example, air combat with the correct formation can confer an advantage, and proper formation of multirole swarm robots can complete the task more efficiently.¹¹ Spatial structure formation for swarm robots aims to deploy robots in a regular and repetitive manner. The robots commonly must maintain specific distances between each other to create a desired pattern. At a global level, the swarm can converge to the state in which it is deployed optimally in the environment.

Whether an individual robot can respond and adapt to changes in the environment with time is an essential factor for more efficient achievement of the task. However, the ability of an individual robot in the swarm is limited, and the spatial structure is formed using only local perception and local communication. Additionally, it is challenging to obtain the global position of each individual robot, and communication costs increase dramatically with increasing robot size for large-scale swarm robotic systems. Currently, most studies address spatial formation under dynamic obstacles,^12,13 but few research efforts focus on spatial formation in the dynamic environment. In the example of a firefighting task,^14
–16 the swarm robots should be deployed immediately on the boundaries of the dynamic target area. Selected challenges for swarm robots in performing such a task include the following:

– Without global positioning, it is quite difficult for a swarm robotic system in an unknown target environment to perform spatial structure formation and adaptive adjustment using only local perception.

– If the environment is changing dynamically, then the swarm robotic system should adjust the spatial structure with time to become more robust.

– When the size of the swarm increases through local interaction, the convergence time of the spatial formation and the total communication cost increase drastically.

Given the above challenges, this article presents a method for adaptive spatial formation of swarm robots in a dynamic environment, and the grouping method is used to improve the convergence speed and reduce communication costs. Two contributions of the article are described as follows:

Grouping method: Our method dynamically separates a swarm of robots into multiple groups, with communication among robots mainly confined to the same group, while different groups can converge independently towards the target shape, thereby reducing the convergence time and ensuring timely reaction to environmental changes.

Adaptation mechanism: We present an adaptive formation method for the swarm robotic system in a dynamic environment based on self-organization, which does not require knowledge of the predefined pattern position. The swarm robotic system can adaptively create a suitable spatial structure for a target environment that is changing dynamically.

The article is organized as follows. ‘Related work’ section discusses related work, and ‘Problem statement of spatial formation of swarm robots’ section defines the problem of spatial formation of swarm robots. ‘Grouping-based adaptive spatial formation method’ section describes the grouping base of swarm robots and the adaptive mechanism in the dynamic environment. ‘Simulation and experimental results’ section presents the simulation and experimental results, and ‘Conclusions and future work’ section outlines the research conclusions and future work.

Related work

Spatial formation by the swarm robotic system has been studied extensively in recent years.^17
–19 The purpose of such research aims to support a group of robots in coordinating with each other to produce and maintain a specific shape in three-dimensional space. The shape can be either predefined by the system designer or adaptively formed by the robots in terms of self-organization. However, because the robots in such a system have limited communication and computation abilities, global information is often not available to each robot, and thus accomplishing this task poses a great challenge.

Several classic methods of spatial formation are available: (1) leader–follower algorithms^20
–22 require individual robots to follow a leader that knows the target shape position or to follow a neighbour that is following a leader. At the same time, the robots should maintain a specific geometric relationship with the robots that they are following. However, this method displays inadequate robustness and strong dependence on the leader. (2) The potential field theory^23

–26 requires the target shape to emit attractive forces and the obstacles to emit repulsive forces, and thus each robot moves along the gradient of the potential field that is the sum of these virtual attractive and repulsive forces. However, this method easily falls into local minima. (3) Biologically inspired methods^27,28 can generate robust and complex emerging behaviours through relatively simple local interactions in the presence of a variety of uncertainties and use either hormone-based models or cellular mechanisms. However, most bio-inspired approaches only give local heuristic rules and cannot supply theoretical proof of system convergence.

In the existing methods of self-organizing spatial formation for a swarm robotic system, the coordinate system is global, the environment is static, or the scale is not sufficiently large. Gilpin et al.²⁹ described the design, fabrication and experimental results for a programmable matter system capable of two-dimensional (2D) shape formation through subtraction. However, the number of robots is limited to a few tens. Rubenstein and Shen³⁰ proposed a scalable self-assembly and self-healing swarm robotic system that allows a swarm of robots to form a shape without knowing the count of robots in advance. However, the swarm has a shared coordinate system that is known by all robots. Cheah et al.³¹ introduced formation with local interactions for avoiding collisions or maintaining specified relative distance constraints. However, the target shape consists of simple closed curves, which might be inadequate in handling unknown environmental changes. Marco et al.³² achieved pattern formation by morphogen gradient diffusion, but the patterns are limited to polygonal shapes, and robots cannot avoid collision. Hahmin and Dong³³ proposed a system that is scalable for the size of the swarm and showed the effectiveness of this scheme for the formation of shapes using agents in a swarm. The Hahmin group analysed stability using the Lyapunov approach. However, the system lacked the dynamic behaviour of the stochastic or obstacle-based environment. Farshad et al.³⁴ implemented the aggregation of honeybees based on various parameter values and proposed two variations of honeybee aggregation. The results demonstrated the efficiency of the proposed variation of honeybee aggregation in terms of aggregation time and ignored local communication among homogeneous robots. Meng et al.³⁵ introduced a morphogenetic approach using a gene regulatory network^36,37 for a swarm robotic system that forms complex shapes in a distributed manner. A theoretical proof of system convergence was presented. The simulation studies demonstrated that the proposed algorithm offers an efficient and robust distributed control mechanism for a swarm robotic system in construction of complex shapes. However, this method operates under a global coordinate system. Rubenstein et al.³⁸ presented a self-assembly based shape formation for a swarm robotic system. Three basic behaviours were applied to form a complex shape via self-organization for kilorobots. However, at the start of the self-assembly process, the robots are placed in an aggregated form with fixed locations and no random localization. Movement of the robots occurs in a sequential edge-following manner, and the convergence time is notably large.

Although most spatial formation methods can form complex shapes via local communication in a distributed manner, these methods focus on the static environment and ignore the convergence speed and communication cost, which are significant to certain tasks.

Problem statement of spatial formation of swarm robots

Example of a swarm robotic system for firefighting

This section introduces an example of multiple-robot firefighting to illustrate the spatial formation problem of swarm robots. In this case, an area contains a fire, and swarm robots are assigned to move into the area to fight the fire as quickly as possible. The swarm robots must locate the situated position based on self-organization using local interaction. Figure 1 shows the sample of the swarm robotic system for firefighting.

Figure 1.

Sample of a swarm robotic system for a firefighting task.

Swarm robots should form suitable spatial shapes that satisfy the unknown environmental requirements. However, the fire area is dynamic and changes over time. Because the fire area might expand or decrease dynamically, the swarm robots must adjust adaptively to surround the fire area. The problem to be solved in the example is that the swarm robots should be adaptively and quickly deployed on the border of the fire area so that they can fight the fire effectively and safely. Additional robots can join dynamically when the number of robots is too small to be able to enclose the area of the fire.

Swarm robots should form the required shape as quickly as possible because the firefighting need is urgent and must occur within a minimum time. Due to the limited coverage of individuals, sufficient firefighting robots are needed to accomplish this task. Swarm robots should attempt to enclose the fire area to extinguish the fire as soon as possible. Therefore, the convergence rate (response to time) by the swarm robots is an important measure for evaluating the effectiveness of the solution. In addition, the spatial formation should have a lower communication costs because many communications might influence the efficiency and performance.

Problem statement

Because the environment is changing over time, the swarm robots should form a suitable spatial structure using only local perception and local communication. The swarm robotic system also adjusts the spatial structure adaptively with changes in the environment over time.

Definition 1 (swarm robotic system)

There are n homogeneous robots in a 2D Euclidean space defined as $A = {α_{1}, α_{2}, \dots, α_{n}}$ .

Definition 2 (environment)

The environment is defined as a set of points E(t), where $E (t) \subseteq ℝ^{2}$ is changing with time t, and ℝ² is 2D continuous space.

Definition 3 (boundary)

The boundary of the environment is defined as the target shape, which is a set of points $P_{b} (t) \subset E (t)$ , where P_b(t) is changing with time t.

Given a boundary of dynamic target shape P_b(t) and a set of robots A, a method should be supplied to enable the robots to converge to P_b(t). To illustrate such problem, selected indices are defined as follows.

Definition 4 (coverage error)

The coverage error for the target shape is defined as the ratio of the area currently uncovered by to the target shape, that is

e (A, P_{b} (t)) = | P_{b} (t) \ \underset{a \in A}{\cup} P_{α} | / | P_{b} (t) |

If all individual robots are homogeneous, then P_α is the range of individual covering the border of the target shape

P_{α} = {x \in ℝ^{2} : ∥ x - x (α) ∥ < δ_{eff}}

where x is a point in 2D space ℝ², x(α) is the current position of robot α in ℝ² and δ_eff is a threshold.

Definition 5 (convergence time)

When the coverage error $e (A, P_{b} (t))$ is less than the threshold ε₀, the total time for the robots to cover the target shape P_b(t) is the convergence time $t_{cvg} (A, P_{b} (t))$ , that is

lim_{t \to t_{cvg} (A, P_{b} (t))} e (A, P_{b} (t)) < ε_{0}

Definition 6 (communication cost)

The total number of messages in the swarm robotic system is defined as the communication cost.

Definition 7 (convergence rate)

The robots A that cover the target area at a certain time are defined as the change rate of the coverage error $e (A, P_{b} (t))$

r_{cvg} (A, P_{b} (t)) = \frac{\partial e (A, P_{b} (t)) (t)}{\partial t}

When the coverage error decreases, the convergence rate $r_{cvg} (A, P_{b} (t)) < 0$ . Figure 2 shows the convergence rate with time. From the above diagram, we can conclude that in a dynamic environment, for a given initial threshold ε₀ of the coverage error, the average convergence rate $\int_{0}^{t_{cvg}} r_{cvg} (A, P_{b} (t)) d t / t_{cvg} = ε_{0} / t_{cvg}$ increases, and the convergence time t_cvg decreases

\begin{array}{l} r_{cvg} (A, P_{b} (t)) = \frac{\begin{array}{l} \partial (e (A, P_{b} (t))) (t) \end{array}}{\begin{array}{l} \partial t \end{array}} \\ \begin{array}{l} = & \frac{\begin{array}{l} \partial (| P_{_{b}} (t) \ \cup_{α \in A} P_{α} | / P_{b} (t) |) \end{array}}{\begin{array}{l} \partial t \end{array}} \\ = & \frac{\begin{array}{l} 1 \end{array}}{\begin{array}{l} | P_{b} (t) | \end{array}} \frac{\begin{array}{l} \partial | P_{b} (t) \ \cup_{α \in A} P_{α} | \end{array}}{\begin{array}{l} \partial t \end{array}} \\ - \frac{\begin{array}{l} | P_{b} (t) \ \cup_{α \in A} P_{α} | \end{array}}{\begin{array}{l} | P_{b} (t {) |}^{2} \end{array}} \frac{\begin{array}{l} \partial | P_{b} (t) | \end{array}}{\begin{array}{l} \partial t \end{array}} \\ = & \frac{\begin{array}{l} 1 \end{array}}{\begin{array}{l} | P_{b} (t) | \end{array}} (\frac{\begin{array}{l} \partial | P_{b} (t) | \end{array}}{\begin{array}{l} \partial t \end{array}} - \frac{\begin{array}{l} \partial | P_{b} (t) \cap \cup_{α \in A} P_{α} | \end{array}}{\begin{array}{l} \partial t \end{array}}) \\ - \frac{\begin{array}{l} | P_{b} (t) \ \cup_{α \in A} P_{α} | \end{array}}{\begin{array}{l} | P_{b} (t {) |}^{2} \end{array}} \frac{\begin{array}{l} \partial | P_{b} (t) | \end{array}}{\begin{array}{l} \partial t \end{array}} \\ = & - \frac{\begin{array}{l} 1 \end{array}}{\begin{array}{l} | P_{b} (t) | \end{array}} \frac{\begin{array}{l} \partial | P_{b} (t) \cap \cup_{α \in A} P_{α} | \end{array}}{\begin{array}{l} \partial t \end{array}} \\ + \frac{\begin{array}{l} | P_{b} (t) \cap \cup_{α \in A} P_{α} | \end{array}}{\begin{array}{l} | P_{b} (t {) |}^{2} \end{array}} \frac{\begin{array}{l} \partial | P_{b} (t) | \end{array}}{\begin{array}{l} \partial t \end{array}} \end{array} \end{array}

Figure 2.

Convergence rate with time.

In equation (5), $\partial | P_{b} (t) \cap \cup_{α \in A} P_{α} | / \partial t$ reflects the ability of swarm robots A to cover the dynamic target shape P_b(t) over time, and $\partial | P_{b} (t) | / \partial t$ reflects the degree of change of the dynamic target shape P_b(t). If the environment is static, $\partial | P_{b} (t) | / \partial t = 0$ . If $\partial | P_{b} (t) | / \partial t > 0$ , the area expands. If $\partial | P_{b} (t) | / \partial t <$ 0, the area shrinks.

We obtain the following observations from the above formula with respect to the change rate of the coverage error in a dynamic environment (with continuously changing target shape P_b(t)):

$| r_{cvg} (A, P_{b} (t)) |$ increases with the decrease in the change rate of the size of the target shape P_b(t), as indicated by the appearance of $\partial | P_{b} (t) | / \partial t$ .

$| r_{cvg} (A, P_{b} (t)) |$ increases with the increase in the ability of the swarm robots to converge to the target shape P_b(t), as indicated by the appearance of $\partial | P_{b} (t) \cap \cup_{α \in A} P_{α} | / \partial t$ .

To enhance the ability of the swarm robot system to respond adaptively to the dynamic environment, the robots must reach the target area as quickly as possible. Under the assumption that all robots move at the same speed, the greater the number of robots that reach the area, the higher the coverage that can be achieved. In a dynamic environment, it is not reasonable to expect the coverage error to reach 0. However, we can accelerate the convergence process, thereby reducing the average error over time by increasing the covering capability $\partial | P_{b} (t) \cap \cup_{α \in A} P_{α} | / \partial t$ .

Problem 1

Given a boundary of dynamic target shape P_b(t) and a set of robots A, identify a method that enables the robots to converge to P_b(t) in as short a time as possible.

Under the condition of the dynamic environment, the error to the target shape is expected to be maintained within a certain threshold, and in order to guarantee the timely response to the environmental changes.

Grouping-based adaptive spatial formation method

Model of individual robot

To investigate the spatial formation problems of swarm robots, we first establish the abstract model of swarm robots and their situated environment. Each robot α is a tuple ${s, x, v, g, C, b}$ , where (1) s represents the current state of robot a, (2) x is the location of robot α, (3) v is the velocity vector of robot α, (4) g is the group of robot α, (5) C is the actions that robot can take and (6) b is the current behaviour of the robot which directs how the robot acts in the environment.

Definition 8 (state)

The robot states are ‘normal’, ‘reference’ and ‘halted’, which are denoted as S = { $s_{nrm}, s_{ref}, s_{hlt}$ }.

Initially, all robots are in the ‘normal’ state, and several ‘reference’ robots might be selected. The robot is ‘halted’ if it has found a suitable position in the environment. The ‘halted’ robot transitions to ‘normal’ when the dynamic environment destroys the stable space structure.

Definition 9 (action)

The robot actions are ‘join’ and ‘quit’, which are denoted as C = {join, quit}.

Definition 10 (behaviour)

The robot behaviours are ‘approach’, ‘revolve’ and ‘locate’, which are denoted as $B = {b_{aph}, b_{rvlv}, b_{loc}}$ .

The individual robot displays three basic types of behaviours. The normal robot will ‘approach’ the reference robot first and subsequently ‘revolve’ the reference robot if the distance between them is less than the safe distance d_safe. The robot will halt at a suitable position in the environment via the ‘locate’ behaviour.

Grouping-based decomposition and organization of swarm robots

Overview of the grouping-based swarm formation in a dynamic environment

A grouping-based mechanism applies this method to reduce the convergence time of the swarm spatial formation. The swarm robotic system is divided into several groups automatically, and all groups can move in parallel. This method can significantly reduce the convergence time, especially for a large-scale swarm. Figure 3 shows the grouping-based swarm formation in the dynamic environment.

Figure 3.

Grouping-based swarm formation in a dynamic environment. (a) The swarm robotic system is divided into several groups. (b) Swarm robots are deployed on the boundary of the dynamic environment.

If we increase the convergence rate $r_{cvg} (A, P_{b} (t))$ , then the swarm robotic system can adjust the spatial structure with time in the environment, which changes dynamically. Because the environment is dynamically changing over time, the swarm robotic system cannot converge forever.

Using the grouping-based method, multiple groups can surround the target area at the same time, which significantly improves the coverage speed.

Group division mechanism

Definition 11 (group)

The swarm robots are divide into several groups, each group has a ‘reference’ robot and others robots are ‘normal’, which are denoted as G = ${α_{ref}, A^{'} : α_{ref} \in A, A^{'} \subseteq A}$ .

Because the number of robots in a swarm robotic system might be quite large, communication among all robots is not necessary. There are many advantages to dividing the swarm robotic system into several groups. First, group division can reduce the communication cost because most communication occurs within the group, and communication between groups is less frequent. Second, group division is also suitable for performing multiple tasks efficiently.

We propose a group division mechanism for swarm robots through local communication, similar to the K-nearest neighbor algorithm. The idea of the algorithm is to consider the distance between two robots, and the robots that are gathered closely can compose a group to the extent possible. First, several robots are randomly selected from the swarm. Second, the robots add their neighbours to their groups. If a robot has joined a group, it cannot be added to another group. The groups are constructed successfully when no additional robots can be added. If a robot fails to join any group, it can be added to the group in which its nearest neighbour is located. Third, one reference robot in the centre of the group is selected in each group.

The group division mechanism is shown in Figure 4. Initially, the swarm robots are randomly present in the area (as shown in Figure 4(a)). Subsequently, three robots (filled with different patterns) located on the edge of the swarm robotic system are selected by local communication (as shown in Figure 4(b)). Using the grouping mechanism described above, three groups are established (connected with a line). The three reference robots (indicated by red crosses) in the centre of the group are selected (as shown in Figure 4(c)).

Figure 4.

Group division mechanism. (a) Initial status. (b) Three agents selected. (c) Three groups established, with reference agents denoted by red crosses.

Algorithm 1 is represented as grouping algorithm. The states of all robots A are initially as s_nrm (line 2) and not grouped (line 3). While the swarm robots are divided into K groups, then there are K robots selected as reference robots ( $g^{K} · a_{ref}$ ) in each group (lines 5–8). The reference robots search the neighbour robots which distance is shorter than δ and the robots that have joined the group constantly join their neighbours until all the robots enter a group (lines 10–18).

Algorithm 1.

Grouping algorithm.

Adaptive mechanism in the dynamic environment

The main concept of the proposed self-organizing formation method is described as follows. Each robot has three basic behaviours $b_{aph}, b_{rvlv}$ and b_loc that can achieve swarm robot spatial formation based on self-organization. This method can also make formation-adaptive adjustments under an environment that is changing dynamically. The following description details the algorithms used to implement the three basic behaviours. Figure 5 shows the three basic behaviours.

Figure 5.

Three basic behaviours. (a) ‘Approach’ behaviour, (b) ‘revolve’ behaviour, and (c) ‘Locate’ behaviour.

‘Approach’ behaviour b_aph: The behaviour b_aph is executed when a robot α is under normal state, that is, α ·s = s_nrm. Algorithm 2 shows each robot α executing behaviour b_aph. Under b_aph, the robot α first moves (line 3) towards a previously selected reference robot α_ref and then start to revolves (line 5) around α_ref in order to maintain the distance between α and α_ref above a safety threshold d_safe.

Algorithm 2.

Execute behaviour b_aph.

‘Revolve’ behaviour b_rvlv: The robot must maintain a safe distance from another robot. When a robot moves near another robot, it must stay removed from the robot if the range is less than the safe distance.

The behaviour b_rvlv is executed when a robot α is under normal state, that is, $α · s = s_{nrm}$ . Algorithm 3 shows the behaviour b_rvlv algorithm. A safe distance d_safe between two robots is required to avoid a collision caused by the robot that is too close (line 3). The robot will revolve the other neighbour robot (line 5). Although the robot does not execute the behaviour b_aph, it does execute behaviour b_loc (line 7).

Algorithm 3.

Execute behaviour b_rvlv.

‘Locate’ behaviour b_loc: If the distance between the current point and the track is within the specified range and the distance between the current position and the halted point is within the safe range, the robot stops the movement and halts. Otherwise, the robot fails to locate and continues to revolve.

Algorithm 4 shows each robot α executing behaviour b_rvlv. x^⋆ is the located robot to the target shape P_b (line 2). If the neighbour robots A_nb of the robot which has been positioned are empty, the revolving robot will be located (line 7).

Algorithm 4.

Execute behaviour b_loc.

To obtain a relatively stable spatial structure formation for the swarm, the robot should halt at a suitable position in the target environment. While the target environment is changing, the robot can locate adaptively.

Self-organizing formation in a dynamic environment

We use the above three basic behaviours for self-organizing formation. The formation based on self-organization is described as follows. As shown in equation (6), the robot states are ‘normal’, ‘reference’ and ‘halted’. The reference robot is the leader of the group, and the normal robot approaches the reference robot in the same group. When the robot has found the suitable position in the dynamic environment, it shifts to the ‘halted’ state. The ‘halted’ state is a temporarily stable state that is adjusted as the environment changes.

The three basic behaviours and the grouping mechanism are applied in the above algorithm. Algorithm 5 shows formation based on self-organization. The swarm robots are first divided into several groups. The normal robot approaches the reference robot in the same group. To evaluate the distance, the revolve and locate behaviours are executed by the robots. All robots halt when they are located successfully, and they will relocate with changes in the environment.

Algorithm 5.

Formation based on self-organization.

Simulation and experimental results

To evaluate the effectiveness of the proposed method, we conduct several experiments. Our simulation and experimental results demonstrate that the proposed method significantly improves the convergence speed and decreases the communication cost, thus validating the effectiveness of the proposed adaptive mechanism. We use the multi-agent simulation software repast to conduct the experiments. The operating system is Win7, and the hardware resources include 4G memory and i5 CPU.

Before presenting the simulation results, we would like to state some general assumptions in the simulations as follows:

– The robots are homogeneous and have the same velocity.

– Only centre of mass motion is considered for the robots, which means each robot is seen as a moving point.

– The robot uses local coordinate positioning to know the position of neighbouring robots.

– The sensing and communication range of a robot is limited. However, the information can be shared through networked communication.

In addition, the following parameter settings are used in the simulations (as shown in Table 1).

Table 1.

Parameter values.

Parameter	Description	Value
V	The speed of robot movement	10
d _safe	The safe distance between robots	13
δ	Maximum perceived distance for neighbours	50
ε ₀	Minimum threshold for coverage error	0.2
δ _eff	The error for boundary detection range	2

Dynamic environment

In this experiment, a series of randomly generated rectangles of varying lengths are interleaved and combined to form a dynamic target area (as shown in Figure 6). The boundary of the target environment is shown by the thick solid line in black. The length of each rectangle changes dynamically with time. Therefore, the robots need to adjust adaptively according to the dynamic borders.

Figure 6.

Dynamic target environment.

In order to improve the ability of the swarm robot system to respond to the dynamic environment, the robot must reach the target area as soon as possible. Assuming that all robots move at the same speed, it is critical that the robot can adjust the position quickly and adaptively to the dynamic boundary.

Experiment: Grouping-based formation in a dynamic target shape

We show how 200 robots were deployed at the boundary of the dynamic target shape by the self-organization method using an automatic group division mechanism. Initially, 200 robots are randomly distributed in the 2D environment. The group division mechanism divides the swarm into three groups, and one reference robot is selected in each group. Figure 7 shows the procedure for an irregular target shape constructed by 200 self-organized robots.

Figure 7.

Snapshots showing the multi-group covered by the dynamic target shape using 200 robots in parallel. (a) Initialisation: Three groups are divided and denoted in red, blue, and green. (b) Three group formations working in parallel in the dynamic environment. (c) Swarm robot reformation with the changing target environment.

The three reference robots lead their groups to move to three different areas of the target environment. The normal robots approach their reference robot in the same group. Once the robot has found the boundary of the target environment that is not occupied by other robots, the robot halts its position to perform the task. While the environment is changing with time, the swarm robotic system should adjust the position adaptively over time.

We also performed experiments with other methods for comparison with our experiments, and the experimental results are analysed in the next section.

Experimental analysis

In this section, we analyse the experiment results. First, the effects of the robot scale on the convergence time and the communication cost are measured in the experiments. Second, the effects of the number of groups on the performance indicators are analysed. Third, our method is compared with two different methods.

1. Effects of the number of robots on the convergence time and communication cost:

The numbers of swarm robots deployed in a spatial formation in the dynamic target environment are 100, 200, 500 and 1000.

As shown in Figures 8 and 9, it is clear that the convergence time and communication cost increase rapidly as the number of robots increases.

Figure 8.

Relationship between convergence time and number of robots.

Figure 9.

Relationship between communication cost and number of robots.

Therefore, communication costs and convergence time are important factors to be considered for the large-scale swarm robots to carry out the spatial formation in a dynamic environment.

2. Effects of the number of groups on the performance indicators:

Figures 10 to 12 evaluate the communication cost, total travel distance and coverage error, respectively, with different sizes of groups.

Figure 10.

Comparison of the communication cost with different numbers of groups.

Figure 11.

Comparison of the total travel distance with different numbers of groups.

Figure 12.

Comparison of the coverage error with different numbers of groups.

It can be observed from the above graphs that as the number of groups increases, the total travelling distance and communication costs decrease, but the coverage error of the dynamic target environments increases. While the number of the groups is 200, the coverage error is near 0.8, then the swarm robotic system cannot form the suitable spatial structure for the target shape. As a result, the number of groups is not as large as possible.

For the large-scale swarm robotic system, the method based on grouping is used to improve the convergence speed and reduce the communication cost. However, we should consider how to divide the groups and how many groups are used.

3. Comparison of the performance parameters with different methods:

In this section, we compare several performance parameters of our method with those of other methods, that is, leader–follower and multi-leader without grouping. These parameters include the following:

Communication cost represents the number of messages at each given time t.

Figure 13 shows a comparison of the communication cost for the grouping method and other methods without grouping. It is clear that grouping-based formation methods have lower communication cost. Because most communications are limited to one group, there is less communication between groups, which also results in faster convergence.

Figure 13.

Comparison of the communication cost for grouping and other methods.

Count of covered robots currently in the target shape P_b.

Figure 14 reflects the number of robots located in the target environment over time for the grouping method and other methods. The grouping method completes the majority of robots’ spatial formation in a short time. The number of individuals covered by the grouping method is relatively larger, that is, the coverage error is small.

Figure 14.

Comparison of the covered robot count for grouping and other methods.

Total travel distance of the robots $\sum_{α \in A} ∥ l (α) ∥$ .

Figure 15 shows the total travel distance for the grouping method and other without-grouping methods. The total travel distance is the lowest with the grouping method because parts of robots that are close to each other first gather into one group and then move together to the target environment. The total travel distance of the robots reflects the energy expenditure of the swarm robot system.

Figure 15.

Comparison of the total travel distance.

Coverage error to the current target shape.

Figure 16 shows the coverage error to the target shape. It is clear that the grouping method has a greater coverage error, and it is more stable in the dynamic environment. The grouping method divides the swarm robots into several groups; each group can adaptively adjust the spatial structure independently in the dynamic environment, so the convergence can be faster. Coverage error is expected to converge to 0.

Figure 16.

Comparison of the coverage error of the target shape for grouping and other methods.

Convergence analysis

The performance measures^39,40 for quantifying the performance of the compared algorithms in this section are mean and standard deviation values on coverage error.⁴¹ The values of three algorithms on adaptive formation in a dynamic environment problem are presented in Table 2. The Wilcoxon rank-sum test⁴² was carried out to indicate the significance between different results at the 0.05 significance level. As shown in Table 2, the algorithm with grouping has smaller values on coverage error at various periods.

According to the several previous indicators in the comparison, we note that the performance of the grouping-based formation method is better than those of the other without-grouping methods in many aspects. The grouping-based method decreases the communication cost and convergence time.

Table 2.

Mean and standard deviation values on coverage error.

Time	With grouping	Multi-leader without grouping	Leader–follower
2500	3.2887E-1 (0.027501)	4.0487 E-1 (0.027515)^a	6.5169 E-1 (0.027662)^a
5000	1.8473E-1 (0.010253)	2.6073E-1 (0.010253)^a	3.2265E-1 (0.015069)^a
10,000	1.0569 E-1 (0.020089)	1.8169 E-1 (0.020089)^a	2.0906E-1 (0.009399)^a
15,000	3.5376 E-2 (0.018715)	1.1137 E-1 (0.018715)^a	1.8431E-1 (0.01229)^a
20,000	1.5529 E-2 (0.012636)	8.9123 E-2 (0.016874)^a	1.8114E-1 (0.012457)^a
22,500	1.5135 E-2 (0.015547)	8.9894 E-2 (0.016997)^a	1.8521 E-1 (0.012732)^a

^a Grouping performs significantly better than the corresponding methods.

Conclusions and future work

According to the existing method, the swarm robotic system operates under a global coordinate system within which the robots must localize. Most spatial formation methods must know the shape position, and it is subsequently difficult to adapt to an unknown dynamic environment, and many methods are more suitable for small-scale robot systems. In reality, it is difficult to adjust the spatial structure with time for a large-scale swarm robotic system in a dynamically changing environment. Communication costs increase dramatically with the increasing size of robots in a large-scale swarm robotic system, and the convergence time is considerable. Table 3 shows a comparative analysis of selected existing methods for swarm spatial formation. For a large-scale complex shape formation without global information in an environment that changes dynamically, our method has lower coverage error than certain existing method for swarm spatial formation.

Table 3.

Comparative analysis of existing methods for swarm spatial formation.

Method	Large scale	Complex shape	Without global information	Dynamic positioning	Dynamic environment	Convergence speed
GRN^36,37	√	√	×	√	Not considered	Fast
Gilpin et al.²⁹	×	√	×	√	Not considered	Fast
Cheah et al.³¹	×	×	√	√	Not considered	Fast
Kilobot³⁸	√	√	√	√	Not considered	Slow
Our method	√	√	√	√	Considered	Fast

GRN: gene regulatory network.

In this article, we presented a grouping-based formation method for a swarm robotic system that can adapt to the dynamic changing environment. In the experiments, we show that the swarm robotic system dynamically adapts in an unknown environment to form a stable shape and can be adjusted with changes in the environment. Compared with the existing methods, our method has two main contributions: (1) an automatic group division algorithm based on local communication dramatically improves the formation speed and decreases the communication cost and (2) the self-organizing algorithm can realize the formation of swarm robots in a completely unknown dynamic environment. Future work will include proof of our theory and implementation of our algorithm on real swarm robots.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was financially supported by the Natural Science Foundation of China under grants 61532004 and 61379051.

ORCID iD

Yin Chen

References

Bayindir

. A review of swarm robotics tasks. Neurocomputing 2016; 172(C): 292–321.

Barca

Sekercioglu

. Swarm robotics reviewed. Robotica 2013; 31(3): 345–359.

Shinnoh

Chong

Lee

. Novel extrapolating methods using exponential function in formation control of swarm robots. Trans Soc Instrum Control Eng 2016; 52(1): 28–36.

Tran

Lee

. A stable formation control using approximation of translational and angular accelerations. Int J Adv Rob Syst 2011; 8(1): 65–75.

Habib

Baudoin

. Robot-assisted risky intervention, search, rescue and environmental surveillance. Int J Adv Rob Syst 2010; 7(1): 1–8.

Bakhshipour

Jabbari Ghadi

Namdari

. Swarm robotics search and rescue: a novel artificial intelligence-inspired optimization approach. Appl Soft Comput 2017; 57: 708–726.

Dietz

. Human perception of swarm robot motion. In: CHI conference extended abstracts human factor in computer systems, Denver, USA, 6–11 May 2017, pp. 2520–2527.

Saska

. Swarm distribution and deployment for cooperative surveillance by micro-aerial vehicles. J Intelligent Rob Syst 2016; 84(1–4): 469–492.

Zhang

Chen

Stan

. Collective behavior coordination with predictive mechanisms. Complex Syst Networks 2016: 67–85.

10.

Senanayake

Senthooran

Barca

. Search and tracking algorithms for swarms of robots. Rob Auton Syst 2016; 75(PB): 422–434.

11.

Varghese

Mckee

. A review and implementation of swarm pattern formation and transformation models. Int J Intelligent Comput Cyber 2009; 2(4): 786–817.

12.

Dang

Horn

. Formation adaptation control of autonomous robots in a dynamic environment. IEEE International conference on industrial technology, Seville, Spain, 17–19 March 2015, pp. 3190–3195.

13.

Zhu

Yang

. A bio-inspired approach to task assignment of swarm robots in 3-D dynamic environments. IEEE Trans Cybern 2017; 47(4): 974–983.

14.

Penders

Alboul

Witkowski

. A robot swarm assisting a human fire fighter. Adv Robot 2011; 25(1): 93–117.

15.

Wang

Kwok

Fang

. Ants based control of swarm robots for bushfire fighting. Artif Int Comput Int 2010; 2010: 528–532.

16.

Gancet

Motard

Naghsh

. User interfaces for human robot interactions with a swarm of robots in support to firefighters. In: International conference on robotics and automation, Alaska, USA, 3–7 May 2010, pp. 2846–2851.

17.

Guo

Meng

Jin

. Analysis of local communication load in shape formation of a distributed morphogenetic swarm robotic system. Evol Comput 2010; 2010: 1–8.

18.

Guo

Meng

Jin

. Swarm robot pattern formation using a morphogenetic multi-cellular based self-organizing algorithm. In: IEEE international conference on robotics and automation, Shanghai, China, 9–13 May 2011, pp. 3205–3210.

19.

Lee

. Automatic mutual localization of swarm robot using a particle filter. J Inf Commun Conver Eng 2012; 10(4): 390–395.

20.

Choi

Kim

. Fuel efficient three dimensional controller for leader-follower UAV formation flight. In: Int Conf Control Autom Syst, Guangzhou, China, 30 May–1 June 2007, pp. 806–811.

21.

Loria

Dasdemir

Jarquin

. Leader-follower formation and tracking control of mobile robots along straight paths. IEEE Trans Control Syst Technol 2016; 24(2): 727–732.

22.

Park

Yoo

. Adaptive leader-follower formation control of mobile robots with unknown skidding and slipping effects. Int J Control Autom Sys 2015; 13(3): 587–594.

23.

Duarte

Rodrigues

Oliveira

. Unleashing the potential of evolutionary swarm robotics in the real world. In: Genetic and evolutionary computation conference companion, Denver, CO, USA, 20–24 July 2016, pp. 159–160.

24.

Balch

Arkin

. Behavior-based formation control for multirobot teams. IEEE Trans Rob Autom 1999; 14(6): 926–939.

25.

Elkilany

Abouelsoud

Fathelbab

AMR

. Adaptive formation control of robot swarms using optimized potential field method. IEEE international conference on industrial technology, Toronto, Canada, 22–25 March 2017, pp. 721–725.

26.

Wang

Cheng

. Path planning of robot based on improved artificial potentional field method. In: International conference on artificial intelligence, automation and control technologies, Wuhan, China, 7–9 April 2017, p. 34.

27.

Rubenstein

Sai

Chuong

. Regenerative patterning in swarm robots: mutual benefits of research in robotics and stem cell biology. Int J Develop Biol 2009; 53(5–6): 869–881.

28.

Shen

Will

Galstyan

. Hormone-inspired self-organization and distributed control of robotic swarms. Auton Rob 2004; 17(1): 93–105.

29.

Gilpin

Knaian

Rus

. Robot pebbles: one centimeter modules for programmable matter through self-disassembly. IEEE international conference on robotics and automation, Alaska, USA, 3–7 May 2010, pp. 2485–2492.

30.

Rubenstein

Shen

. Automatic scalable size selection for the shape of a distributed robotic collective. In: IEEE/RSJ international conference on intelligent robots and systems, Taipei, Taiwan, 18–22 October 2010, pp. 508–513.

31.

Cheah

Hou

Slotine

EJJ

. Region-based shape control for a swarm of robots. Automatica 2009; 45(10): 2406–2411.

32.

Marco

Matteo

Franco

. Experiments of morphogenesis in swarms of simple mobile robots. Appl Artif Int 2004; 18(9–10): 903–919.

33.

Hahmin

Dong

. Potential-function-based shape formation in swarm simulation. Int J Control Autom Syst 2014; 12(2): 442C–449C.

34.

Farshad

Khairulmizam

Abdul

. Imitation of honeybee aggregation with collective behavior of swarm robots. Int J Comput Int Syst 2011; 4(4): 739–748.

35.

Meng

Guo

Jin

. A morphogenetic approach to flexible and robust shape formation for swarm robotic systems. Robot Auton Syst 2013; 61(1): 25–38.

36.

Jin

. Adaptive swarm robot region coverage using gene regulatory networks. In: Conference towards autonomous robotic systems, Birmingham, UK, 1–3 September 2014, pp. 197–208.

37.

Shirazi

Sun

. Bio-inspired self-organising multi-robot pattern formation: a review. Robot Auton Syst 2017; 91(C): 83–100.

38.

Rubenstein

Cornejo

Nagpal

. Robotics. Programmable self-assembly in a thousand-robot swarm. Science 2014; 345(6198): 795–799.

39.

Zou

Zhang

Yang

. Adaptive neighborhood selection for many-objective optimization problems. Appl Soft Comput 2018; 64: 186–198.

40.

Zou

Yang

. A prediction strategy based on center points and knee points for evolutionary dynamic multi-objective optimization. Appl Soft Comput 2017; 61: 806–818.

41.

Derrac

Garcła

Hui

. Analyzing convergence performance of evolutionary algorithms: a statistical approach. Inf Sci 2014; 289(5): 41–58.

42.

Wilcoxon

. Individual comparisons by ranking methods. Biomet Bull 1945; 1(6): 80–83.

Grouping-based adaptive spatial formation of swarm robots in a dynamic environment

Abstract

Keywords

Introduction

Related work

Problem statement of spatial formation of swarm robots

Example of a swarm robotic system for firefighting

Problem statement

Definition 1 (swarm robotic system)

Definition 2 (environment)

Definition 3 (boundary)

Definition 4 (coverage error)

Definition 5 (convergence time)

Definition 6 (communication cost)

Definition 7 (convergence rate)

Problem 1

Grouping-based adaptive spatial formation method

Model of individual robot

Definition 8 (state)

Definition 9 (action)

Definition 10 (behaviour)

Grouping-based decomposition and organization of swarm robots

Overview of the grouping-based swarm formation in a dynamic environment

Group division mechanism

Definition 11 (group)

Adaptive mechanism in the dynamic environment

Self-organizing formation in a dynamic environment

Simulation and experimental results

Dynamic environment

Experiment: Grouping-based formation in a dynamic target shape

Experimental analysis

Conclusions and future work

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References