Consensus of Mobile Robots under Markovian Communication

1. Introduction

The consensus problem of mobile robots (or multi-agents) by information exchange is very important in engineering, and therefore, over the past few decades, it has attracted much research attention. In [1,2], Olfati-Saber and Murray introduced theoretical framework for solving the consensus problem. In [3,4], the consensus problems of the first-order integrator system with communication of undirected switching topology were proposed. In [5], for the single integrator system with communication of directed switching topology, it has been demonstrated that consensus is reached when the graph has the spanning tree. Hatano and Mesbahi [6] proposed the agreement problem above the random information exchange network. In [7], Porfiri and Stilwell provided sufficient conditions for reaching consensus almost certainly in the case of a linear system where the communication flow is given by a directed graph derived from a random graph process. Under a similar model of communication topology, Zhang [8] presented the necessary and sufficient conditions of the mean square consensus of double-integrator agents with stochastic switching communication topology.

For systems whose dynamics change in various possible scenarios, the Markovian jump system is an effective description. Recently, some interesting results with regard to Markovian jump systems have been presented on uncertain transition probabilities [10–12]. Noticing that the Markov chain can be used to describe the stochastic switching of communication among mobile robots, this paper addresses the mean square consensus problem of mobile robots under the Markovian communication of partly known transition probabilities. An sufficient condition of this problem is provided and the corresponding design algorithm is given.

In this paper, ℤ⁺ is used to denote the set of all nonnegative integers. The n×n real identity matrix is denoted by I_n. The Euclidean norm is denoted by ‖•‖. If a matrix P is positive (negative) definite, it is denoted by P>0(<0). The Kronecker product is represented by ⊗ and the expected value is represented by E[•].

The remainder of the paper is organized as follows. Section 2 describes a mobile robot system and its consensus problem. The condition and algorithm for the mean square consensus problem is derived in Section 3. Section 4 provides the numerical simulation results and Section 5 draws conclusions.

2. Mobile robots system and its consensus problem

Consider n mobile robots moving in a plane. At time t ∈[0, ∞), the state of the ith (i ∈{1,…,n}) robot is

z c i ( t ) = [ p x i ( t ) p . x i ( t ) p y i ( t ) p . y i ( t ) ] ∈ ℝ 4

where (p_xi(t),p_yi (t)) and (p_xi(t),ṗ_i (t)) represent position and velocity, respectively. Accordingly, the dynamics of the ith robot is modelled as

z . c i ( t ) = [ p . x i ( t ) p .. x i ( t ) p . y i ( t ) p .. y i ( t ) ] = [ 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 ] [ p x i ( t ) p . x i ( t ) p y i ( t ) p . y i ( t ) ] + [ 0 0 1 0 0 0 0 1 ] [ p .. x i ( t ) p .. y i ( t ) ] = A c i z c i ( t ) + B c i u c i ( t )

(1)

where accelerati on (p̈_xi(t), p̈_i (t)) acts as the control input u_ci(t). Suppose that these mobile robots are controlled in the sampled-data system framework [16] of zero-order holders and a given sampling period h>0. Thus, the discrete time model of the ith robot is obtained as

z i ( k + 1 ) = A i z i ( k ) + B i u i ( k ) , ​ k ∈ ℤ +

(2)

with

z i ( k ) = z c i ( k h ) u i ( k ) = u c i ( k h ) A i = e A c i h = [ 1 h 0 0 0 1 0 0 0 0 1 h 0 0 0 1 ] B i = ∫ 0 h e A c i ( h − τ ) B c i d τ = [ h 2 2 0 h 0 0 h 2 2 0 h ]

The communication situation among these n robots is described by matrix

D ( k ) = [ d 11 ( k ) … d 1 n ( k ) ⋮ ⋱ ⋮ d n 1 ( k ) ⋯ d n n ( k ) ] ∈ ℝ n × n , ​ k ∈ ℤ +

(3)

where d_ij(k) ∈ (0,1} : d_ij(k) = 1 means that z_j(k) is known by the ith robot at kh, while d_ij (k) = 0 means that z_j(k) is unknown by the ith robot at kh. Given m constant matrix D₁,…,D_m ∈ ℝ^n×n. The entries of these matrices take value from {0,1}. It is assumed that D(k) randomly varies in {D₁,…,D_m} as k increases, i.e., D(k) can be expressed as D _rk with a stochastic process r_k whose state space is {1,…,m}. In this paper, r_k is typically assumed to be a discrete time homogeneous Markovian chain of partly known transition probabilities. That is to say, some entries are inaccessible for the transition probabilities matrix Γ = (γ_ls) ∈ ℝ^m×m with γ_ls = Pr(r_k+1=s|r_k = l). For example, when m=4, Γ may be

[ ? γ 12 γ 13 ? ? γ 22 ? γ 24 γ 31 ? γ 33 ? γ 41 ? ? γ 44 ]

where ‘?’ represents the inaccessible entries. For l = {1,…,m}, define

U l ≜ { s : γ l s ​ ​ is ​ known } ​ ⊂ { 1 , ⋯ , m }

The task of these n mobile robots is to go to a prescribed target point (p*_x,p*_y). Among the n robots, only the 1st robot knows (p_x,p_y). As the leading robot, the 1st robot adopts the following control law

u 1 ( k ) = − G ( ∑ j = 1 n d 1 j ( k ) ( z j ( k ) − z 1 ( k ) ) − ( z 1 ( k ) − z * ) )

(4)

with z* = [p_x^* 0 p_y* 0]^T ∈ ℝ⁴ and the feedback gain matrix

G = [ k 1 k 2 0 0 0 0 k 1 k 2 ] ∈ ℝ 2 × 4

(5)

The other robots unaware of (p_x*, p_y*) have to utilize a control law without z*

u i ( k ) = − G ∑ j = 1 n d i j ( k ) ( z j ( k ) − z i ( k ) ) , ​ ∀ i ∈ { 2 , ⋯ , n }

(6)

The mobile robots system is said to reach mean square consensus if ∀ i ∈ { 1 , ⋯ n } , ∀ z i ( 0 ) ∈ ℝ 4 , ∀ r 0 ∈ { 1 , ⋯ , m } , lim k → ∞ E ‖ z i ( k ) − z * ‖ 2 = 0 . This paper aims to design k₁ and k₂ such that the n robots reach mean square consensus.

3. Main result

3.1 A Sufficient Condition of Mean Square Consensus

For the mobile robot system, from (2), (4), (5) and (6), we can easily see that its discrete time dynamics and control in x-direction are the same as that in the y-direction. Therefore an investigation in x-direction is enough. For i ∈ {1,…,n}, denote

e i ( k ) = [ p x i ( k h ) p . x i ( k h ) ] − [ p x * 0 ] ∈ ℝ 2

(7)

From (2), (4) and (7), we can obtain

e 1 ( k + 1 ) = [ 1 h 0 1 ] e 1 ( k ) − [ h 2 2 h ] [ k 1 k 2 ] ( ∑ j = 1 n d 1 j ( r k ) ( e j ( k ) − e 1 ( k ) ) − e 1 ( k ) )

(8)

From (2), (6) and (7), we can obtain ∀i ∈ {2,…,n}

e i ( k + 1 ) = [ 1 h 0 1 ] e i ( k ) − [ h 2 2 h ] [ k 1 k 2 ] ∑ j = 1 n d i j ( r k ) ( e j ( k ) − e i ( k ) )

(9)

Now, consider all the n robots together. Define

e ( k ) = [ e 1 ​ Τ ( k ) e 2 ​ Τ ( k ) ⋯ e n ​ Τ ( k ) ] Τ ∈ ℝ 2 n

(10)

A combination of (8), (9) and (10) leads to

e ( k + 1 ) = ( A − B K C r k ) e ( k ) ≜ F ( k 1 , k 2 , r k ) e ( k )

(11)

where

A = I n ⊗ [ 1 h 0 1 ] ∈ ℝ 2 n × 2 n B = I n ⊗ [ h 2 2 h ] ∈ ℝ 2 n × n K = I n ⊗ [ k 1 k 2 ] ∈ ℝ n × 2 n C r k = D r k ⊗ I 2 − diag ( 1 + ∑ j = 1 n d 1 j ( k ) , ∑ j = 1 n d 2 j ( k ) , ⋯ , ∑ j = 1 n d n j ( k ) ) ⊗ I 2

It is noticed that C_rk driven by r_k varies in the set {C₁,…,C_m} which consists of m constant matrices. For any l ∈ {1,…,m}, C_l ∈ ℝ^2n×2n can be calculated from D_l.

Theorem 1: The robot system described in (2), (4), (5) and (6) reaches mean square consensus under the feedback gains k₁ and k₂ if m positive definite matrices P₁,…,P_m ∈ ℝ^2n×2n and a real number β ≥ 1 exist such that ∀l ∈ {1,…,m},

β F Τ ( k 1 , k 2 , l ) ∑ s ∈ U l γ l s P s F ( k 1 , k 2 , l ) − ∑ s ∈ U l γ l s P l < 0 ,

(12)

β F Τ ( k 1 , k 2 , l ) P s F ( k 1 , k 2 , l ) − P l < 0 , ​ ​ s ∈ W l

(13)

Proof: Conditions (12) and (13) imply ∀l ∈ {1,…,m),

F Τ ( k 1 , k 2 , l ) ∑ s ∈ U l γ l s P s F ( k 1 , k 2 , l ) − ∑ s ∈ U l γ l s P l < 0 F Τ ( k 1 , k 2 , l ) P s F ( k 1 , k 2 , l ) − P l < 0 , ​ ​ ​ ​ s ∈ W l

and hence

η l = λ max [ F Τ ( k 1 , k 2 , l ) ∑ s ∈ U l γ l s P s F ( k 1 , k 2 , l ) − ∑ s ∈ U l γ l s P l ] < 0 ξ l = max s ∈ W l ( λ max [ F Τ ( k 1 , k 2 , l ) P s F ( k 1 , k 2 , l ) − P l ] ) < 0

Consider the stochastic Lyapunov function

V ( e ( k ) , r k ) = e Τ ( k ) P r k e ( k )

Then ∀r_k = l ∈ {1,…,m}, we have

E [ V ( e ( k + 1 ) , r k + 1 | e ( k ) , r k ) ] − V ( e ( k ) , r k ) = e Τ ( k ) ( F Τ ( k 1 , k 2 , l ) ∑ s ∈ { 1 , ⋯ , m } γ l s P s F ( k 1 , k 2 , l ) − P l ) e ( k ) = e Τ ( k ) ( F Τ ( k 1 , k 2 , l ) ∑ s ∈ U l γ l s P s F ( k 1 , k 2 , l ) − ∑ s ∈ U l γ l s P l ) e ( k ) + e Τ ( k ) ( F Τ ( k 1 , k 2 , l ) ∑ s ∈ W l γ l s P s F ( k 1 , k 2 , l ) − ∑ s ∈ W l γ l s P l ) e ( k ) ≤ η l ‖ e ( k ) ‖ 2 + ∑ s ∈ W l γ l s ξ l ‖ e ( k ) ‖ 2 ≤ − ρ ‖ e ( k ) ‖ 2

where

ρ = | max l ∈ { 1 , ⋯ , m } ( η l + ( 1 − ∑ s ∈ U l γ l s ) ξ l ) | > 0.

Therefore, ∀ N ∈ { 1 , 2 , 3 , ⋯ } , ∀ e ( 0 ) ∈ ℝ 2 , ∀ r 0 ∈ { 1 , ⋯ , m }

∑ k = 0 N E [ ‖ e ( k ) ‖ 2 ] ≤ 1 ρ ∑ k = 0 N ( E [ V ( e ( k ) , r k ) ] − E [ V ( e ( k + 1 ) , r k + 1 ) ] ) ≤ 1 ρ ( V ( e ( 0 ) , r 0 ) − E [ V ( e ( N + 1 ) , r N + 1 ) ] ) ≤ 1 ρ V ( e ( 0 ) , r 0 )

which means

lim k → ∞ E [ ‖ e ( k ) ‖ 2 ] = 0

Since the y-direction model is the same as the x-direction model, the motion in y-direction is also convergent. Thus we conclude

lim k → ∞ E [ ‖ z 1 ( k ) − z * ⋮ z n ( k ) − z * ‖ 2 ] = 0.

3.2 Design Method

Given a pair (k₁,k₂), let the conditions in Theorem 1

β F Τ ( k 1 , k 2 , l ) ∑ s ∈ U l γ l s P s F ( k 1 , k 2 , l ) − ∑ s ∈ U l γ l s P l < 0 β F Τ ( k 1 , k 2 , l ) P s F ( k 1 , k 2 , l ) − P l < 0 , ​ ​ s ∈ W l 0 ≤ β ∈ ℝ , ​ ​ 0 < P i ∈ ℝ 2 n × 2 n , ​ ​ i ∈ { 1 , ⋯ , m } , ​ ​ l ∈ { 1 , ⋯ , m }

be represented by L(k₁,k₂,β) < 0. Obviously, when β is fixed, L(k₁, k₂, β) < 0 is a linear matrix inequality (LMI) which can be solved efficiently. For any a pair of (k₁, k₂), define

β ̄ ( k 1 , k 2 ) = sup L ( k 1 , k 2 , β ) < 0 β

Based on the LMI technique and bisection search, we provide a calculation method of β ̄ ( k 1 , k 2 ) as follows.

Step a) Set a precision ε > 0, a sufficiently large β_max such that L(k₁, k₂, β_max) < 0 has no solution and a sufficiently small β_min > 0 such that L(k₁, k₂, β_min) < 0 has solutions.

Step b) Let β_temp = (β_min + β_max)/2, solve L(k₁, k₂, β_temp) < 0.

Step c) If L(k₁, k₂, β_temp) < 0. has solutions, β_min = β_temp; if L(k₁, k₂,β) < 0 has no solution, β_max = β_temp.

Step d) If β_max – β_min < ε, β(k₁, k₂) = β_min and terminate the algorithm; if β_max – β_min ≥ ε, go to Step b).

From Theorem 1, it is known that those (k₁,k₂) s whose β ̄ ( k 1 , k 2 ) > 1 can guarantee the mean square consensus of the mobile robot system. Roughly speaking, in these (k₁, k₂) s whose β ̄ ( k 1 , k 2 ) > 1 , a pair of (k₁, k₂) with a large β ̄ produce better robustness which is a capability of the system of retaining mean square consensus under uncertainties such as parameter perturbances and noises. Therefore, we want to find the pair of (k₁, k₂) which have the largest β ̄ , i.e., to solve the optimization problem

μ = sup k 1 ∈ ℝ k 2 ∈ ℝ β ̄ ( k 1 , k 2 ) .

(14)

Problem (14) is an unconstrained nonlinear optimization problem of only two variables. It is solved in this paper by the following method. At first, in the k₁−k₂ plane, the designer gives a rectangle [ k 1 _ , k 1 ̄ ] × [ k 2 _ , k 2 ̄ ] in which the optimal solution lies. Subsequently, give a positive integer N (e.g., N = 500) and determine the set

X = { ( k 1 , k 2 ) | k 1 = k 1 _ + i ( k 1 ̄ − k 1 _ ) / N , i ∈ { 0 , 1 , ⋯ , N } k 2 = k 2 _ + j ( k 2 ̄ − k 2 _ ) / N , j ∈ { 0 , 1 , ⋯ , N } }

containing (N + 1)² points. Then, calculate β ̄ for every point of X and obtain

( k 1 * , k 2 * ) = arg max ( k 1 , k 2 ) ∈ X β ̄ ( k 1 , k 2 ) .

Finally, with (k₁*,k₂*) as the initial guess, solve (14) using the BFGS Quasi-Newton algorithm [19] and acquire the optimal solution (k_1opt,k_2opt).

4. A numerical example

In the numerical example, n=6, h=0.1s, m=4,

D 1 = [ 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 ] , D 2 = [ 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 ] D 3 = [ 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 ] , D 4 = [ 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 ]

Figure 1 illustrates the four communication situations corresponding to D₁ ∼ D₄. An arrow from the ith to the jth one in Figure 1 represents d_ij = 1. The partly unknown transition probabilities of r_k are OPEN IN VIEWER

Γ = [ 0.3 ? 0 .04 ? 0 .52 0 .4 ? ? ? ? 0 .03 0 .5 0 .3 ? ? 0 .64 ] .

Using the calculation steps in Section 3, β ̄ s of different (k₁, k₂) are obtained and displayed in Figure 2. The optimization problem (14) is solved. The result is μ = 1.1270 > 1 and OPEN IN VIEWER

( k 1 opt , k 2 opt ) = ( − 4.18 , − 6.43 )

which is also displayed in Figure 2. With target (p* _x , p* _y ) = (183,152) and initial states selected randomly, the motion of six robots is simulated under transition probabilities respectively. Figure 3 and Figure 4 show the motion. It can be seen that these robots move to the target point under either Γ₁ or Γ₂.

OPEN IN VIEWER

Figure 3.

Motion of six robots under Γ₁

OPEN IN VIEWER

Figure 4.

Motion of six robots under Γ₂

Γ 1 = [ 0.3 0.25 0.04 0.41 0.52 0.4 0.05 0.03 0.4 0.07 0.03 0.5 0.3 0.05 0.01 0.64 ] , Γ 2 = [ 0.3 0.36 0.04 0.3 0.52 0.4 0.01 0.07 0.2 0.27 0.03 0.5 0.3 0.04 0.02 0.64 ] ,

5. Conclusion

The consensus problem of a mobile robot system has been studied under a Markovian switching communication topology of partly known transition probabilities. The control input of each robot depends on the information exchange among robots. A stochastic Lyapunov function has been employed to investigate the mean square consensus of mobile robots, and the controller design problem has been solved by using numerical optimization techniques.