Sage Journals: Discover world-class research

Abstract

In this article, we address a formation control problem for a group of autonomous robots to track a moving target in the presence of obstacles. In the proposed method, desired formations, which consist of virtual nodes arranged in specific shapes, are first generated. Then, autonomous robots are driven toward these virtual nodes without collisions with each other using a novel control scheme, which is based on artificial force fields. The convergence analysis is shown based on Lyapunov’s stability. The novelty of the proposed approach lies in a new combination of rotational force field and repulsive force field to design a mechanism so that robots can avoid and escape complex obstacle shapes. The effectiveness of the proposed method is illustrated with numerical examples using V-shape and circular shape formations.

Keywords

Formation control stability of a swarm collision avoidance vector fields swarm intelligence

Introduction

Research activities in multiagent systems have offered a wide range of applications in various areas such as physics, biology, cybernetics, and agriculture. In the field of multiagent systems, one of the most important problems is formation control, in which agents in the system are required to form desired shapes. Typical potential applications in formation control include search and rescue missions, forest fire detection and surveillance, source seeking, and so on. Autonomous robots of a multiagent system can be underwater vehicles,^1,2 unmanned aerial vehicles,^3,4 mobile sensor networks,^5

–12 rectangular agents,¹³ and nonholonomic mobile robots.^14

–18

Centralized control protocols have been constructed based on the common assumption that the information of all agents is available or the multiagent system possesses all-to-all communication. The drawbacks of the centralized communication control architect are inflexibility and large computational costs for each controller for each agent especially when the number of robots is large. In contrast, a distributed or decentralized control approach can provide more flexibility, easier implementation, and less computation loads as the controller of each agent only requires the information of its neighbor agents.^{6,7,18

–21}

In formation control of a multiagent system, desired tasks of the system, such as tracking a moving target, are executed by the cooperation of a robot team. The formation control problem of autonomous robots is motivated by natural behaviors of creatures such as fish schooling, bird flocking, or ant swarming. Here, the members in the formation are required to collaborate with others to achieve common goals such as velocity matching and collision avoidance. The formation of a swarm of mobile robots can be generated and controlled by different methods in the literature. It is well-known that the artificial potential field method plays a pivotal role in controlling the coordination and the motion of a swarm so that its agents move toward target positions.^22

–28 It is well established that the potential field generates impulsive/attractive forces for mobile robots to avoid collision and maintain distances in coordination control problems.⁵ Many works on the formation control method using the random connections among neighboring members in a swarm as an α-lattice configuration were reported in a variety of papers.^{5

–12,29,30} In this direction, the attractive/repulsive force fields are employed to link neighboring robots so that a robust formation without collisions is established. In a different approach, a dynamic framework was introduced by Hou et al.³¹ and Cheah et al.,³² in which the robots of a swarm can adapt their formation by rotating and scaling during their movement. Similarly, the attractive/repulsive force fields were also utilized by Eren³³ to control robots to converge to given positions of a desired shape.

Although the artificial potential field has been regarded as a powerful tool for path planning of mobile robots, it still possesses some limitations due to local minimum problems. This can lead to a situation where a robot can get stuck if facing with an obstacle. In this context, the attractive force of the target and the repulsive force of the obstacles are equal and collinear but in an opposite direction. As a result, the total force on the robot is equal to zero, which traps the robot there. In addition, the traditional potential field method exhibits shortcomings in complex environments which contain convex and concave obstacle shapes, such as U-shaped obstacles or long walls and so on. When facing with these kinds of obstacles, robots can be trapped in them, and hence prevented from reaching targets.³⁴ The summary of related work is shown in Table 1. Recent research methods were proposed to address local minima avoidance^41,42 that the reader can refer to.

Table 1.

Summary of related work in multiagent formation control.

LCF	DFF	FS
Flocking of mobile sensor networks,^5 –7 flocking of multiagent systems,^8 –11 and adaptation and stability of a swarm in a dynamic environment.^12,29,30	Formation control following a framework, ^33,35,36 and formation control following dynamic region.^31,32	Our article presents a new approach to multi-robot formation control following a desired shape formation (V-shape^37,38 or circular shape,^39,40 etc.) to track, and encircle a moving target under the effect of the dynamic environment.
LCF is mainly designed based on the random connections among the neighboring members in an α-lattice configuration. The convergence and adaptation of a swarm in a dynamic environment were verified. However, when we need a practical formation, such as V-shape, circular shape or linear formation, and so on. LCF method is still constrained. In this method, each robot’s motion depends on the motion of its neighbors.	In the DFF method, all robots in the group move together within a given framework or region. They stay within a moving region and are able to adjust their formation by rotating and scaling during their movement. This method does not require specific orders or positions of all robots inside the given region. Each robot’s motion depends on the motion of its neighbors and framework.	In our approach, the shape of the desired formation is easily designed. Robots are independently controlled by the attractive potential field from the virtual nodes in the desired formation. Moreover, the designed virtual nodes guarantee that the neighboring robots do not interact with each other. Hence, robots easily converge to these virtual nodes under the velocity matching. Using an added rotational vector field, robots can quickly escape convex and concave obstacles to continue to track the target.

LCF: α-lattice connection formation; DFF: dynamic framework formation; FS: formation following desired shape.

In many studies, the dynamics of agents are modeled as single integrator,^13,43,44 double integrators,^5,7,10,45,46 and unicycles.^47,48 In narrow space, the shapes of agents are taken into consideration for the formation control problem.^13,44 In this article, a formation control problem for point-based agents with double-integrator dynamics is addressed. Theoretical development of the paper sets a framework, which can be employed to design a formation control system for various agents with more complicated dynamics and shapes. The particle model in this article has been extensively used in previous work. The work of Olfati-Saber⁵ presents a theoretical framework for design and analysis of distributed flocking algorithms using the double-integrator dynamics for the dynamics of an agent. In applications, it is employed to model mobile robots that have omnidirectional motion capability, such as the Rovio mobile robots.^7,10 It is also used in theoretical work for mobile sensor networks.^45,46

The main contributions of this article are in the following. The formation control algorithms are designed to drive multiple robots to converge to the desired positions to capture a moving target while avoiding collision with other agents and obstacles. However, the communication is still all-to-all since there is a need to compare the distances of agents to the target to choose the leader of the swarm. Once the leader is chosen, the control law of an agent is calculated based on the positions and velocities of its neighbor agents. In this case, the control algorithm is distributed, which helps save computational costs. The stability of the formation is maintained and collision avoidance among robots is obtained while the swarm tracks a moving target. In addition, the novelty of the article lies in the combination of the rotational and repulsive force fields, from which the obstacle avoidance control algorithm is constructed to drive robots to escape obstacles without collisions.

The structure of the article is organized as follows. In section Formulation, the problem formulation is presented. In section Control algorithms, the formation control algorithms are presented. Section Case study presents a case study for two typical examples of V-shape and circular shape formation control. Section Simulation results presents some simulation results. Finally, section Conclusion concludes the article with some remarks and future research topics.

Problem formulation

In this article, a swarm of N robots is considered with their mission of tracking a moving target in two-dimensional space. Let $p_{i} = (x_{i}, y_{i})^{T}$ and $v_{i} = (v_{i x}, v_{i y})^{T}$ be the position and velocity vectors of robot i ( $i = 1, 2, 3, ..., N$ ), respectively. The dynamic model of robot i is

\begin{array}{l} {\dot{p}}_{i} = v_{i} \\ {\dot{v}}_{i} = u_{i} \end{array}

for $i = 1, 2, 3, ..., N$ .

Conditions for a formation of autonomous robots are as follows:

There are no collisions among robots.

Robots must converge to the desired positions.

Robots must avoid collision with obstacles.

The formation must be maintained under the influence of the environment.

A desired formation of a multi-robot system consists of virtual nodes which will be occupied by the robots of the system. To facilitate the control design and analysis, we introduce the following definitions.

Definition 1

In the desired formation, a virtual node j ( $j = 1, 2, .., N$ ; $q_{j} = (x_{j}, y_{j})^{T}$ ; $v_{j} = (v_{j x}, v_{j y})^{T}$ ) is a desired position for robot i, for which $lim_{t \to \infty} ∥ p_{i} (t) - q_{j} (t) ∥ = 0$ .

Definition 2

Let $d_{p_{i} q_{j}} < r_{a}$ be the distance of robot i to virtual node j ( $j = 1, 2, 3, ..., N$ ). If $d_{p_{i} q_{j}} < r_{a}$ , where $r_{a} = d / 2 - λ_{a}$ , d is the distance between two neighbor virtual nodes, and $λ_{a}$ is a positive constant, then robot i is an active robot. Otherwise, it is called a free robot. Here, $r_{a}$ is denoted as the radius of the active circle surrounding the virtual node (see Figure 1).

Figure 1.

Description of the formation control method using the desired V-shape and circular shape structure. Agents use algorithm 1 to reach their virtual nodes to form the desired formations. The leader is selected by using algorithm 2.

Definition 3

Let l denote the index of the current leader of the swarm.

Definition 4

In the desired formation, virtual node j is called an active node if a robot i ( $i = 1, 2, .., N$ ) lies in the active circle of the virtual node j (see Figure 1). Otherwise, it is called a free virtual node.

Definition 5

The desired V-shape formation consists of two line formations. These line formations are driven by a selected leader and connected by a formation angle ϕ. In each line of the formation, the virtual nodes are equidistant to its neighboring ones.

Definition 6

The desired circular shape formation is a circle in which all virtual nodes are distributed evenly on the circle and the target lies in the center of the circle.

Definition 7

Let $N_{i}^{k} (t)$ be the set of the neighboring robots of the robot i at time t, such that

N_{i}^{k} (t) = {\forall k : d_{i}^{k} = ∥ p_{i} - p_{k} ∥ \leq r_{r}, k \in 1, ..., N, k \neq i}

where $r_{r}$ is the repulsive radius surrounding each robot, and $d_{i}^{k}$ is the Euclidean distance between robots k and i.

Definition 8

A set of the neighboring obstacles of robot i at time t is defined as

O_{i}^{o} (t) = {\forall k : d_{i o_{k}} \leq r_{β}, k \in 1, ..., M}

where $r_{β} > 0$ , M is the number of obstacles, and $d_{i o_{k}} = ∥ p_{i} - p_{o_{k}} ∥$ are the obstacle detection range and the Euclidean distance between robot i and obstacle $o_{k}$ , respectively.

Control algorithms

This section presents control algorithms to guarantee that all robots will converge to their desired positions in the desired formation. While tracking a moving target, collision and obstacle avoidance of the swarm must be achieved.

Control architecture

To address our problem, we propose the control input $u_{i}$ for each robot as follows

u_{i} = {\begin{array}{l} u_{i}^{t} + u_{i}^{o} & if robot i is a leader \\ u_{i}^{f} + u_{i}^{o} + u_{i}^{c} & otherwise \end{array}

where $u_{i}^{f}$ is used to control the formation connection, $u_{i}^{o}$ drives robots to avoid obstacles, $u_{i}^{c}$ helps robots avoid collision during the motion of the swarm, and $u_{i}^{t}$ serves as a tracking controller. Hence, it can drive the leader of the swarm to move toward the target. In equation (4), when collision avoidance for robot i is active, other robots lie in its repulsive radius $r_{r}$ , which activates $u_{i}^{c}$ . Similarly, when an obstacle lies in the obstacle sensing range $r^{β}$ , obstacle avoidance is active, leading to the activation of $u_{i}^{o}$ . The stability analysis of the main results in this article will be based on Lyapunov’s stability theorem.^49,50

Formation connection control algorithm

Initially, there exists an attractive force field for each virtual node j $(j = 1, 2, ... N)$ . The resulting attractive force fields drive free robots to move toward their desired positions. The free robots will then become active and will occupy these desired positions. The tracking control objective for each robot is to make the distance between robot i and virtual node j ( $d_{p_{i} q_{j}} = ∥ p_{i} - q_{j} ∥$ ) approach zero as fast as possible. In other words, $lim_{t \to \infty} ∥ p_{i} - q_{j} ∥ = 0$ and $lim_{t \to \infty} ∥ v_{i} - v_{j} ∥ = 0$ . Based on the above argument, the formation control law for formation connection is presented in algorithm 1.

In algorithm 1, $κ_{i}^{p 1}$ , $κ_{i}^{p 2}$ , $κ_{i}^{p 3}$ , and $κ_{i}^{v}$ are positive constants; $(p_{i} - q_{j})$ and $(v_{i} - v_{j})$ are the relative position and velocity vectors between robot i and virtual node j, respectively. Two potential fields $f_{i j}^{1} = - κ_{i}^{p 3} (p_{i} - q_{j}) / ∥ p_{i} - q_{j} ∥$ and $f_{i j}^{2} = - κ_{i}^{p 1} (p_{i} - q_{j})$ are employed as the artificial attractive forces. Free robots are driven toward the desired formation using the constant potential field $f_{i j}^{1}$ , while active robots are controlled to approach the virtual nodes using the linear potential field $f_{i j}^{2}$ . In addition, the component $- κ_{i}^{v} (v_{i} - v_{j})$ serves as a damping term. Thus, using algorithm 1, the robots of the swarm can quickly converge to the desired positions, which are the virtual nodes of the desired formation. The stability of the formation is stated in the following.

Theorem 1

Consider the active robot i with its dynamic model (1) and control input $u_{i}^{j}$ given in algorithm 1 at the active node j in the desired formation. If the velocity of node j is smaller than the maximum velocity of robot i, and node $j - 1$ is also active, then the system (1) will converge to the equilibrium state, at which $p_{i} = q_{j}$ and $v_{i} = v_{j}$ for all i and j.

Proof

In order to analyze the stability of the robot i at the active node j when the node $j - 1$ is also active, we rewrite the control law $u_{i}^{f}$ as follows

u_{i}^{f} = f_{i j}^{2} - κ_{i}^{v} (v_{i} - v_{j}) + {\dot{v}}_{j}

Consider the vector field $f_{i j}^{2} = - κ_{i}^{p 1} (p_{i} - p_{j}) = (P_{i}, Q_{i}, Z_{i})^{T}$ where $P_{i} = κ_{i}^{p 1} (x_{i} - x_{j})$ , $Q_{i} = κ_{i}^{p 1} (y_{i} - y_{j})$ , and $Z_{i} = 0$ . According to Freeman and Kokotovic,⁴⁹ we obtain

rot (f_{2 i}^{j}) = {(\frac{\partial Z_{i}}{\partial y_{i}} - \frac{\partial Q_{i}}{\partial z_{i}}, \frac{\partial P_{i}}{\partial z_{i}} - \frac{\partial Z_{i}}{\partial x_{i}}, \frac{\partial Q_{i}}{\partial x_{i}} - \frac{\partial P_{i}}{\partial y_{i}})}^{T} = 0

Equation (6) shows that the vector field $f_{i j}^{2}$ is irrotational. Consider the scale function

V_{i j} = \frac{1}{2} κ_{i}^{p 1} (p_{i} - q_{j}) (p_{i} - q_{j})^{T}

Taking the negative gradient of the function $V_{i}^{f}$ , we obtain

\begin{matrix} - \nabla V_{i j} = - \nabla (\frac{1}{2} κ_{i}^{p 1} (p_{i} - q_{j}) (p_{i} - q_{j})^{T}) \\ = - \nabla (\frac{1}{2} κ_{i}^{p 1} ({(x_{i} - x_{j})}^{2} + (y_{i} - y_{j})^{2}) \\ = {(\begin{matrix} - \frac{1}{2} κ_{i}^{p 1} \frac{\partial}{\partial x_{i}} ({(x_{i} - x_{j})}^{2} + (y_{i} - y_{j})^{2} \\ - \frac{1}{2} κ_{i}^{p 1} \frac{\partial}{\partial y_{i}} ({(x_{i} - x_{j})}^{2} + (y_{i} - y_{j})^{2} \end{matrix})}^{T} \\ = {(\begin{matrix} - κ_{i}^{p 1} (x_{i} - x_{j}) \\ - κ_{i}^{p 1} (y_{i} - y_{j}) \end{matrix})}^{T} = - κ_{i}^{p 1} (p_{i} - p_{j}) \\ = f_{i}^{f 2} \end{matrix}

Equations (6) and (8) show that the vector field $f_{i}^{f 2}$ is a potential field, and its potential function is $V_{i}^{f}$ .

Let ${\bar{x}}_{1} = p_{i} - q_{j}$ and ${\bar{x}}_{2} = v_{i} - v_{j}$ be the relative position and velocity of the robot i and node j, respectively. The error dynamic model of the system is given as

{\dot{\bar{x}}}_{1} = {\bar{x}}_{2}

{\dot{\bar{x}}}_{2} = u_{i}^{j} - {\dot{v}}_{j}, i, j = 1, 2, ..., N

From equations (5) and (9),

\dot{\bar{x}} = A \bar{x}

where $\bar{x} = ({\bar{x}}_{1}, {\bar{x}}_{2})^{T}$ and

A = [\begin{matrix} O_{2} & I_{2} \\ - κ_{i p 1}^{j} I_{2} & - κ_{i}^{v} I_{2} \end{matrix}]

where $O_{2}$ is the zero matrix of 2 and $I_{2}$ is the identity matrix of 2. It can easily be shown that the eigenvalues of matrix A are the roots of the polynomial $s^{2} + κ_{i}^{p 1} s + κ_{i}^{v}$ , which have negative real parts since $κ_{i}^{p 1}$ is positive. Hence, the system (11) is asymptotically stable.⁵⁰□

Remark 1

It is well established that the Lyapunov theory is employed for the stability proof of formation and flock control of multiagent systems.⁵ For more information about the Lyapunov theory, the reader is referred to the work of Freeman and Kokotovic⁴⁹ and Khalil.⁵⁰

Remark 2

Figure 1 illustrates a desired formation (V-shape or circular shape formation) of N virtual nodes. The desired formation contains a desired position for each robot. Algorithm 1 allows each free robot i to firstly seek its closest free virtual node (for instance, j) so that it will be active at this virtual node. If the position of an active robot i is still not at the desired one (e.g. robot k in Figure 1 with $k = 1, 2, ..., N, k \neq l$ ), then it will automatically move to virtual node $(j - 1)$ until it occupies the desired position.

Algorithm 1

Reaching the desired positions at the virtual nodes in the desired formation.

In order to allow robot i to approach node j as fast as possible, we use the attractive force from node j, which is proportional to its velocity. This means that the factor $κ_{i}^{p 1}$ in algorithm 1 depends on the velocity $v_{j}$ . This factor is given as

κ_{i}^{p 1} = κ_{i}^{p d} + ε_{1} ∥ v_{j} ∥

where $κ_{i}^{p d}$ and $ε_{1}$ are positive.

Collision avoidance control algorithm

This section presents a method for the collision avoidance among the robots during their movement based on the artificial repulsive potential field. The potential field has been widely used in addressing flocking and formation control of multiagent systems.^5,9,22
–24 In general, a potential function $ξ (.)$ , which depends on the distance among agents or between agents and obstacles, is constructed. A typical feedback control law consists of two parts: the gradient of the potential function and the velocity consensus term.^5,9,22
–24

In order to avoid the collision between robots i and k (i, $k = 1, 2, ..., N$ ; $i \neq k \neq l$ ), the local repulsive force field is created surrounding each robot within the repulsive radius $r_{r}$ as

f_{i k} = ((\frac{1}{d_{i k}} - \frac{1}{r_{r}}) \frac{κ_{i k}^{c 1}}{{(d_{i k})}^{2}} - κ_{i k}^{c 2} (d_{i k} - r_{r})) c_{i k}^{c} n_{i k}

where positive constants $κ_{i k}^{c 1}$ and $κ_{i k}^{c 2}$ are employed to deal with fast interaction. The unit vector from robots k to i is described as $n_{i k} = (p_{i} - p_{k}) / ∥ p_{i} - p_{k} ∥$ . The scalar $c_{i k}^{c}$ is defined as N

c_{i k}^{c} = {\begin{array}{l} 1, & if k \in N_{i}^{k} (t) \\ 0, & otherwise \end{array}

The algorithm for the collision avoidance is built based on the repulsive vector field (14) combined with the relative velocity vector $κ_{i k}^{c} (v_{i} - v_{k})$ between robots k and i as follows

u_{i}^{c} = \sum_{k = 1, k \neq i}^{N} (f_{i k} - c_{i k}^{c} κ_{i k}^{c} (v_{i} - v_{k}))

The controller (16) reveals that neighboring robots are controlled to leave each other when distances among them are too close. As in the study of Olfati-Saber,⁵ we employ repulsive fields to avoid collision among agents. The analysis is quite similar to that in the study of Olfati-Saber.⁵ Therefore, our control mechanism guarantees that collision avoidance in the swarm is achieved.

Obstacle avoidance control algorithm

This section presents a control algorithm for robots to pass through M obstacles. The obstacle avoidance control algorithm for each member robot i ( $i = 1, 2, ..., N$ ) is designed as follows

u_{i}^{o} = \sum_{h = 1}^{M} (f_{i}^{o p} + f_{i}^{o r} + κ_{i}^{o} c_{i h}^{o} (v_{i} - v_{o_{h}}))

where relative velocity vector $(v_{i} - v_{o_{h}})$ between robot i and its neighboring obstacle $o_{h}$ is utilized as a damping term with damping scaling factor $κ_{i}^{o}$ , and the scalar $c_{i h}^{o}$ is defined as

c_{i h}^{o} = {\begin{array}{l} 1, & if h \in O_{i}^{o} (t) \\ 0, & otherwise \end{array}

The repulsive force field $f_{i}^{o p}$ is created to drive robot i to move away from its neighboring obstacle (see Figure 2). This force field is designed as

f_{i}^{o p} = ((\frac{1}{d_{i o_{h}}} - \frac{1}{r_{β}}) \frac{κ_{i}^{o 1}}{{(d_{i o_{h}})}^{2}} - κ_{i}^{o 2} (d_{i o_{h}} - r_{β})) c_{i o_{h}}^{o} n_{i o_{h}}

where positive factors $κ_{i}^{o 1}$ and $κ_{i}^{o 2}$ are used to control the fast obstacle avoidance, $r_{β}$ is the obstacle detection range defined in definition 8, and $n_{i o_{h}} = (p_{i} - p_{o_{h}}) / ∥ p_{i} - p_{o_{h}} ∥$ is a unit vector.

Figure 2.

The description of the repulsive force field $f_{i}^{o p}$ surrounding the neighboring obstacle o of the robot i (a), and its amplitude $∥ f_{i}^{o p} ∥$ (b).

In control law (17), the rotational force field (see Figure 3) is added to combine with the repulsive force (see Figure 2) to drive robot i to quickly escape its neighboring obstacle. While the potential force field is used to enable it to avoid collision with its neighboring obstacle, the rotational force field is used to solve the local minimum problems; for instance, the robot meets a trapping point, at which the repulsive force of the obstacles and the attractive force of the target are balanced. Under the effect of the added rotational force field, the robot always escapes this trapping point. Furthermore, when robot is trapped in complex obstacles (e.g. U-shape or long wall), the rotational vector field will help it find a new path to escape these obstacles. The direction of the rotational force can be clockwise or counter clockwise (see Figure 3). Hence, this rotational force is built as

f_{i}^{o r} = w_{i o_{h}} c_{i o_{h}} n_{i}^{o r}

where the unit vector $n_{i}^{o r}$ is given as

n_{i}^{o r} = c_{i}^{o r} {((y_{i} - y_{o_{h}}) / d_{i o_{h}}, - (x_{i} - x_{o_{h}}) / d_{i o_{h}})}^{T}

where the scalar $c_{i}^{o r}$ is used to define the direction for the rotational force: the rotational force is clockwise if $c_{i}^{o r} = 1$ and counter clockwise if $c_{i}^{o r} = - 1$ . Now, we consider the relationship between this unit vector and the vector $p_{i} - p_{o_{h}}$ .

Figure 3.

The clockwise rotational force field (a) and the counter clockwise rotational force field (b).

Let σ be the angle between these vectors. Then, we have

cos σ = \frac{c_{i}^{o r} ((x_{i} - x_{o_{h}}) (y_{i} - y_{o_{h}}) - (y_{i} - y_{o_{h}}) (x_{i} - x_{o_{h}}))}{{(d_{i o_{h}})}^{2}} = 0

Equation (22) shows that the unit vector is always perpendicular to vector $(p_{i} - p_{o_{h}})$ . The positive gain factor $w_{i o_{h}}$ in equation (20) is used as a control element to drive robots to quickly escape obstacles. Therefore, this control element is designed such that the total force on robots always has the direction in the selected rotational direction. This control element is given as follows

w_{i o_{h}} = (1 + c) (∥ f_{i}^{top} ∥ + λ_{o})

where $λ_{o}$ is a positive factor and the force $f_{i}^{top}$ is described as

f_{i}^{top} = f_{i j} + f_{i}^{o p}

where $f_{i}^{o p}$ is the repulsive force from the neighboring obstacles of robot i, and $f_{i j}$ is the attractive force from the virtual node j in the desired formation (see algorithm 1). The constant c in equation (23), which depends on angle α between the sum vector $f_{i}^{top}$ and the unit vector $n_{i}^{o r}$ (see Figure 4), is described as follows

c = {\begin{array}{l} c_{1}, & if α < π / 2 \\ c_{2}, & otherwise \end{array}

where two constants $c_{1}$ and $c_{2}$ can be chosen as $- 1 < c_{1}$ , $0 < c_{2}$ , and $c_{1} < c_{2}$ . Equation (23) guarantees that robot i always moves in the direction of the rotational force $f_{i}^{o r}$ . Hence, it can easily escape the obstacles in order to continue with its swarm to track the moving target.

Figure 4.

The description of the obstacle escape of a robot i while reaching a virtual node j: clockwise (a) and counter clockwise (b).

The total vector for the control law for agent i is $f^{s} = f_{i}^{o r} + f_{i}^{top}$ . From equations (20) and (23), $∥ f_{i}^{o r} ∥ = w_{i o_{h}}$ . It is clear that when $α < π / 2$ , the angle between $f^{s}$ and $n_{i o_{h}}$ is smaller than $π / 2$ . When $α \geq π / 2$ , $∥ f_{i}^{o r} ∥ = w_{i o_{h}} > ∥ f_{i}^{top} ∥$ . This implies that the angle between $f_{s}$ and $n_{i o_{h}}$ is smaller than $α / 2$ , which is smaller than $π / 2$ . As a result, the total vector drives the agent to the direction to escape the obstacle (see Figure 4).

The obstacle avoidance analysis of the proposed scheme follows a similar approach as in theorem 6 in the technical report by Olfati-Saber.⁵¹ Unlike the method of Olfati-Saber,⁵¹ in our method, when an agent meets an obstacle, a rotational force field is generated which changes total force field. Hence, the direction of the agent is turned around the obstacle.

We summarize the above analysis in the following theorem.

Theorem 2

Consider the active robot i with its dynamic model (1). If robot i detects an obstacle in its obstacle detection range as in Figure 4, the control law in equation (17) will drive robot i to escape the obstacle.

Remark 3

The protocol for collision avoidance for the agents of the system in subsection Control architecture employs a repulsive force in equation (14). Here, the shapes of agents are simplified to be points or circles. In contrast, the obstacle avoidance in this section is realized using repulsive and rotational forces in equations (19) and (20) for a class of complex obstacles (which can be large and nonconvex). This enables agents to escape the obstacles effectively. The constraint posed on a nonconvex obstacle is that the radius of the osculating circle of the obstacle is larger than $r_{β}$ , which is the obstacle detection range. The rotational field is only activated if the obstacle is in the obstacle detection range of the agent. However, if there are many rotational forces due to many obstacles, the control algorithm of the agent will have the rotational force from the obstacle with the highest priority.

Remark 4

The complex obstacle used in our analysis is in a U-shape, which is nonconvex (see Figure 4). A rigorous study would be conducted to see whether our obstacle avoidance approach can work with a more general class of complex obstacles in the future.

Target tracking control algorithm

Firstly, a robot, which is closest to the target, is selected as the leader in order to generate the desired formation. Then, this leader leads its formation to track a moving target. When the leader encounters a risk, such as it is broken or trapped in obstacles, it must transfer its leadership to another, and becomes a free member robot in the swarm. The leader is selected as in algorithm 2.

The target tracking controller, which is designed based on the relative position between the leader and the target, has to guarantee that the formation’s motion is always driven toward the target. As introduced above, the V-shape and circular shape formations are utilized to track and encircle a moving target. Hence, the tracking task is to make the distance between the leader and the target $d_{l}^{t} = ∥ p_{l} - p_{t} ∥$ , approaching the radius of the desired circular formation $r^{τ}$ as fast as possible. This means that $lim_{t \to \infty} ∥ p_{l} - p_{t} ∥ = 0$ and $lim_{t \to \infty} ∥ v_{l} - v_{t} ∥ = 0$ . Based on the above analysis, the control law for the target tracking is proposed as follows

u_{l}^{t} = f_{l}^{t} - κ_{l}^{v} (v_{l} - v_{t}) + {\dot{v}}_{t}

where $κ_{l}^{t}$ and ${\dot{v}}_{t}$ are the positive constant and the acceleration of the target, respectively, and $(v_{l} - v_{t})$ is the relative velocity vector between the leader and the target.

The potential field from the target is used to drive the leader moving toward the target, and is given by

f_{l}^{t} = {\begin{array}{l} ((\frac{1}{d_{l}^{t}} - \frac{1}{r_{τ}}) \frac{κ_{l}^{t 2}}{{(d_{l}^{t})}^{2}} - κ_{l}^{t 3} \frac{(d_{l}^{t} - r_{τ})}{r^{t} - r^{τ}}) n_{l}^{t}, & if d_{l}^{t} < r^{t} \\ - κ_{l}^{t 1} n_{l}^{t}, & otherwise \end{array}

where $κ_{l}^{t 2}$ and $κ_{l}^{t 3}$ are positive constants, and $r_{t}$ and $r_{τ}$ are the target approaching radius and the desired radius of the circular formation ( $r_{tmin} < r^{τ} < r^{t}$ ), respectively. Here, $κ_{l}^{t 1} = κ_{l}^{t d 1} + ε_{2} ∥ v_{t} ∥$ where $κ_{l}^{t d 1}$ and $ε_{2}$ are positive constants. The unit vector along the line connection from the target to the leader is computed as $n_{l}^{t} = (p_{l} - p_{t}) / ∥ p_{l} - p_{t} ∥$ . In equation (27), the constant attractive force $f_{l}^{t 2} = - κ_{l}^{t 1} n_{l}^{t}$ is used to track the target when $d_{l}^{t} > r^{t}$ . On the other hand, the attractive/repulsive force field surrounding the equilibrium position, at which $∥ p_{l} - p_{t} ∥ = r^{τ}$ and $v_{l} - v_{t} = 0$ , is employed to encircle the target when $d_{l}^{t} \leq r^{t}$ . Hence, using this combined vector field, the leader can easily approach the target at the equilibrium position.

Theorem 3

Consider the leader l described by model (1) and governed by control law (26) when $d_{l}^{t} \leq r^{t}$ . If the velocity of the target is smaller than the maximum velocity of the leader, then the system (1) will converge to the equilibrium state, at which $v_{l} = v_{t}$ and $(p_{l} - p_{t}) = τ (p_{l} - p_{t}) / ∥ p_{l} - p_{t} ∥$ .

Proof

Firstly, we consider the vector field $f_{1 l}^{t} = K_{l} n_{l}^{t}$ in equation (27), where $K_{l} = (κ_{l}^{t 2} / d_{l}^{t} - κ_{l}^{t 2} / r^{τ}) (d_{l}^{t})^{2} - κ_{l}^{t 1} (d_{l}^{t} - r^{τ}) / (r^{t} - r^{τ})$ . Let $P_{l} = K_{l} (x_{l} - x_{t}) / ∥ p_{l} - p_{t} ∥$ , $Q_{l} = K_{l} (y_{l} - y_{t}) / ∥ p_{l} - p_{t} ∥$ , and $Q_{l} = 0$ . Then, we have

rot (f_{1 l}^{t}) = {(\frac{\partial Z_{l}}{\partial y_{l}} - \frac{\partial Q_{l}}{\partial z_{l}}, \frac{\partial P_{l}}{\partial z_{l}} - \frac{\partial Z_{l}}{\partial x_{l}}, \frac{\partial Q_{l}}{\partial x_{l}} - \frac{\partial P_{l}}{\partial y_{l}})}^{T} = 0

Equation (28) shows that the vector field $f_{1 l}^{t}$ is not rotational.

Consider the scale function

V_{l}^{t} = \frac{1}{2} (κ_{l}^{t 2} (\frac{1}{d_{l}^{t}} - \frac{1}{r^{τ}})^{2} + \frac{κ_{l}^{t 1} {(d_{l}^{t} - r^{τ})}^{2}}{(r^{t} - r^{τ})})

Taking the negative gradient of $V_{l}^{t}$ , we obtain

\begin{matrix} - \nabla V_{l}^{t} = - \nabla (\frac{κ_{l}^{t 2}}{2} {(\frac{1}{d_{l}^{t}} - \frac{1}{r^{τ}})}^{2} + \frac{κ_{l}^{t 1} {(d_{l}^{t} - r^{τ})}^{2}}{2 (r^{t} - r^{τ})}) \\ = - (\frac{κ_{l}^{t 2}}{d_{l}^{t}} - \frac{κ_{l}^{t 2}}{r^{τ}}) \nabla (\frac{1}{d_{l}^{t}} - \frac{1}{r^{τ}}) \\ - \frac{κ_{l}^{t 1} (d_{l}^{t} - r^{τ})}{(r^{t} - r^{τ})} \nabla (d_{l}^{t} - r^{τ}) \\ = (\frac{κ_{l}^{t 2}}{d_{l}^{t}} - \frac{κ_{l}^{t 2}}{r^{τ}} \frac{1}{{(d_{l}^{t})}^{2}} \nabla d_{l}^{t} - \frac{κ_{l}^{t 1} (d_{l}^{t} - r^{τ})}{(r^{t} - r^{τ})}) \nabla d_{l}^{t} \\ = ((\frac{κ_{l}^{t 2}}{d_{l}^{t}} - \frac{κ_{l}^{t 2}}{r^{τ}}) \frac{1}{{(d_{l}^{t})}^{2}} - \frac{κ_{l}^{t 1} (d_{l}^{t} - r^{τ})}{(r^{t} - r^{τ})}) \nabla d_{l}^{t} \\ = ((\frac{κ_{l}^{t 2}}{d_{l}^{t}} - \frac{κ_{l}^{t 2}}{r^{τ}}) \frac{1}{{(d_{l}^{t})}^{2}} - \frac{κ_{l}^{t 1} (d_{l}^{t} - r^{τ})}{(r^{t} - r^{τ})}) \frac{(p_{l} - p_{t})}{∥ p_{l} - p_{t} ∥} \\ = f_{1 l}^{t} \end{matrix}

Hence, equations (28) and (30) show that the vector field $f_{1 l}^{t}$ is also a potential field, and its potential function is $V_{l}^{t}$ .

In order to analyze the stability of the leader at the equilibrium position, at which $∥ p_{l} - p_{t} ∥ = r^{r}$ and $v_{l} - v_{t} = 0$ , let ${\tilde{x}}_{1} = p_{l} - p_{t}$ and ${\tilde{x}}_{2} = v_{l} - v_{t}$ . Then, the error dynamic of the system is described as

{\dot{\tilde{x}}}_{1} = {\tilde{x}}_{2}

{\dot{\tilde{x}}}_{2} = {\dot{v}}_{l} - {\dot{v}}_{t} = u_{l}^{t} - {\dot{v}}_{t}

From equations (26) and (31), we have

{\dot{\tilde{x}}}_{1} = {\tilde{x}}_{2}

{\dot{\tilde{x}}}_{2} = \nabla V_{l}^{t} - κ_{l}^{t v} {\tilde{x}}_{2}

To analyze the stability of the system (33), we choose the following Lyapunov function candidate

V_{τ} = V_{l}^{t} + \frac{1}{2} {\tilde{x}}_{2}^{T} {\tilde{x}}_{2}

Taking the time derivative of equation (35) along the trajectory of the system (33), we obtain

{\dot{V}}_{τ} = \nabla V_{l}^{t} {\dot{\tilde{x}}}_{1} + {\tilde{x}}_{2}^{T} {\dot{\tilde{x}}}_{2} = κ_{l}^{t v} {\tilde{x}}_{2}^{T} {\tilde{x}}_{2} \leq 0

According to LaSalle’s theorem, ${\tilde{x}}_{2} \to 0$ .⁵⁰ It can easily be shown that ${\tilde{x}}_{2}$ is uniformly continuous. Hence, according to Barbalat’s lemma, ${\dot{\tilde{x}}}_{2} \to 0$ .⁵² This implies from equation (33) that $\nabla V_{l}^{t} \to 0$ or $f_{l}^{t} \to 0$ . Hence, $d_{l}^{t} \to r^{τ}$ due to the description of the potential force function in equation (27). So, the system (33) is stable at the equilibrium position when using the control law (26). In other words, using the controller (26), the leader will converge to the equilibrium position, at which the distance between the leader and the target is equal to the radius of the desired circular formation. □

Remark 5

The formation of the swarm changes with respect to the relative position between the leader and the target. Initially, a robot will be chosen as a leader to lead its formation toward the target if it is closest to the target. During the motion of the swarm, if the current leader faces any risk (for instance, it is broken from the formation or hindered by the environment), then a new leader is nominated. Algorithm 2 guarantees that this new leader will reorganize the formation and continue to lead the swarm to track the target.

Algorithm 2

Leader selection.

Remark 6

Obstacles in the environment can be sensed by several methods. Onboard sensors of each agent can detect them. In addition, hybrid approaches can employ a group of aerial drones to capture the images of obstacles and agents and transfer data to the agents.^19,20

Remark 7

The paper⁵³ addressed the swarm tracking problem to capture a moving target in a specific formation using artificial potentials and sliding mode control. The dynamics used in this work are fully actuated. The artificial potentials are used for the formation and tracking control goals. Sliding techniques are used to deal with uncertainty, which exhibits robustness of the proposed control method. The control framework by Yao et al.⁵³ was then applied for agents with nonholonomic dynamics by Gazi et al.⁵⁴ Our control strategy shares the same principle as in the studies of Yao et al.⁵³ and Gazi et al.⁵⁴ where artificial potentials are employed for formation and target tracking control. On the one hand, the work of Yao et al.⁵³ and Gazi et al.⁵⁴ considers robustness issues, which we do not address in this article. On the other hand, our article deals with collision and obstacle avoidance, which are not included in the article.^53,54

Case study

The proposed algorithms as discussed in the previous section can allow the robots to follow predefined formations such as V-shape, circular, or line shape. Due to their similarity, we just present two cases of V-shape and circular shape. Let $p_{l} = (x_{l}, y_{l})^{T}$ and $p_{t} = (x_{t}, y_{t})^{T}$ be the positions of the leader and the target, respectively. The relative position vector between the leader and the target is $(p_{l} - p_{t}) = (x_{l} - x_{t}, y_{l} - y_{t})^{T}$ , and the distance between them is determined as $d_{l}^{t} = \sqrt{{(x_{l} - x_{t})}^{2} + {(y_{l} - y_{t})}^{2}}$ .

V-shape formation

Firstly, in order to build the V-shape desired formation, we design the right side of this V-shape based on the desired formation angle $ϕ_{d}$ and the relative position between the leader and the target. As presented in Figure 5, the coordinates of the base node $q_{μ}$ on the coordinate system $x^{'} y^{'}$ ( ${q^{'}}_{μ} = (x_{μ^{'}}, y_{μ^{'}})^{T}$ ) are determined as follows

(\begin{matrix} {x^{'}}_{μ} \\ {y^{'}}_{μ} \end{matrix}) = ∥ q_{μ} - p_{l} ∥ (\begin{matrix} cos δ_{d} \\ sin δ_{d} \end{matrix})

where the angle $δ_{d} = ∠ (q_{μ} - p_{l}), (p_{t} - p_{l})$ is equal to $ϕ_{d} / 2$ and $ϕ_{d} > 0$ is the desired formation angle (see Figure 5). The base node $q_{μ}$ is employed to generate virtual nodes on the right side of the V-shape. It lies on the line which deviates with an angle of $δ_{d}$ from the line connecting the leader and the target. The distance between the base node $q_{μ}$ and the leader is equal to the distance of consecutive virtual nodes on the right wing of the V-shape. By rotating and translating equation (37) according to coordinate systems $x ” y ”$ and $x y$ ,⁵⁵ we obtain the position of the desired node $q_{μ}$ on the coordinate system $x y$ as follows

q_{μ} = p_{l} + R {q^{'}}_{μ}

Figure 5.

The description of the method to build the V-shape desired formation.

From base node $q_{μ}$ and the position of the leader, we determine a unit vector along the line connecting from $q_{μ}$ to $p_{l}$ as $n_{μ l} = (p_{l} - q_{μ}) / ∥ p_{l} - q_{μ} ∥$ . The rotational matrix R, which depends on the rotational angle θ, is determined as

R = {\begin{array}{l} (\begin{matrix} cos θ & - sin θ \\ sin θ & cos θ \end{matrix}), & if θ rotates clockwise \\ (\begin{matrix} cos θ & sin θ \\ - sin θ & cos θ \end{matrix}), & otherwise \end{array}

Now, a virtual node j ( $d_{j}^{l} = ∥ p_{l} - q_{j} ∥ = j d$ ; $q_{j} = (x_{j}, y_{j})^{T}$ ; $v_{j} = (v_{j x}, v_{j y})^{T}$ ; $j = 1, 2, ..., N^{⋆}$ ; $N^{⋆} \in R$ ) is determined by the unit vector $n_{μ l}$ as

(q_{j} - p_{l}) = j d n_{μ l}

Here, d is the distance between any two consecutive virtual nodes. Note that $∥ p_{l} - q_{μ} ∥ = d$ . Substituting $n_{μ l} = (p_{l} - q_{μ}) / ∥ p_{l} - q_{μ} ∥$ into equation (40), we obtain

q_{j} = (1 + j) p_{l} - j q_{μ}

Equation (41) can be rewritten as

(\begin{matrix} x_{j} \\ y_{j} \end{matrix}) = (\begin{matrix} (1 + j) x_{l} \\ (1 + j) y_{l} \end{matrix}) - (\begin{matrix} j x_{μ} \\ j y_{μ} \end{matrix})

Equation (42) shows that when j changes from $j = 1$ to $j = N^{⋆}$ , we obtain the formation of the $N^{⋆}$ virtual nodes. These nodes lie on a line connecting $p_{l}$ and $q_{μ}$ and are equally spaced (the right side of the desired V-shape formation; see Figure 5).

Similarly, the virtual node j on the left side of the V-shape is designed as

(q_{j} - q_{l}) = j d n_{l η}

where $n_{l η} = (q_{η} - p_{l}) / ∥ q_{η} - p_{l} ∥$ is a unit vector. Hence,

q_{j} = (1 - j) p_{l} + j q_{η}

where $q_{η}$ is the position of the base node on the line which deviates from the line through the leader and the target with an angle of $(π - δ_{d})$ (see Figure 5). The base node $q_{η}$ of the left side is similar to the base node $q_{μ}$ of the right side of the V-shape. The distance between the base node $q_{η}$ and the leader is equal to the distance of consecutive virtual nodes on the left wing of the V-shape. Similar to equation (38), this base node is determined as

q_{η} = p_{l} + R {q^{'}}_{η}

Using equation (45), we obtain the formation of the virtual node j. They lie on the line through $p_{l}$ and $q_{η}$ and are equally spaced (the left side of the V-shape; see Figure 5). Finally, the law to generate the desired V-shape formation of the virtual nodes j $(j = 1, 2, ..., N)$ is proposed as

q_{j} = {\begin{array}{l} (1 + ξ_{1}) p_{l} - ξ_{1} q_{μ}, & if j \leq N / 2 + 1 \\ (1 - ξ_{2}) p_{l} + ξ_{2} q_{μ}, & otherwise \end{array}

where $ξ_{1} = j - 1$ and $ξ_{2} = j - 1 - floor (N / 2)$ are positive factors. Using equation (46), the virtual nodes j ( $j = 1, 2, ..., N$ ) will be evenly distributed to both sides of the leader. Hence, we obtain a V-shape formation due to these desired virtual nodes and a constant formation angle $ϕ_{d} = 2 δ_{d}$ , as shown in Figure 6(a). In some cases, such as under the influence of an environmental factor (noises, wind, obstacle avoidance, etc.), the formation angle needs to be changed to adapt to the effect of this environment. Thus, the formation angle is chosen as

ϕ (t) = ϕ_{d} + ε_{3} ϕ (t)

Figure 6.

The description of the distributed virtual node j in the desired V-shape formation (a) and in the desired circular shape formation (b).

where $ε_{3}$ is a positive constant, and $ϕ (t)$ is used as a sensing function that decides the formation angle $ϕ (t)$ . However, this formation angle $ϕ (t)$ must guarantee that there are no collisions among the members in the formation. In other words, it depends on the repulsive radius of each robot. Hence, the smallest formation angle is computed as $ϕ_{dmin} = arccos (1 - r_{r}^{2} / 2 d^{2})$ .

Circular formation

As presented above, the circular formation is used to encircle the moving target when the distance between the leader and the target is shorter than the target approaching radius $d_{l}^{t} = ∥ p_{l} - p_{t} ∥ \leq r^{t}$ . Hence, this desired formation is designed based on the relative position between the target and the leader, as shown in Figure 6.

The position of the virtual nodes j ( $j = 1, 2, ..., N$ ) on the circle, whose central point is at the target’s position $p_{t}$ and whose radius is $d_{l}^{t} = ∥ p_{l} - p_{t} ∥$ , is computed as

q_{j} = p_{l} + R {q^{'}}_{j}, j = 1, 2, ..., N

The position of the virtual node j on the coordinate system $x^{'} y^{'}$ ( ${q^{'}}_{j} = ({x^{'}}_{j}, {y^{'}}_{j})^{T}$ ) is computed as

(\begin{matrix} {x^{'}}_{j} \\ {y^{'}}_{j} \end{matrix}) = d_{l}^{t} (\begin{matrix} cos (2 j π / N) \\ sin (2 j π / N) \end{matrix}), j = 1, 2, ..., N

Let the virtual node owned by the leader be the first position in the circular desired formation. Substituting equation (49) into equation (48), we have the circular formation of the virtual node j as follows

(\begin{matrix} x_{j} \\ y_{j} \end{matrix}) = (\begin{matrix} x_{t} \\ y_{t} \end{matrix}) + R d_{l}^{t} (\begin{matrix} cos (2 ζ π / N) \\ sin (2 ζ π / N) \end{matrix}), j = 1, 2, ..., N; ζ = j - 1

Equation (50) shows that the distributed virtual nodes j ( $j = 1, 2, ..., N$ ) on the circular desired formation are equidistant, and the distance from them to the target is $d_{l}^{t} = ∥ p_{l} - p_{t} ∥$ (see Figure 6(b)). The desired radius is chosen such as the distances among agents guarantee collision avoidance when the circle formation is achieved.

Simulation results

In this section, we use the V-shape and circular desired formations, which are built in section Case study, to illustrate the proposed control algorithms. We assume that the initial velocities of the robots and the target are zero. The initial positions of the robots are random. Each robot can sense the position of other robots within its sensing range as well as the positions of the target and obstacles. The target moves in a sine wave trajectory, which is defined as $p_{t} = (0.9 t + 640, 160 sin (0.01 t) + {250)}^{T}$ . The general parameters of the simulations are listed in Table 2.

Table 2.

Parameter values.

Parameter	Definition	Value
N	Number of robots	9
$ϕ_{d}$	Desired formation angle	$2 π / 3$ rad
$r^{τ}$	Desired radius of circular formation	60 m
$r^{t}$	Target approach radius	100 m
$r_{r}$	Collision radius around each robot	45 m
d	Desired distance between robots in the V-shape	60 m
λ, $λ^{⋆}$ , $λ_{α}$	Positive constants	15,10, 5
$ε_{1}$ , $ε_{2}$ , $ε_{3}$	Positive constants	1, 0.5, 0.7
$κ_{i}^{c 1}$ , $κ_{i}^{c 2}$	Constants for fast repulsion	80, 12
$κ_{i}^{o 1}$ , $κ_{i}^{o 2}$	Constants for fast obstacle avoidance	90, 15
$κ_{l}^{t 1 d}$ , $κ_{l}^{t 2}$ , $κ_{l}^{t 3}$	Constants for approaching to target	1, 0.6, 4
$κ_{i}^{p 1 d}$ , $κ_{i}^{p 2}$ , $κ_{i}^{p 3}$	Positive constants	3, 4, 9
$κ_{i}^{f}$ , $κ_{l}^{t v}$ , $κ_{i k}^{c}$	Damping constants	1, 1.2, 1.5

Achievement of desired formation

For this simulation, the formation angle is selected as $ϕ (t) = 2 π / 3$ . The proposed algorithms were used to generate the desired formations (V-shape and circular shape) and control the robots to move toward the virtual nodes in the desired formation (algorithm 1).

The results in Figure 7 show that the desired formations were easily created. Robots, which have random initial positions, quickly achieved the desired positions in these desired formations while tracking a moving target without collisions. The position permutations among the members in the formation appeared, but they did not influence the structure of the formation when tracking the target. As shown in Figure 7, at the initial time, one robot was chosen as the leader to drive its formation toward the target in a V-shape formation. At time t = 70 s, the V-shape formation was constructed, and it was kept until the square robot detected the obstacle $O_{1}$ . At time t = 160 s, while avoiding the obstacle $O_{1}$ , the virtual node, which was owned by the square robot, became a free node. Then, this virtual node attracted the triangular robot to become the active node at time t = 200 s. After escaping the obstacle, the square robot quickly approached the remaining free node of the desired formation, as shown in Figure 7. Similarly, the rhombus robot was permuted with other robots in the formation while avoiding the obstacle $O_{2}$ . At time t = 250 s, the V-shape formation changed to the circular formation to encircle the target. In this situation, the member robots became the free robots, and then they approached the desired circular formation. Figure 8 shows that this circular formation was kept around the target at the desired radius $r^{τ}$ at time t = 320 s. In other words, the leader’s position is stable at the equilibrium point, at which $∥ p_{l} - p_{t} ∥ = r^{τ}$ .

Figure 7.

The evolution of a swarm following the desired formations under the influence of the dynamic environment while tracking a moving target.

Figure 8.

The distance between the leader and the target in case the leader is not hindered while tracking a moving target.

Next we consider the connection of a swarm when the leader was trapped in the complex obstacle (e.g. U-shape obstacle; see Figure 9). In this situation, the actual leader had to transfer its leadership to other members in the swarm, and managed to escape this obstacle. Figure 10 shows that, at time t = 0 s, the square robot was chosen as the leader, and its leadership was kept until it was trapped in the U-shape obstacle at time t = 200 s. While avoiding obstacle, the square leader transferred its leadership to the triangular robot, which was not faced with any obstacles and closest to the target. Then, this square leader became a free robot. It automatically found a way (lilac way) to escape this U-shape obstacle in order to continue following its formation.

Figure 9.

Path planning for a swarm following the desired formations while tracking a moving target with the leader permutation.

Figure 10.

Distance between the leaders while tracking a moving target in case the leader is permuted.

After receiving the leadership, the triangular robot reorganized a new formation and continued to lead this formation to track the target. The distance between the new leader and the target shrunk until it achieved the active radius of the circular desired formation $∥ p_{l} - p_{t} ∥ = r^{τ}$ . Then, this distance was maintained to encircle the moving target (see Figure 10). Moreover, Figure 9 shows that the position permutation between the square leader and the triangular leader did not influence the structure of the formation.

The robustness of the swarm in noisy environment

In this subsection, we examine the robustness of the formation under the influences of noise and the change of the formation angle. Distances and velocities of agents are affected by noises, whose profiles are the Gaussian function with zero mean and variance of 1 (see Figure 11). The formation angle $ϕ (t)$ is used for simulations as $ϕ (t) = 2 π / 3 + 1.6 sin (0.2 t)$ (see Figure 12).

Figure 11.

Measurement noise.

Figure 12.

Formation angle $ϕ (t) / 2$ while tracking a moving target.

Figure 14 shows that robot i was always close to active node j in the desired formation, and its formation was maintained following the desired formations (V-shape and circular formation) under the influence of the noisy environment and the changes of the formation angle $ϕ (t) / 2$ . The position error between each robot i and active node j, at which this robot i was occupying, is small (see Figures 12 and 13). Figure 14 also reveals that from the random initial positions, the free robots quickly found their desired position in the desired V-shape formation. Then, they tracked a moving target in a stable V-shape formation. At time t = 70 s, under the influence of the sudden change of the formation angle from $ϕ = 2 π / 3$ to $ϕ = (π - 0.6)$ , the formation was broken, but it was quickly redesigned to continue to track the moving target. In contrast, when the formation angle $ϕ (t)$ changed slowly, the formation of robots was always maintained following the desired V-shape formation with the small position errors (see Figures 13 and 14). Moreover, the simulation results show that the noise had influences on the position errors of the robot formation, but they only caused small formation changes, as shown in Figure 13.

Figure 13.

Position errors $∥ p_{i} - q_{j} ∥$ between the positions of the agents and their desired positions under the effect of the noise.

Figure 14.

The influences of noises and the different formation angles on the swarm’s trajectory while tracking a moving target.

Conclusion

In this article, a new method for decentralized formation control of autonomous robots has been presented, in which the swarm tracks a moving target in a dynamic and noisy environment. The robot system can form predefined formations such as V-shape or circular shape while avoiding collisions among agents of the swarm. The new mechanism which combines the rotational and the repulsive forces can drive robots to quickly escape complex obstacles such as those with concave shapes. The theoretical analysis of the proposed algorithm is given. In our future research, the proposed approach would serve as a framework for addressing the formation control of multiagent systems in two-dimensional space such as unmanned aerial vehicles and underwater robots.

Footnotes

Authors’ note

The views, opinions, findings, and conclusions reflected in this publication are solely those of the authors and do not represent the official policy or position of the USDOT/OSTR, or any State or other entity.

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 partially supported by the National Aeronautics and Space Administration under grant number NNX15AI02H issued through the NVSGC-RI program under sub-award no 19-21, the RID program under sub-award no 19-29, and the NVSGC-CD program under sub-award no 18-54. This work was also partially supported by the US Department of Transportation, Office of the Assistant Secretary for Research and Technology (USDOT/OST-R) under grant number 69A3551747126 through INSPIRE University Transportation Center () at Missouri University of Science and Technology.

ORCID iD

Thang Nguyen

References

Yang

Zhang

. Geometric formation control for autonomous underwater vehicles. In: 2010 IEEE International Conference on Robotics and Automation, Anchorage, AK, USA, 3–7 May 2010, pp. 4288–4293. IEEE.

Zhang

Yan

Xie

. Consensus-based leader-following formation control for a group of semi-biomimetic robotic fishes. Int J Adv Robot Syst 2017; 14(4): 1729881417720784.

Pham

Feil-Seifer

. A distributed control framework for a team of unmanned aerial vehicles for dynamic wildfire tracking. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada, 24–28 September 2017, pp. 6648–6653. IEEE.

Palacios

Quesada

ESE

Sanahuja

. Test bed for applications of heterogeneous unmanned vehicles. Int J Adv Robot Syst 2017; 14(1): 1729881416687111.

Olfati-Saber

. Flocking for multi-agent dynamic systems: algorithms and theory. IEEE Trans Automat Contr 2006; 51(3): 401–420.

Jadbabaie

Lin

Morse

. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans Automat Contr 2003; 48(6): 988–1001.

Lim

Sheng

. Multirobot cooperative learning for predator avoidance. IEEE Trans Contr Syst Trans 2015; 23(1): 52–63.

Sheng

. Flocking control of a mobile sensor network to track and observe a moving target. In: 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan, 12–17 May 2009, pp. 3129–3134. IEEE.

Olfati-Saber

. Distributed tracking for mobile sensor networks with information-driven mobility. In: 2007 American Control Conference, New York, NY, USA, 9–13 July 2007, pp. 4606–4612. IEEE.

10.

Sheng

. Distributed sensor fusion for scalar field mapping using mobile sensor networks. IEEE Trans Cybern 2013; 43(2): 766–778.

11.

Ogren

Fiorelli

Leonard

. Cooperative control of mobile sensor networks: adaptive gradient climbing in a distributed environment. IEEE Trans Automat Contr 2004; 49(8): 1292–1302.

12.

Dai

Choi

Lee

. Adaptive formation control and collision avoidance using a priority strategy for nonholonomic mobile robots. Int J Adv Robot Syst 2013; 10(2): 140.

13.

Nguyen

. Formation control and obstacle avoidance of multiple rectangular agents with limited communication ranges. IEEE Trans Contr Network Syst 2017; 4(4): 680–691.

14.

Nguyen

Han

. Distributed flocking control of mobile robots by bounded feedback. In: 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 27–30 September 2016, pp. 563–568. IEEE.

15.

Nguyen

Azimi

. Bounded distributed flocking control of nonholonomic mobile robots, Swarm Intelligence - Volume 1: Principles, current algorithms and methods, Chap. 11, pp. 297–321, September 2018. IET.

16.

Nguyen

. Distributed formation control of nonholonomic mobile robots by bounded feedback in the presence of obstacles. 2017 IEEE International Conference on Real-time Computing and Robotics (RCAR), Okinawa, Japan, 14–18 July 2017, pp. 206–211. IEEE.

17.

Han

Dinh

. Flocking of mobile robots by bounded feedback. In: 2016 IEEE International Conference on Automation Science and Engineering (CASE), Fort Worth, TX, USA, 21–25 August 2016, pp. 689–694. IEEE.

18.

Santiaguillo-Salinas

Aranda-Bricaire

. Containment problem with time-varying formation and collision avoidance for multiagent systems. Int J Adv Robot Syst 2017; 14(3): 1729881417703929.

19.

Saska

Vonásek

Krajník

. Coordination and navigation of heterogeneous MAV-UGV formations localized by a ‘hawk-eye’-like approach under a model predictive control scheme. Int J Robot Res 2014; 33(10): 1393–1412.

20.

Saska

Krajník

Vonásek

. Fault-tolerant formation driving mechanism designed for heterogeneous MAV-UGVs groups. J Intell Robot Syst 2014; 73(1): 603–622.

21.

Lau

. Practical formation control of multiple unicycle-type mobile robots with limited sensing ranges. J Intell Robot Syst 2011; 64(2): 245–275.

22.

Cui

. New potential functions for mobile robot path planning. IEEE Trans Robotic Autom 2000; 16(5): 615–620.

23.

Sheng

. Dynamic target tracking and observing in a mobile sensor network. Robot Auton Syst 2012; 60(7): 996–1009.

24.

Dang

Horn

. Intelligent swarm-finding in formation control of multi-robots to track a moving target. Int J Comput Elect Autom Contr Inform Eng April 2014; 8(4): 561–567. http://waset.org/Publications?p=88.

25.

Dang

Horn

. Distributed formation control for autonomous robots following desired shapes in noisy environment. In: 2016 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), Baden-Baden, Germany, 19–21 September 2016, pp. 285–290. IEEE.

26.

Dang

Horn

. Formation control of autonomous robots to track a moving target in an unknown environment. In: 2014 IEEE International Conference on Robotics and Biomimetics (ROBIO 2014), Bali, Indonesia, 5–10 December 2014, pp. 896–901. IEEE.

27.

Dang

Horn

. Path planning for a formation of autonomous robots in an unknown environment using artificial force fields. In: 2014 18th International Conference on System Theory, Control and Computing (ICSTCC), Sinaia, Romania, 17–19 October 2014, pp. 773–778. IEEE.

28.

Dang

Horn

. Formation control of autonomous robots following desired formation during tracking a moving target. In: 2015 IEEE 2nd International Conference on Cybernetics (CYBCONF), Gdynia, Poland, 24–26 June 2015, pp. 160–165. IEEE.

29.

Liu

Passino

. Stable social foraging swarms in a noisy environment. IEEE Trans Automat Contr 2004; 49(1): 30–44.

30.

Gazi

Passino

. Stability analysis of swarms. IEEE Trans Automat Contr 2003; 48(4): 692–697.

31.

Hou

Cheah

Slotine

JJE

. Dynamic region following formation control for a swarm of robots. In: 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan, 12–17 May 2009, pp. 1929–1934. IEEE.

32.

Cheah

Hou

Slotine

JJE

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

33.

Eren

. Formation shape control based on bearing rigidity. Int J Contr 2012; 85(9): 1361–1379.

34.

Fu-guang

Peng

Xin-qian

. AUV local path planning based on virtual potential field. In: 2005 IEEE International Conference Mechatronics and Automation, Niagara Falls, Ontario, Canada, 29 July–1 August 2005, pp. 1711–1716, Vol. 4. IEEE.

35.

Das

Fierro

Kumar

. A vision-based formation control framework. IEEE Trnas Robot Autom 2002; 18(5): 813–825.

36.

Spletzer

Fierro

. Optimal positioning strategies for shape changes in robot teams. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain, 18–22 April 2005, pp. 742–747. IEEE.

37.

Gould

Heppner

. The V-formation of Canada geese. The Auk July 1974; 91(3): 494–506. http://www.jstor.org/stable/4084469.

38.

Badgerow

. An analysis of function in the formation flight of Canada geese. The Auk October 1988; 105(4): 749–755. http://www.jstor.org/stable/4087389.

39.

Wang

Xie

Cao

. Forming circle formations of anonymous mobile agents with order preservation. IEEE Trans Autom Contr 2013; 58(12): 3248–3254.

40.

Lee

Yoon

Chong

. A mobile sensor network forming concentric circles through local interaction and consensus building. J Robot Mech 2009; 21(4): 469–477.

41.

Okamoto

Akella

. Novel potential-function-based control scheme for non-holonomic multi-agent systems to prevent the local minimum problem. Int J Syst Sci 2015; 46(12): 2150–2164.

42.

Okamoto

Akella

. Avoiding the local-minimum problem in multi-agent systems with limited sensing and communication. Int J Syst Sci 2016; 47(8): 1943–1952.

43.

Song

Liu

Feng

. Coverage control for mobile sensor networks with input saturation. Unmanned Syst 2016; 04(01): 15–21.

44.

. Formation control of multiple elliptical agents with limited sensing ranges. Automatica 2012; 48(7): 1330–1338.

45.

Shi

Teo

. Cooperative enclosing control for multiple moving targets by a group of agents. Int J Contr 2015; 88(1): 80–89.

46.

Nguyen

Teague

. Collaborative and compressed mobile sensing for data collection in distributed robotic networks. IEEE Transactions on Control of Network Systems 2018; 5(4): 1729–1740.

47.

Briñon-Arranz

, Seuret

Canudas-de-Wit

. Cooperative control design for time-varying formations of multi-agent systems. IEEE Trans Autom Contr 2014; 59(8): 2283–2288.

48.

Liu

. Cooperative control for moving-target circular formation of nonholonomic vehicles. IEEE Trans Autom Contr 2017; 62(7): 3448–3454.

49.

Freeman

Kokotovic

. Robust nonlinear control design: state-space and Lyapunov techniques. Berlin: Springer Science & Business Media, 2008.

50.

Khalil

. Nonlinear systems, 3rd ed. Upper Saddle River: Prentice Hall, 2002, p. 9.

51.

Olfati-Saber

Flocking for multi-agent dynamic systems: algorithms and theory. Technical Report Tech. Rep. 2004-005, California Inst. Technol., Pasadena, CA, 2004.

52.

Slotine

JJE

. Applied nonlinear control. Vol. 199. Englewood Cliffs: Prentice hall, 1991.

53.

Yao

Ordóñe

Gaz

. Swarm tracking using artificial potentials and sliding mode control. J Dynam Syst Meas Contr 2007; 129(5): 749–754.

54.

Gazi

Fidan

Ordóñez

. A target tracking approach for nonholonomic agents based on artificial potentials and sliding mode control. J Dynam Syst Meas Contr 2012; 134(6): 061004–13.

55.

Lial

Hungerford

. Mathematics with applications. Boston: Addison-Wesley, 2002.

Formation control for autonomous robots with collision and obstacle avoidance using a rotational and repulsive force–based approach

Abstract

Keywords

Introduction

Problem formulation

Definition 1

Definition 2

Definition 3

Definition 4

Definition 5

Definition 6

Definition 7

Definition 8

Control algorithms

Control architecture

Formation connection control algorithm

Theorem 1

Proof

Remark 1

Remark 2

Collision avoidance control algorithm

Obstacle avoidance control algorithm

Theorem 2

Remark 3

Remark 4

Target tracking control algorithm

Theorem 3

Proof

Remark 5

Remark 6

Remark 7

Case study

V-shape formation

Circular formation

Simulation results

Achievement of desired formation

The robustness of the swarm in noisy environment

Conclusion

Footnotes

Authors’ note

Declaration of conflicting interests

Funding

ORCID iD

References