# Necessary and Sufficient Conditions for Circle Formations of Mobile Agents with Coupling Delay via Sampled-Data Control

Authors: Jianwei Zhao; Hongxiang Hu; Chen Wang; Guangming Xie
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A circle forming problem for a group of mobile agents governed by first-order system is investigated, where each agent can only sense the relative angular positions of its neighboring two agents with time delay and move on the one-dimensional space of a given circle. To solve this problem, a novel decentralized sampled-data control law is proposed. By combining algebraic graph theory with control theory, some necessary and sufficient conditions are established to guarantee that all the mobile agents form a pregiven circle formation asymptotically. Moreover, the ranges of the sampling period and the coupling delay are determined, respectively. Finally, the theoretical results are demonstrated by numerical simulations.


---

## Body

## 1. Introduction

In recent years, decentralized control in networked multiagent systems has attracted considerable attention from various scientific communities [1–5] due to its broad applications in physics, biology, and engineering [6–8]. Meanwhile, it should be noted that decentralized control has many advantages in achieving cooperative group performance, especially with low operational costs, high robustness, and flexible scalability.As a popular research topic in decentralized control, formation control [9–12] refers to coordinating a group of agents such that they can form a predesigned geometrical configuration through local interactions so that some tasks can be finished by the collaboration of the agents. Forming circle formations becomes a benchmark problem, since on one hand circle formations are one of the simplest classes of formations with geometric shapes and on the other they are natural choices of the geometric shapes for a robotic team to exploit an area of interest [13–15]. Research efforts have been made in the systems and control community. In [16], a novel pursuit-based approach has been presented to investigate collective motions and formations of a large number of agents with single-integrator kinematics and double-integrator dynamics on directed acyclic graphs, respectively. Furthermore, the problem of pattern formation based on complex Laplacians has been studied in [17]. More recently, Lin et al. [18] have studied the leader-follower formation problem based on complex-valued Laplacians for graphs whose edges are attributed with complex weights and designed a novel linear control law to achieve the shape of a planar formation. In that work, the linear control law can only solve the formation problem asymptotically. Lou and Hong [19] have considered the distributed surrounding of a convex target set by a group of agents with switching communication graphs and proposed a distributed controller to make the agents surround a given set with equal distance and the desired projection angles specified by a complex-value adjacency matrix.However, in some practical situations, it is more desirable for the multiagent systems to reach the formation in a finite time, such as when high precision performance and stringent convergence time are required. In [20], Xiao et al. have developed a novel finite-time formation control framework for multiagent systems. In their framework, the problems of time-invariant formation, time-varying formation, and trajectory tracking have been discussed, respectively, and some sufficient conditions for finite-time formation have been presented.In addition, the coupling delay [21, 22] between neighboring agents, which may deteriorate the system’s performance or even destabilize it, is always unavoidable in real circumstance with practical reasons, such as the finite switching and spreading speed of the hardware and circuit implementation. Due to this observation, Qin et al. [23] have studied the consensus problem for second-order dynamic agents under directed arbitrarily switching topologies with communication delay. They have proven that consensus can be reached if the delay is small enough. Very recently, Chen et al. [24] have considered the consensus problem of nonlinear multiagent systems with state time delay and obtained some consensus results by designing an adaptive neural network control strategy. In their work, it should be noted that the approximation property of radial basis function neural networks is used to neutralize the uncertain nonlinear dynamics of agents.In this paper, we investigate a circle formation problem of mobile agents with the coupling delay, where each agent is described by a kinematic point. Specifically, in the circle formation problem [25], all the agents move counterclockwise on the one-dimensional space of a given circle. We assume that each agent can only sense the relative angular positions of its neighboring two agents that are immediately in front of or behind it. The objective is to design appropriate decentralized control law such that all the agents can form a pregiven circle formation. Considering the limitations inherited in practical systems, such as the finite computing resource, we employ sampled-data control [26–30] when studying the circle formation problem of mobile agents with the coupling delay. Under the decentralized sampled-data control framework, the whole system is modeled in a hybrid fashion, and the continuous-time system is equivalently transformed into a discrete-time system. Furthermore, based on the discrete-time system, some necessary and sufficient conditions are established to guarantee that all the mobile agents form a pregiven circle formation asymptotically. We emphasize that the formulation of circle formation problem in our paper mainly follows the work in [25]. However, [25] has focused on the situation with the locomotion constraint that the mobile agents can only move forward but not backward which is motivated by several types of mobile robots, while this paper focuses on the case with time delay. Thus the way we deal with the circle formation problem with time delay here is quite different from that in [25].The rest of the paper is organized as follows. In Section2, some basic definitions in graph theory and the system model are provided. In Section 3, a novel decentralized sampled-data control law is proposed, based on which the main analytical results are obtained. In Section 4, numerical simulations are implemented to demonstrate the analytic results. Finally, the paper is concluded in Section 5.Notations. Throughout this paper, ϕ denotes the empty set, (
·
)
T and (
·
)
-
1 denote transpose and inverse, respectively. For A
∈
R
N
×
N, λ
i
A is the eigenvalue of the matrix A. Moreover, A
=
diag
⁡
A
1
,
…
,
A
N denotes a block diagonal matrix with the matrices A
i, (
i
=
1
,
…
,
N
) on the main diagonal. If the range of the indices i is clear from the context, this notation is abbreviated by A
=
diag
⁡
A
i.


## 2. Preliminaries

In this section, some basic definitions in graph theory and system model are firstly introduced for the subsequent use.Consider multiagent systems consist ofN agents, which are initially located on a given circle and can only move on the circle. The agent indexes belong to a finite index set I
=
{
1,2
,
…
,
N
}, and we label the agents counterclockwise as shown in Figure 1. Each agent has the dynamics as follows:(1)x˙it=uit,∀i∈I,where x
i
t is the position of agent i at time t measured by angles, and u
i
(
t
) is the decentralized control of agent i. Here, without loss of generality, it is assumed that the initial values of the agents satisfy(2)0≤x1t<x2t<⋯<xNt<2π,which means that all the agents do not coincide in the beginning.Figure 1
Agents distributed on a circle.In the multiagent systems, each agent can communicate with several other agents which are defined as its neighbors, and the neighbor set of agenti is denoted by N
i. Specially, in the circle formation problem, each agent can only sense the relative angular positions of its neighboring two agents that are immediately in front of or behind it, and it follows that N
i
=
i
+
,
i
-, where (3)i+=i+1ifi=1,…,N-11ifi=N,i-=i-1ifi=2,…,NNifi=1.Obviously, the interconnection topology between the agents in the circle formation problem is ring [31].Supposed
i is the desired angular distance between agents i and i
+. Then the pregiven circle formation can be described by a vector d
=
d
1
,
d
2
,
…
,
d
N
∈
R
N, where d
i
>
0, and ∑
i
=
1
N
d
i
=
2
π. Denote the auxiliary variable y
i as follows:(4)yi=xi+-xiifi=1,…,N-1x1+2π-xNifi=N,where y
i is the angular distance between agents i and i
+. The main objective of this paper is to design an appropriate decentralized control u
i
(
t
) such that a group of agents form a pregiven circle formation asymptotically; that is, l
i
m
t
→
∞
y
i
(
t
)
=
d
i
,
∀
i
∈
I. In [24, 25], Wang et al. adopted the following decentralized control to solve the circle formation problem:(5)uit=di-di+di-yit-didi+di-yi-t,∀i∈I.In this paper, we assume that each agent can only receive the neighbor information with the coupling delay. Specifically, by using periodic sampling technology and zero-order hold circuit, a decentralized sampled-data control induced from (5) is given as (6)uit=di-di+di-yikh-h-didi+di-yi-kh-hift∈kh,kh+τdi-di+di-yikh-didi+di-yi-khift∈kh+τ,kh+h,where h
>
0 is the sampling period, τ is the coupling delay between neighboring agents, and it is assumed that τ
<
h. In the next section, we investigate the circle formation problem of the closed-loop system (1) and (6).


## 3. Main Results

In this section, the convergence analysis of circle formations is presented, and some necessary and sufficient conditions are established.Given the decentralized sampled-data control (6), (1) evolves according to the following dynamic:(7)x˙it=di-di+di-yikh-h-didi+di-yi-kh-hift∈kh,kh+τdi-di+di-yikh-didi+di-yi-khift∈kh+τ,kh+h,∀i∈I, and then it follows that ∀
t
∈
k
h
,
k
h
+
τ, (8)y˙it=xi+t-xit′=didi++diyi+kh-h-di+di++diyikh-h-di-di+di-yikh-h+didi+di-yi-kh-h=-di+di++di+di-di+di-yikh-h+didi+di-yi-kh-h+didi++diyi+kh-h,and ∀
t
∈
k
h
+
τ
,
k
h
+
h
(9)y˙it=-di+di++di+di-di+di-yikh+didi+di-yi-kh+didi++diyi+kh.Denotey
(
t
)
=
y
1
(
t
)
,
…
,
y
N
(
t
)
T, and (8) and (9) can be rewritten as(10)y˙t=-Ld·ykh-h∀t∈kh,kh+τ-Ld·ykh∀t∈kh+τ,kh+h,where the matrix L
(
d
) is given by(11)Ld=d2d2+d1+dNd1+dN-d1d2+d10⋯0-d1d1+dN-d2d2+d1d3d3+d2+d1d2+d1-d2d3+d2⋯000-d3d3+d2d4d4+d3+d2d3+d2⋯00⋮⋮⋮⋮⋮⋮000⋯dNdN+dN-1+dN-2dN-1+dN-2-dN-1dN+dN-1-dNd1+dN00⋯-dNdN+dN-1d1d1+dN+dN-1dN+dN-1.According to (10), it implies that (12)ykh+τ-ykh=-τLdykh-hykh+h-ykh+τ=-h-τLdykh,which follows that (13)ykh+h-ykh=-τLdykh-h-h-τLdykh=IN-h-τLdykh-τLdykh-h.Then, the dynamics (13) is summarized as follows:(14)ykh+hykh=Φykhykh-h,k=0,1,2,…,where Φ
=
I
N
-
h
-
τ
L
d
-
τ
L
d
I
N
0. Furthermore, it should be noted that the continuous-time system (7) solves the circle formation problem if and only if the discrete-time system (14) solves the circle formation problem. Before presenting the main results, some useful lemmas are introduced as follows.Lemma 1 (see [26]).
Given the matrixL
(
d
), the following statements hold:(1)
L
(
d
) is diagonalizable and λ
i
d
∈
0,2, i
=
1,2
,
…
,
N;
(2)
0 is a single eigenvalue;
(3)
whenN is even, 2 is an eigenvalue, and when N is odd, 2 is not.Lemma 2 (see [32]).
Given the system(15)Zk+1=AZk,where A
∈
R
n
×
n, then system (15) solves the consensus problem if and only if 1 is an algebraically simple eigenvalue of A and is the unique eigenvalue of maximum modulus.Then the main result of the paper is given by the following theorem.Theorem 3.
Consider a network withN agents governed by the form (1); then the decentralized sampled-data control (6) solves the circle formation problem if and only if τ
<
1
/
m
a
x
λ
i
(
d
) and τ
<
h
<
2
τ
+
2
/
m
a
x
λ
i
d, where λ
i
(
d
) is the eigenvalue of the matrix L
(
d
).Proof.
Firstly, denote the matrixD
=
diag
⁡
d
1
,
d
2
,
…
,
d
N, and then one has D
-
1
L
(
d
)
D
=
L
T
(
d
), which is the Laplacian matrix of strongly connected graph. Let the auxiliary variable δ
(
k
h
+
h
)
=
D
-
1
0
0
D
-
1
y
(
k
h
+
h
)
y
(
k
h
), and rewrite (14) as (16)δkh+h=D-100D-1·IN-h-τLd-τLdIN0·ykh+hykh=D-100D-1·IN-h-τLd-τLdIN0·D00Dδkh=IN-h-τLTd-τLTdIN0δkh.
Obviously, from (15), it can be concluded that (14) solves the circle formation problem if and only if (16) solves the consensus problem. Denote the matrix Φ
~
=
I
N
-
(
h
-
τ
)
L
T
(
d
)
-
τ
L
T
(
d
)
I
N
0, and one obtains that(17)Φ~·12N=IN-h-τLTd-τLTdIN0·1N1N=12N,and it implies that 1 is an eigenvalue of Φ
~.
According to Lemma2, we proceed to prove that 1 is an algebraically simple eigenvalue of Φ
~ and also is the unique eigenvalue of maximum modulus if and only if τ
<
1
/
max
⁡
λ
i
(
d
) and τ
<
h
<
2
τ
+
2
/
max
⁡
λ
i
(
d
). From Lemma 1, there exists a matrix B, such that L
T
(
d
)
=
B
·
Λ
·
B
-
1, where Λ
=
diag
⁡
0
,
λ
2
(
d
)
,
…
,
λ
N
(
d
). Furthermore, one obtains that (18)Φ~=BB·IN-h-τΛ-τΛIN0·B-1B-1,and it follows that Φ
~ is similar to a block diagonal matrix diag
⁡
A
1
,
A
2
,
…
,
A
N, where A
i
=
1
-
(
h
-
τ
)
λ
i
(
d
)
-
τ
λ
i
(
d
)
1
0. Moreover, it is obvious that 1 and 0 are two eigenvalues of A
1.
In order to solve the circle formation problem, one should guarantee that all the eigenvalues ofA
i are located in the unit circle for i
=
2,3
,
…
,
N. Actually, all the matrixes A
i have the same form; hence one can analyze them together. Consider the auxiliary matrix 1
-
h
-
τ
λ
-
τ
λ
1
0, where λ
∈
0,2, and its eigenvalues can be obtained by solving the characteristic equation(19)αs=s2+h-τλ-1s+τλ=0.Let the roots of (19) be s
1
,
s
2, and it should be noted that there are two cases of the roots of (19).
For case 1, the second-order polynomialα
(
s
) has two real roots, that is, s
1
,
s
2
∈
R, and one has Δ
=
h
-
τ
λ
-
1
2
-
4
τ
λ
≥
0, which follows that(20)h∈τ+1λ+2τλ,+∞∪-∞,τ+1λ-2τλ.
Then, to guarantee thats
1
,
s
2
∈
-
1,1, the following condition should be satisfied:(21)1-h-τλ2∈-1,1⟺τ-1λ<h<τ+3λα1>0⟺hλ>0α-1>0⟺h<2τ+2λ.
Next, to determine the range of the sampling periodh, we should divide it into three cases. In the first case, when τ
λ
≥
1, one has τ
-
1
/
λ
≥
τ
+
1
/
λ
-
2
τ
/
λ, and τ
+
3
/
λ
≤
τ
+
1
/
λ
+
2
τ
/
λ. Hence it follows that h
∈
ϕ. In the second case, when 1
/
2
≤
τ
λ
<
1, one obtains that τ
-
1
/
λ
<
τ
+
1
/
λ
-
2
τ
/
λ, τ
+
3
/
λ
>
2
τ
+
2
/
λ, and τ
≥
τ
+
1
/
λ
-
2
τ
/
λ, which follows that h
∈
τ
+
1
/
λ
+
2
τ
/
λ
,
2
τ
+
2
/
λ. In the third case, when τ
λ
<
1
/
2, one has τ
-
1
/
λ
<
τ
+
1
/
λ
-
2
τ
/
λ, τ
+
3
/
λ
>
2
τ
+
2
/
λ, and τ
<
τ
+
1
/
λ
-
2
τ
/
λ, which obtains that h
∈
τ
,
τ
+
1
/
λ
-
2
τ
/
λ
∪
τ
+
1
/
λ
+
2
τ
/
λ
,
2
τ
+
2
/
λ. Therefore, it concludes that(22)h∈ϕifτ≥1λh∈τ+1λ+2τλ,2τ+2λif14λ≤τ<1λh∈τ,τ+1λ-2τλ∪τ+1λ+2τλ,2τ+2λifτ<14λ.
For case 2, the second-order polynomialα
(
s
) has a pair of conjugate complex roots, that is, s
1
,
s
2
∈
C, and one has Δ
=
h
-
τ
λ
-
1
2
-
4
τ
λ
<
0, which follows that(23)h∈τ+1λ-2τλ,τ+1λ+2τλ.Moreover, one has s
1
·
s
2
=
s
1
2
=
τ
λ. In order to locate the roots of α
(
s
) in the unit circle, one has τ
λ
<
1; that is, τ
<
1
/
λ.
Therefore, the eigenvalues of the auxiliary matrix1
-
(
h
-
τ
)
λ
-
τ
λ
1
0 are located in the unit circle if and only if τ
<
1
/
λ and τ
<
h
<
2
τ
+
2
/
λ, and it can directly follow that the eigenvalues of the block diagonal matrix diag
⁡
A
2
,
…
,
A
N are in the unit circle if and only if τ
<
1
/
max
⁡
λ
i
(
d
) and τ
<
h
<
2
τ
+
2
/
max
⁡
λ
i
(
d
). Obviously, one obtains that 1 is an algebraically simple eigenvalue of Φ
~ and is also the unique eigenvalue of maximum modulus if and only if τ
<
1
/
max
⁡
λ
i
(
d
) and τ
<
h
<
2
τ
+
2
/
max
⁡
λ
i
(
d
), and the decentralized sampled-data control (6) solves the circle formation problem. This completes the proof.According to Lemma1, when the number of the agents is even, 2 is the maximum eigenvalue of the matrix L
(
d
). Therefore, based on Theorem 3 and its proof, we have the following corollary.Corollary 4.
Consider a network withN agents governed by the form (1), and N is even; then the decentralized sampled-data control (6) solves the circle formation problem if and only if τ
<
1
/
2 and τ
<
h
<
2
τ
+
1.


## 4. Numerical Simulation

In this section, an example is provided to illustrate the effectiveness of the proposed theoretical results.Consider six agents in the multiagent systems, with the edges of their interaction topology1,2
,
2,3
,
3,4
,
4,5
,
5,6
,
6,1, and the initial values of the six agents are chosen as x
(
0
)
=
1
/
10
π
,
3
/
20
π
,
1
/
4
π
,
2
/
5
π
,
1
/
2
π
,
3
/
5
π. Moreover, the pregiven circle formation is described by the vector d
=
1
/
3
π
,
1
/
3
π
,
1
/
3
π
,
1
/
3
π
,
1
/
3
π
,
1
/
3
π.According to Lemma1, one has max
⁡
λ
i
d
=
2, and it follows that τ
<
1
/
2 and τ
<
h
<
2
τ
+
1. Hence, we choose τ
=
0.4, h
=
0.8. From (6), (7), and (10), the evolution of y
i
t and x
i
t is shown in Figure 2, and one can see that the multiagent system (1) with the decentralized sampled-data control (6) achieves the pregiven circle formation.Figure 2
The evolution ofy
i
(
t
) and x
i
(
t
) with the decentralized sampled-data control, when τ
=
0.4 and h
=
0.8 which meets the condition in Corollary 4.Furthermore, we chooseτ
=
0.4, h
=
1.85, and then h
>
2
τ
+
1, which do not meet for the condition in Corollary 4, and hence the multiagent system cannot achieve the pregiven circle formation, and the evolution of y
i
(
t
) and x
i
(
t
) is shown in Figure 3.Figure 3
The evolution ofy
i
(
t
) and x
i
(
t
) with the decentralized sampled-data control, when τ
=
0.4 and h
=
1.85 which does not meet the condition in Corollary 4.


## 5. Conclusion

This paper has discussed the circle forming problem for a group of mobile agents which are governed by first-order dynamics. In this study, each agent can only sense the relative delayed angular positions of its neighboring two agents and move on the one-dimensional space of a given circle. With the help of periodic sampling technology and zero-order hold circuit, a novel decentralized sampled-data control has been proposed. By combining algebraic graph theory with control theory, some necessary and sufficient conditions have been established to guarantee that all the mobile agents form a pregiven circle formation asymptotically. Finally, the simulations have confirmed our theoretical results. In the future, we will focus on the situations where the agent has the intrinsic dynamic, and the decentralized sampled-data control needs to be designed.



---

*Source: 1056594-2016-06-22.xml*