Sage Journals: Discover world-class research

Abstract

In this paper, a distributed formation control algorithm with delayed information exchange is discussed. The algorithm, which is derived from the flocking behaviour of birds and consensus theory, enables robots to move in formation at a desired velocity. After a series of orthogonal transformations to the original formation system, the upper bound tolerable delay is obtained by using matrix theory and the Nyquist criterion. According to the results, the upper bound tolerable delay depends on the control parameters and eigenvalues of the Laplacian matrix. Therefore, the effect of the parameters on the maximum tolerable delay is analysed, obtaining the following conclusions: the upper bound tolerable delay is proportional to the parameters associated with the velocity, inversely proportional to the parameters associated with the position, and inversely proportional to the difference between the eigenvalue of Laplacian matrix and 1. The simulation results of a four-robot formation system with different communication delays verify the effectiveness of the formation control algorithm and the correctness of the theoretical analysis.

Keywords

robotics formation stability communication delay

1. Introduction

The distributed formation control of large groups of autonomous robots has been a topic of great interest in the last few years, partly due to broad applications in cooperative search and rescue missions using multiple robots, the space exploration of coordinated mini-satellites, and mine countermeasures employing multiple autonomous underwater vehicles [1, 2]. At present, numerous results involving the distributed formation control of multi-robot systems with different models of individual dynamics, formation requirements and application domains presented in the recent literature [3-8]. In many swarming systems, the robots form and maintain a certain formation through limited interactions, using only relative information from a subset of the group. For example, in [3] the authors study a bio-inspired formation feedback scheme which mimics the collective motion of birds and fish. Flocking is a typical coordinated motion of a network of agents in a self-organized way. There has been great interest among control scientists and robotics scientists in analysing this phenomenon and the derived consensus problem [9, 10].

However, within the enlarged application range of a multi-robot system, one particular problem becomes increasingly apparent, namely that communication constraints will greatly depress the performance of the formation system in some practical applications. These negative factors involve delayed information exchange, communication failure or interruption, limited communication range and a high error bit rate. For example, adverse underwater environments lead to poor communication when using underwater sound communication, which is not good for a multiple autonomous underwater vehicles system. In this paper, we mainly investigate one of these aspects-the effect of communication delays on formation control. It is well known that communication delays will not only reduce the performance of the formation system, but they may also even lead to instability where the delays are too large. Thus, the design of an effective control strategy in the presence of communication delays and the investigation of its stability is an important issue.

Following the research on collective flocking and the consensus theory, the consensus protocol has become a powerful tool for designing a control law of formation with delayed information exchange. There are some remarkable results, where each individual is modelled as a double integrator [11-17], other forms of linear systems [18] and nonlinear systems [19]. Owing to the delays contained in the system, the stability analysis becomes more difficult and has been a hot topic in recent years. Until now, the problem of formation stability has mainly been investigated by the frequency domain method [11-13], the eigenvalue analysis method [14] and the Lyapunov stability theory [15, 16].

The previous research has usually been concern with static formation rather than with formation using a non-zero desired velocity. Sometimes, we expect that robots will not only reach the desired positions, but also converge on a desired velocity. Considering the non-static predefined velocity, Munz et al. [16] introduce an additional term in the control law that contains the reference velocity so as to get more accurate predictive position information. Delay-dependent stability conditions are obtained based on the Lyapunov stability theory. However, the construction of the Lyapunov function partly depends on the authors' experience. In this paper, we investigate a distributed formation control law for a second-order multi-robot system with the delayed exchange of information between neighbouring robots. Each robot is assumed to have instantaneous access to its own state information, but delayed state information of its neighbours. In addition, a predictive term is involved in the control law, as in [16]. We assume that the communication graph or formation graph is undirected and connected, and that the communication delays between any two neighbouring robots are constant, homogeneous and symmetric. Based on these simplified conditions, we apply frequency domain arguments to gain an accurate expression of the upper bound tolerable delay which guarantees that the formation becomes stable at a certain point. Furthermore, we study the effect of initial conditions on the equilibrium of the multi-robot system. In addition, the relationship between the upper bound delay and the parameters is also studied.

This paper is organized as follows: Section 2 gives the background of algebraic graph theory and the mathematical model of formation control. Section 3 presents the delay-dependent stability analysis method of the multi-robot formation. Section 4 shows some simulation results, and this is followed by a summary and conclusions in Section 5.

2. Problem Statement

2.1. Formation Graph

The formation graph G is used to denote communication between neighbouring robots. The undirected graph G=(V,E,A) is defined with a vertex set V={1,2,…,n} to represent the robots, an edge set E⊆V×V to represent the communication links, and a adjacency matrix A =[a_ij],where A ∈ R ^n×n is given by a_ij>0 if (i, j)∈E, and a_ij=0 otherwise. Suppose that each vertex has no self-loop, i.e., a_ii=0 for all i. In this paper, we use the weighted adjacency matrix, which is much more general than the 0-1 adjacency matrix. In particular, we let the sum of a_ij in the row i be 1. If there exists an edge from vertex i to vertex j, i.e., robot j can receive data from robot i, then i and j are called adjacent. All the adjacency robots of i are defined as N_i={j|(i,j)∈E}. The cardinality of the set N_i is called the degree of i. The diagonal degree matrix is Δ =diag(|N_i|). The Laplacian of G is a matrix L = Δ - A . For an undirected graph, the Laplacian matrix L is symmetric positive semi-definite. If the graph G is connected, the Laplacian matrix L has a simple zero eigenvalue, and the corresponding eigenvector is the vector of ones, 1 . In addition, the Laplacian matrix L is diagonalizable by the orthogonal matrix U with the orthogonal similarity transformation U ^T LU = λ , where λ =diag(λ₁…, λ_n,), λ_n≥…λ₂>λ₁=0 are ordered eigenvalues of L , and U consists of eigenvectors, with each column associated with an eigenvalue. In particular, the last column and the last row of U are the right eigenvector and left eigenvector of the zero eigenvalue of L respectively, that is 1/ $\sqrt{n}$ . This property is very important in discussing the equilibrium of the formation. The details can be found in [17]. A path from i to j is a sequence of edges of the form (i, j₁), (j₁,j₂),…,(j_m, j)∈E. If there is a path between any two nodes of the graph G, then G is said to be connected in the case of undirected graphs, and strongly connected in the case of directed graphs.

In order to achieve a stable formation for the multi-robot system, the formation graph must meet one requirement, i.e., the graph G must contain a spanning tree or else the graph G must be connected, no matter whether there are communication delays.

2.2. Formation Control

Consider a multi-robot system that consists of n robots. The dynamics of each robot is described by a double integrator:

{\dot{x}}_{i} (t) = v_{i} (t), {\dot{v}}_{i} (t) = u_{i} (t),

(1)

where x _i(t)∈ R ^N is the position, v _i(t)∈ R ^N is the velocity of a robot i, and u _i(t)∈ R ^N is the control input of that robot.

The robots adjust their control inputs to achieve and maintain a stable formation, moving with the desired relative positions and orientations. In this paper, we also hope that the robots can move at a desired velocity.

Definition 1[6]: Supposing a vector H =[( h ₁)^T,…,( h _n)^T]^T, where h _i∈ R ^N is the desired position of robot i, then n robots are in formation H if, and only if, there exist vectors q ₁∈ R ^N, q ₂∈ R ^N such that x _i(t)- h _i= q ₁, v _i(t)= q ₂, (i=1,…,n), where q ₁ is the position vector and q ₂ is the desired velocity vector. If there exist mapping functions q₁(⋅) and q₂(⋅) such that $x_{i} (t) - h_{i} - q_{1} (t) \to 0$ and $v_{i} (t) - q_{2} (t) \to 0 as t \to \infty$ , the robots are said to converge on formation H.

Suppose that the communication delay from robot j to i is τ_ij, τ_ij∈R⁺ and that the communication is symmetric, i.e., a_ij=a_ji, τ_ij=τ_ji. In this paper, a distributed formation control algorithm is considered based on the consensus theory. Since each robot can access its own state information instantaneously through embedded sensors, robot i uses its own current information in the control law in this paper. However, communication delays between neighbouring robots cannot be neglected in some applications. Taking communication delays into account, robot i receives out-dated state information of its neighbours. Inspired by the work presented in [16], the control law is designed thus:

\begin{array}{l} u_{i} (t) = {\dot{v}}_{d} (t) - c_{0} (v_{i} (t) - v_{d} (t)) + c_{1} \sum_{j \in N_{i}} a_{i j} \\ [(x_{j} (t - τ_{i j}) - h_{j}) - (x_{i} (t) - h_{i}) + v_{d} (t) τ_{i j}], \\ + c_{2} \sum_{j \in N_{i}} a_{i j} (v_{j} (t - τ_{i j}) - v_{i} (t)) \end{array}

(2)

where c₀ is the damping coefficient, c₁ and c₂ are position and velocity feedback gain respectively, the parameters c₀, c₁ and c₂ are positive scalars, N_i represents the neighbour set of robot i, and v _d(t) represents the desired velocity of v _i(t). If v _d(t)=0, the robots form a stationary formation. Otherwise, the robots move at the velocity v _d(t). As distinct from previous controllers, the controller (2) contains an additional predictive term v _d(t)τ_ij due to the non-zero desired velocity. Therefore, robot i needs to know the value of τ_ij, which can be solved by adding a time stamp in message transmission. If the desired velocity is time-varying, the term ${\dot{v}}_{d} (t) τ_{i j}$ should also be added to the velocity coupling term, which is omitted in this paper due to the constant desired velocity.

The proposed formation protocol is distributed in the sense that each robot only needs information from its neighbours. This distributed mode reduces the complexity of connections between robots significantly.

3. Analysis of the Delayed Multi-robot Formation

This section focuses on the stability of the formation with control law (2). The control of formation and stability analysis are particularly difficult because of communication delays. Usually, there is an upper bound delay τ* which, when exceeded, will see the system become unstable. In this section, expressions of the upper bound delay will be given for a multi-robot system on the assumption that all of the neighbouring robots have the same constant communication delay τ and a fixed reference velocity v _d.

3.1. Formation Stability

The closed-loop dynamics of a robot i are:

\begin{array}{l} {\dot{x}}_{i} (t) = v_{i} (t) \\ {\dot{v}}_{i} (t) = - c_{0} (v_{i} (t) - v_{d}) + c_{1} \sum_{j \in N_{i}} a_{i j} \\ [(x_{j} (t - τ) - h_{j}) - (x_{i} (t) - h_{i}) + v_{d} τ] . \\ + c_{2} \sum_{j \in N_{i}} a_{i j} (v_{j} (t - τ) - v_{i} (t)) \end{array}

(3)

According to the Newton-Leibniz formula:

υ_{d} τ = \int_{0}^{t} υ_{d} d s - \int_{0}^{t - τ} υ_{d} d s .

Considering ${\tilde{x}}_{i} (t) = x_{i} (t) - h_{i} - \int_{0}^{t} v_{d} d s$ , ${\tilde{v}}_{i} (t) = v_{i} (t) - v_{d}$ , the closed-loop system of (3) is reformulated as:

\begin{array}{l} {\dot{\tilde{x}}}_{i} (t) = {\tilde{v}}_{i} (t) \\ {\dot{\tilde{v}}}_{i} (t) = - c_{0} {\tilde{v}}_{i} (t) + c_{1} \sum_{j \in N_{i}} a_{i j} ({\tilde{x}}_{j} (t - τ) - {\tilde{x}}_{i} (t)) . \\ + c_{2} \sum_{j \in N_{i}} a_{i j} ({\tilde{v}}_{j} (t - τ) - {\tilde{v}}_{i} (t)) \end{array}

(4)

If the dynamics of every robot can be decoupled in all coordinates for 2D and 3D formations, the problem can be discussed in a 1D space. Thus, we discuss formation stability in a 1D space. Now, let ${\tilde{x}}_{i}$ and ${\tilde{v}}_{i}$ be the generalized position and velocity of a robot i, and $\tilde{x} (t) = {[{\tilde{x}}_{1} (t), \dots, {\tilde{x}}_{n} (t)]}^{T}$ , $\tilde{v} (t) = {[{\tilde{v}}_{1} (t), \dots, {\tilde{v}}_{n} (t)]}^{T}$ . The formation model of the multi-robot system is written in the vector form:

\begin{array}{l} \dot{\tilde{x}} (t) = \tilde{v} (t) \\ \dot{\tilde{v}} (t) = - c_{0} \tilde{v} (t) + c_{1} A \tilde{x} (t - t) - c_{1} \tilde{x} (t) + c_{2} A \tilde{v} (t - t) - c_{2} \tilde{v} (t)' \end{array}

(5)

where A is the adjacency matrix of the weighted graph G. Here, the degree matrix of G is a unit matrix I _n×n, and the Laplacian matrix is L = I - A . It is possible to find an orthogonal matrix U to diagonalize the adjacency matrix A:

u^{T} A u = I - λ .

Now, let $\tilde{x} = U \bar{x}$ , $\tilde{v} = U \bar{v}$ . The following system can be derived from system (5):

\begin{array}{l} \dot{\bar{x}} (t) = \bar{v} (t), \\ \dot{\bar{v}} (t) = - c_{0} \bar{v} (t) + c_{1} (I - λ) \bar{x} (t - τ) - c_{1} \bar{x} (t) . \\ + c_{2} (I - λ) \bar{v} (t - τ) - c_{2} \bar{v} (t) \end{array}

(6)

Now, the closed-loop control system (6) can be decoupled into n subsystems, each with the following form:

\begin{array}{l} {\dot{\bar{x}}}_{i} (t) = {\bar{v}}_{i} (t), \\ {\dot{\bar{v}}}_{i} (t) = - c_{0} {\bar{v}}_{i} (t) + c_{1} (1 - λ_{i}) {\bar{x}}_{i} (t - τ) - c_{1} {\bar{x}}_{i} (t), \\ + c_{2} (1 - λ_{i}) {\bar{v}}_{i} (t - τ) - c_{2} {\bar{v}}_{i} (t) \end{array}

(7)

where i=1,2,…,n, ${\bar{x}}_{i} (t)$ and ${\bar{v}}_{i} (t)$ are the ith components of $\bar{x}$ and $\bar{v}$ , respectively.

Note that the last variables ${\bar{x}}_{n}$ and ${\bar{v}}_{n}$ are defined by ${\bar{x}}_{n} = {(U^{T})}_{n} {\tilde{x}}_{n}$ and ${\bar{v}}_{n} = {(U^{T})}_{n} {\tilde{v}}_{n}$ , where ${(U^{T})}_{n}$ represents the nth row of U ^T. Therefore, the variable ${\bar{x}}_{n}$ corresponds to the average of the position of all the robots, and ${\bar{v}}_{n}$ represents the average of velocity of them. Notice that this result holds on the basis of a symmetric connected communication network.

Taking the Laplace transform of Eq. (7), we get:

\begin{array}{l} s {\bar{x}}_{i} (s) - {\bar{x}}_{i} (0) = {\bar{v}}_{i} (s), \\ s {\bar{v}}_{i} (s) - {\bar{v}}_{i} (0) = - c_{0} {\bar{v}}_{i} (s) + c_{1} (1 - λ_{i}) e^{- τ s} {\bar{x}}_{i} (s) - c_{1} {\bar{x}}_{i} (s), \\ + c_{2} (1 - λ_{i}) e^{- τ s} {\bar{v}}_{i} (s) - c_{2} {\bar{v}}_{i} (s) + I n t g (s, τ) \end{array}

(8)

According the Eq. (8), we have:

{\bar{x}}_{i} (s) = \frac{{\bar{v}}_{i} (0) + (s + c_{0} + c_{2} + c_{2} (λ_{i} - 1) e^{- τ s}) {\bar{x}}_{i} (0) + I n t g (s, τ)}{s^{2} + (c_{0} + c_{2}) s + (λ_{i} - 1) (c_{2} s + c_{1}) e^{- τ s} + c_{1}},

(9)

where $I n t g (s, τ) = (1 - λ_{i}) \int_{- τ}^{0} (c_{1} x (t) + c_{2} v (t)) e^{- (t + τ) s} d t$ .

It is obvious that the feedback loop contains the eigenvalue λ_i of the Laplacian matrix and the communication delay τ. The characteristic equation of the system is:

s^{2} + (c_{0} + c_{2}) s + (λ_{i} - 1) (c_{2} s + c_{1}) e^{- τ s} + c_{1} = 0.

(10)

The necessary and sufficient condition of forming a stable formation is that all of the characteristic roots of Eq. (10) are located in the left-half complex plane.

Consider:

F_{i} (s, e^{- τ s}) = s^{2} + (c_{0} + c_{2}) s + (λ_{i} - 1) (c_{2} s + c_{1}) e^{- τ s} + c_{1} .

Because c₀, c₁, and c₂ are positive and λ_i≥0, the roots of F_i(s,e^−τs) are located in the left-half complex plane when τ=0. Therefore, the system (6) is stable for τ=0. As a result, the formation with the control law (2) is stable for τ=0.

Next, we analyse the formation stability for τ>0. Here, we discuss the stability of the system (6) by analysing the stability of ${F^{'}}_{i} (s, e^{- τ s}) = 1 + G_{i} (s)$ , where:

G_{i} (s) = \frac{(λ_{i} - 1) (c_{2} s + c_{1}) e^{- τ s}}{s^{2} + (c_{0} + c_{2}) s + c_{1}} .

Let s=jω. The necessary and sufficient condition of the stability of the ith subsystem (7) associated with λ_i is that the trajectory of G_i(jω) does not enclose the point (−1, j0) for all ω∈[0,∞).

If $| G_{i} (j ω) | = 1$ , we get the following equation:

{({(c_{1} - ω^{2})}^{2} + {(c_{0} + c_{2})}^{2} ω^{2})}^{1 / 2} = | 1 - λ_{i} | {(c_{1}^{2} + c_{2}^{2} ω^{2})}^{1 / 2} .

(11)

According to the Gerschgorin disk theorem, the eigenvalues of the Laplacian matrix L , λ_i, are in the circle with a centre (1, 0) and a radius 1. Since L is a real symmetric matrix, there is 0≤λ_i≤2. Denoting λ'_i=1-λ_i, then −1≤1-λ_i≤1, (1-λ_i)²≤1, λ'_i²≤1.

Eq. (11) can also be expressed as:

ω^{4} + ({(c_{0} + c_{2})}^{2} - λ_{i}^{'}^{2} c_{2}^{2} - 2 c_{1}) ω^{2} + c_{1}^{2} (1 - λ_{i}^{'}^{2}) = 0.

(12)

Denote $χ = {(c_{0} + c_{2})}^{2} - λ_{i}^{'}^{2} c_{2}^{2} - 2 c_{1}$

If χ≥0, there exists a root ω=0 of Eq. (12), otherwise there does not exit any positive real root ω>0 of Eq. (12), which means that $| G_{i} (j ω) | < 1$ for any τ>0. Therefore, the subsystem (7) associated with λ_i is stable independent of the delay τ. In a word, if for all λ_i there is χ≥0, the formation of the multi-robot system (3) is stable for any τ>0.

If χ<0 and $χ^{2} - 4 c_{1}^{2} (1 - λ_{i}^{'}^{2}) < 0$ for a certain λ_i, there does not exit any positive real root ω>0 of Eq. (12), which means that $| G_{i} (j ω) | < 1$ . Thus, the subsystem (7) associated with λ_i is stable for any τ>0.

If χ<0 and $χ^{2} - 4 c_{1}^{2} (1 - λ_{i}^{'}^{2}) \geq 0$ , the real roots of Eq. (12) about ω are:

ω = {((- χ \pm {(χ^{2} - 4 c_{1}^{2} (1 - λ_{i}^{'}^{2}))}^{1 / 2}) / 2)}^{1 / 2} .

Let $φ (G_{i} (j ω)) = - π$ . When λ'_i ≤0,

\arctan (c_{2} ω / c_{1}) - ω τ - \arctan 2 ((c_{0} + c_{2}) ω, c_{1} - ω^{2}) = - π .

Now, ωτ∈[0,3π/2],

τ = (π + \arctan (c_{2} ω / c_{1}) - \arctan 2 ((c_{0} + c_{2}) ω, c_{1} - ω^{2})) / ω

(13)

When λ'_i >0,

π + \arctan 2 (c_{2} ω, c_{1}) - ω τ - \arctan 2 ((c_{0} + c_{2}) ω, c_{1} - ω^{2}) = - π

Now, ωτ∈[π,5π/2],

τ = (2 π + \arctan 2 (c_{2} ω, c_{1}) - \arctan 2 ((c_{0} + c_{2}) ω, c_{1} - ω^{2})) / ω

(14)

Where arctan2 is an arc tangent function valued on (−π,π]. Combining the results of formulas (13) and (14), we obtain the upper bound delay of the ith subsystem, marked by τ_i. The upper bound delay of the whole system is τ*=min{τ_i}.

Remarks:

1) The subsystem (7) associated with λ_i=0 or other eigenvalues has the characteristic root s=0, which means that the subsystem will be marginally stable. If, for any τ∈[0,τ*), all of the characteristic roots of each subsystem are located in the left-half complex plane, the multi-robot system is stable.

2) This paper only considers the case of a homogenous constant time delay. The problem of formation control with time-varying delays can be solved by substituting the time-varying delays with the maximum constant delay and utilizing the buffering technique, as in [11].

3.2. Formation Equilibrium

It is also important to estimate the effect of the initial conditions. However, there are some differences due to communication delays. The following part will discuss the effect of the initial conditions on the formation properties.

Assume that each robot has been informed of the state information of neighbouring robots at time t=0, i.e., ${\bar{x}}_{i} (t) = {\bar{x}}_{i} (0)$ , ${\bar{v}}_{i} (t) = 0$ when t∈[−τ,0]. Considering the subsystem (7) associated with λ₁=0, it converges to the equilibrium ${\bar{x}}_{1 e q}$ for any delay τ∈[0,τ*). The ${\bar{x}}_{1 e q}$ is given by the limit when s goes to zero, i.e.,

{\bar{x}}_{1 e q} = \lim_{t \to \infty} {\bar{x}}_{1} (t) = \lim_{s \to 0} s {\bar{x}}_{1} (s) = {\bar{x}}_{1} (0) .

The subsystem (7) associated with λ_i>0 converges with the equilibrium ${\bar{x}}_{i e q} = 0$ for any delay τ∈[0,τ*).

Since $\bar{x} = U^{- 1} \tilde{x}$ , $\bar{v} = U^{- 1} \tilde{v}$ , we have:

{\tilde{x}}_{e q} = U {\bar{x}}_{e q} = (1 / \sqrt{n}) \cdot {\bar{x}}_{1 e q} \cdot 1 = (1 / n) \sum {\tilde{x}}_{i} (0) \cdot 1 .

All of the ${\tilde{x}}_{i}$ come to a common value $(1 / n) \sum {\tilde{x}}_{i} (0)$ eventually. It is also obvious that the final formation equilibrium is not affected by the delay if there is priori knowledge of the neighbours of every robot. Since: ${\tilde{x}}_{i} (t) = x_{i} (t) - h_{i} - \int_{0}^{t} v_{d} d s$ , then

$x_{i} (t) - h_{i} = (1 / n) \sum {\tilde{x}}_{i} (0) + \int_{0}^{t} v_{d} d s$ when t goes to infinity.

We infer that $x_{i} (t) - h_{i} - q_{1} (t) \to 0 as t \to \infty$ .

Remarks:

3) Assume that a robot i has no access to the state of its neighbours within the beginning interval (0, τ) because of the communication delay, i.e., ${\bar{x}}_{i} (t) = 0$ , ${\bar{v}}_{i} (t) = 0$ when -τ≤t≤0. At the same time, $I n t g (s, τ) = 0$ . The equilibrium ${\bar{x}}_{1 e q}$ will be:

{\bar{x}}_{1 e q} = \lim_{t \to \infty} {\bar{x}}_{1} (t) = \lim_{s \to 0} s {\bar{x}}_{1} (s) = ({\bar{v}}_{1} (0) + c_{0} {\bar{x}}_{1} (0)) / (c_{0} + c_{1} τ) .

The equilibriums of other subsystems can still be ${\bar{x}}_{i e q} = 0$ .

From these two different cases of initial conditions, it can be inferred that although different initial conditions may lead to different equilibriums, all the ${\tilde{x}}_{i} (t)$ can still reach a common value. However, the equilibrium of the latter situation is related to the communication delay. These subsystems achieve the common value if, and only if, they have the same communication delay. As to a formation with different communication delays, we will not discuss it in this paper.

The limit of ${\tilde{v}}_{i} (t)$ is obtained by $\lim_{t \to \infty} {\tilde{v}}_{i} (t) = \lim_{t \to \infty} {\dot{\tilde{x}}}_{i} (t) = 0$ . Since ${\tilde{v}}_{i} (t) = v_{i} (t) - v_{d}$ as mentioned before, $v_{i} (t)$ is for all robots will converge to the desired velocity, i.e., $v_{d} = v_{i} (t) - q_{2} (t) \to 0 as t \to \infty$ .

Now, we have the following theorem.

Theorem 1: Given a multi-robot system consisting of n robots with dynamics (1) and a control law (2), where the communication network is fixed, connected, symmetric (i.e., a_ij=a_ji), a normalized adjacency matrix A , a fixed constant delay τ, a reference velocity v _d, and a specified formation H , if τ∈[0, τ*) holds, where τ*=min{τ_i},τ_i is calculated by formulas (13) and (14), the desired multi-robot system formation will be asymptotically achieved and hold stable, i.e., $x_{i} (t) - h_{i} - q_{1} (t) \to 0, v_{i} (t) - v_{d} = v_{i} (t) - q_{2} (t) \to 0$ as $t \to \infty$ for all i.

From theorem 1, the formation will hold stable for small delays but become unstable for large delays.

4. Simulations and Analysis

In this section, we illustrate our conclusions through several simulations and analyse the simulation results to get a deeper understanding.

4.1. First Simulation

Consider a set of four robots with dynamics (1) and control law (2) in 2D space. We construct two topologies of networks for the formation, expressed by adjacency matrices, A ₁= [0 1/2 0 1/2; 1/2 0 1/2 0; 0 1/2 0 1/2; 1/2 0 1/2 0], A ₂= [0 1/3 1/3 1/3; 1/3 0 1/3 1/3; 1/3 1/3 0 1/3; 1/3 1/3 1/3 0]. The eigenvalues of L ₁ and L ₂ are [0 1 1 2] and [0 1.333 1.333 1.333].

To concentrate our attention on the relationship between the upper bound delay τ* and parameters c₀, c₁, c₂ of the eigenvalue λ_i, here we only discuss combinations of parameters c₀, c₁, c₂, for which the upper bound delay τ* is computable according to the formula (13) and (14). To ensure χ<0 when λ_i>0 and χ<0 when λ_i=0, we set c₀=1, c₁=2, c₂=1 as the basic combination, and then change c₀, c₁, and c₂ separately in the computable range of τ*. We obtain the results as shown in Fig.1 and Fig.2. From the two figures, it can be seen that τ* is proportional to the value of c₀ and the value of c₂, and inversely proportional to the value of c₁. Therefore, we can set a larger value for c₀ and c₂, and a smaller value for c₁ when the multi-robot system has large communication delays.

Comparing Fig.1 and Fig.2 for the same combination of c₀, c₁ and c₂, the system with topology A ₂ is much more tolerant with the delay than the system with topology A ₁. This is attributed to the effect of the eigenvalues of the Laplacian matrix on the value of τ*. To investigate the relationship between λ_i and τ*, set c₀=0.1, c₁=10 and c₂=0.1. Fig.3 shows the value of τ* with a different λ_i. As can be seen from Fig.3, the upper bound delay τ* is inversely proportional to the difference between the value of λ_i and 1. For an extreme case, where λ_i is equal to 1, τ* will go to infinity. Thus, the subsystem (7) associate with λ_i=1 is stable for any delay. This assertion can also be obtained by analysing equation (10) directly, of which both characteristic roots s=0, -(c₀+c₂) have nothing to do with τ.

Figure 1.

c₀=1, c₁=2 and c₂=1 as a benchmark, the upper bound delay τ* over c₀(a), c₁(b) and c₂(c) with topology A ₁

Figure 2.

c₀=1, c₁=2 and c₂=1 as a benchmark, the upper bound delay τ* over c₀(a), c₁(b) and c₂(c) with topology A ₂

Figure 3.

c₀=0.1, c₁=10 and c₂=0.1, the upper bound delay τ* over λ_i

4.2. Second Simulation

The following simulations demonstrate the formation process of four robots with the fixed topology A ₁= [0 1/2 0 1/2; 1/2 0 1/2 0; 0 1/2 0 1/2; 1/2 0 1/2 0]. The initial positions of the four robots are (0, 0), (0, 0.5), (0, 1), (0, 1.5). The initial velocity is 0m/s. The desired formation is formulated as follows. The geometry formation is a square with an edge length of 1m, i.e., the desired relative positions are (0, 0), (1, 0), (0, 1), (1, 1). The desired velocity is (0.5m/s, 0.5m/s) for all four of the robots. The robots exchange information via a symmetric communication network with a homogeneous constant delay τ>0. Let the parameters be c₀=1, c₁=2 and c₂=1. The upper bound delay is calculated as τ*=2.4981s. Therefore, the formation will be achieved and kept for any τ∈[0,τ*).

We define the formation average error function as:

E = \sum_{(i, j)}^{} ‖ (x_{i} - h_{i}) - (x_{j} - h_{j}) ‖ / n .

The simulation time is 50s and the simulation step is 0.01s. Fig. 4 shows the process of the velocity change of the four robots and the formation average error within t=0~50s when τ=1.5s. It is clear that the speed on the X-direction and Y-direction of every robot can converge to the desired value within t=30~40s. Moreover, the error of this formation goes to zero asymptotically. Therefore, we conclude that the four robots reach the desired formation and move at the desired velocity thereafter. The system is stable for τ=1.5s. The formation process within t=0~50s in Fig.5 also demonstrates that the multi-robot system can converge on the desired formation and desired velocity when τ=1.5s.

When increasing the communication delay, it is not only the stabilization time of the system that increases, but equally the system may become unstable. Larger delays bring in long-time oscillation which impedes the progress of the stabilization of the system. When τ>τ*, the four robots cannot reach the desired formation. Fig. 6 depicts the process of the velocity change of the four robots and the formation average error within t=0~50s when τ=2.5s. It can be seen that the persistent oscillation of velocity occurs both on the X-direction and Y-direction. Moreover, the formation average error of the multi-robot system diverges over time. The formation process within t=0~50s in Fig.7 also demonstrates that the multi-robot system cannot converge on the desired formation or desired velocity when τ>τ*.

In summarizing these examples, it can be seen that the formation conditions derived from this paper are correct and not conservative because of the frequency domain method adopted.

Figure 4.

Velocity on the X-direction (a) and Y-direction (b) and the formation average error (c) over time when τ=1.5s with topology A ₁

Figure 5.

The trajectory of robots when τ=1.5s with topology A ₁

Figure 6.

Velocity on the X-direction (a) and Y-direction (b) and the formation average error (c) over time when τ=2.5s with topology A ₁

Figure 7.

The trajectory of robots when τ=2.5s with topology A ₁

Next, we switch the fixed topology of four robots to the other one A ₂= [0 1/3 1/3 1/3; 1/3 0 1/3 1/3; 1/3 1/3 0 1/3; 1/3 1/3 1/3 0], as mentioned before. The initial conditions and configurations are the same as with the first simulations about topology A ₂. The upper bound delay is calculated as τ*=5.6397s. Fig. 8 and Fig. 9 show the simulation results when τ=3.0s with the topology A ₂. The results are consistent with our conclusion. To observe the long-time tendency of the formation further, we get the simulation results within t=0~200s when τ>τ*. Fig. 10 shows the velocity and formation average error of the four robots when τ=5.7s. The multi-robot system cannot converge with the desired formation any more. The trajectory of the robots is not clear when the running time is too long, and we do not give the figure for the robots' trajectory here. The movement tendency can also be inferred by the formation average error.

In comparing these two groups of simulations with the same initial configuration, it can be seen that the formation with topology A ₂ has a quicker convergence rate than the formation with topology A ₁.

Figure 8.

Velocity on the X-direction (a) and Y-direction (b) and the formation average error (c) over time when τ=3.0s with topology A ₂

Figure 9.

The trajectory of robots when τ=3.0s with topology A ₂

Figure 10.

Velocity on the X-direction (a) and Y-direction (b) and the formation average error (c) over time when τ=5.7s with topology A ₂

4.3. Analysis

The control strategy used in this paper is derived from flocking behaviours, and the multi-robot formation performs in a distributed manner. The control strategy and conclusions in this paper can also be applied to a multi-robot system with more robots. Once the parameters c₀, c₁ and c₂ are fixed, the upper bound delay is only dependent on the eigenvalues of the Laplacian of the formation graph. Through multiple simulations of a different number of robots and different topologies, we find the rule that the denser the formation graph is, the larger the upper bound delay is. Obviously, it can also be concluded from the above simulation results of a four-robot formation. In a practical application, especially for multiple autonomous underwater vehicles, it is not appropriate to realize highly frequent communication, and so it is still necessary to develop some compromise measures in order to get an optimal state according to the specific situation.

5. Conclusion

In this paper, we present the formation stability of a multi-robot system with a homogeneous constant communication delay. We assume that the communication network is connected and symmetric. The matrix theory and Nyquist criterion are used to conduct the stability analysis. The results show that the multi-robot system can reach the desired formation and move at a desired velocity when the delay is smaller than a certain value. The derived stability conditions are supported by the simulation results. The relationship between the upper bound delay and parameters is also investigated. Further research will involve consideration of the convergence rate with respect to the delay and its parameters, formation with time-varying delay and multiple different delays.

Footnotes

6. Acknowledgments

This work is supported by the National Natural Science Foundation of China under Grant No. 60975071.

References

Kalantar

Zimmer

U.R.

(2007). Distributed shape control of homogeneous swarms of autonomous underwater vehicles. Autonomous Robots, vol. 22, no. 1, pp. 37–53.

Michael

Zavlanos

M.M.

Kumar

Pappas

G.J.

(2008). Distributed Multi-Robot Task Assignment and Formation Control, Proceedings - IEEE International Conference on Robotics and Automation, ICRA 2008, pp. 128–133, Pasadena, CA, 2008.

Tanner

H.G.

Jadbabaie

Pappas

G.J.

(2005). Flocking in teams of nonholonomic agents. Lect. Notes Contr. Inf., vol. 309, pp. 229–39.

Yamaguchi

(2003). A distributed motion coordination strategy for multiple nonholonomic mobile robots in cooperative hunting operations. Robotics and Autonomous Systems, vol. 43, no. 4, pp. 257–282.

Chio

T.S.

Tarn

T.J.

(2003). Rules and control strategies of multi-robot team moving in hierarchical formation, IEEE International Conference on Robotics and Automation, pp. 2701–2706, Taipei, Taiwan, Sep. 2003.

Lafferriere

Williams

Caughman

(2005). Decentralized control of vehicle formations. Systems & Control Letters, vol. 54, no. 9, pp. 899–910.

Z.H.

Wang

Hull

R.A.

(2008). Cooperative control of dynamical systems with application to autonomous vehicles. IEEE Transactions on Automatic Control, vol. 53, no. 4, pp. 894–911.

Dimarogonasa

D.V.

Johansson

K.H.

(2010). Stability analysis for multi-agent systems using the incidence matrix: Quantized communication and formation control. Automatica, vol. 46, no. 4, pp. 695–700.

Olfati-Saber

(2006). Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on Automatic Control, vol. 51, no. 3, pp. 401–420.

10.

Ren

(2006). Consensus based formation control strategies for multi-vehicle systems, American Control Conference, pp. 4237–4242, Minneapolis, USA, Jun. 2006.

11.

Yang

Fang

H.J.

(2010). Forced consensus in networks of double integrator systems with delayed input. Automatica, vol. 46, no. 3, pp. 629–632.

12.

Yang

H.Y.

(2010). Formation control of multi-agent with diverse delays. Journal of Zhejiang University (Engineering Science), vol. 44, no. 7, pp. 1355–1360.

13.

Liu

C.L.

Tian

Y.P.

(2008). Formation control of second-order dynamic agents with heterogeneous communication delays, Proceedings of the 27th Chinese Control Conference, pp. 536–540, China.

14.

Triplett

Morgansen

(2006). Abbreviated zero order hold for formation control in the presence of communication and sensing delays, Proceedings of the 2006 American Control Conference, pp. 6081–6087, Minneapolis, USA, Jun. 2006.

15.

Secchi

Fantuzzi

(2008). Formation control over delayed communication networks, 2008 IEEE International Conference on Robotics and Automation, pp. 563–568, Pasadena, CA, May 2008.

16.

Munz

Papachristodoulou

Allgower

(2008). Delay-dependent rendezvous and flocking of large scale multi-agent systems with communication delays, Proceedings of the 47th IEEE Conference on Decision and Control, pp. 2038–2043, Cancun, Mexico, Dec. 2008.

17.

Seuret

Dimarogonas

D.V.

Johansson

K.H.

(2009). Consensus of double integrator multi-agents under communication delay, the 8th IFAC Workshop on Time Delay Systems, Roumanie: IFAC, 2009.

18.

Fax

J.A.

Murray

R.M.

(2003). Information flow and cooperative control of vehicle formations. IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1465–1476.

19.

Wachter

L.M.

Ray

L.E.

(2009). Stability of potential function formation control with communication and processing delay, 2009 American Control Conference. pp. 2997–3004, 2009.

Stable Formation Control of Multi-Robot System with Communication Delay