# Finite-Time Formation Control without Collisions for Multiagent Systems with Communication Graphs Composed of Cyclic Paths

Authors: J. F. Flores-Resendiz; E. Aranda-Bricaire; J. González-Sierra; J. Santiaguillo-Salinas
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

This paper addresses the formation control problem without collisions for multiagent systems. A general solution is proposed for the case of any number of agents moving on a plane subject to communication graph composed of cyclic paths. The control law is designed attending separately the convergence to the desired formation and the noncollision problems. First, a normalized version of the directed cyclic pursuit algorithm is proposed. After this, the algorithm is generalized to a more general class of topologies, including all the balanced formation graphs. Once the finite-time convergence problem is solved we focus on the noncollision complementary requirement adding a repulsive vector field to the previous control law. The repulsive vector fields display an unstable focus structure suitably scaled and centered at the position of the rest of agents in a certain radius. The proposed control law ensures that the agents reach the desired geometric pattern in finite time and that they stay at a distance greater than or equal to some prescribed lower bound for all times. Moreover, the closed-loop system does not exhibit undesired equilibria. Numerical simulations and real-time experiments illustrate the good performance of the proposed solution.


---

## Body

## 1. Introduction

During the last years, formation control in multiagent systems has received much attention due to the wide range of applications in which they can be used as exploration, rescue tasks, toxic residues cleaning, and so forth, [1, 2]. A very important issue in formation control is the collision avoidance problem, with either other agents or obstacles [3]. If the formation control algorithms are designed in a totally centralized way, that is, with information exchange among all the agents, the computational load can increase seriously. On the other hand, an additional constraint arises if the communication among agents is restricted. Then, in most cases it is assumed that every agent in the group knows for all time the state or simply the position of a specific subset of robots and, eventually, can sense the position of any robot within a certain radius, [4]. Taking into account this difficulty several types of communications, as cyclic or balanced formations graphs, have been studied, [5–8].Initially, the proposed solutions to the noncollision problem were designed as the sum of attractive and repulsive vector fields, in most cases obtained as the negative gradient of potential functions. Attractive potential functions are centred, for each agent, at its desired position, while the repulsive potential functions are centred at the positions of the rest of agents or even at obstacles’ positions, [9, 10]. Under this approach, one main drawback is the fact that the combination of gradients of attractive and repulsive potential functions could result in the appearance of undesired equilibrium points, leading the agents to get stuck at an undesired formation. Attending this problem, a solution has been proposed with the requirement of having totally centralized schemes [11]. Moreover, the repulsive vector fields are designed in such a way that they appear smoothly as the distance between any pair of agents becomes smaller and tends to infinity when this distance tends to zero. Then, although the collision avoidance is ensured, the position among agents can be arbitrarily small, which could imply a collision in real applications where physical dimensions cannot be ignored.Related works can be found in [12] where authors consider formation control problems under limited and intermittent sensing. Based on a navigation function framework, a decentralized hybrid controller is developed to ensure network connectivity and collision avoidance while controlling the formation. In [13] the differential game approach is used for a group of agents to reach desired target positions while avoiding collisions among them. A methodical approach to the problem of collision avoidance of mobile robots taking advantages of multiagent systems has been presented in [14]. In order to achieve the trajectory, a control strategy based on a pure pursuit algorithm was implemented in the robots. The collision avoidance in the leader-follower multiagent systems was studied in [15]. The graph theory is used to model the communication topology between agents. To avoid collisions between neighboring agents, a fuzzy separation controller is proposed.In a recent work, a new strategy for designing the repulsive vector fields has been proposed [16]. This approach differs from the classical one on the use of scaled unstable focus structures centred at the position of others agents. These functions cannot be obtained as the gradient of a scalar function of the distance between agents. Although this technique can also lead to undesired equilibria, these can be removed. The key point is to use an unstable focus scaled by a function depending on the distance among agents. This scaling function vanishes when the agents are far enough and tend to infinity as distance tends to zero. The analysis in [16] has been presented for the case of two agents only, while in [5] an extension to an arbitrary number of agents has been presented for the case of a directed cyclic pursuit communication graph.In this paper we study the noncollision problem in formation control using discontinuous vector fields for an arbitrary number of agents. In one hand we undertake the design of attractive vector fields based on the well known cyclic pursuit algorithm but, unlike the results reported in the literature [7], we focus our analysis on normalized vector fields. That is, regarding only the attractive part, the agents move at constant known velocity and they reach the desired formation in finite time. Moreover, the case of more general communication graphs is analysed as the combination of single cyclic pursuit schemes. On the other hand, the repulsive vector fields have the unstable focus structure scaled by a suitable constant. As mentioned before, the general problem of an arbitrary number of robots is treated and the designed controllers are proven to be effective from the case where no collision risk exists to the one when a robot is rounded by a set of robots and there could be collision with any of them. It will be shown in this paper that this is the most complex situation that can occur.This paper is organized as follows. We start in Section2 stating some useful definitions and technical preliminaries. After this, in Section 3 we present the problem statement along with a couple of standing assumptions. The main contribution is given in Section 4, initially regarding the finite time convergence problem. Then, we take into account all the possible scenarios of collisions, starting with the simplest case of two robots in danger of collision. Based on this simple case we extend the study to risk of multiple collisions. Numerical simulations and real-time experiments are presented in Sections 5 and 6, respectively. Finally, in Section 7, we list the conclusions and outlooks of this research.


## 2. Preliminaries

As we mentioned before, in this section we state some useful definitions [17, 18] and a technical lemma that we will use in the rest of the paper.Definition 1 (formation graph).
A formation graphG
=
{
V
,
E
,
C
} that describes the communication among the agents consists of a set of vertices V
=
{
R
1
,
…
,
R
n
} corresponding to each of the agents in the group and a set of edges E
=
{
(
R
j
R
i
)
∈
V
×
V
,
i
≠
j
}, which denotes the agent R
i receives information about R
j. Finally, a set C
=
{
c
j
i
∈
R
2
∣
(
R
j
R
i
)
∈
V
×
V
,
i
≠
j
} of constant vectors that represent the relative desired position of agent R
i with respect to R
j.For a directed communication graph,(
R
j
R
i
)
∈
E implies that (
R
i
R
j
)
∉
E. For an undirected formation graph (
R
j
R
i
)
∈
E implies that (
R
i
R
j
)
∈
E.Definition 2 (paths and cycles).
There exists a path between the verticesR
i and R
j in the formation graph if there is a sequence of edges (
R
i
R
m
1
)
,
(
R
m
1
R
m
2
)
,
…
,
(
R
m
r
R
j
) for some i
≠
j. We call a “cycle” to some path that starts and finishes in the same vertex.If there is a path between any two vertices of the formation graph, then the graph is called connected. If a formation graph is connected and the vectorc
j
i
∈
C satisfies the so-called closed-formation condition [19], that is, c
i
m
1
+
c
m
1
m
2
+
⋯
+
c
m
r
i
=
0, then the formation control problem is solvable and the formation graph is said to be well-defined.Definition 3 (Laplacian matrix).
The Laplacian matrix associated with a formation graphG is given by (1)
L
G
=
Δ
-
A
d
,where Δ is the degree matrix defined as Δ
=
diag
{
g
1
,
…
,
g
n
}, where g
i is the number of edges directed to R
i, i
=
1
,
…
,
n, and A
d is the adjacency matrix of G defined as follows: (2)
a
i
j
=
1
,
if
(
R
j
R
i
)
∈
E
0
,
otherwise
.Proposition 4.
Consider the dynamical systemx
˙
=
A
x, where x
=
x
1
,
…
,
x
n
T and the matrix A
∈
R
n
×
n is Hurwitz. Then thenormalized system x
˙
=
A
D
(
x
)
x with D
(
x
)
=
diag
1
/
x
1
,
…
,
1
/
x
n is stable with finite time convergence.Proof.
SinceA is Hurwitz, then, for every matrix Q
=
Q
T
>
0 there exists a matrix P
=
P
T
>
0 such that the Lyapunov equation A
T
P
+
P
A
=
-
Q holds and V
=
x
T
P
x is a Lyapunov function for the system x
˙
=
A
x. Taking V
=
x
T
P
x as a Lyapunov function candidate and evaluating the time derivative along the trajectories of the normalized system we have(3)
V
˙
=
x
T
D
x
A
T
P
+
P
A
D
x
x
.Note that, since D
(
x
) is diagonal, it follows that x
T
D
(
x
)
v
≤
x
T
D
(
x
)
v and v
T
D
(
x
)
x
≤
v
T
D
(
x
)
x, where v
=
A
T
P
x; therefore(4)
V
˙
≤
x
T
D
(
x
)
A
T
P
+
P
A
D
(
x
)
x
.Moreover, since the matrix A is Hurwitz, the Lyapunov equation A
T
P
+
P
A
=
-
Q always admits a positive definite solution P for every positive definite matrix Q. Taking Q
=
I the time derivative is bounded from above by (5)
V
˙
≤
-
D
(
x
)
x
2
.Now, since D
(
x
) is diagonal, we have(6)
D
(
x
)
=
max
⁡
1
x
i
=
1
min
⁡
x
i
≥
1
max
⁡
x
i
,
i
=
1
,
…
,
n
.On the other hand, knowing that (7)
x
≥
max
⁡
x
i
,it is true that (8)
1
x
≤
1
max
⁡
x
i
≤
D
(
x
)
,
i
=
1
,
…
,
n
,which implies directly that(9)
-
1
x
≥
-
D
(
x
)
.Then, V
˙ is bounded as follows: (10)
V
˙
≤
-
x
.If we regard the quadratic form x
T
P
x as a norm for vector x, we can write (11)
V
˙
≤
-
l
p
x
T
P
x
1
/
2
,where l
p
>
0 is a proportionality constant. This leads to finally write the last expression as (12)
V
˙
≤
-
l
p
V
1
/
2
,that, according to [20], ensures convergence in finite time.


## 3. Problem Statement

Consider a group ofn mobile agents denoted by N
=
{
R
1
,
…
,
R
n
} moving on a plane. The cartesian coordinates of agent R
i are given by z
i
(
t
)
=
x
i
(
t
)
,
y
i
(
t
)
T
∈
R
2, i
=
1
,
…
,
n. Every robot is described by the kinematic model(13)
z
˙
i
=
u
i
,
i
=
1
,
…
,
n
,where u
i
=
u
i
1
,
u
i
2
T
∈
R
2 are the velocities along the X- and Y-axes. In this paper we consider a decentralized general scheme. We assume that robot R
i can detect the position of a subset of robots N
i
⊂
N, where N
i
≠
∅, i
=
1
,
…
,
n. Therefore, the desired position of robot R
i, say z
i
*, with respect to N
i is defined by(14)
z
i
*
=
1
n
i
∑
j
∈
N
i
‍
(
z
j
+
c
j
i
)
,where n
i is the cardinality of N
i and c
j
i
=
[
h
j
i
,
v
j
i
]
T, ∀
j
∈
N
i. Throughout the paper, the following assumptions are supposed to hold.Assumption 5.
AgentR
i measures the position of agents R
j
∈
N
i for all time and, eventually, can detect the presence of any other agent within a circle of radius d. More precisely, R
i can detect the agents in the set M
i
(
t
)
=
{
R
j
∈
N
∣
z
i
(
t
)
-
z
j
(
t
)
≤
d
}.Assumption 6.
The initial conditions of all agents satisfyz
i
(
0
)
-
z
j
(
0
)
>
d, ∀
i
≠
j.


### 3.1. Control Goal

The goal is to design control lawsu
i
=
α
(
z
i
,
z
i
*
,
M
i
(
t
)
), i
=
1
,
…
,
n, such that(i)
the agents reach a desired formation; that is,lim
t
→
∞
(
z
i
(
t
)
-
z
i
*
(
t
)
)
=
0;
(ii)
there are no collisions among agents; moreover, at all times robots remain at some distance greater than or equal to a predefined distanced from each other; that is, z
i
(
t
)
-
z
j
(
t
)
≥
d, ∀
t
≥
0, i
≠
j.


## 3.1. Control Goal

The goal is to design control lawsu
i
=
α
(
z
i
,
z
i
*
,
M
i
(
t
)
), i
=
1
,
…
,
n, such that(i)
the agents reach a desired formation; that is,lim
t
→
∞
(
z
i
(
t
)
-
z
i
*
(
t
)
)
=
0;
(ii)
there are no collisions among agents; moreover, at all times robots remain at some distance greater than or equal to a predefined distanced from each other; that is, z
i
(
t
)
-
z
j
(
t
)
≥
d, ∀
t
≥
0, i
≠
j.


## 4. Control Design

The control design is presented in two parts, one of each attending a different objective according to the control goal. We start proposing a control law based on normalized attractive vector fields to ensure finite time convergence of the agents to the desired formation.


### 4.1. Attractive Vector Fields

The control law to reach the desired formation pattern is designed based on attractive vector fields proportional to the position error; that is,(15)
γ
i
=
-
k
z
~
i
,
i
=
1
,
…
,
n
,where z
~
i
=
z
i
-
z
i
* corresponds to the position errors and k
>
0 is a design parameter. In this paper, we consider a normalized version of (15) to treat a suitable system where all the agents move at the same known velocity; namely,(16)
γ
i
=
-
μ
z
~
i
z
~
i
,
z
~
i
≠
0
0
,
z
~
i
=
0
i
=
1
,
…
,
n
,where μ is the constant velocity of all agents. In real time experiments, the control law (16) can induce chattering effects which can be avoided as it is shown in Section 6. Now, we can state our first main result regarding a cyclic pursuit directed communication graph, as shown in Figure 1(a), which is the basement for further cases.Figure 1
Cyclic pursuit formation graphs.
(a)
(b)Theorem 7.
Consider system (13) and the control law (16). Also assume a formation graph with directed cyclic pursuit topology (Figure 1(a)). Then, in the closed-loop system (13)–(16) the mobile robots converge to the desired formation in finite time.Proof.
Consider the error coordinatesz
~
i
=
z
i
-
z
i
*, i
=
1
,
…
,
n. For the closed-loop system (13)–(16) the error dynamics is given by(17)
z
~
˙
1
=
-
μ
z
~
1
z
~
1
+
μ
z
~
2
z
~
2
,
⋮
z
~
˙
n
=
-
μ
z
~
n
z
~
n
+
μ
z
~
1
z
~
1
.Or, in matrix form, it is given by(18)
z
~
˙
=
-
μ
L
(
G
)
⊗
I
2
z
~
1
z
~
1
,
…
,
z
~
n
z
~
n
T
,where L
(
G
) is the Laplacian matrix of the communication graph in Figure 1(a), μ
>
0 is the constant velocity of agents, ⊗ denotes the Kronecker product, and I
2
∈
R
2
×
2 is the identity matrix. This yields to write(19)
z
~
˙
=
-
μ
L
G
⊗
I
2
D
z
~
⊗
I
2
z
~
,where(20)
D
(
z
~
)
=
diag
1
z
~
1
,
…
,
1
z
~
n
.Therefore, the closed-loop system has the same form as z
~
˙
=
-
μ
L
(
G
)
⊗
I
2
z
~ but is affected by the normalization as the system in the Proposition 4; then it is enough to show that in the system without normalization the agents converge asymptotically to the desired formation to ensure finite time convergence for the closed-loop system (13)–(16). According to [11], the Laplacian matrix of a connected formation graph has a single zero eigenvalue, λ
1
=
0, associated with the vector [
1
,
…
,
1
]
T
∈
R
n, while the rest of them satisfy Re
(
λ
2
)
,
…
,
Re
(
λ
n
)
>
0. As it was assumed, the closed formation condition holds, which directly implies z
~
1
+
⋯
+
z
~
n
=
0. Then, is it possible to analyse a subsystem formed by the first n
-
1 error coordinates knowing that z
~
n
=
-
z
~
1
+
⋯
+
z
~
n
-
1. For the specific case of a cyclic pursuit directed formation graph the Laplacian matrix has the form(21)
L
G
=
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
-
1
0
⋯
0
1
;then, the reduced system is given by(22)
e
˙
=
-
μ
L
r
(
G
)
⊗
I
2
e
,where e
=
[
z
~
1
,
…
,
z
~
n
-
1
]
T and L
r
(
G
)
∈
R
(
n
-
1
)
×
(
n
-
1
) is the resulting matrix for the reduced system.
Then, the stability of the system is simplified to the analysis of the matrix(23)
L
r
(
G
)
=
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
1
1
⋯
1
2
.In order to verify that L
r
(
G
)
>
0 we compute the determinant of the n
-
1 first principal minors. Denote by M
k the determinant of the principal minor of dimension k. Therefore, for the first n
-
2 cases it is clear that M
1
=
M
2
=
⋯
=
M
n
-
2
=
1 because all of them are upper diagonal matrices. To check that |
M
n
-
1
|
>
0 we develop by the last column in an iterative way (24)
M
n
-
1
=
2
M
n
-
2
+
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
1
1
⋯
1
1
︸
n
-
2
dimension
=
2
M
n
-
2
+
M
n
-
3
+
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
1
1
⋯
1
1
︸
n
-
3
dimension
⋮
M
n
-
1
=
2
M
n
-
2
+
M
n
-
3
+
⋯
+
M
2
+
M
1
+
1
=
n
>
0
.This ensures all the eigenvalues of L
r
(
G
) have strictly positive real parts, and this implies the reduced system e
˙
=
-
μ
L
r
(
G
)
⊗
I
2
e is asymptotically stable, that is, z
~
1
,
…
,
z
~
n
-
1
→
0 as t
→
∞, and because of the relation z
~
n
=
-
z
~
1
+
⋯
+
z
~
n
-
1, it is clear that also z
~
n
→
0 as t
→
∞. Then, in the whole system z
~
˙
=
-
μ
L
(
G
)
⊗
I
2
z
~ agents converge asymptotically to the desired formation, and even more, by direct application of Proposition 4, for the closed-loop system (13)–(16), the agents reach the desired formation in finite time. This concludes the proof.In the last proof, the closed formation condition was useful in order to reduce the original system. In the same way, we can state a corollary to show the stability for the case of an undirected cyclic pursuit formation graph.Corollary 8.
Consider the closed-loop system (13)–(16) using an undirected communication graph (Figure 1(b)). Then, the agents converge to the desired formation in finite time.Proof.
The closed-loop system in terms of the Laplacian matrix and using initially (15) instead of (16) takes the form(25)
z
~
˙
=
-
μ
1
-
1
2
0
⋯
-
1
2
-
1
2
1
-
1
2
⋯
0
0
-
1
2
1
⋯
0
⋮
⋮
⋮
1
-
1
2
-
1
2
0
⋯
-
1
2
1
⊗
I
2
z
~
,which in terms of the Laplacian matrix can be written as(26)
z
~
˙
=
-
μ
1
2
L
(
G
)
⊗
I
2
z
~
,where the Laplacian matrix of an undirected cyclic pursuit formation graph is(27)
L
(
G
)
=
2
-
1
0
⋯
-
1
-
1
2
-
1
⋯
0
0
-
1
2
⋯
0
⋮
⋮
⋮
2
-
1
-
1
0
⋯
-
1
2
.Now, if we consider the undirected graph as a combination of two directed graphs, we have(28)
L
+
G
=
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
-
1
0
⋯
0
1
,
L
-
G
=
1
0
0
⋯
-
1
-
1
1
0
⋯
0
0
-
1
1
⋯
0
⋮
⋮
⋮
1
0
0
0
⋯
-
1
1
,where the Laplacian L
+
(
G
) corresponds to the directed (clockwise) original graph, while L
-
(
G
) corresponds to the opposite direction (counter-clockwise) formation graph. Both Laplacian matrices L
+
(
G
) and L
-
(
G
) satisfy the closed-formation condition. This means that ∑
p
=
1
n
‍
z
~
p
+
=
∑
p
=
1
n
‍
z
~
p
-
=
0, where z
~
p
+ and z
~
p
- are the error variables defined for the formation described for L
+
(
G
) and L
-
(
G
), respectively. Combining these conditions we have(29)
∑
p
=
1
n
‍
z
~
p
+
+
∑
p
=
1
n
‍
z
~
p
-
=
∑
p
=
1
n
‍
z
~
p
+
+
z
~
p
-
=
0
,which by simplifying becomes(30)
∑
p
=
1
n
‍
z
~
p
+
+
z
~
p
-
=
∑
p
=
1
n
‍
2
z
p
-
z
p
+
1
+
c
p
+
1
,
p
+
z
p
-
1
+
c
p
-
1
,
p
=
2
∑
p
=
1
n
‍
z
~
p
=
0
,where z
~
p are the error variables for the composed Laplacian L
(
G
). As before, knowing that the Laplacian matrix of a connected communication graph has a single zero eigenvalue, λ
1
=
0, while the rest of them satisfy Re
(
λ
2
)
,
…
,
Re
(
λ
n
)
>
0. Using the relationship z
~
n
=
-
z
~
1
+
⋯
+
z
~
n
-
1 the analysis can be reduced again to the first n
-
1 error variables, in such a way that(31)
e
˙
=
-
μ
1
2
L
r
(
G
)
⊗
I
2
eis asymptotically stable, with e defined as above. This implies, again, z
~
1
,
…
,
z
~
n
-
1
→
0 as t
→
∞ which also means z
~
n
→
0 as t
→
∞. As a result, the closed-loop system z
~
˙
=
-
(
μ
/
2
)
L
(
G
)
⊗
I
2
z
~ is asymptotically stable, which ensures in the closed-loop system (13)–(16) by application of Proposition 4, the agents reach the desired formation in finite time.Example 9.
To cover a more general class of communication graphs, let us consider as an example the graphic shown in Figure2. This communication graph can be described entirely as the superposition of two directed cyclic pursuit communication subgraphs, that is, the combination of the cyclic paths P
1
=
{
R
4
R
3
,
R
3
R
2
,
R
2
R
1
,
R
1
R
4
} and P
2
=
{
R
4
R
3
,
R
3
R
2
,
R
2
R
4
}. The errors for the closed-loop system are given in matrix form, by(32)
z
~
˙
=
-
μ
1
-
1
0
0
0
1
-
1
0
0
0
1
-
1
-
1
2
-
1
2
0
1
⊗
I
2
z
~
,which can be written in terms of the Laplacian matrix as(33)
z
~
˙
=
-
μ
Δ
-
1
L
(
G
)
⊗
I
2
z
~with Δ defined as in Section 2. Since Δ
-
1
>
0 the analysis is reduced to the properties of L
(
G
). For this particular example we have(34)
Δ
-
1
=
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
2
,
L
(
G
)
=
1
-
1
0
0
0
1
-
1
0
0
0
1
-
1
-
1
-
1
0
2
,while the Laplacian matrices corresponding to the subgraphs P
1 and P
2 are(35)
L
1
G
=
1
-
1
0
0
0
1
-
1
0
0
0
1
-
1
-
1
0
0
1
,
L
2
(
G
)
=
0
0
0
0
0
1
-
1
0
0
0
1
-
1
0
-
1
0
1
.As the Laplacian matrices for each cyclic path satisfy a different closed-formation condition, we have for the errors defined by L
1
(
G
) that z
~
1
(
1
)
+
z
~
2
(
1
)
+
z
~
3
(
1
)
+
z
~
4
(
1
)
=
0 while for L
2
(
G
) the condition implies z
~
2
(
2
)
+
z
~
3
(
2
)
+
z
~
4
(
2
)
=
0. Then, if we combine these conditions, for the general system matrix Δ
-
1
L
(
G
) the relation is z
~
1
+
2
z
~
2
+
2
z
~
3
+
2
z
~
4
=
0. It is important to notice that, in the last expression, the coefficient for every z
~
i, i
=
1
,
…
,
n, is related with the cyclic paths in which the agent R
i is involved. Even more, if a linear dependency among error variables can be found, then it is always possible to focus the analysis on reduced systems as in previous cases. Then, we present the next result for a more general class of communication graphs.Figure 2
Four agents formation graphs with two cycles.Theorem 10.
Consider a group ofn agents moving in the plane, described by (13) along with the control law (16). Consider now a connected formation graph which is composed entirely as the superposition of m different cyclic paths. Then, in the closed-loop system (13)–(16) the mobile robots converge to the desired formation in finite time.Proof.
For this case, knowing that the stability of the closed-loop system can be analysed using the system without normalization(36)
z
~
˙
=
-
μ
L
N
G
⊗
I
2
z
~
,where L
N
(
G
)
=
Δ
-
1
L
(
G
), with Δ
-
1 defined as in Section 2. If there are m different cyclic paths described by L
k
(
G
), k
=
1
,
…
,
m, also m different closed-formation conditions can be stated. The combination of all these conditions leads to(37)
m
1
z
~
1
+
m
2
z
~
2
+
⋯
+
m
n
z
~
n
=
0
,where m
i represents the number of cycles the ith agent is involved with. As the communication graph is connected there exists a single zero eigenvalue while the rest satisfy Re
(
λ
2
)
,
…
,
Re
(
λ
n
)
>
0. Using (37) the system can be reduced to the first n
-
1 error variables such that(38)
e
˙
=
-
μ
Δ
r
-
1
L
r
(
G
)
⊗
I
2
e
,with e defined as above, Δ
r
-
1
=
diag
{
1
/
g
1
,
…
,
1
/
g
n
-
1
} and L
r
(
G
)
∈
R
(
n
-
1
)
×
(
n
-
1
) having strictly positive real part eigenvalues. This implies again that z
~
1
,
…
,
z
~
n
-
1
→
0 as t
→
∞ which also means z
~
n
→
0 as t
→
∞. As a result, the whole closed-loop system is asymptotically stable and as a consequence, by application of Proposition 4, in the system (13)–(16) the agents reach the desired formation in finite time.Remark 11.
Corollary8 and Theorem 10 are extensions of the results presented in [5], where the simplified case of the directed cyclic pursuit formation graph was studied. A complete generalization of this result would be the study of finite time formation control using general communication graphs possessing a spanning tree [18]. This is left as an issue for future research.


### 4.2. Repulsive Vector Fields

Once we have shown the finite time convergence for agents, we attend the noncollision problem by designing a proper complementary control law based on repulsive vector fields focusing on the distance among agents. For this purpose it is useful to define the relative distance variablesp
i
j
=
x
j
-
x
i and q
i
j
=
y
j
-
y
i, i
,
j
=
1
,
…
,
n, i
≠
j. Note that if we consider the plane p
i
j
-
q
i
j, we can identify the origin as a collision between ith and jth agents and a circle of radius d, centered at the origin as the influence region between any two agents. Outside this circle, only attractive vector fields prevail while inside the circle the discontinuous repulsive vector fields appear. This is shown in Figure 3.Figure 3
Relative distance betweenith and jth agents on the plane p
i
j
-
q
i
j.The first step to design the repulsive vector fields is done regarding the most simple case of a scenario when only two robots are in risk of collision. Then, the situation is geometrically generalized to the case of a robot rounded by a group of possible colliding robots. The vector fields are proposed in such a way that for robotR
i there exists an unstable counterclockwise focus, centred at the position of the other robots. The general expression of the repulsive vector fields is(39)
β
i
=
ε
∑
j
=
1
,
j
≠
i
n
‍
δ
i
j
(
x
i
-
x
j
)
-
(
y
i
-
y
j
)
(
x
i
-
x
j
)
+
(
y
i
-
y
j
)
,where ε
>
0 and the functions δ
i
j depend on the distance between R
i and R
j; in the next way(40)
δ
i
j
=
1
,
if
z
i
-
z
j
≤
d
,
0
,
if
z
i
-
z
j
>
d
,where d is the minimum allowed distance between any pair of agents. If the sensed area is the same for all agents, it is clear that δ
i
j
=
δ
j
i, i
≠
j. Finally, the control law for each agent is given by(41)
u
i
=
γ
i
+
β
i
,
i
=
1
,
…
,
n
,where γ
i is given by (16) and β
i is given by (39). Now consider the case when there exist collision risk between agents R
r and R
s only while the rest of agents are far enough each one from the others. Then δ
s
r
=
1, and the dynamics of R
r and R
s are(42)
z
˙
r
=
-
μ
z
~
r
z
~
r
+
ε
(
x
r
-
x
s
)
-
(
y
r
-
y
s
)
(
x
r
-
x
s
)
+
(
y
r
-
y
s
)
,
z
˙
s
=
-
μ
z
~
s
z
~
s
+
ε
(
x
s
-
x
r
)
-
(
y
s
-
y
r
)
(
x
s
-
x
r
)
+
(
y
s
-
y
r
)
.Regarding the described situation, we state the next theorem that is fundamental because it is the most simple case of danger of collision.Theorem 12.
Consider the system (13) and the control law (41) along with definitions (16), (39), and (40). Suppose that there exists risk of collision between only two agents at time instant t
>
0 and that the design parameter ε satisfies ε
>
μ
/
d. Then, in the closed-loop system (13)–(41) the mobile robots reach their desired position at finite time and they stay for all t
≥
0 at a distance greater than or equal to d.Proof.
Assume first that there aren
-
2 agents without danger of a collision; then it is necessary to show R
r and R
s will avoid collision between them and stay at some minimum distance from each other. As mentioned above, there exists a circle, given by(43)
σ
r
s
=
p
r
s
2
+
q
r
s
2
-
d
2
=
0
,where the composite control law becomes discontinuous. Under the mentioned scenario, the trajectories defined by p
r
s and q
r
s lie inside the region σ
r
s
≤
0. Once the repulsive vector fields appear, the behaviour of trajectories is determined by analysing the time derivative of (43) evaluated along the closed-loop system. The dynamics of relative position variables is(44)
p
˙
r
s
q
˙
r
s
=
-
μ
z
~
s
z
~
s
-
z
~
r
z
~
r
+
2
ε
p
r
s
-
q
r
s
p
r
s
+
q
r
s
.Then,(45)
σ
˙
r
s
=
2
p
r
s
q
r
s
p
˙
r
s
q
˙
r
s
,
σ
˙
r
s
=
2
-
μ
p
r
s
,
q
r
s
z
~
s
z
~
s
-
z
~
r
z
~
r
+
4
ε
p
r
s
2
+
q
r
s
2
.At this point, it is necessary to ensure that σ
˙
r
s
>
0; in the inner region σ
r
s
≤
0. That means the resulting vector field inside the discontinuous surface points outwards. First consider the case when the attractive vector field points to inside the surface. Then, the constant ε should be selected in such a way that σ
˙
r
s
>
0. Taking the case where attractive fields for both agents point to each other, resulting in the most negative magnitude in σ
˙
r
s and restricting our analysis to the limit of the discontinuous surface, where σ
r
s
=
p
r
s
2
+
q
r
s
2
=
d
2, we can easily check that the time derivative of σ
r
s is bounded from below by(46)
σ
˙
r
s
>
2
-
2
μ
d
+
2
ε
d
2
;therefore if ε
>
μ
/
d then σ
˙
r
s
>
0. This implies that there exists a repulsive resulting vector field between R
r and R
s such that they will reject each other at least until they reach a distance d. Moreover, since z
r
(
0
)
-
z
s
(
0
)
≥
d, then the agents not only avoid the collision but also satisfy z
r
(
t
)
-
z
s
(
t
)
≥
d for all time.Even though the control laws proposed in this paper are not intended to produce a sliding mode motion, in case that the attractive vector fields outside the surface point to the surfaceσ
i
j
=
0, then a sliding behaviour should exist on the surface such that the agents stay at a distance d, until there exist conditions for the trajectories to leave the surface σ
r
s
=
0. This situation might occur depending on the initial conditions, [21, 22].In order to generalize the problem under discussion, it is insightful to consider now the situation of having three different robotsR
r, R
s, and R
t and possible collision risks between R
r and R
s and R
r and R
t as shown in Figure 4. This leads to present the next result, where we show the reasoning to generalize the noncollision scenario.Figure 4
AgentR
r in risk of collision with both R
s and R
t, d
r
s
,
d
r
t
<
d.Theorem 13.
Consider the system (13) and the control law (41) along with definitions (16), (39), and (40). Suppose that there exists a risk of collision among three agents at time instant t, as shown in Figure 4, and that ε
>
2
(
μ
/
d
). Then, in the closed-loop system (13)–(41) the mobile robots reach their desired position in finite time and they stay at a distance greater than or equal to d for all t
≥
0.Proof.
In this case, due to the possible collision among the different agents, the discontinuous surface consists of two different components, each one being related with a pair of agents; that is,(47)
σ
=
σ
r
s
σ
r
t
=
p
r
s
2
+
q
r
s
2
-
d
2
p
r
t
2
+
q
r
t
2
-
d
2
=
0
.According to Figure 4, δ
r
s
=
δ
r
t
=
1 which implies the dynamics(48)
p
˙
r
s
q
˙
r
s
=
-
μ
z
~
s
z
~
s
-
z
~
r
z
~
r
+
2
ε
p
r
s
-
q
r
s
p
r
s
+
q
r
s
+
ε
p
r
t
-
q
r
t
p
r
t
+
q
r
t
,
p
˙
r
t
q
˙
r
t
=
-
μ
z
~
t
z
~
t
-
z
~
r
z
~
r
+
2
ε
p
r
t
-
q
r
t
p
r
t
+
q
r
t
+
ε
p
r
s
-
q
r
s
p
r
s
+
q
r
s
.To analyse the behaviour on the discontinuity surface we use the positive definite function(49)
V
=
1
4
σ
T
σ
,whose time derivative is given by(50)
V
˙
=
1
2
σ
T
σ
˙
=
1
2
σ
r
s
σ
˙
r
s
+
σ
r
t
σ
˙
r
t
,
V
˙
=
σ
r
s
[
p
r
s
,
q
r
s
]
p
˙
r
s
q
˙
r
s
+
σ
r
t
[
p
r
t
,
q
r
t
]
p
˙
r
t
q
˙
r
t
.Evaluate V
˙ considering that the trajectories lie in the inner region of σ
=
0, which implies σ
r
s
,
σ
r
t
≤
0; that is, p
r
s
2
+
q
r
s
2
=
d
r
s
2 and p
r
t
2
+
q
r
t
2
=
d
r
t
2, with d
r
s
,
d
r
t
<
d. Hence,(51)
V
˙
≤
σ
*
-
μ
[
p
r
s
,
q
r
s
]
z
~
s
z
~
s
-
z
~
r
z
~
r
-
μ
[
p
r
t
,
q
r
t
]
z
~
t
z
~
t
-
z
~
r
z
~
r
+
2
ε
d
r
s
2
+
2
ε
d
r
t
2
z
~
s
z
~
s
-
z
~
r
z
~
r
+
2
ε
[
p
r
s
,
q
r
s
]
p
r
t
q
r
t
,where σ
*
=
max
⁡
{
σ
r
s
,
σ
r
t
}. Now, we bound the norm of the difference of unitary vectors as(52)
z
~
s
z
~
s
-
z
~
r
z
~
r
≤
2
,
z
~
t
z
~
t
-
z
~
r
z
~
r
≤
2
.Therefore, V
˙ is bounded from above by(53)
V
˙
≤
σ
*
-
4
μ
d
*
+
4
ε
d
*
2
-
2
ε
d
*
2
,where d
*
=
max
⁡
{
d
r
s
,
d
r
t
}. Since we have selected ε
>
2
(
μ
/
d
*
), we get(54)
-
4
μ
d
*
+
2
ε
d
*
2
>
0
,which finally implies that(55)
V
˙
<
0
.Then, the trajectories of the closed-loop system point outwards of the surfaces σ
r
s
=
σ
r
t
=
0 in every point inside σ
=
0. As it was assumed, for any initial conditions the trajectories start outside σ
=
0; then, in order to avoid getting into the surface, it is enough to ensure that they point towards the surface as d
*
→
d; this means that ε
>
2
(
μ
/
d
), ensuring the distance between agents will be greater than or equal to the predefined distance d. This concludes the proof.At this point, we would add more agents to analyse a more complex collision problem. Geometrically, the most general case occurs when a robotR
r is surrounded by 6 other agents. Figure 5 shows this case, where R
i is in danger of collision with 6 other robots, and any of these 6 robots is in danger of collision with other 2 robots only. The behaviour of the surrounding agents has already been analysed. This occurs when all of them are at distance d from each other. Now, we can state our second main result, proceeding by induction to propose a solution to the general noncollision problem.Figure 5
AgentR
r in risk of collision with 6 different robots, d
r
i
<
d, i
=
1
,
…
,
6.Theorem 14.
Consider the system (13) and the control law (41) along with definitions (16), (39), and (40). Suppose that there exists a risk of collision among p
+
1
≥
4 agents at time instant t, as shown in Figure 5 and ε
>
6
(
μ
/
d
). Then, in the closed-loop system (13)–(41) the mobile robots reach their desired position in finite time and they stay at a distance greater than or equal to d for all t
≥
0.Proof.
For simplicity, and without loss of generality, let us denote byR
r the robot at the center of the configuration shown in Figure 5 and assume that there are p robots R
1
,
R
2
,
…
,
R
p around R
r. The cases p
=
1 and p
=
2 have already been analysed, resulting in conditions ε
>
μ
/
d and ε
>
2
(
μ
/
d
), respectively. Then, to proceed by induction, we take the Lyapunov function V
p
=
(
1
/
4
)
σ
T
σ, with σ
=
[
σ
r
1
,
…
,
σ
r
p
]
T, whose time derivative satisfies V
˙
p
<
0 if ε
>
p
(
μ
/
d
) for p
=
2. Now, we analyse the case for p
+
1 possible colliding robots; then the discontinuous surface σ is composed of p
+
1 components given by(56)
σ
=
σ
r
1
σ
r
2
⋮
σ
r
p
σ
r
,
p
+
1
=
p
r
1
2
+
q
r
1
2
-
d
2
p
r
2
2
+
q
r
2
2
-
d
2
⋮
p
r
p
2
+
q
r
p
2
-
d
2
p
r
,
p
+
1
2
+
q
r
,
p
+
1
2
-
d
2
=
0
.According to Figure 5, δ
r
1
=
δ
r
2
=
⋯
=
δ
r
p
=
δ
r
,
p
+
1
=
1; therefore the dynamics of the relative position variables are(57)
p
˙
r
k
q
˙
r
k
=
-
μ
z
~
k
z
~
k
-
z
~
r
z
~
r
+
2
ε
p
r
k
-
q
r
k
p
r
k
+
q
r
k
+
∑
j
=
1
,
j
≠
k
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
.Consider now the positive definite function(58)
V
p
+
1
=
1
4
σ
T
σ
=
V
p
+
1
4
σ
r
,
p
+
1
2
.The time derivative of V
p
+
1 in terms of the functions σ
i
j is(59)
V
˙
p
+
1
=
V
˙
p
+
1
2
σ
r
,
p
+
1
σ
˙
r
,
p
+
1
.By hypothesis, V
˙
p
<
0; then we have to ensure V
˙
p
+
1
<
0 for ε
>
(
p
+
1
)
(
μ
/
d
). This is achieved if the product σ
r
,
p
+
1
σ
˙
r
,
p
+
1
<
0. Then, since we are evaluating the Lyapunov function inside the surface σ
=
0, σ
r
,
p
+
1
<
0, the analysis reduces to show that σ
˙
r
,
p
+
1
>
0; hence(60)
σ
˙
r
,
p
+
1
=
[
p
r
,
p
+
1
,
q
r
,
p
+
1
]
p
˙
r
,
p
+
1
q
˙
r
,
p
+
1
,which evaluated along the dynamics of the closed-loop system becomes(61)
σ
˙
r
,
p
+
1
=
p
r
,
p
+
1
,
q
r
,
p
+
1
·
-
μ
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
+
2
ε
p
r
,
p
+
1
-
q
r
,
p
+
1
p
r
,
p
+
1
+
q
r
,
p
+
1
+
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
.Taking into account that we are analyzing the closed-loop system behaviour inside the region p
r
,
p
+
1
2
+
q
r
,
p
+
1
2
=
d
r
,
p
+
1
2. Then, we have(62)
σ
˙
r
,
p
+
1
=
2
ε
p
d
r
,
p
+
1
2
+
p
r
,
p
+
1
,
q
r
,
p
+
1
-
μ
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
+
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
·
-
μ
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
+
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
.If we take the most negative possible case, we have(63)
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
≤
2
,
p
r
j
-
q
r
j
p
r
j
+
q
r
j
≤
2
d
r
,
p
+
1
,and, V
˙ reduces in the worst case to(64)
σ
˙
r
,
p
+
1
=
2
ε
p
d
r
,
p
+
1
2
-
2
p
μ
d
r
,
p
+
1
-
2
ε
p
d
r
,
p
+
1
.
If we take the proposed conditionε
>
(
p
+
1
)
(
μ
/
d
*
) can be easily verified that σ
˙
r
,
p
+
1
>
0 resulting in a general requirement for ensuring V
˙
p
+
1
<
0. Again, if we consider the trajectories of the closed-loop system start outside σ
=
0, this condition becomes ε
>
(
p
+
1
)
(
μ
/
d
). This implies the repulsive vector fields will reject agents from each other keeping them to a distance greater than or equal to the minimum allowed distance d. Since there does not exist any condition where a given agent can be in a risk of collision with more than 6 robots, this concludes the proof.


## 4.1. Attractive Vector Fields

The control law to reach the desired formation pattern is designed based on attractive vector fields proportional to the position error; that is,(15)
γ
i
=
-
k
z
~
i
,
i
=
1
,
…
,
n
,where z
~
i
=
z
i
-
z
i
* corresponds to the position errors and k
>
0 is a design parameter. In this paper, we consider a normalized version of (15) to treat a suitable system where all the agents move at the same known velocity; namely,(16)
γ
i
=
-
μ
z
~
i
z
~
i
,
z
~
i
≠
0
0
,
z
~
i
=
0
i
=
1
,
…
,
n
,where μ is the constant velocity of all agents. In real time experiments, the control law (16) can induce chattering effects which can be avoided as it is shown in Section 6. Now, we can state our first main result regarding a cyclic pursuit directed communication graph, as shown in Figure 1(a), which is the basement for further cases.Figure 1
Cyclic pursuit formation graphs.
(a)
(b)Theorem 7.
Consider system (13) and the control law (16). Also assume a formation graph with directed cyclic pursuit topology (Figure 1(a)). Then, in the closed-loop system (13)–(16) the mobile robots converge to the desired formation in finite time.Proof.
Consider the error coordinatesz
~
i
=
z
i
-
z
i
*, i
=
1
,
…
,
n. For the closed-loop system (13)–(16) the error dynamics is given by(17)
z
~
˙
1
=
-
μ
z
~
1
z
~
1
+
μ
z
~
2
z
~
2
,
⋮
z
~
˙
n
=
-
μ
z
~
n
z
~
n
+
μ
z
~
1
z
~
1
.Or, in matrix form, it is given by(18)
z
~
˙
=
-
μ
L
(
G
)
⊗
I
2
z
~
1
z
~
1
,
…
,
z
~
n
z
~
n
T
,where L
(
G
) is the Laplacian matrix of the communication graph in Figure 1(a), μ
>
0 is the constant velocity of agents, ⊗ denotes the Kronecker product, and I
2
∈
R
2
×
2 is the identity matrix. This yields to write(19)
z
~
˙
=
-
μ
L
G
⊗
I
2
D
z
~
⊗
I
2
z
~
,where(20)
D
(
z
~
)
=
diag
1
z
~
1
,
…
,
1
z
~
n
.Therefore, the closed-loop system has the same form as z
~
˙
=
-
μ
L
(
G
)
⊗
I
2
z
~ but is affected by the normalization as the system in the Proposition 4; then it is enough to show that in the system without normalization the agents converge asymptotically to the desired formation to ensure finite time convergence for the closed-loop system (13)–(16). According to [11], the Laplacian matrix of a connected formation graph has a single zero eigenvalue, λ
1
=
0, associated with the vector [
1
,
…
,
1
]
T
∈
R
n, while the rest of them satisfy Re
(
λ
2
)
,
…
,
Re
(
λ
n
)
>
0. As it was assumed, the closed formation condition holds, which directly implies z
~
1
+
⋯
+
z
~
n
=
0. Then, is it possible to analyse a subsystem formed by the first n
-
1 error coordinates knowing that z
~
n
=
-
z
~
1
+
⋯
+
z
~
n
-
1. For the specific case of a cyclic pursuit directed formation graph the Laplacian matrix has the form(21)
L
G
=
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
-
1
0
⋯
0
1
;then, the reduced system is given by(22)
e
˙
=
-
μ
L
r
(
G
)
⊗
I
2
e
,where e
=
[
z
~
1
,
…
,
z
~
n
-
1
]
T and L
r
(
G
)
∈
R
(
n
-
1
)
×
(
n
-
1
) is the resulting matrix for the reduced system.
Then, the stability of the system is simplified to the analysis of the matrix(23)
L
r
(
G
)
=
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
1
1
⋯
1
2
.In order to verify that L
r
(
G
)
>
0 we compute the determinant of the n
-
1 first principal minors. Denote by M
k the determinant of the principal minor of dimension k. Therefore, for the first n
-
2 cases it is clear that M
1
=
M
2
=
⋯
=
M
n
-
2
=
1 because all of them are upper diagonal matrices. To check that |
M
n
-
1
|
>
0 we develop by the last column in an iterative way (24)
M
n
-
1
=
2
M
n
-
2
+
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
1
1
⋯
1
1
︸
n
-
2
dimension
=
2
M
n
-
2
+
M
n
-
3
+
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
1
1
⋯
1
1
︸
n
-
3
dimension
⋮
M
n
-
1
=
2
M
n
-
2
+
M
n
-
3
+
⋯
+
M
2
+
M
1
+
1
=
n
>
0
.This ensures all the eigenvalues of L
r
(
G
) have strictly positive real parts, and this implies the reduced system e
˙
=
-
μ
L
r
(
G
)
⊗
I
2
e is asymptotically stable, that is, z
~
1
,
…
,
z
~
n
-
1
→
0 as t
→
∞, and because of the relation z
~
n
=
-
z
~
1
+
⋯
+
z
~
n
-
1, it is clear that also z
~
n
→
0 as t
→
∞. Then, in the whole system z
~
˙
=
-
μ
L
(
G
)
⊗
I
2
z
~ agents converge asymptotically to the desired formation, and even more, by direct application of Proposition 4, for the closed-loop system (13)–(16), the agents reach the desired formation in finite time. This concludes the proof.In the last proof, the closed formation condition was useful in order to reduce the original system. In the same way, we can state a corollary to show the stability for the case of an undirected cyclic pursuit formation graph.Corollary 8.
Consider the closed-loop system (13)–(16) using an undirected communication graph (Figure 1(b)). Then, the agents converge to the desired formation in finite time.Proof.
The closed-loop system in terms of the Laplacian matrix and using initially (15) instead of (16) takes the form(25)
z
~
˙
=
-
μ
1
-
1
2
0
⋯
-
1
2
-
1
2
1
-
1
2
⋯
0
0
-
1
2
1
⋯
0
⋮
⋮
⋮
1
-
1
2
-
1
2
0
⋯
-
1
2
1
⊗
I
2
z
~
,which in terms of the Laplacian matrix can be written as(26)
z
~
˙
=
-
μ
1
2
L
(
G
)
⊗
I
2
z
~
,where the Laplacian matrix of an undirected cyclic pursuit formation graph is(27)
L
(
G
)
=
2
-
1
0
⋯
-
1
-
1
2
-
1
⋯
0
0
-
1
2
⋯
0
⋮
⋮
⋮
2
-
1
-
1
0
⋯
-
1
2
.Now, if we consider the undirected graph as a combination of two directed graphs, we have(28)
L
+
G
=
1
-
1
0
⋯
0
0
1
-
1
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
1
-
1
-
1
0
⋯
0
1
,
L
-
G
=
1
0
0
⋯
-
1
-
1
1
0
⋯
0
0
-
1
1
⋯
0
⋮
⋮
⋮
1
0
0
0
⋯
-
1
1
,where the Laplacian L
+
(
G
) corresponds to the directed (clockwise) original graph, while L
-
(
G
) corresponds to the opposite direction (counter-clockwise) formation graph. Both Laplacian matrices L
+
(
G
) and L
-
(
G
) satisfy the closed-formation condition. This means that ∑
p
=
1
n
‍
z
~
p
+
=
∑
p
=
1
n
‍
z
~
p
-
=
0, where z
~
p
+ and z
~
p
- are the error variables defined for the formation described for L
+
(
G
) and L
-
(
G
), respectively. Combining these conditions we have(29)
∑
p
=
1
n
‍
z
~
p
+
+
∑
p
=
1
n
‍
z
~
p
-
=
∑
p
=
1
n
‍
z
~
p
+
+
z
~
p
-
=
0
,which by simplifying becomes(30)
∑
p
=
1
n
‍
z
~
p
+
+
z
~
p
-
=
∑
p
=
1
n
‍
2
z
p
-
z
p
+
1
+
c
p
+
1
,
p
+
z
p
-
1
+
c
p
-
1
,
p
=
2
∑
p
=
1
n
‍
z
~
p
=
0
,where z
~
p are the error variables for the composed Laplacian L
(
G
). As before, knowing that the Laplacian matrix of a connected communication graph has a single zero eigenvalue, λ
1
=
0, while the rest of them satisfy Re
(
λ
2
)
,
…
,
Re
(
λ
n
)
>
0. Using the relationship z
~
n
=
-
z
~
1
+
⋯
+
z
~
n
-
1 the analysis can be reduced again to the first n
-
1 error variables, in such a way that(31)
e
˙
=
-
μ
1
2
L
r
(
G
)
⊗
I
2
eis asymptotically stable, with e defined as above. This implies, again, z
~
1
,
…
,
z
~
n
-
1
→
0 as t
→
∞ which also means z
~
n
→
0 as t
→
∞. As a result, the closed-loop system z
~
˙
=
-
(
μ
/
2
)
L
(
G
)
⊗
I
2
z
~ is asymptotically stable, which ensures in the closed-loop system (13)–(16) by application of Proposition 4, the agents reach the desired formation in finite time.Example 9.
To cover a more general class of communication graphs, let us consider as an example the graphic shown in Figure2. This communication graph can be described entirely as the superposition of two directed cyclic pursuit communication subgraphs, that is, the combination of the cyclic paths P
1
=
{
R
4
R
3
,
R
3
R
2
,
R
2
R
1
,
R
1
R
4
} and P
2
=
{
R
4
R
3
,
R
3
R
2
,
R
2
R
4
}. The errors for the closed-loop system are given in matrix form, by(32)
z
~
˙
=
-
μ
1
-
1
0
0
0
1
-
1
0
0
0
1
-
1
-
1
2
-
1
2
0
1
⊗
I
2
z
~
,which can be written in terms of the Laplacian matrix as(33)
z
~
˙
=
-
μ
Δ
-
1
L
(
G
)
⊗
I
2
z
~with Δ defined as in Section 2. Since Δ
-
1
>
0 the analysis is reduced to the properties of L
(
G
). For this particular example we have(34)
Δ
-
1
=
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
2
,
L
(
G
)
=
1
-
1
0
0
0
1
-
1
0
0
0
1
-
1
-
1
-
1
0
2
,while the Laplacian matrices corresponding to the subgraphs P
1 and P
2 are(35)
L
1
G
=
1
-
1
0
0
0
1
-
1
0
0
0
1
-
1
-
1
0
0
1
,
L
2
(
G
)
=
0
0
0
0
0
1
-
1
0
0
0
1
-
1
0
-
1
0
1
.As the Laplacian matrices for each cyclic path satisfy a different closed-formation condition, we have for the errors defined by L
1
(
G
) that z
~
1
(
1
)
+
z
~
2
(
1
)
+
z
~
3
(
1
)
+
z
~
4
(
1
)
=
0 while for L
2
(
G
) the condition implies z
~
2
(
2
)
+
z
~
3
(
2
)
+
z
~
4
(
2
)
=
0. Then, if we combine these conditions, for the general system matrix Δ
-
1
L
(
G
) the relation is z
~
1
+
2
z
~
2
+
2
z
~
3
+
2
z
~
4
=
0. It is important to notice that, in the last expression, the coefficient for every z
~
i, i
=
1
,
…
,
n, is related with the cyclic paths in which the agent R
i is involved. Even more, if a linear dependency among error variables can be found, then it is always possible to focus the analysis on reduced systems as in previous cases. Then, we present the next result for a more general class of communication graphs.Figure 2
Four agents formation graphs with two cycles.Theorem 10.
Consider a group ofn agents moving in the plane, described by (13) along with the control law (16). Consider now a connected formation graph which is composed entirely as the superposition of m different cyclic paths. Then, in the closed-loop system (13)–(16) the mobile robots converge to the desired formation in finite time.Proof.
For this case, knowing that the stability of the closed-loop system can be analysed using the system without normalization(36)
z
~
˙
=
-
μ
L
N
G
⊗
I
2
z
~
,where L
N
(
G
)
=
Δ
-
1
L
(
G
), with Δ
-
1 defined as in Section 2. If there are m different cyclic paths described by L
k
(
G
), k
=
1
,
…
,
m, also m different closed-formation conditions can be stated. The combination of all these conditions leads to(37)
m
1
z
~
1
+
m
2
z
~
2
+
⋯
+
m
n
z
~
n
=
0
,where m
i represents the number of cycles the ith agent is involved with. As the communication graph is connected there exists a single zero eigenvalue while the rest satisfy Re
(
λ
2
)
,
…
,
Re
(
λ
n
)
>
0. Using (37) the system can be reduced to the first n
-
1 error variables such that(38)
e
˙
=
-
μ
Δ
r
-
1
L
r
(
G
)
⊗
I
2
e
,with e defined as above, Δ
r
-
1
=
diag
{
1
/
g
1
,
…
,
1
/
g
n
-
1
} and L
r
(
G
)
∈
R
(
n
-
1
)
×
(
n
-
1
) having strictly positive real part eigenvalues. This implies again that z
~
1
,
…
,
z
~
n
-
1
→
0 as t
→
∞ which also means z
~
n
→
0 as t
→
∞. As a result, the whole closed-loop system is asymptotically stable and as a consequence, by application of Proposition 4, in the system (13)–(16) the agents reach the desired formation in finite time.Remark 11.
Corollary8 and Theorem 10 are extensions of the results presented in [5], where the simplified case of the directed cyclic pursuit formation graph was studied. A complete generalization of this result would be the study of finite time formation control using general communication graphs possessing a spanning tree [18]. This is left as an issue for future research.


## 4.2. Repulsive Vector Fields

Once we have shown the finite time convergence for agents, we attend the noncollision problem by designing a proper complementary control law based on repulsive vector fields focusing on the distance among agents. For this purpose it is useful to define the relative distance variablesp
i
j
=
x
j
-
x
i and q
i
j
=
y
j
-
y
i, i
,
j
=
1
,
…
,
n, i
≠
j. Note that if we consider the plane p
i
j
-
q
i
j, we can identify the origin as a collision between ith and jth agents and a circle of radius d, centered at the origin as the influence region between any two agents. Outside this circle, only attractive vector fields prevail while inside the circle the discontinuous repulsive vector fields appear. This is shown in Figure 3.Figure 3
Relative distance betweenith and jth agents on the plane p
i
j
-
q
i
j.The first step to design the repulsive vector fields is done regarding the most simple case of a scenario when only two robots are in risk of collision. Then, the situation is geometrically generalized to the case of a robot rounded by a group of possible colliding robots. The vector fields are proposed in such a way that for robotR
i there exists an unstable counterclockwise focus, centred at the position of the other robots. The general expression of the repulsive vector fields is(39)
β
i
=
ε
∑
j
=
1
,
j
≠
i
n
‍
δ
i
j
(
x
i
-
x
j
)
-
(
y
i
-
y
j
)
(
x
i
-
x
j
)
+
(
y
i
-
y
j
)
,where ε
>
0 and the functions δ
i
j depend on the distance between R
i and R
j; in the next way(40)
δ
i
j
=
1
,
if
z
i
-
z
j
≤
d
,
0
,
if
z
i
-
z
j
>
d
,where d is the minimum allowed distance between any pair of agents. If the sensed area is the same for all agents, it is clear that δ
i
j
=
δ
j
i, i
≠
j. Finally, the control law for each agent is given by(41)
u
i
=
γ
i
+
β
i
,
i
=
1
,
…
,
n
,where γ
i is given by (16) and β
i is given by (39). Now consider the case when there exist collision risk between agents R
r and R
s only while the rest of agents are far enough each one from the others. Then δ
s
r
=
1, and the dynamics of R
r and R
s are(42)
z
˙
r
=
-
μ
z
~
r
z
~
r
+
ε
(
x
r
-
x
s
)
-
(
y
r
-
y
s
)
(
x
r
-
x
s
)
+
(
y
r
-
y
s
)
,
z
˙
s
=
-
μ
z
~
s
z
~
s
+
ε
(
x
s
-
x
r
)
-
(
y
s
-
y
r
)
(
x
s
-
x
r
)
+
(
y
s
-
y
r
)
.Regarding the described situation, we state the next theorem that is fundamental because it is the most simple case of danger of collision.Theorem 12.
Consider the system (13) and the control law (41) along with definitions (16), (39), and (40). Suppose that there exists risk of collision between only two agents at time instant t
>
0 and that the design parameter ε satisfies ε
>
μ
/
d. Then, in the closed-loop system (13)–(41) the mobile robots reach their desired position at finite time and they stay for all t
≥
0 at a distance greater than or equal to d.Proof.
Assume first that there aren
-
2 agents without danger of a collision; then it is necessary to show R
r and R
s will avoid collision between them and stay at some minimum distance from each other. As mentioned above, there exists a circle, given by(43)
σ
r
s
=
p
r
s
2
+
q
r
s
2
-
d
2
=
0
,where the composite control law becomes discontinuous. Under the mentioned scenario, the trajectories defined by p
r
s and q
r
s lie inside the region σ
r
s
≤
0. Once the repulsive vector fields appear, the behaviour of trajectories is determined by analysing the time derivative of (43) evaluated along the closed-loop system. The dynamics of relative position variables is(44)
p
˙
r
s
q
˙
r
s
=
-
μ
z
~
s
z
~
s
-
z
~
r
z
~
r
+
2
ε
p
r
s
-
q
r
s
p
r
s
+
q
r
s
.Then,(45)
σ
˙
r
s
=
2
p
r
s
q
r
s
p
˙
r
s
q
˙
r
s
,
σ
˙
r
s
=
2
-
μ
p
r
s
,
q
r
s
z
~
s
z
~
s
-
z
~
r
z
~
r
+
4
ε
p
r
s
2
+
q
r
s
2
.At this point, it is necessary to ensure that σ
˙
r
s
>
0; in the inner region σ
r
s
≤
0. That means the resulting vector field inside the discontinuous surface points outwards. First consider the case when the attractive vector field points to inside the surface. Then, the constant ε should be selected in such a way that σ
˙
r
s
>
0. Taking the case where attractive fields for both agents point to each other, resulting in the most negative magnitude in σ
˙
r
s and restricting our analysis to the limit of the discontinuous surface, where σ
r
s
=
p
r
s
2
+
q
r
s
2
=
d
2, we can easily check that the time derivative of σ
r
s is bounded from below by(46)
σ
˙
r
s
>
2
-
2
μ
d
+
2
ε
d
2
;therefore if ε
>
μ
/
d then σ
˙
r
s
>
0. This implies that there exists a repulsive resulting vector field between R
r and R
s such that they will reject each other at least until they reach a distance d. Moreover, since z
r
(
0
)
-
z
s
(
0
)
≥
d, then the agents not only avoid the collision but also satisfy z
r
(
t
)
-
z
s
(
t
)
≥
d for all time.Even though the control laws proposed in this paper are not intended to produce a sliding mode motion, in case that the attractive vector fields outside the surface point to the surfaceσ
i
j
=
0, then a sliding behaviour should exist on the surface such that the agents stay at a distance d, until there exist conditions for the trajectories to leave the surface σ
r
s
=
0. This situation might occur depending on the initial conditions, [21, 22].In order to generalize the problem under discussion, it is insightful to consider now the situation of having three different robotsR
r, R
s, and R
t and possible collision risks between R
r and R
s and R
r and R
t as shown in Figure 4. This leads to present the next result, where we show the reasoning to generalize the noncollision scenario.Figure 4
AgentR
r in risk of collision with both R
s and R
t, d
r
s
,
d
r
t
<
d.Theorem 13.
Consider the system (13) and the control law (41) along with definitions (16), (39), and (40). Suppose that there exists a risk of collision among three agents at time instant t, as shown in Figure 4, and that ε
>
2
(
μ
/
d
). Then, in the closed-loop system (13)–(41) the mobile robots reach their desired position in finite time and they stay at a distance greater than or equal to d for all t
≥
0.Proof.
In this case, due to the possible collision among the different agents, the discontinuous surface consists of two different components, each one being related with a pair of agents; that is,(47)
σ
=
σ
r
s
σ
r
t
=
p
r
s
2
+
q
r
s
2
-
d
2
p
r
t
2
+
q
r
t
2
-
d
2
=
0
.According to Figure 4, δ
r
s
=
δ
r
t
=
1 which implies the dynamics(48)
p
˙
r
s
q
˙
r
s
=
-
μ
z
~
s
z
~
s
-
z
~
r
z
~
r
+
2
ε
p
r
s
-
q
r
s
p
r
s
+
q
r
s
+
ε
p
r
t
-
q
r
t
p
r
t
+
q
r
t
,
p
˙
r
t
q
˙
r
t
=
-
μ
z
~
t
z
~
t
-
z
~
r
z
~
r
+
2
ε
p
r
t
-
q
r
t
p
r
t
+
q
r
t
+
ε
p
r
s
-
q
r
s
p
r
s
+
q
r
s
.To analyse the behaviour on the discontinuity surface we use the positive definite function(49)
V
=
1
4
σ
T
σ
,whose time derivative is given by(50)
V
˙
=
1
2
σ
T
σ
˙
=
1
2
σ
r
s
σ
˙
r
s
+
σ
r
t
σ
˙
r
t
,
V
˙
=
σ
r
s
[
p
r
s
,
q
r
s
]
p
˙
r
s
q
˙
r
s
+
σ
r
t
[
p
r
t
,
q
r
t
]
p
˙
r
t
q
˙
r
t
.Evaluate V
˙ considering that the trajectories lie in the inner region of σ
=
0, which implies σ
r
s
,
σ
r
t
≤
0; that is, p
r
s
2
+
q
r
s
2
=
d
r
s
2 and p
r
t
2
+
q
r
t
2
=
d
r
t
2, with d
r
s
,
d
r
t
<
d. Hence,(51)
V
˙
≤
σ
*
-
μ
[
p
r
s
,
q
r
s
]
z
~
s
z
~
s
-
z
~
r
z
~
r
-
μ
[
p
r
t
,
q
r
t
]
z
~
t
z
~
t
-
z
~
r
z
~
r
+
2
ε
d
r
s
2
+
2
ε
d
r
t
2
z
~
s
z
~
s
-
z
~
r
z
~
r
+
2
ε
[
p
r
s
,
q
r
s
]
p
r
t
q
r
t
,where σ
*
=
max
⁡
{
σ
r
s
,
σ
r
t
}. Now, we bound the norm of the difference of unitary vectors as(52)
z
~
s
z
~
s
-
z
~
r
z
~
r
≤
2
,
z
~
t
z
~
t
-
z
~
r
z
~
r
≤
2
.Therefore, V
˙ is bounded from above by(53)
V
˙
≤
σ
*
-
4
μ
d
*
+
4
ε
d
*
2
-
2
ε
d
*
2
,where d
*
=
max
⁡
{
d
r
s
,
d
r
t
}. Since we have selected ε
>
2
(
μ
/
d
*
), we get(54)
-
4
μ
d
*
+
2
ε
d
*
2
>
0
,which finally implies that(55)
V
˙
<
0
.Then, the trajectories of the closed-loop system point outwards of the surfaces σ
r
s
=
σ
r
t
=
0 in every point inside σ
=
0. As it was assumed, for any initial conditions the trajectories start outside σ
=
0; then, in order to avoid getting into the surface, it is enough to ensure that they point towards the surface as d
*
→
d; this means that ε
>
2
(
μ
/
d
), ensuring the distance between agents will be greater than or equal to the predefined distance d. This concludes the proof.At this point, we would add more agents to analyse a more complex collision problem. Geometrically, the most general case occurs when a robotR
r is surrounded by 6 other agents. Figure 5 shows this case, where R
i is in danger of collision with 6 other robots, and any of these 6 robots is in danger of collision with other 2 robots only. The behaviour of the surrounding agents has already been analysed. This occurs when all of them are at distance d from each other. Now, we can state our second main result, proceeding by induction to propose a solution to the general noncollision problem.Figure 5
AgentR
r in risk of collision with 6 different robots, d
r
i
<
d, i
=
1
,
…
,
6.Theorem 14.
Consider the system (13) and the control law (41) along with definitions (16), (39), and (40). Suppose that there exists a risk of collision among p
+
1
≥
4 agents at time instant t, as shown in Figure 5 and ε
>
6
(
μ
/
d
). Then, in the closed-loop system (13)–(41) the mobile robots reach their desired position in finite time and they stay at a distance greater than or equal to d for all t
≥
0.Proof.
For simplicity, and without loss of generality, let us denote byR
r the robot at the center of the configuration shown in Figure 5 and assume that there are p robots R
1
,
R
2
,
…
,
R
p around R
r. The cases p
=
1 and p
=
2 have already been analysed, resulting in conditions ε
>
μ
/
d and ε
>
2
(
μ
/
d
), respectively. Then, to proceed by induction, we take the Lyapunov function V
p
=
(
1
/
4
)
σ
T
σ, with σ
=
[
σ
r
1
,
…
,
σ
r
p
]
T, whose time derivative satisfies V
˙
p
<
0 if ε
>
p
(
μ
/
d
) for p
=
2. Now, we analyse the case for p
+
1 possible colliding robots; then the discontinuous surface σ is composed of p
+
1 components given by(56)
σ
=
σ
r
1
σ
r
2
⋮
σ
r
p
σ
r
,
p
+
1
=
p
r
1
2
+
q
r
1
2
-
d
2
p
r
2
2
+
q
r
2
2
-
d
2
⋮
p
r
p
2
+
q
r
p
2
-
d
2
p
r
,
p
+
1
2
+
q
r
,
p
+
1
2
-
d
2
=
0
.According to Figure 5, δ
r
1
=
δ
r
2
=
⋯
=
δ
r
p
=
δ
r
,
p
+
1
=
1; therefore the dynamics of the relative position variables are(57)
p
˙
r
k
q
˙
r
k
=
-
μ
z
~
k
z
~
k
-
z
~
r
z
~
r
+
2
ε
p
r
k
-
q
r
k
p
r
k
+
q
r
k
+
∑
j
=
1
,
j
≠
k
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
.Consider now the positive definite function(58)
V
p
+
1
=
1
4
σ
T
σ
=
V
p
+
1
4
σ
r
,
p
+
1
2
.The time derivative of V
p
+
1 in terms of the functions σ
i
j is(59)
V
˙
p
+
1
=
V
˙
p
+
1
2
σ
r
,
p
+
1
σ
˙
r
,
p
+
1
.By hypothesis, V
˙
p
<
0; then we have to ensure V
˙
p
+
1
<
0 for ε
>
(
p
+
1
)
(
μ
/
d
). This is achieved if the product σ
r
,
p
+
1
σ
˙
r
,
p
+
1
<
0. Then, since we are evaluating the Lyapunov function inside the surface σ
=
0, σ
r
,
p
+
1
<
0, the analysis reduces to show that σ
˙
r
,
p
+
1
>
0; hence(60)
σ
˙
r
,
p
+
1
=
[
p
r
,
p
+
1
,
q
r
,
p
+
1
]
p
˙
r
,
p
+
1
q
˙
r
,
p
+
1
,which evaluated along the dynamics of the closed-loop system becomes(61)
σ
˙
r
,
p
+
1
=
p
r
,
p
+
1
,
q
r
,
p
+
1
·
-
μ
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
+
2
ε
p
r
,
p
+
1
-
q
r
,
p
+
1
p
r
,
p
+
1
+
q
r
,
p
+
1
+
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
.Taking into account that we are analyzing the closed-loop system behaviour inside the region p
r
,
p
+
1
2
+
q
r
,
p
+
1
2
=
d
r
,
p
+
1
2. Then, we have(62)
σ
˙
r
,
p
+
1
=
2
ε
p
d
r
,
p
+
1
2
+
p
r
,
p
+
1
,
q
r
,
p
+
1
-
μ
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
+
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
·
-
μ
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
+
∑
j
=
1
p
‍
ε
p
r
j
-
q
r
j
p
r
j
+
q
r
j
.If we take the most negative possible case, we have(63)
z
~
p
+
1
z
~
p
+
1
-
z
~
r
z
~
r
≤
2
,
p
r
j
-
q
r
j
p
r
j
+
q
r
j
≤
2
d
r
,
p
+
1
,and, V
˙ reduces in the worst case to(64)
σ
˙
r
,
p
+
1
=
2
ε
p
d
r
,
p
+
1
2
-
2
p
μ
d
r
,
p
+
1
-
2
ε
p
d
r
,
p
+
1
.
If we take the proposed conditionε
>
(
p
+
1
)
(
μ
/
d
*
) can be easily verified that σ
˙
r
,
p
+
1
>
0 resulting in a general requirement for ensuring V
˙
p
+
1
<
0. Again, if we consider the trajectories of the closed-loop system start outside σ
=
0, this condition becomes ε
>
(
p
+
1
)
(
μ
/
d
). This implies the repulsive vector fields will reject agents from each other keeping them to a distance greater than or equal to the minimum allowed distance d. Since there does not exist any condition where a given agent can be in a risk of collision with more than 6 robots, this concludes the proof.


## 5. Numerical Simulation Results

A numerical simulation was carried out in order to illustrate the performance of the proposed algorithm. The simulated system consists of nine mobile robotsR
1
,
…
,
R
9 and the goal is to reach the formation shown in Figure 6, where the relative position vectors are defined as c
21
=
c
32
=
[
0,1.5
]
T, c
43
=
c
54
=
[
-
1.5,0
]
T, c
65
=
c
76
=
[
0
,
-
1.5
]
T, c
87
=
[
1.5,0
]
T, and c
19
=
[
1.5
,
-
1.5
]
T. The constant velocity when no collision risk exists is μ
=
1 and the minimum allowed distance is d
=
1. According to the condition found above, the parameter ε was set to ε
=
6 to ensure the minimum distance condition will not be violated.Figure 6
Desired formation, where the agents have been located according to the desired geometric pattern.Results are shown in Figures7 and 8. In Figure 7 all the possible distances among agents have been drawn. Despite the apparent complexity of this graph, two aspects are to be emphasized. First, note that the distance between any pair of agents is always greater than or equal to the predefined distance d
=
1. Second, and perhaps more interestingly, note that some agents converge to their desired positions without sliding, while some others reach the discontinuity surfaces σ
r
s
=
0, and slide for some time interval until they eventually escape and reach the desired configuration. On the other hand, in Figure 8 the positions of agents corresponding to selected time instants are shown. The convergence to the desired formation becomes clear. An animation of the time evolution of the closed-loop system can be found in the attached supplementary material (Supplementary Material available online at http://dx.doi.org/10.1155/2015/948086).Figure 7
Distances among the nine agents.Figure 8
Agents distribution on the plane at different times.


## 6. Real-Time Experiments

For real-time experiments, we used unicycle-type robots as agents. For this reason, the control strategies previously developed are modified for the case of this type of mobile robots. The kinematic model for each robotR
i, according to Figure 9, is given by (65)
x
˙
i
y
˙
i
θ
˙
i
=
cos
⁡
θ
i
0
sin
θ
i
0
0
1
v
i
w
i
,
i
=
1
,
…
,
n
,where v
i is the longitudinal velocity of the middle point of wheels axis of the ith robot, w
i is its angular velocity, and θ
i is the orientation with respect to the X-axis. It is known that systems like (65) cannot be stabilized by any continuous and time-invariant control law [23]. For this reason, to avoid singularities in the control law, it is common in the literature [16, 19] to study the kinematics of a point α
i off the wheels' axis. The coordinates of point α
i are given by(66)
α
i
=
α
x
i
α
y
i
=
x
i
+
l
cos
⁡
θ
i
y
i
+
l
sin
θ
i
.Figure 9
Kinematic model of the unicycle-type mobile robot.The kinematics of pointα
i is given by(67)
α
˙
i
=
α
˙
x
i
α
˙
y
i
=
A
i
θ
i
v
i
w
i
,where(68)
A
i
θ
i
=
cos
⁡
θ
i
-
l
sin
θ
i
sin
θ
i
l
cos
⁡
θ
iis the decoupling matrix for each robot R
i. The decoupling matrix is nonsingular since det
⁡
A
i
θ
i
=
l
≠
0. By defining auxiliary control variables u
i
=
u
i
x
,
u
i
y
T it is possible to establish a strategy for controlling the position of the point α
i by(69)
v
i
w
i
=
A
i
-
1
θ
i
u
i
x
u
i
y
,where(70)
A
i
-
1
θ
i
=
cos
⁡
θ
i
sin
θ
i
-
sin
θ
i
l
cos
⁡
θ
i
lis the inverse of the decoupling matrix. The closed-loop system (67)–(69) produces(71)
α
˙
i
=
u
i
.The desired position of robot R
i, related to the coordinates α
i, is given by(72)
α
i
*
=
1
n
i
∑
j
∈
N
i
‍
α
j
+
c
j
i
.Then, a formation control with collision avoidance, similar to that presented in Section 4, is defined as(73)
u
i
=
γ
~
i
+
β
~
i
,
i
=
1,2
,
…
,
n
,where γ
~
i and β
~
i are similar to the case of point robots but related to coordinates α
i. It is clear that (71) is the same as the case of point robots presented in (13). Thus, the analysis of convergence and collision avoidance is reduced to the case of point robots presented before. Although the control strategy (69) steers the coordinates of the points α
i to a desired position, the angles θ
i remain uncontrolled.When a robotR
i is near its equilibrium point, the formation control law γ
i induces the so-called chattering phenomenon, which is highly undesired. To eliminate the chattering effects we propose to switch to a proportional control in a small neighborhood of radius ρ, close to the equilibrium point. Hence, the control law is given by(74)
γ
i
=
-
μ
(
α
i
-
α
i
*
)
α
i
-
α
i
*
,
if
α
i
-
α
i
*
>
ρ
-
μ
ρ
α
i
-
α
i
*
,
if
α
i
-
α
i
*
≤
ρ
,
i
=
1,2
,
…
,
n
.The ratio μ
/
ρ helps us to avoid an abrupt change in the control law when we switch from the normalized control law to the proportional one. The value ρ was chosen so that the chattering effects are alleviated. In our case, we have tried different values until obtaining a satisfactory result.


### 6.1. Experimental Platform

The real-time experiments were carried out over an experimental setup composed of the following elements.(i)
Four differential-drive mobile robots, model AmigoBot manufactured by MobileRobots Inc. (Figure10): Each one is furnished on the top with infrared markers which form a geometric pattern such that the centroid of this figure coincides with the middle point of the wheels’ axis of each robot for identification. The parameters of AmigoBot robots are wheel radius r
=
0.06 meters, length of wheels axis L
=
0.28 meters, distance to the front point of the robot l
=
0.15 meters, 8 sonar sensors to avoid collisions or locate obstacles, and the maximum longitudinal velocity of 1 m/s. They feature wireless serial ethernet for remote operations, two position encoders, and built-in velocity controllers. The workspace measures are 3.6
×
4.8 meters. The linear and angular velocities v
i and w
i obtained from the control law developed in this paper are transformed into linear velocities of the right and left wheel v
r
i, v
l
i through the isomorphism:(75)
v
r
i
v
l
i
=
1
2
2
L
2
-
L
v
i
w
i
,
i
=
1
,
…
,
n
.
Note that in (75) the value of r is not used because the information sent to each mobile robot is the linear velocity of each wheel.
(ii)
A positioning system: The position and orientation of each robot is measured through a vision system composed of12 cameras Flex 13 manufactured by Natural Point (Figure 11) which are located at a height of 4 meters. These cameras have a resolution of 1280
×
1024 pixels with a frequency of 120 frames per second. To detect an object, it must have a minimum of 3 markers and at least 3 cameras must locate the object within their range of vision.
(iii)
One Intel core i3-based computer: The software Motive calculates the position of the centroid of the geometric figure formed by the markers and its orientation. The control law is calculated in Visual C++ using Aria libraries which are also used to communicate with the robots. The protocol VRPN is used to share information between Motive and Visual C++. Finally, the velocities of each wheel are sent through Wi-Fi to the robots.Figure 10
AmigoBot robots.Figure 11
Cameras Flex 13.


### 6.2.  Real-Time Experiment

The experiment consists of four agentsR
1
,
…
,
R
4 and the goal is to reach the square formation shown in Figure 12 where the relative position vectors are defined as c
21
=
[
-
1,0
]
T, c
14
=
[
0
,
-
1
], c
24
=
[
-
1
,
-
1
]
T, c
42
=
[
1,1
]
T, c
32
=
[
0,1
]
T, and c
43
=
[
1,0
]
T. The constant velocity when no collision risk exists is μ
=
0.1 m/s, the minimum allowed distance is d
=
0.6 meters, ρ
=
0.05 meters, and the parameter ε was set to ε
=
2
(
μ
/
d
)
=
1
/
3. In this case, the theoretical value of ε has to be ε
>
3
(
μ
/
d
)
=
1
/
2. Even though the value of ε used in the experiment is less than the theoretical value, the experiment was successful because one robot can only be in collision danger with at most two robots simultaneously. The initial conditions for the agents are [
x
1
,
y
1
]
T
=
[
-
0.10666,0.43272
]
T, [
x
2
,
y
2
]
T
=
[
-
0.01551
,
-
0.36721
]
T, [
x
3
,
y
3
]
T
=
[
-
0.06131
,
-
1.08734
]
T, and [
x
4
,
y
4
]
T
=
[
-
0.08414,1.0719
]
T. Figure 13 shows a comparison between a numerical simulation and a real-time experiment of the trajectory in the plane of the agents. As can be seen, numerical simulation and real-time experiment responses are close, but they exhibit some differences. This can be explained by a number of reasons amongst the following: the theoretical results are valid for first-order systems, while the real robots are modeled by second-order differential equations. Second, the employed kinematic model does not take into account dynamic effects like mass, inertia, and so forth. Despite these differences, the multiagent system converges to the desired formation.Figure 12
Desired formation.Figure 13
Trajectory in the plane of the four agents.Figure14 shows the position errors of both the numerical simulation and real-time experiment, which converge to zero allowing the agents to achieve the desired formation.Figure 14
Position errors of the four agents.
(a)
Position error ofR
1
(b)
Position error ofR
2
(c)
Position error ofR
3
(d)
Position error ofR
4In Figure15 all the possible distances among agents are depicted. Notice that the distance between agents in the real-time experiment is lower than the design parameter d. This is explained because of some dynamics that are not taken into account in the model.Figure 15
Distances among the four agents.
(a)
Distances in the experiment
(b)
Distances in the simulationFinally, Figure16 shows the control inputs to achieve the desired formation. Once the agents are aligned into the desired geometric pattern the longitudinal velocity as the angular velocity converges to zero. The attached file shows a video of this real-time experiment.Figure 16
Control inputs.
(a)
Velocities ofR
1
(b)
Velocities ofR
2
(c)
Velocities ofR
3
(d)
Velocities ofR
4


## 6.1. Experimental Platform

The real-time experiments were carried out over an experimental setup composed of the following elements.(i)
Four differential-drive mobile robots, model AmigoBot manufactured by MobileRobots Inc. (Figure10): Each one is furnished on the top with infrared markers which form a geometric pattern such that the centroid of this figure coincides with the middle point of the wheels’ axis of each robot for identification. The parameters of AmigoBot robots are wheel radius r
=
0.06 meters, length of wheels axis L
=
0.28 meters, distance to the front point of the robot l
=
0.15 meters, 8 sonar sensors to avoid collisions or locate obstacles, and the maximum longitudinal velocity of 1 m/s. They feature wireless serial ethernet for remote operations, two position encoders, and built-in velocity controllers. The workspace measures are 3.6
×
4.8 meters. The linear and angular velocities v
i and w
i obtained from the control law developed in this paper are transformed into linear velocities of the right and left wheel v
r
i, v
l
i through the isomorphism:(75)
v
r
i
v
l
i
=
1
2
2
L
2
-
L
v
i
w
i
,
i
=
1
,
…
,
n
.
Note that in (75) the value of r is not used because the information sent to each mobile robot is the linear velocity of each wheel.
(ii)
A positioning system: The position and orientation of each robot is measured through a vision system composed of12 cameras Flex 13 manufactured by Natural Point (Figure 11) which are located at a height of 4 meters. These cameras have a resolution of 1280
×
1024 pixels with a frequency of 120 frames per second. To detect an object, it must have a minimum of 3 markers and at least 3 cameras must locate the object within their range of vision.
(iii)
One Intel core i3-based computer: The software Motive calculates the position of the centroid of the geometric figure formed by the markers and its orientation. The control law is calculated in Visual C++ using Aria libraries which are also used to communicate with the robots. The protocol VRPN is used to share information between Motive and Visual C++. Finally, the velocities of each wheel are sent through Wi-Fi to the robots.Figure 10
AmigoBot robots.Figure 11
Cameras Flex 13.


## 6.2.  Real-Time Experiment

The experiment consists of four agentsR
1
,
…
,
R
4 and the goal is to reach the square formation shown in Figure 12 where the relative position vectors are defined as c
21
=
[
-
1,0
]
T, c
14
=
[
0
,
-
1
], c
24
=
[
-
1
,
-
1
]
T, c
42
=
[
1,1
]
T, c
32
=
[
0,1
]
T, and c
43
=
[
1,0
]
T. The constant velocity when no collision risk exists is μ
=
0.1 m/s, the minimum allowed distance is d
=
0.6 meters, ρ
=
0.05 meters, and the parameter ε was set to ε
=
2
(
μ
/
d
)
=
1
/
3. In this case, the theoretical value of ε has to be ε
>
3
(
μ
/
d
)
=
1
/
2. Even though the value of ε used in the experiment is less than the theoretical value, the experiment was successful because one robot can only be in collision danger with at most two robots simultaneously. The initial conditions for the agents are [
x
1
,
y
1
]
T
=
[
-
0.10666,0.43272
]
T, [
x
2
,
y
2
]
T
=
[
-
0.01551
,
-
0.36721
]
T, [
x
3
,
y
3
]
T
=
[
-
0.06131
,
-
1.08734
]
T, and [
x
4
,
y
4
]
T
=
[
-
0.08414,1.0719
]
T. Figure 13 shows a comparison between a numerical simulation and a real-time experiment of the trajectory in the plane of the agents. As can be seen, numerical simulation and real-time experiment responses are close, but they exhibit some differences. This can be explained by a number of reasons amongst the following: the theoretical results are valid for first-order systems, while the real robots are modeled by second-order differential equations. Second, the employed kinematic model does not take into account dynamic effects like mass, inertia, and so forth. Despite these differences, the multiagent system converges to the desired formation.Figure 12
Desired formation.Figure 13
Trajectory in the plane of the four agents.Figure14 shows the position errors of both the numerical simulation and real-time experiment, which converge to zero allowing the agents to achieve the desired formation.Figure 14
Position errors of the four agents.
(a)
Position error ofR
1
(b)
Position error ofR
2
(c)
Position error ofR
3
(d)
Position error ofR
4In Figure15 all the possible distances among agents are depicted. Notice that the distance between agents in the real-time experiment is lower than the design parameter d. This is explained because of some dynamics that are not taken into account in the model.Figure 15
Distances among the four agents.
(a)
Distances in the experiment
(b)
Distances in the simulationFinally, Figure16 shows the control inputs to achieve the desired formation. Once the agents are aligned into the desired geometric pattern the longitudinal velocity as the angular velocity converges to zero. The attached file shows a video of this real-time experiment.Figure 16
Control inputs.
(a)
Velocities ofR
1
(b)
Velocities ofR
2
(c)
Velocities ofR
3
(d)
Velocities ofR
4


## 7. Conclusions

A solution to the general noncollision problem in formation control has been proposed. This solution is based on the combination of attractive and repulsive vector fields. The attractive forces are designed proportionally to the error of each robot. The repulsive vector fields are designed as unstable focus centred at the position of the other robots. Besides, the attractive field was normalized to ensure the agents move at constant velocity when no danger of collision exists. As a by-product, finite time convergence is ensured. We analysed geometrically all the possible cases of multiple collisions and we proved the proposed control law is suitable in all situations, ensuring that the agents reach the desired geometric pattern in finite time and that they stay at a distance greater than a predefined bound. As a further research, the analysis can be extended not only to a general class of formation graph possessing a spanning tree but also to nonholonomic robots. Moreover, the differences that can be seen between the real-time experiment and the numerical simulation, due to unmodeled dynamics, motivate us to extend our work considering second-order agents.



---

*Source: 948086-2015-05-18.xml*