Consensus Based Least Squares Estimation for SingIe-Integrator MuIti-Agent Syste

AIi AIouache | Qing-He Wu

Abstract—This paper discusses consensus tracking of single-integrator multi-agent systems with a time varying reference state based on the least squares estimation theory to deal with the case of communications disturbance.Since none of the followers can communicate with the leader within the accepted time due to communications disturbance,least squares estimation is applied for online estimation of the time varying reference state and reducing the tracking errors occurred due to communications disturbance.A theoretical proof is provided under some assumptions while the necessary and sufficient conditions are demonstrated for which consensus is reached on the time-varying reference state in case of communications disturbance.Finally,a Matlab example is given to validate the effectiveness of the proposed approach.

1.Introduction

In recent years,multi-agent systems have gained a lot of interest due to their advantages for accomplishing complex tasks compared with a single agent.Consensus tracking of multi-agent systems is the most studied issue in the literature.Consensus tracking means to reach an agreement regarding a certain quantity of interest that depends on the state of all the agents[1]-[3].

The applications of consensus tracking algorithms are numerous in different domains,such as rendezvous control of multi nonholonomic agents[4]-[6],formation control[7],[8],and flocking attitude alignment[9],[10].The special cases are consensus tracking with a dynamical leader based on the virtual structure approach[11]and consensus of the second-order multi-agent system with multi leaders[12].

The basic theoretical framework of consensus problems for networked dynamical systems was introduced by the studies of Saber and Murray[13],[14],which were inspired by the earlier work of Fax and Murray[15],[16].Jadbabaieet al.[17]demonstrated that all the agents could eventually move in the same direction with a simple neighbor rule despite the absence of the centralized coordination and each agent’s set of neighbors changing with time as the system evolved under a joint connection topology.So as a special consensus problem,tracking has also been explored by many scholars,consensus tracking control was proposed in [18] for double integrator dynamics,when there was a coupling between the neighbors’ information state derivatives.Consensus tracking for multi-vehicle control with a constant or time-varying reference state was proposed by Ren[19],[20].Later consensus tracking control was also studied in other different conditions,such as consensus with noise measurement[21],with time delay[22],and with uncertain dynamics[23].

1.1.ReIated Works

Most of the previously cited works operate under the hypothesis that the leader always keeps connected with a partial set of followers.However in the physical applications,the communications between the followers and the leader may fail due to many reasons like noise and the errors of the sensors,therefore the followers can not receive the information of the leader,which may cause the instability of the multi-agent system.Therefore many works have investigated the problems of the communications failure between the agents of the systems.Leader following consensus tracking for multi-agent systems with multiplicative noise was analyzed by Djaidja and Wu[24].A fast consensus tracking approach for discrete time multi-agent systems with input and communications delay was studied by [25].The formation control problem for single-integrator multi-agent systems with diverse communications and input delay was investigated by [26].In [27],particle swarm optimization was used to tackle communications failure for tracking control of multiple mobile robots formation.Formation control of multi-agent systems in realistic fading environments was proposed in [28] and [29].Songet al.[30]used tools from stochastic differential delay equation (SDDE),martingale theory,and stochastic inequality for establishing sufficient conditions which led mean square consensus with multiplicative noise and time delay under directed fixed topologies.Jin and Yuan[31]proposed a robust adaptive sliding mode approach to the asymptotic consensus problem for a class of multi-agent systems with time-varying additive actuator faults and communications perturbation,however the design is complex and the performance of the multi-agent system is not further analyzed for the timing of communications disturbance.

1.2.Proposed Approach

The contribution of this paper is to propose least squares estimation for consensus tracking of single-integrator multi-agent systems with a time varying reference state to overcome the case of communications disturbance.

The proposed approach is primarily based on Ren’s fundamental algorithm presented in [19] for multivehicle consensus with a time varying reference state.If none of the followers can communicate with the leader within the accepted time due to communications disturbance,therefore the proposed approach is adapted to improving the stability and robustness of the multi-agent system for achieving consensus even communications fail among the agents.The main idea behind this work is that the followers try to predict the coming information from the leader based on the information which had been received before and take the corresponding action in case of communications disturbance by estimating the time varying reference state according to online collected data for reducing the tracking errors occurred due to communications failure.

A theoretical proof is provided for the proposed approach under some assumptions while the necessary and sufficient conditions are also demonstrated,for which consensus is reached on the time-varying reference state in case of communications disturbance.At the end,a Matlab example is given to validate the effectiveness of the proposed approach by supposing the case of communications disturbance and comparing the results with the fundamental algorithm of Ren[19].

The rest of this paper is structured as follows:Section 2 gives some background about the graph theory and least squares estimation technique.Section 3 formulates the consensus algorithm for single-integrator multi-agent systems with a time-varying reference state and the problem statement.Section 4 describes in details the proposed approach and provides a theoretical proof under some assumptions with the necessary and sufficient conditions.The comparative results of Matlab simulations are given in Section 5.Finally,conclusions and further investigations are given in Section 6.

2.Background

The graph theory is used to represent the allowed information flow between the agents of the system.Each node of the graph represents an agent,which is connected to its neighbors through an adjacency matrix,where each node has some effects on its neighbors for sharing communications information.This section gives a brief tutorial on the algebraic graph theory and some basic concepts of the least squares estimation theory.

2.1.Graph Theory

The information exchange among vehicles is modelled by directed or undirected graphs[13].A directed graph is a pair (Vp,εp),where the setVp={1,2,…,p} is a finite nonempty node set andεp⊆Vp×Vpis an edge set of ordered pairs of nodes,called edges.The edge (i,j) in the edge set of a directed graph denotes that the vehiclejcan receive information from the vehicleibut not necessarily vice versa.

An undirected graph can be viewed as a special case of a directed graph,where an edge (i,j) in the undirected graph corresponds to edges (i,j) and (j,i) in the directed graph.A directed tree is a directed graph in which every node has exactly one parent expect for one node,called the root,which has no parent and has a directed path to every other node.In undirected graphs,a tree is a graph in which every pair of nodes are connected by exactly one undirected path.

The adjacency matrix Ap=[ai,j]∈Rp×pof a directed graph (Vp,εp) is defined such thatai,jis a positive weight if(j,i)∈εp,andai,j=0 if (j,i)∉εp.Self-edges are not allowed unless otherwise indicated.The adjacency matrix of an undirected graph is defined analogously except thatai,j=aj,ifor alli≠jbecause (j,i)∈εpimplies(i,j)∈εp.

The matrix Lpsatisfiesli,j≤0,li,j=0,i=1,2,…,p.For an undirected graph,Lpis symmetrical and it is called the Laplacian matrix.

2.2.Least Squares Estimation

Least squares estimation is a mathematical method that can realize the best fitting in terms of the minimum square error according to the given data.

Given the data of the input vector xi=[x1,i,x2,i,…,xn,i]Tand the output vector Yi=[y1,y2,…,yn]T,wherendenotes the number of the variables that are related to Y.Therefore we may define the mathematical model for the given data as

The least squares estimation problem aims to search a regression coefficientthat minimizes the following valueJ==εTε.The regression vectoris obtained,such that the matrix ΦTΦ is reversible.

In order to accelerate the estimation process for the vehicle and to perform regularly prediction with new data,then the recursive least squares estimation algorithm with an attenuation factor is adopted.

3.ProbIem Statement

Consider an interconnected system composed ofnagents with single-integrator dynamics:

Or in a matrix form,(1) may be rewritten as follows

Suppose a multi-agent system which consists ofnidentical vehicles as described above with an additional vehicle labelledn+1,which acts as the unique leader of the team.Therefore the (n+1)th vehicle is named as the leader and the vehicles 1,2,…,nare named as followers.

The vehiclen+1 has the information state as following,where ξrdenotes the time varying reference state.

The consensus reference state satisfies

where (·,·) is bounded,piecewise continuous int,and locally Lipschitz in ξr.

The consensus problem with a time varying reference state is solved if and only if ξi(t)→ξr(t),wherei=1,2,…,nast→∞.

Assume the team of the vehicles as an interaction topology withn+1 nonempty nodes.Therefore according to the graph theory tutorial given in the subsection 2.1,we can get the corresponding directed graph Gn+1for the multiagent system,i.e.,,the adjacency matrix An+1,and the matrix Ln+1which is the non-symmetrical Laplacian matrix associated with the graph Gn+1.

In general,there are two primary methods to solve the consensus tracking problem for the multi-agent system.A consensus tracking algorithm was proposed in [19] as

whereaiis the positive constant scalar andai,jis the (i,j) entry of the adjacency matrix An+1with the additional assumption thatai,n+1=1,if (n+1,i)∈εn+1,andai,n+1=0 otherwise.

When An+1is constant andai,n+1=1,i=1,2,…,n,the consensus tracking problem with a time-varying reference state is solved with (1).However,the topology condition is too rigorous,hence another control law was proposed in[19] as

wherei=1,2,…,n,j=1,2,…,n+1,ai(t) is the (i,j) entry of the adjacency matrix An+1(t) at timet,γis a positive constant scalar,and(t).

The consensus problem is solved if and only if the corresponding directed graph Gn+1has a directed spanning tree.Equation (5) solves consensus tracking of the time varying reference state for the multi-agent system if the communications are available among the agents as demonstrated in [19],however in case of communications disturbance[27],this paper proposes a solution for consensus tracking based on the least squares estimation theory as demonstrated in the following section.

4.Proposed Approach

The cooperative control approach proposed in this paper is developed based on (5),thus it is valid when the communications between the leader and the followers are available,specifically the followers which can communicate with the leader directly.Moreover,the proposed algorithm is adapted for estimating the value of the time varying reference stateξrusing least squares estimation.When the communications between the leader and the followers are failed,the reference state ξris substituted by the estimated state,i.e.,.

Before getting into the development of the proposed approach,the following assumptions are presented as sufficient conditions for the application of the proposed algorithm.

Assumption A.We assume that the reference state ξrhasNderivatives in the time interval of the process,i.e.,[t0,T],whereNis a positive integer number.Tis the duration of the process,andT=t0+td+tras indicated in Fig.1.

As shown in Fig.1,we consider that the instantt0denotes the moment when the reference state ξris available to a portion of the followers.tddenotes the moment when the reference information is not available to the followers due to communications disturbance.trdenotes the moment when the reference information becomes available again.

Assumption B.We assume that the information packet about the reference state that the follower received from the leader is proportional to the timetd.Here,it is supposed that the sampling frequency is 1,thustdmeans the number of the information packets that the follower receives during the period [t0,td].For reducing the influence of the old data and paying more attention to the new states,an attenuation factor is added at least squares estimation.

Assumption C.We assume that the multi-agent system is stable and also can achieve consensus tracking after the momentT(i.e.,T=t0+td+tr).

The reference state ξris assumed to be available again if and only if

Fig.1.Timing of communications disturbance.

wherei=1,2,…,nandδdenotes the critical deviation.Notice that if the cumulative state deviation of some followers is more thanδ,the whole system will be instable and it will never reach consensus tracking even if the reference state ξris available again.

Assumption D.Since communications disturbance is more likely tooccur in the tracking process when the state sof followers are very close to the reference state ξr,then the estimated valueis also very close to the reference state ξr.Henceweassume that the time,which the followers spend on trackingand achieving ξi=,is very short and can be ignored compared with the timetr.

Theorem 1.If the time-varying reference state ξrhasNderivatives in the time interval of the process [t0,T],therefore an estimation functioncan be obtained according to the received information (td) states,which satisfies the following inequalitydt＜δ1, whereδ1is affected bytd,N,andtr.

Proof.

wherek=min(N,td-1) andJ=1,2,…,MwithMdenoting the dimension of the state.

with Φ=[φJ,1,φJ,2,…,φJ,m]T,φJ,i=[1,t,…,tk], and θ=[aJ,0,aJ,1,…,aJ,k]T,wherem=td,therefore

with ε=[εJ,1,εJ,2,…,εJ,m]Tdenotingthe residual vector.

Then,according to the least squares estimation theory,there exists a vector θ which can minimize the value of εTε.

Hence an estimation functionis obtained and it is the best fitting to the statein the time interval [t0,t0+td].

Therefore in the time interval [t0+td,T],the following inequalitydt＜δ1/Mis reasonable,and obviously the followingdt＜δ1is reasonable,too.Meanwhile,k=min(N,td-1), thusδ1is inversely proportional totdorN,also it is proportional totr.Finally,Theorem 1 is proved.

Theorem 2.If the time-varying reference state ξrhasNderivatives in the time interval [t0,T] andN＞μ1,td＞μ1,andtr＜μ2.The valuesμ1andμ2are the critical values which makeδ1＜δ,and the directed graph Gn+1has a directed spanning tree.Therefore the consensus tracking problem is solved if the estimated valueis adopted at the time interval [t0+td,T].

Proof.

The proof of this theorem can be given by the following two steps.

Step 1:Firstly,when the reference state is available,,it is necessary to prove that the consensus tracking problem is solved if the graphhas a directed spanning tree.

According to (1),(5) can be rewritten as

Equation (9) can be rewritten in a matrix form as follows

Since the directed graph of Ln+1has a directed spanning tree,we can induce that rank(Ln+1)=n.This implies that rank(Ln,n+1)=n.

Ln,n+1can be rewritten as [B∣b], where B constitutes the firstncolumns of Ln,n+1,and b is the last column of Ln,n+1.Notice that the summation of each row of Ln,n+1is zero,hence b=-B1n.Therefore we can get that rank(B)=n.

When we substitute [B∣b] fo Ln,n+1in (9),we get

Since B is full rank,it is invertible.Then (9) can be rewritten as

Moreover,(12) can be rewritten as

From (14),we can get that ξ(t)→1n⊗ξr(t) ast→∞.It follows that ξi(t)→ξr(t) wherei=1,2,···,nast→∞,then the consensus tracking is solved.

Step 2:Secondly,we need to prove that the consensus tracking problem is solved when the estimated stateis adopted.At time interval [t0+td,T],the cumulative state deviation of followers at that time interval can be written as

withi=1,2,…,n.

According to Assumption D,(15) can be rewritten as

From Theorem 1,we can induce the following as

whereδ1＜δ.Equation (17) implies that after the moment of disturbanceTand when ξris available again,the consensus problem still can be solved.

Theorem 3.If the time-varying reference state ξrhasNderivatives in the time interval [t0,T] andN＞μ1,td＞μ1,andtr＜μ2,whereμ1andμ2are critical values,thenδ1＜δ,and the directed graph Gn+1has a directed spanning tree,therefore

wheretddenotes the last state that the follower can get before ξrbecomes unavailable.

Proof.

According to the definition ofμ2,we can get

According to Theorem 1,we can write the following as

From (18) and (19),the following inequality can be deduced

The inequality (20) is given by Theorem 3,which has been proved.Through the above analysis,it can be concluded that the proposed approach predicts the coming reference state by analysing the states that have been received before.Therefore in case of communications disturbance,the least squares estimation algorithm is applied to estimate the time-varying reference state for the consensus tracking of the multi-agent system.Moreover,the robustness and stability of the multi-agent system are also enhanced as demonstrated by Theorem 3.

5.SimuIation ResuIts

This section presents a simulation example for verifying the effectiveness of the proposed approach comparing with the fundamental algorithm given by (5).

The simulation is performed on a group of four follower robots and one leader robot in one dimensional environment (M=1),where each robot is modelled by(1).

Fig.2.Communications topology for the multi-agent system.

Assume that the communications topology among the robots as indicated in Fig.2 with the time varying reference state ξr(t) is available only to the leader robot numbered 1.

Assume that the function of the reference stateξr(t)is sin(t).Suppose that the reference state ξr(t) is not available during the time interval [18 s,21 s],hence the disturbance instant istd=18 s and the reference is available again at the instanttr=21 s.Figs.3 and 4 illustrate the results obtained by applying the control law of (5) to the multi-agent system.Notice that the followers keep the reference state of the momenttd=18 s during the time interval [18 s,21 s] and the multi-agent system fails to reach consensus as shown in Fig.3 and large tracking errors are resulted as illustrated in Fig.4.

By applying (5) for the multi-agent system under communications disturbance,a large cumulative state deviation and large tracking errors are obtained as illustrated in Figs.3 and 4,respectively.In the practical applications,such a large deviation will cause the system to be instable and even the system cannot achieve consensus tracking after the reference state is available again due to many reasons,such as the limited communications distance.

Fig.3.Consensus tracking with a time-varying reference state using (5) under communications disturbance.

Fig.4.Tracking errors using (5) under communications disturbance.

Now the proposed least squares estimation algorithm is adopted for the multi-agent system,and the obtained results of consensus tracking can be seen in Figs.5 and 6.

The results of Fig.5 show a less cumulative state deviation compared with the results of Fig.3 and the system successfully achieves consensus even with communications disturbance.The results of Fig.6 show that the tracking errors are reduced,compared with the results of Fig.4.

The obtained results demonstrate that the proposed leader follower cooperative approach provides stability and robustness for the multi-agent system to achieve consensus under communications disturbance compared with the fundamental algorithm of Ren given by (5).

Fig.5.Consensus tracking with a time-varying reference state under communications disturbance using the proposed least squares estimation algorithm.

Fig.6.Tracking errors under communications disturbance using the proposed least squares estimation algorithm.

6.ConcIusions

This paper described the development of a leader follower approach for consensus tracking of singleintegrator multi-agent systems with a time varying reference state based on least squares estimation to deal with the case of communications disturbance.The estimation of the reference state was done according to online collected data for reducing the tracking errors due to communications failure.

Firstly,the significance of the consensus tracking algorithm for the multi-agent system was illustrated.Secondly,the assumptions as well as the necessary and sufficient conditions were given for the application of the algorithm.These assumptions can be satisfied in many practical applications.After that the theoretical proof was provided to show the validity of the proposed algorithm.

A simulation example was carried out to compare the performance of the developed least squares estimation approach with the fundamental algorithm proposed by Ren[19]for consensus tracking of single-integrator multi-agent systems and supposing the case of communications disturbance.The comparative results demonstrated the effectiveness and the advantages of the proposed approach to deal with the communications disturbance for consensus tracking of single-integrator multi-agent systems compared with the fundamental algorithm of Ren.

In the future work,we attempt to investigate the double integrator dynamics and nodes with nonlinear dynamics.