Gabriel Rodrigues De Campos
email: gabriel.rodrigues-de-campos@gipsa-lab.grenoble-inp.fr

Alexandre Seuret
email: alexandre.seuret@gipsa-lab.grenoble-inp.fr

Necs Team

Improved Consensus Algorithms using Memory Effects

This paper deals with simple integrator consensus problems. It is well-known that introducing a delay leads in general to a reduction of performances or to instability. Therefore, investigating the effect of time-delays in consensus problems is an important issue. The objective is the design of a improved consensus algorithm for continuous-time multi-agent systems. The novel algorithm proposes to sampled, in an appropriate manner, part of the multi-agent systems information such that the algorithm converges, assuming that at each instant, agent's control laws will also consider the sampled past information of its neighbors. Stability conditions expressed in terms of LMI's and based on algebraic communication matrix structure are provided. The efficiency of the method is tested for different network communication schemes.

I. INTRODUCTION

Network control systems (NCS) are spatially distributed systems with a communication network used between sensors, actuators, and identifies control over networks as one of the key future directions for control. Their primary advantages includes their low cost, reduced weight, and power requirements, simple installation and maintenance, and higher reliability.

This means NCS's applications can be found in a large range of areas such as mobile sensor networks ( [START_REF] Ogren | Cooperative control of mobile sensor networks: Adaptive gradient climbing in a distributed environment[END_REF]), remote surgery, haptic collaboration over Internet, multi-robot systems ( [START_REF] Olfati-Saber | Consensus problems in network of agents with switching topology and time delays[END_REF]), automated highway systems, averaging in communication networks ( [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF]) and formation control ( [START_REF] Dimarogonas | A connection between formation infeasibility and velocity alignment in kinematic multi-agent systems[END_REF]). Several results have appeared in recent literature that consider systems with different motion models, symmetry of communication and network interactions. A recent review of the vast literature in the field can be found in [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF], [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF] and [START_REF] Ren | A survey of consensus problems in multi-agent coordination[END_REF].

We consider a "consensus" algorithm (or protocol) as an interaction rule that specifies the information exchange between an agent and all of its neighbors over the network in order to reach an agreement regarding a certain quantity of interest that depends on the state of all agents. However, the use of a shared network introduces new challenges, such as delays over communications, packet losses or even communication blackout, witch can dramatically affect "consensus" convergence rate and cooperative control laws efficiency ( [START_REF] Muenz | Delay robustness in consensus problems[END_REF]). Here, we consider that agents are assumed to obey a simple integrator model.

Conventional control theories with many ideal assumptions, such as synchronized control and nondelayed sensing and actuation, must be reevaluated before they can be applied to NCSs. For most applications, delays lead to a reduce of performances or can even lead to instability. However there exists some cases where the introduction of a delay in the control loop can help to stabilize a system which would not be stable without it (see [START_REF] Gu | Stability of time-delay systems[END_REF], [START_REF] Seuret | Static output feedback sliding mode control design via an artificial stabilizing delay[END_REF]).

In the present article, we will prove that the simple integrator consensus algorithm belongs to this class of systems and provide a novel consensus algorithm based on sampling approach. To do so, the classical consensus algorithm ẋ(t) = -Lx(t) is modified into a new algorithm (see Figure 1), where δ ∈ R and τ ≥ 0 are additional parameters. Note that if δ and/or τ are taken as zeros, then the classical algorithm is retrieved. As the delay is now a control parameter, we can choose it of the most appropriate form. In this article, we will consider a sampling delay, τ (t) = tt k , t k ≤ t < t k+1 , already used in [START_REF] Rodrigues De Campos | Continous-time double integrator consensus algortihms improved by an appropriate sampling[END_REF] or in [START_REF] Seuret | A novel stability analysis of sampled-data systems with applications to multi-rate sampling and packet loss[END_REF] where the t k 's satisfies 0 = t 0 < t 1 < ... < t k < ... corresponds to the sampling instants. For the sake of simplicity, we will assume that the sampling process is periodic, i.e. the difference between two successive sampling instants t k+1t k = T , is constant.

From computational point of view, this choice is relevant with respect to the introduction of a constant delay τ since in the sampling delay case, only one data is held in the algorithm whereas in the case of a constant delay, all values of x in the interval [tτ t] should be kept in memory.

-L A method to design the algorithm parameters, including the appropriated sampling period T, on a "optimal" way is proposed based on a LMI's formulation. The communication graphs are supposed to be directed and undirected.

1 s x(t) -δA + -L 1 s x(t) t k -+ +
This paper is organized as follows: Section 2 presents the problem treated in this article. Section 3 will be dedicated to the establishment of the appropriated model, and in Section 4 we will proceed to stability analysis of the algorithm. Section 5 includes illustrating simulation results and performance analysis, and finally, Section 6 will present our conclusions and indicate possible future research efforts.

Throughout the paper, the superscript 'T ' stands for matrix transposition, R n denote the n-dimensional Euclidean space, and R n×m is the set of n×m real matrices. The set S n stands for the set of symmetric matrices of R n×n . I represents the identity matrix. Finally, for any matrix M , the notation (M ) i denotes the i th line of M and λ k (M ) represents the k th eigenvalue of M . The notation |.| corresponds the Euclidean norm and, for any function φ : [-τ, 0] → R n , the notation |φ| τ corresponds to max θ∈[-τ, 0] |φ(θ)|.

For the graph G with N vertices and edge set given by E = {(i, j) : j ∈ N i } the adjacency matrix A = A(G) = (a ij ) is the N ×N matrix given by a ij = 1, if (i, j) ∈ E and a ij = 0, otherwise. The degree d i of vertex i is defined as the number of its neighboring vertices, i.e. d i = #j : (i, j) ∈ E. Let ∆ be the N × N diagonal matrix of d i 's. The Laplacian of G is the matrix L = ∆ -A. For an undirected graph the Laplacian matrix is symmetric positive semidefinite. Zero is a simple eigenvalue of L (the corresponding eigenvector is the vector of ones, -→ 1 ) if and only if the associated directed graph has a directed spanning tree.

A. Preliminary lemmas and definitions

In order to clarify the presentation, a definition of exponential stability will be stated here.

Definition 1: ([13]) Let α > 0 be some positive, constant, real number. The system is said to be exponentially stable with the decay rate α, or α-stable, if there exists a scalar F ≥ 1 such that the solution x(t; t 0 , φ) satisfies:

|x(t; t 0 , φ)| ≤ F |φ| τ e -α(t-t0) . (1)
In the sequel we will say that a system is α-stable if the solution of the system are exponentially stable with a decay rate α g .

II. PROBLEM STATEMENT

In this paper the following problem in addressed. Consider the classical simple integrator consensus algorithm

ẋi (t) = j∈Ni a ij (x j (t k ) -x i (t)) i ∈ {1, . . . , N }, (2)
where x represents the vector containing the agents variables. This algorithm is distributed in the sense that each vehicle needs only information from its neighbors. Moreover, consensus algorithms can be archived asymptotically if and only if the graph associated to the Laplacian L has a directed spanning tree (page 25 [START_REF] Ren | Distributed Consensus in Multi-vehicle cooperative Control: theory and applications[END_REF]). We then derive the control law:

ẋ(t) = -Lx(t) , (3)
with

x(t) = [x 1 (t), .., x N (t)] T .
In this paper we will proposed an improved algorithm for simple integrator agents. The goal is a performance comparaison between the proposed and the classical algortihm, where memory's effects on system's stability will be bring forward. Assuming that there exists a constant and positive scalar µ such that:

j∈Ni a ij = µ, i ∈ {1, . . . , N },
the previous algorithm is modified into a new algorithm defined by

ẋ(t) = (-µI + (1 -δ)A)x(t) + δAx(t k ), (4)
where A is the adjacency matrix of the communication graph. As said before, there exists some cases where the introduction of a delay in the control loop can have stabilizing properties.

Consider further that all the the sampling period is constant and equal to T . Then (4) can be written as:

ẋ(t) = (-L -δA)x(t) + δAx(t k ) (5)
By the Leibnitz formula, we have x(t k ) = x(t)t t k ẋ(s)ds, for all differentiable functions x. System (5) can be rewritten as:

ẋ(t) = -Lx(t) -δA t t k ẋ(s)ds. (6)
Note that the matrix µI -A corresponds to the Laplacian matrix. This representation is a way to understand how the delay affects the consensus problem. From the point of view of agent i, the state x i is available at every time t without any delay. However the data coming from the other agents j ∈ N i are received by agent i after a time-delay (sampling period) chosen for control.

A. Definition of an appropriate model

This section focuses on the definition of a suitable modeling of the consensus algorithm [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF] to analyze its convergence. Knowing that the vector -→ 1 is an eigenvector associated to the eigenvalue 0 of the Laplacian matrix, it is possible to find a change of coordinates x = W z such that:

U (-µI + A)W = B 0 0 T 0 , (7)
where

U = U 1 U 2 = W -1 and U 2 = (U ) N .
In the case of a symmetric matrix A, the rest of the Laplacian eigenvalues are all positive. We denote them by 0 < λ 2 ≤ . . . ≤ λ N . It thus means that B ∈ R x is a diagonal matrix with -λ i for graphs containing a directed spanning tree.

The following lemma provides an appropriate way to rewrite (6) based on the properties of the matrix L.

Lemma 1: The system (6) can be rewritten in the following way:

ż1 (t) = (-B + δ(B + µI))z 1 (t) -δ(B + µI)z 1 (t k ), (8a) ż2 (t) = -µz 2 (t) + µz 2 (t k ), (8b)
where z 1 ∈ R N -1 , z 2 ∈ R and the matrix B in given in [START_REF] Rodrigues De Campos | Continous-time double integrator consensus algortihms improved by an appropriate sampling[END_REF].

Proof: Consider system ( 6)

ż1 (t) ż2 (t) = - B 0 0 T 0 z 1 (t) z 2 (t) - A ′ 1 A ′ 2 t t-τ ż(s)ds, where A ′ 1 A ′ 2 = U AW and A ′ 2 = (U AW ) N .
We can then rewrite (5) into two equations where

z 1 = U 1 x ∈ R (N -1)
and z 2 = U 2 x ∈ R N represent respectively the N -1 first components and the last component of z. From ( 7), simple matrix calculations lead us to

A 1t A 2t = U AW = B + µI 0 0 T µ (9)
Using the Leibnitz formula, ( 5) can be rewritten as

ż1 (t) = -Bz 1 (t) + δ(B + µI) t t k ż1 (s)ds, ż2 (t) = -δµ t t k ż2 (s)ds. (10)
The consensus problem is now expressed into an appropriate form to perform stability criteria. In the case of a symmetric network, the matrix W is an orthogonal matrix which means

U = W T . Then if the last column of W is β -→ 1 , then U 2 = 1/(βN )
-→ 1 , which means that z 2 corresponds to the average of the position of all agents. This does not hold always for asymmetric communication network.

In the sequel, a stability analysis of the algorithm is proposed for any graph with a directed spanning tree, represented by the Laplacian L. Requiring a directed spanning tree is less stringent than requiring a strongly connected and balanced graph ( [START_REF] Ren | Distributed Consensus in Multi-vehicle cooperative Control: theory and applications[END_REF]). Also, an inherent assumption is that all agents are synchronized and share the same clock. This analysis is composed by two parts, one dealing with the stability of the algorithm and another concerning the agreement of the agents. More particularly, we will propose a method to choose appropriately the algorithm parameters δ and T for a given L, considering a performance optimisation.

III. DOES THIS ALGORITHM ALWAYS IMPROVE STANDARD PERFORMANCES?

Assume that the Laplacian graph corresponds to a symmetric graph. Let B be the diagonal matrix of the Laplacian eigenvalues defined before. We know that

B = -    λ i . . . 0 . . . . . . . . . 0 . . . λ N -1    . (11)
As seen previously, and for i ∈ [0, N -1] we have

ż1i (t) = (-λ i + δ(λ i + µ))z 1i (t) -δ(λ i + µI)z 1i (t k ). ( 12
)
For sake of simplicity, take b = δ(λ i + µ), and

ż1i (t) = (-λ i + b)z 1i (t) -bz 1i (t k ). (13)
By integrating the previous equation, we can have the following recurrence equation

z 1i (t k+1 ) = A(λ i , δ, T )z 1i (t k ), (14)
with A(λ i , δ, T ) = exp (-λi+b)T -λi -λi+b + b -λi+b . Note that system's ( 14) stability increases as A(λ i , δ, T ) decreases.

In this section we will prove that by varying δ and T values close to zero, we can achieve a performance improvement for ∀λ i , if

δA(λ i , δ, T ) δT ≤ 0, f or some δ values (15a) δA(λ i , δ, T ) δδ ≤ 0, f or some T values (15b)
From ( 14), by derivation of A(λ i , δ, T ), we have

δA(λ i , δ, T ) δT = (-λ i + b)e (-λi+b)T -λ i (-λ i + b) (16a) δA(λ i , δ, T ) δδ = T (λ i + µ)e (-λi+b)T -λ i (-λ i + b) -e (λi+b)T -λ i (λ i + µ) (-λ i + b) 2 + λ i + µ (-λ i + b) + b(λ i + µ) (-λ i + b) 2 (16b)
When we evaluate the previous equation for T ≃ 0 and for δ ≃ 0, respectively, we have

δA(λ i , δ, T ) δT = -λ i ≤ 0 (17a) δA(λ i , δ, T ) δδ = e -λiT (λ i + µ)(T + 1 λ i ) - λ i + µ λ i ≤ 0 (17b)
As δA(λi,δ,T ) δT = -λ i is negative semi-definite for all value of δ, and δA(λi,δ,T ) δδ is also negative semi definite for small values of T, we can then conclude that for small values of δ and T system (14) tends to converge rapidly when compare with the trivial algorithm. The pertinent problem of how to chose theses parameters values has been rased here, and will be treated in the next section.

IV. STABILITY ANALYSIS

A. Preliminary stability analysis

This section deals with the stability analysis of (8b). The following lemma holds.

Lemma 2: The system defined in (8b) is stable for any sampling period T and any δ. The variable z 2 is constant Proof: Consider k ≥ 0 and any t ∈ [t k t k+1 [ and any parameters T , δ. The previous ordinary differential equation has known solutions of the form

∀t, z 2 (t) = z 2 (0) (18)
z 2 (t) = e -δµ(t-t k ) C 0 -z 2 (t k ) (19)
where C 0 ∈ R represent the initial condition of the ordinary differential equation. The initial condition is determined at time t = t k . We then obtain C 0 = 0 and thus

∀t ∈ [t k t k+1 [, z 2 (t) = z 2 (t k ) (20)
Then, we deduce

z 2 (t k ) = z 2 (0)
which means that z 2 is constant

B. Stability analysis of the consensus algorithm

Consider the consensus algorithm (5) rewritten in the form of [START_REF] Muenz | Delay robustness in consensus problems[END_REF]. For z 1 dynamics analysis, we can establish

ż1 (t) = A(δ)z 1 (t) + A d (δ) ż1 (t k ), (21)
with A(δ) = (-B + δ(B + µI)) and A d (δ) = -δ(B + µI).

The following theorem holds based on the result of [START_REF] Seuret | A novel stability analysis of sampled-data systems with applications to multi-rate sampling and packet loss[END_REF]. Theorem 1: Consider the proposed consensus algorithm (5) associated to a given Laplacian L representing a communication graph with a directed spanning tree, a given α > 0, δ > 0 and T > 0.

Assume that there exist P > 0, R > 0 and S 1 and X ∈ S n and two matrices S 2 ∈ R n×n and N ∈ R 2n×n that satisfy

Π 1 + h α (T, 0)M T 2 XM 2 + f α (T, 0)Π 2 < 0, (22)
Π 1 + h α (T, T )M T 2 XM 2 g α (T, T )N * -g α (T, T )R < 0, ( 23
)
where

Π 1 = 2M T 1 P (M 0 + αM 1 ) -M T 3 (S 1 M 3 + 2S 2 M 2 ) -2N M 3 Π 2 = M T 0 (RM 0 + 2S 1 M 3 + 2S 2 M 2 ),
and

M 0 = A(δ) A d (δ) , M 1 = I 0 , M 2 = 0 I , M 3 = I -I .
The functions f α , g α and h α for all scalars T and τ ∈ [0 T ] are given by

f α (T, τ ) = (e 2α(T -τ ) -1)/2α, g α (T, τ ) = e 2αT (1 -e -2ατ )/2α, h α (T, τ ) = 1 α e 2αT -1 2αT -e 2ατ . ( 24
)
Then, the consensus algorithm ( 5) with the parameter δ and the sampling period T is thus α-stable. Moreover the consensus equilibrium is given by

x(∞) = U 2 x(0).
(25) Proof: Consider the consensus algorithm [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF]. Using Lemma 1, the algorithm is rewritten as [START_REF] Muenz | Delay robustness in consensus problems[END_REF]. The stability of the second equation (8b) is ensured based on the discrete time Lyapunov theorem. Consider α ∈ R and a positive definite matrix P ∈ R 2N which defines a Lyapunov function V for the discrete-time system defined by x k = x(t k ) given by V (k) = x T k P x k . The objective is to ensure that the increment ∆V α is negative definite ( [START_REF] Verriest | Stability analysis of linear systems with stochastically varying delays[END_REF]):

∆V α = V (k + 1) -e -2αT V (k) < 0.
We introduce here a novel type of functional for all t ∈

[t k t k+1 ]. W α (t, x t ) = f α (T, τ )ζ T 0 (t)[S 1 ζ 0 (t) + 2S 2 x k ] +f α (T, τ ) t t k ξ T (s)M T 0 RM 0 ξ(s)ds +H α (T, τ )x T k Xx k (26)
where

ζ 0 (t) = x(t) -x k , ξ(s) = [x T (s) x T k ] T and H α (T, τ ) = e -2ατ α τ T e 2αT -1 2α -e 2ατ -1 2α . Denote V (t, x t ) = x T (t)P x(t) + W α (t, x t ).
Consider a positive scalar 0 < ǫ < T and the functional W α at time t kǫ and t k + ǫ. Since ζ 0 (t k + ǫ) and f α (T k-1 , T k-1ǫ) tend to 0 as ǫ → 0 for all α > 0, the following equalities are satisfied

lim ǫ→0 W α (t k -ǫ, x t k -ǫ ) = lim ǫ→0 W α (t k + ǫ, x t k +ǫ ) = 0.
(27) This ensures that the extended functional V is continuous with respect to t at all sampling instants and differentiable over [t k t k+1 [ and W α (t k+1 , x t k+1 ) -W α (t k , x t k ) = 0. No additional constraint is introduced on S 1 and S 2 , W α is not necessary positive definite within two sampling instants. It yields

∆ α V (k) = V (t k+1 , x t k+1 ) -e -2αT V (t k , x t k ) = e -2αT t k+1 t k d e 2ατ (s) V (s, x s ) = e -2αT t k+1 t k e 2ατ (s) ( V (s, x s ) + 2α V (s, x s ))ds
The rest of the proof consists in ensuring Ṽ = V (s, x s ) + 2α V (s, x s ) < 0. From (24), we have, for all α ∈ R and for all τ ∈ [0,

T k ], ḟα (T, τ ) + 2αf α (T, τ ) = -1 and d dτ (e 2ατ H α 4) = h α 4. This leads to Ṽ (t, x t ) = 2x T (t)P ẋ(t) -ζ T 0 (t)[S 1 ζ 0 (t) + 2S 2 x k ] +2f α (T, τ ) ẋ(t) T [RM 0 ξ(t) + 2S 1 ζ 0 (t) + 2S 2 x k ] +h α (T, τ )x T k Xx k + 2αx T (t)P x(t) - t t k ξ T (s)M T 0 RM 0 ξ(s)ds.
(28) Consider a matrix N ∈ R 2n×n and the following equality

2N [x(t) -x k ] = t t k [2N ẋ(s)] ds = t t k [2N M 0 ξ(s)] ds.
(29) Since R > 0 and consequently non singular, a classical bounding ensures that for all t ∈ [t k , t k+1 [ and for all s

∈ [t k , t] 2ξ T (t)N M 0 ξ(s) ≤ ξ T (t)N R -1 N T ξ(t) + ξ T (s)M T 0 RM 0 ξ(s).
Integrating the previous inequality over [t k , t], the following inequality is obtained

- t t k ξ T (s)M T 0 RM 0 ξ(s)ds ≤ -2ξ T (t)N [x(t) -x k ] +τ ξ T (t)N R -1 N T ξ(t), (30)
Noting that

ẋ(t) = Ax(t) + A d x(t k ) = M 0 ξ(t), x(t) = M 1 ξ(t), x(t k ) = M 2 ξ(t), ζ 0 (t) = x(t) -x(t k ) = M 3 ξ(t),
and adding (30) to (28), the following inequality is obtained for all

t ∈ [t k , t k+1 [ Ṽ (t, x t ) ≤ ξ T (t)[Π 1 + f α (T, τ )Π 2 + τ N R -1 N T ]ξ(t).
(31) The previous inequality does not depend linearly on τ but on both τ and a non linear function of τ , f α (T, τ ).

The solution proposed here is to use the convexity property of the exponential function ensuring that e 2ατ ≥ 1 + 2ατ . Consequently, the following upper-bound is obtained τ ≤ (e 2ατ -1)/2α ≤ e 2ατ (1e -2ατ )/2α, ≤ g α (T, τ ).

Since R, consequently R -1 is positive definite, we have

Ṽ (t, x t ) ≤ ξ T (t)[Π 1 + f α (T, τ )Π 2 + g α (T, τ )N R -1 N T ]ξ(t).
To prove that Ṽ is negative definite for all τ , a convexity property is employed. Since the previous inequality is linear with respect to τ , it is necessary and sufficient to ensure the negativity at the edges. This leads to

Π 1 + f α (T, 0)Π 2 < 0, Π 1 + g α (T, T )N R -1 N T < 0.
This leads to ( 22) and (23) using the Schur complement. The global algorithm ( 8) is then exponentially stable with a decay rate α. Moreover, z 1 → 0 and z 2 → z 2 (∞), and thus the consensus equilibrium is

x(∞) = W z 2 (∞) = [W 1 -→ 1 ] 0 n-1×1 z 2 (∞) = z 2 (∞) -→ 1 .
The proof is concluded by noting that z 2 = U 2 x and that z 2 (∞) is expressed in (18)

V. EXAMPLES

Cooperative control of under-water vehicles network under varying-topology and communications constraints have been studied in order to implement the proposed algorithms. Consider a set of six and four agents connected through, respectively, the undirected and directed graphs shown in Figure 2.

To each graph is associated a Laplacian matrix given by

L 0 =        
-1 0.5 0 0.5 0 0.5 0.5 -1 0.5 0 0 0 0 0.5 -1 0.5 0 0 0 0 0.5 -1 0.5 0 0 0 0 0.5 -1 0.5 0.5 0 0 0 0.5 -1

        , L 1 =     -1 1 0 0 0 -1 1 0 0 0 -1 1 1 0 0 -1     .
For simulations purposes we took as initial conditions: x T 0 (0) = [30 25 15 0 -10 -20] and x T 1 (0) = [30 25 15 0]. Those two graphs are balanced, witch implies that consensus equilibrium value will be defined as the average of initial conditions presented just before.

The objective is to find the highest value for α (on the vertical axis) that guarantees algorithm (5) convergence. Figure 3, as a 3-D representation of α stability results, shows the maximum convergence rate satisfying Theorem 1 for several values of δ and T , and for L 0 and L 1 , with T ∈ [0, 1.5]s and δ ∈ [0, 2]. We can identified a crest for specific values of (δ, T ) meaning a improved behavior, and the best positive value of α is obtained when (δ,T)=(2;0.32) and (δ,T)=(2;0.2), for graph G 0 and graph G 1 respectively.

The stability conditions proposed in this article are sufficient but not necessary conditions. Optimality is obtained for a certain value of (δ, T ), and once it changes, this leads to a reduction of performances, as it will be shown in the following.

Figure [START_REF] Dimarogonas | A connection between formation infeasibility and velocity alignment in kinematic multi-agent systems[END_REF] shows simulations of the classical algorithm (3) as well as from the algorithm (5) considering L 0 , L 1 , and for several values of δ and T . The aim here is to compare systems performances with two different approaches and justify the interest of the proposed algorithm. Figure 4(a-b) show simulation results of the classical consensus algorithm. Figure 4(c-d) show simulation results using the optimal pair (δ,T) according to Theorem 1 and recovered on Figure 3.We can see that they correspond to a faster algorithm when compared with the trivial algorithm. In Figure 4(e-f), we kept the optimal value of T and changed δ value. Finally, for Figure 4(g-h), we kept the optimal value of δ and changed T value. In 4(c-d-e-f) we can then see that convergence rate decreases when compared to the others results. It's also possible to observe that the agreement value for the modified algorithm remains the average of the initial conditions.

VI. CONCLUSION

The influence of a sampled delays in consensus algorithms for simple integrator agents have been studied. An optimisation of controller parameters is proposed so that exponential stability of the solutions is achieved based on discrete-time Lyaponov Theorem and expressed in terms of LMI. Also, conditions for improved performances based on Laplacian's eigenvalues are provided here. Simulation results show the efficiency of the proposed algorithm, as well as the conservation of averaging properties. Further work might include asynchronous study of such systems.

Fig. 1 .

 1 Fig. 1. Corresponding schema for the proposed algorithm.

Fig. 2 .

 2 Fig. 2. Corresponding graphs of the matrices L 0 and L 1 .

decay rate for G 1 Fig. 3 .

 13 Fig. 3. Convergence rate of the consensus algorithm for several values of (δ, T ) and for the communication graphs G 0 and G 1 .

Fig. 4 .

 4 Fig. 4. System's behavior for different settings

This work was supported by the European Project FeedNetBack: http://www.feednetback.eu/.


Lara Briñón Arranz
email: lara.brinon-arranz@inrialpes.fr

Alexandre Seuret
email: alexandre.seuret@gipsa-lab.grenoble-inp.fr

Carlos Canudas De Wit
email: carlos.canudas-de-wit@gipsa-lab.grenoble-inp.fr

Collaborative Estimation of Gradient Direction by a Formation of AUVs *

Keywords: Multi-agent systems, collaborative control, gradient estimation

This work deals with the source-seeking problem in which the task is to locate the source of some signal using a fleet of AUVs (autonomous underwater vehicles). The present paper proposes a distributed solution in which a group of vehicles uniformly distributed in a fixed circular formation, estimates the gradient direction of the signal propagation. The distributed algorithm takes into account the communication constraints and depends on direct signal measurements. Our approach is based on the previous results in formation control to stabilize the fleet in a circular formation with time-varying center and in a collaborative sourceseeking algorithm. The results are supported through computer simulations.

INTRODUCTION

Cooperative control problems and multi-agent systems have received much attention in recent years. The field includes consensus algorithms for multi-agent systems [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF][START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF], flocking [START_REF] Olfati-Saber | Flocking for multi-agent dynamic systems: Algorithms and theory[END_REF], distributed sensor networks [START_REF] Ögren | Cooperative control of mobile sensor networks: Adaptive gradient climbing in a distributed environment[END_REF][START_REF] Zhang | Cooperative filters and control for cooperative exploration[END_REF], and autonomous systems as underwater and unmanned air vehicles (AUVs and UAVs) [START_REF] Leonard | Collective motion, sensor networks and ocean sampling[END_REF][START_REF] Raffard | Distributed optimization for cooperative agents: Application to formation flight[END_REF]. Cooperative formation control and motion coordination have been extensively studied, see [START_REF] Fax | Information flow and cooperative control of vehicle formations[END_REF][START_REF] Sarlette | Coordinated motion design on Lie groups[END_REF][START_REF] Martínez | Motion coordination with distributed information[END_REF][START_REF] Ögren | A control lyapunov function approach to multiagent coordination[END_REF], among many others. Control laws have been provided to make a fleet of agents (vehicles) obtain circular and parallel formations [START_REF] Leonard | Collective motion, sensor networks and ocean sampling[END_REF][START_REF] Sepulchre | Stabilization of planar collective motion with limited communication[END_REF]. Many extensions based on these works have been developed: three-dimensional formation control [START_REF] Scardovi | Stabilization of collective motion in three dimensions[END_REF][START_REF] Hernandez | Three-dimensional motion coordination in a time-invariant flowfield[END_REF], planar circular formation control in a flow-field [START_REF] Paley | Stabilization of collective motion in a time-invariant flowfield[END_REF], and stabilization of a fleet to other closed forms [START_REF] Paley | Stabilization of symmetric formations to motion around convex loops[END_REF][START_REF] Briñón | Elastic formation control based on affine transformations[END_REF].

In [START_REF]Translation control of a fleet circular formation of AUVs under finite communication range[END_REF], a new control law is proposed to translate a circular * This work was supported by EU STREP project FeedNet-Back FP7-ICT-2007-2.

formation following a desired external reference trajectory of its center. Designing a collaborative reference to move the formation is a first step to achieve the source location of some signal. For example, the source could be a point of chemical contamination and the signal would be that chemical's concentration in the environment. The objective of the source-seeking problem is to obtain the direction to steer the formation towards the source by a cooperative algorithm using the concentration measurements of the agents.

There exist many different approaches to resolve the sourceseeking problem in the literature. The extremum seeking problem is solved under different hypotheses using a single nonholonomic vehicle, [START_REF] Krstic | Stability of extremum seeking feedback for general nonlinear dynamic systems[END_REF][START_REF] Cochran | Source seeking with a nonholonomic unicycle without position measurements and with tuning of angular velocity Part I: Stability analysis[END_REF]. In this case all the measurements would come from a single vehicle as it changes position over time. Another strategy consists in approximating the gradient value of the signal using concentration measurements of multiple vehicles at different locations [START_REF] Ögren | Cooperative control of mobile sensor networks: Adaptive gradient climbing in a distributed environment[END_REF]. Some collaborative methods have been proposed, based on distributed estimation of the concentration plume [START_REF] Sahyoun | Dynamic plume tracking using mobile sensors[END_REF][START_REF] Rabbat | Distributed optimization in sensor networks[END_REF]. In theses cases, the fonction signal is estimated or approximated and the source localization becomes a distributed optimization problem.

The work presented in [START_REF] Moore | Source seeking via collaborative measurements by a circular formation of agents[END_REF] deals with a collaborative multiagent algorithm to solve the source seeking problem using only direct signal measurements by a circular formation of agents. This new approach considers all-to-all communication (i.e. every agent talks to every other agent) between the agents and the control law needs the information of all the agents to converge. Our objective now is to design a collaborative algorithm based on this previous one but considering restricted communication. The present paper adresses another possible solution to the source localisation problem. We show how a group of vehicles uniformly distributed in a circular formation, is able to approximate the gradient direction of the signal propagation to steer the formation towards the source location. The signal propagation, which will be considered here, is either constant or time-varying. In order to achieve this objective under limited communication, each agent estimates its own direction based on its neighbors' concentration measurements. We include a consensus algorithm to converge to the same desired gradient direction. In literature there are some results in the field of consensus filters and sensor fusion [START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF][START_REF] Zhang | Cooperative filters and control for cooperative exploration[END_REF] which deal with the consensus problem of a sensor network measuring a signal corrupted by noise. These approaches could be applied to reduce the noise propagation and to cooperative exploration missions.

This paper is organized as follows. First, Section 2 recalls previous work on translation control of a circular formation. Section 3 presents a result on gradient approximation and the problem formulation. In Section 4, we propose a first algorithm for the case of constant signal distribution that combines standard consensus tools, and show its limitations both by theoretical convergence analysis and simulations. Then, Section 5 refines the previous approach by introducing an improved estimation algorithm based on averaging. Section 6 deals with the case of time-varying signal distributions. Conclusions and future works are presented in Section 7.

Notation. Let G = (V, E) be an undirected graph with an adjacency matrix A = [a kj ] that specifies the communication topology of the multi-agent system: a kj = 1 if agents k and j ∈ V communicate, else a kj = 0. The set of nodes (agents) is denoted by

V = {1, . . . , N }. Let N k = {k ∈ V : a kj = 0} the set of neighbors of agent k and J k = N k ∪ {k}. The Laplacian matrix L of graph G is defined as L = ∆ -A
where ∆ is the diagonal matrix which contains the degree of each agent, i.e. ∆ kk = d k = j a kj . In the sequel, ⊗ denotes the Kronecker product and, for simplicity, we define M2 = M ⊗ I2 where M is a square matrix and IN is the identity matrix of order N . Moreover, R π 2 ∈ R 2×2 denotes the rotation matrix counterclockwise through an angle π 2 .

BACKGROUND

The algorithm to estimate the gradient direction of a signal distribution presented in this paper builds on the previous result on formation control [START_REF]Translation control of a fleet circular formation of AUVs under finite communication range[END_REF]. Consider a group of N agents modeled as kinematic unicycle vehicles of the following form, for each vehicle k:

ẋk =v k cos θ k (1a) ẏk =v k sin θ k (1b)
where r k = (x k , y k ) T is the position vector, θ k is the heading angle, and the control inputs are the vehicle's forward velocity v k > 0 and turning rate θk , see [START_REF]Translation control of a fleet circular formation of AUVs under finite communication range[END_REF]. With appropriate limits on the control inputs, this model can provide a reasonable approximation for many air and underwater vehicles.

Stabilization of a fleet of N agents to a circular formation around its center of mass was developed in [START_REF] Leonard | Collective motion, sensor networks and ocean sampling[END_REF]. In [START_REF]Translation control of a fleet circular formation of AUVs under finite communication range[END_REF] a control law which asymptotically stabilizes the vehicles to a circular formation around a dynamic center point c(t) = (c x , c y ) T with a uniform distribution (i.e. with the agents evenly separated on the circle by 2π/N radians each) is presented. The center of the formation c(t) is an external reference known for all the agents. With a fixed radius R > 0, desired rotational velocity ω 0 and the control param-eters κ > 0 and K, the control law of [START_REF]Translation control of a fleet circular formation of AUVs under finite communication range[END_REF] is given as:

v k = R|ω 0 |(cos ψ k , sin ψ k ) T + ċ θk = 1 - ṙT k ċ v 2 k ψk - ṙT k R π 2 c v 2 k ψk = ω 0 (1 + κR|ω 0 |(cos ψ k , sin ψ k )(r k -c)) - ∂U ∂ψ k U (ψ) = - K N N/2 m=1 1 2m 2 a T m L2am (2)
where N/2 is the largest integer less than or equal to N/2, am = (cos mψ1, sin mψ1, . . . , cos mψN , sin mψN ), L is the Laplacian matrix associated with the communication network of the vehicles, and ψ k (t) is an inner state of the dynamic controller, and initialized to

ψ k (0) = arctan ẏk (0) -ċy (0) ẋk (0) -ċx(0) + k π
where k = 0 if ẋk (0) -ċx (0) > 0 and k = 1 otherwise.

Assuming that c(t) is twice differentiable, has bounded first and second time-derivatives, and satisfies sup t≥0 | ċ(t)| < R|ω0|, then the control law above drives the vehicles to trajectories that lie on the circle with radius R and whose center follows the time-varying external reference c(t). Moreover, if K > 0 and a geometric ring communication graph (i.e. each agent is linked to its two closest neighbors on the circle) is assumed, then the vehicles will be uniformly distributed on that circle.

Consider now the stable circular formation described by a center point c, a radius R and an angle φ which is linearly increasing with time (i.e. φ = ω 0 t for some angular speed ω 0 > 0. Therefore, the position of each agent k is given by the following equation:

x k = cx + R cos φ + k 2π N y k = c y + R sin φ + k 2π N (3)
This equation describes a formation where the agents are uniformly distributed on a circle of radius R. In the context of source-seeking problem, the objective is that the center of the formation c(t) follows a trajectory which converges to the maximum of a signal, that is usually its source. Using this previous work on formation control, a first result in collaborative source-seeking is accomplished in [START_REF] Moore | Source seeking via collaborative measurements by a circular formation of agents[END_REF]. The authors consider here a stable circular formation of N mobile agents in the plane. The agents are stabilized by the previous control law [START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF]. The authors provide an outer-loop control that steers the formation by determining ċ(t) in a collaborative way. This control law allows the formation to move such that its center converges to the source location, if the signal distribution decreases around the source in such a way that level sets are circles or ellipses centered on source location. The main constraint of the algorithm of [START_REF] Moore | Source seeking via collaborative measurements by a circular formation of agents[END_REF] is the all-to-all communication assumption.

PROBLEM FORMULATION

The objective of this work, is to estimate the gradient direction of the source distribution based on the concentration

ω 0 r 1 -c r 2 -c r 4 -c r 3 -c SOURCE u * Figure 1: Problem formulation
measurements obtained by a circular formation of agents taking into account the communication contraints. This estimated direction will be the reference velocity of the formation center in order to steer the group of agents to the source location.

Consider a fleet of N vehicles uniformly distributed along a circular formation. The position of each agent k is described by equation (3). Our approach considers that the circular formation is not moving. Only the estimation of gradient direction is addressed here.

Assumption 1 For the following, we suppose that the center of the circular formation c is fixed and known to all the agents.

The distribution of the signal strength in the environment will be described by an unknown positive spatial mapping ρ : R 2 → R + , and so agent k measures the signal strength at its position as ρ(r k ). Our approach deals with the approximation of the gradient direction of this signal distribution ρ by a circular formation of agents at a given location c, see Fig. 1.

Gradient Approximation

Consider a fleet of agents given by (3) taking measurements of a signal distribution ρ.

Let ∇ρ(c) = (∇ x ρ(c), ∇ y ρ(c))
denote the gradient of function ρ in the center of the circular formation. The following Lemma is proposed:

Lemma 1 Let ρ be a bounded function and ρ(r k ) the measure obtained by agent k where r k is its position vector given by (3). If Assumption 1 is satisfied and the agents are uniformly distributed in the circle centered at c, then: (i) Considering a fleet of N > 2 agents the following equation is satisfied:

1 N N k=1 ρ(r k )(r k -c) = R 2 2 ∇ρ(c) T + o(R 2 ) ( 4
)
(ii) Considering only one agent moving along the circular formation, the following equation is satisfied:

1 T T 0 ρ(r(w0t))(r(w0t) -c)dφ = R 2 2 ∇ρ(c) T + o(R 2 ) ( 5
)
where T = 2π/w 0 Proof. In both cases (i) and (ii) the uniform distribution of the agents along a fixed circle is assumed, then N k=1 (r kc) = 0 and 2π 0 (r k -c)dφ = 0 respectively. By definition of gradient of the function ρ at a fixed location c the following equation holds:

ρ(r k ) -ρ(c) = ∇ρ(c)(r k -c) + o(R) (6)
Multiplying this previous equation by the relative vector (r k -c) and summing over k = 1, . . . , N , it yields:

1 N N k=1 ρ(r k )(r k -c) = 1 N N k=1 [∇ρ(c)(r k -c)](r k -c) + o(R 2 )
Analyzing in terms of components and using (3) to express the position of the agents r k , the right-hand side of the previous equation is given by:

R 2 N N k=1 ∇ x ρ(c) cos 2 φ k + ∇ y ρ(c) cos φ k sin φ k ∇ x ρ(c) sin φ k cos φ k + ∇ y ρ(c) sin 2 φ k where φ k = φ + k 2π N .
Thanks to the uniform distribution if N > 2 then N k=1 cos (2k 2π N ) = 0 (the same equality also holds for the sinus) and trigonometric properties ensure that:

1 N N k=1 [∇ρ(c)(r k -c)](r k -c) = R 2 2 ∇ρ(c) T
Thus, the equality (4) is satisfied.

A similar analysis can be applied to second case (ii). Using trigonometric properties, integrating along the circle (in the interval [0, 2π]) and thanks to the equality 2π 0 cos φdφ = 0 (the same equality also holds for sin φ) we obtain the following equation:

1 T T 0 [∇ρ(c)(r(w0t) -c)](r(w0t) -c)dt = R 2 2 ∇ρ(c) T (7)
and equality ( 5) is straightforwardly obtained.

This result provides an approximation of gradient of the signal distribution at the center of the circular formation.

Problem Formulation

Our objective is to develop a distributed algorithm to estimate the gradient direction of the signal distribution ρ at the center of a circular formation of agents.

The communication contraints are taken into account through a communication graph G. Due to these communication restrictions each agent estimates its own gradient direction z k using the information of its neighbors according to the communication topology. The objective is to make all estimated directions z k converge to the mean direction defined as:

u * = 1 N N k=1 u k ; u k = ρ k (r k -c) (8)
where u k is the relative position vector of agent k weighted by its concentration measurement ρ k = ρ(r k ). Thanks to Lemma 1 (i), this mean vector u * approximates the gradient direction of the signal distribution at the center of the formation c. A consensus algorithm is implemented to obtain the same estimated gradient direction of the signal distribution for all the agents.

COLLABORATIVE ESTIMATION OF GRADIENT DIRECTION 4.1 Consensus algorithm

Consensus filters for sensor networks are developed in [START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF]. In this work, the authors consider a sensor network of size N with information flow (communication graph) G. Each sensor k measures the same signal that is corrupted by noise. Based on this approach for sensor networks, we propose the following consensus algorithm for the multi-agents system to estimate the gradient direction of the signal propagation by a fixed circular formation in a collaborative way:

żk = κ j∈N k a kj (z j -z k ) + j∈J k a kj (u j -z k )
where κ > 0 is a control parameter which is introduced to make the algorithm more flexible. The consensus variable is the vector z k ∈ R 2 which represents the estimated gradient direction by agent k. The input u k = ρ k (r k -c) ∈ R 2 , depends on the concentration measurements and the position of the agent in the formation. Therefore, the input of the algorithm is not the same signal corrupted by noise, but a different vector for each agent. This is the main difference with respect to the consensus filter algorithm.

Using the Laplacian matrix of the communication topology of the multi-agents system the previous equation can be rewritten in a matrix way:

ż = -κL ⊗ I2z + IN ⊗ I2(u -z) + A ⊗ I2u -∆ ⊗ I2z = -(I N + ∆ + κL) 2 z + (I N + A) 2 u
where z = (z T 1 , z T 2 , . . . , z T N ) T and u = (u T 1 , u T 2 , . . . , u T N ) T are vectors of dimension 2N , and I N the identity matrix of order N . Let A κ = (I N + ∆ + κL) 2 , and B = (I N + A) 2 . Note that by definition, Aκ is a positive definite matrix. Then, the previous equation becomes:

ż = -Aκz + Bu (9)
Consider the vector of dimension 2N , u * = 1⊗u * , where 1 = (1, . . . , 1) T ∈ R 2 is the vector of ones that is always a right eigenvector of L corresponding to the eigenvalue 0. Then the error equation is η = z -u * . Using [START_REF] Sarlette | Coordinated motion design on Lie groups[END_REF], the dynamics of the error can be written as:

η = -A κ η + B(u -u * ) -u *
The stability of this algorithm is analyzed using the Lyapunov function V = 1 2 η T A κ η. Differentiating this function we obtain:

V = -η T A T κ Aκη + (u -u * ) T B T Aκη -u * T Aκη Let u * ≤ ν,
due to the soft variation of the concentration levels of the signal distribution considered here, then

V ≤ -λ 2 min (Aκ) η 2 + ν √ 2N (1 + dmax) η + (u -u * ) T B T A κ η This is because u * T Aκ = 1 T ⊗ u * T (IN + ∆ + κL)2 = (1 + d 1 , . . . , 1 + d N ) ⊗ u * T and thus u * T A κ ≤ u * 2 N k=1 (1 + d k ) 2 ≤ ν √ 2N (1 + d max )
It is plausible to assume that a bound on maximal signal concentration is known from the problem setting. Therefore, (u-u * ) ≤ α where α depends on the radius of the circular formation and on the greatest concentration measurement obtained by the agents. For simplicity, let γ be a bound of the following matrix norm B T A κ ≤ γ. Taking these considerations into account the following equation holds:

(u -u * ) T B T Aκ ≤ αγ
The derivative of the Lyapunov function is bounded by:

V ≤ -λ 2 min (A κ ) η 2 + ν √ 2N (1 + d max ) + αγ η
Based on the proof of Proposition 2 in [START_REF] Olfati-Saber | Consensus filters for sensor networks and distributed sensor fusion[END_REF] a closed ball B β centered at η = 0 is defined with radius

β = ν √ 2N (1 + d max ) + αγ λ 2 min (Aκ) Let Ωm = {η : V (η) ≤ m} be a level set of the Lyapunov function V (η) with m = 1 2 λmax(Aκ)β 2 . Then, B β is con- tained in Ω c because η ≤ β =⇒ V (η) = 1 2 η T Aκη ≤ 1 2 λmax(Aκ)β 2 = m,
and thus η ∈ Ωm. As a result, any solution of (10) starting in R 2N \Ωm satisfies V < 0. Thus, it enters Ωm in some finite time and remains in Ωm thereafter. This guarantees global asymptotic -stability of η = 0 with a radius = βλ max (A κ )/λ min (A κ ). To show this, note that

1 2 λ min (A κ ) η 2 ≤ V (η) ≤ 1 2 λ max (A κ )β 2
Thus, the solutions enter the region

η ≤ β λmax(Aκ) λ min (A κ )
which implies the radius of -stability is

= ν √ 2N (1 + d max ) + αγ λ 2 min (A κ ) λ max (A κ ) λ min (A κ )
-stability of η = 0 implies -tracking of the mean vector u * by every agent, therefore -consensus is asymptotically reached.

After the previous detailed analysis this result can be presented as a Theorem: ν. Then, z * (t) = 1 ⊗ u * is a globally asymptoticallystable equilibrium of the dynamics of the distributed algorithm given by

ż = -κL 2 z -L 2 u + (I N + ∆) 2 (u -z) ( 10
)
with u = (ρ1(r1 -c) T , . . . , ρN (rN -c) T ) T and = (ν √ 2N (1 + dmax) + αγ)λ 1 2 max (Aκ) λ 5 2
min (Aκ) where the matrix Aκ and the constants α and γ are previously defined.

Remark 1 Analyzing the linear system (9) it seems evident that the control parameter κ has an important role in the convergence velocity of the algorithm. The simulation results show that taking κ >> 1 the amplitude of oscillations of the estimated gradient directions z k are smaller. Therefore, the error η is also reduced. However, the analysis of this property is still under investigation.

Simulations

In this section we present simulations results of the previous algorithm. All simulations show a circular formation of five agents with radius R = 1m and angular velocity of ω0 = 1rad/s. The communication graph is a ring.

In Fig. 2 and3, the source-seeking consensus algorithm [START_REF] Martínez | Motion coordination with distributed information[END_REF] from Theorem 1 is implemented with κ = 50. For these simulations, the function ρ representing the signal distribution centered at the origin has circular level sets,

ρ(x, y) = 100e -(x 2 +y 2 )/10
. Therefore, the gradient vector ∇ρ(c) provides the adequate direction to steer the formation to the source location. Both figures (a) show two snapshots. The void circles represent the initial conditions and the black dashed lines the initial estimated direction z k of each agent. The red circles represent the position of the agents at t = 50s and the red lines are the estimated gradient directions at that time. The blue line is the real direction of the gradient at center c. Both figures (b) show the components of the consensus variable z k and the mean vector u * . The estimated directions z k oscillate around the vector u * which approximates the true gradient direction for any initial conditions. In Fig. 2 the circular formation is centered at c = (2, 2) and the oscillations of the estimated gradient directions z k are smaller than in Fig. 3 where the formation is centered at source location. In this second case, as the mean of the directions is equal to zero, the convergence region of radius leads to completely wrong gradient direction estimations.

Conclusions and limitations of the algorithm

The final gradient direction z k estimated by each agent oscillates with period T = 2π/ω 0 . The amplitude of these oscillations depends on the concentration measurements ρ k .

When the formation is closer to the source location, the measurements are greater, thus, the amplitude of oscillations are greater as well. Moreover, as the gradient is closed to zero in the neighborhood of the source (at least with the Gaussian profile we use), a ball of radius around 0 leaves the gradient direction essentially unknown; thus Theorem 1 does not guarantee good behavior in the neighborhood of the source.

Another limitation of the previous consensus algorithm [START_REF] Martínez | Motion coordination with distributed information[END_REF] is that the radius depends on the constants α and γ which cannot necessarily be small values. In order to avoid these problems, an averaging approach is presented in the following section.

REFINED COLLABORATIVE ESTIMA-TION OF GRADIENT DIRECTION RE-SULT

The previous section presents a collaborative algorithm, which uses the concentration measurements obtained by a formation of agents to estimate the gradient direction of a signal distribution in its center.

The agents describe a periodic movement, it means that r k (t) = r k (t + T ) with T = 2π/ω0. Therefore, the measurements ρ k obtained by agent k is a periodic map because ρ(r k (t)) = ρ(r k (t + T )). In conclusion, the input variable of the consensus algorithm u k = ρ k (r k -c) is a T -periodic function with T = 2π/ω 0 . Estimated directions z k obtained by the consensus algorithm [START_REF] Martínez | Motion coordination with distributed information[END_REF] shown in Fig. 2 and 3 are also periodic. The average of these solutions approximates the gradient direction of the source. Thanks to these observations, an analysis of the average properties of the input variable u k seems adequate. In this section, the previous distributed consensus algorithm is improved using the periodic properties of the measurements ρ(r k ).

Estimation Algorithm using time-average inputs

We present an improved estimation algorithm based on the periodic properties of the input u k . The input vector u k in previous consensus algorithm is replaced by its mean value over one period T = 2π/ω 0 which is defined as:

u k = 1 T t t-T ρ k (r k (τ ) -c)dτ (11)
Therefore, thanks to Lemma 1 (ii) the new mean vector u * approximates the gradient of the signal propagation ρ in the center of the circular formation:

u * = 1 N N k=1 u k (12)
The new input variable of the improved algorithm based on [START_REF] Martínez | Motion coordination with distributed information[END_REF], is the mean vector u = (u T 1 , u T 2 , . . . , u T N ) T , and the objective is defined as u * = 1 ⊗ u * . Following the analysis developed in section 4.1, let us assume that the following inequality (u-u * ) ≤ α is satisfied. Using these considerations, a new algorithm is proposed in the following theorem:

Corollary 1 Consider a circular formation of N agents defined by (3) with a connected communication graph G and Assumption 1 is satisfied. Let ρ : R 2 → R + be a bounded fonction and the mean vector u * defined in [START_REF] Sepulchre | Stabilization of planar collective motion with limited communication[END_REF] satisfies u * ≤ ν. Then, z * (t) = 1 ⊗ u * is a globally asymptotically -stable equilibrium of the dynamics of the distributed algorithm given by

ż = -κL 2 z -L 2 u + (I N + ∆) 2 (u -z) (13) with = (ν √ 2N (1 + dmax) + αγ)λ 1 2 max (Aκ) λ 5 2 min (A κ )
Remark 2 Considering Assumption 1 (the circular formation is fixed) by definition, the mean input u is a constant vector after a time period T . Therefore, the input variable u converges to the mean vector u * and moreover, its derivative is equal to zero. Then, ν → 0 and α → 0. It implies that the radius of the convergence region converges to zero after a period T , the consensus is achieved and all the agents estimate the mean vector u * which approximates the gradient direction at the center of the formation.

Remark 3

The gradient direction estimated by the agents will be the velocity reference of the formation center to steer the fleet of agents to the source location. If the formation is moving, the gradient of the signal distribution in the circle center becomes time-varying and the concentration measurements does not satisfy the periodic properties anymore. Therefore, the consensus algorithm makes that the agents would estimate the gradient direction before a period T . A detailed investigation of our algorithms when the formation moves along the estimated gradient direction towards the source location is our next research goal.

Simulations

The simulations show the same circular formation of five agents from the previous simulations. In Fig. 4 and5 the improved distributed algorithm (13) from Corollary 1 is implemented with κ = 1 by a circular formation centered at c = (2, 2) T and at source location, respectively. The measured signal is the same as in previous simulations. Due to the circular level sets of the signal propagation the gradient vector ∇ρ(c) provides the adequate direction to steer the formation to the source location. Both figures (a) show two snapshots, the initial conditions and the stable situation at t = 50s. Both figures (b) show the components of consensus variable z k . This algorithm allows to remove the oscillations and the final vectors z k (red lines) are parallel to the gradient direction for all the agents (blue line). The problem of oscillations when the formation is centered at source location is also solved and the final directions z k are equal to zero, i.e. the formation decides to stay in the desired location. The estimated directions z k converge to the gradient direction approximated by the mean vector u * for any initial conditions.

In Fig. 6 the same algorithm ( 13) is implemented with an elliptical signal distribution defined by ρ(x, y) = 100e -(x 2 /10+y 2 /2)/10 . The estimated directions z k converge to the gradient direction ∇ρ(c). In this case, this direction will not directly steer the formation to the source location, but a formation moving along the respective gradient direction will be progressively steered towards the source over several consecutive steps.

COLLABORATIVE GRADIENT ESTIMA-TION OF TIME-VARYING SIGNAL DIS-TRIBUTION 6.1 Gradient approximation

In this section, we assume that the signal distribution ρ depends both on the position and on time, i.e. ρ(r k , t). Consider a fleet of agents given by (3) taking measurements of a signal distribution ρ. An extension of the previous Lemma 1 is proposed in the sequel to cope with this time-varying signal distribution.

Lemma 2 Let ρ be a bounded function and ρ(r k , t) the measure obtained at time t by agent k, where r k is its position vector given by (3). If Assumption 1 is satisfied and the agents are uniformly distributed in the circle centered at c, then for a fleet of N > 2 agents, the following equation is satisfied: Proof. The proof is similar to the one of Lemma 1(i).

1 N N k=1 ρ(r k , t)(r k -c) = R 2 2 ∇ρ(c, t) T + o(R 2 ) (14)
A direct consequence of the previous lemma is that the distributed estimation algorithm from Theorem 1 with the u k 's defined in (8) also holds for time-varying signal distribution.

However the extension of the case (ii) from Lemma 1 to time-varying signal distributions is not straightforward. Indeed, if the signal distribution depends on the time variable, equation ( 7) is not valid anymore.

Simulations

The same circular formation of five agents from the previous simulations is still considered. Figure 7 shows the simulation results of the gradient estimation of a time-varying signal distribution. The distribution is given by ρ((x, y), t) = 100e -((x-2cos(t/10)) 2 +y 2 )/10

In order to compare the directions of the effective gradient and of the resulting estimations, we consider the angle (in radians) between the ∇ρ(c, t) T (and z k , respectively) and (1, 0) T . In Figure 7 (a), one can see that each estimated direction, obtained by the algorithm [START_REF] Martínez | Motion coordination with distributed information[END_REF] with κ = 100, oscillates around the effective gradient direction with an amplitude as in Theorem 1. Figure 7 (b) shows the same situation but implementing the algorithm from Corollary 1 with κ = 100. In this case, a consensus on the estimates is clearly reached. However there exists an error between the estimated direction and the effective one. Figures 8 and9 show three snapshots of of the previous simulations. They shows the difference between the resulting estimates from Theorem 1 and Corollary 1. As a conclusion, the gradient estimation by using a uniform distributed formation agent appears as a more accurate solution when the signal distribution becomes time-varying.

CONCLUSIONS

This paper presents a cooperative multi-agent algorithm to estimate the gradient direction of a signal distribution. This distributed algorithm uses the concentration measurements of the signal obtained by a group of vehicles uniformly distributed in a fixed circular formation. Our approach takes into account the communication constraints of the network, avoiding the case of all-to-all communication. To achieve this objective, a first distributed consensus algorithm based on instantaneous sensor measurements is presented. Then, we propose an improved algorithm based on the average inputs. For time-invariant signal distributions, we note that if the formation is fixed, this second algorithm reaches exact consensus and converge to the gradient direction at the formation center.

However, when the signal distributions become time-varying, we show that the first algorithm is still valid whereas the analysis of the the second one leads to additional difficulties. In simulations, we indeed show that the first one seems more promising than the second one.

This analysis requires that formation is fixed. Our final ob- jective is to use this estimated direction to locate the source. Then, our next research aim is to analyze and improve these algorithms when the formation moves along the estimated gradient direction towards the source location.

Theorem 1 Figure 2 :

 12 Figure 2: Simulation of a circular formation of five agents centered at c = (2, 2) T . The function ρ representing the signal distribution centered at the origin has circular level sets. The consensus algorithm of Theorem 1 is implemented with κ = 50.

Figure 3 :

 3 Figure 3: Simulation of a circular formation of five agents centered at c = (0, 0) T . The function ρ representing the signal distribution centered at the origin has circular level sets. The consensus algorithm (10) is implemented with κ = 50.

Figure 4 :

 4 Figure 4: Simulation of a circular formation of five agents centered at c = (2, 2) T . The function ρ representing the signal distribution centered at the origin has circular level sets. The mean input consensus algorithm (10) is implemented.

Figure 5 :

 5 Figure 5: Simulation of a circular formation of five agents centered at c = (0, 0) T . The function ρ representing the signal distribution centered at the origin has circular level sets. The mean input consensus algorithm of (13) is implemented.

Figure 6 :

 6 Figure 6: Simulation of the distributed algorithm (13) by a circular formation of five agents centered at c = (2, 2) T . The function ρ representing the signal propagation centered at the origin has elliptical level sets.

1 Figure 7 :

 17 Figure 7: Evolution of the direction, given in radians of the estimates (soft lines) and the real gradient (red bold line) for a time-varying signal distribution.

Figure 8 :

 8 Figure 8: Simulation of a circular formation of five agents centered at c = (1, 3) T . The function ρ representing the signal distribution of a moving source has circular level sets. The distributed consensus algorithm (10) is implemented with κ = 100.

Figure 9 :

 9 Figure 9: Simulation of a circular formation of five agents centered at c = (1, 3) T . The function ρ representing the signal distribution of a moving source has circular level sets. The distributed consensus algorithm (13) is implemented with κ = 100.