POLITECNICO DI TORINO
Master‘s degree in Mechatronic Engineering
Master‘s degree thesis
Control of heterogeneous multi-agent systems and aerospace applications
Supervisors: Candidate:
Prof. Elisa Capello Rodolfo Pietrasanta
Prof. Yasumasa Fujisaki
Contents
1 Introduction 4
1.1 Multi-agent systems . . . 4
1.2 Thesis outline . . . 7
2 Mathematical tools 9 2.1 Graph theory . . . 9
2.2 Algebraic graph theory . . . 12
2.3 Some properties of matrices . . . 20
2.4 Kronecker Product . . . 21
2.5 Differential equations canonical form . . . 23
3 Undirected graphs case 25 3.1 Measurable velocities . . . 27
3.2 Non-measurable velocities . . . 32
4 Directed graph cases 36 4.1 Eigenprojections in dynamic systems . . . 36
4.2 Rigid dynamics, continuous time . . . 43
4.3 Rigid dynamics, discrete time . . . 49
4.4 Flexible dynamics, continuous time . . . 52
4.5 External disturbances . . . 58
5 Failure Management 63 6 Conclusions 71 7 References 73 7.1 Figures . . . 75
1 Introduction
1.1 Multi-agent systems
In recent times, multi-agent system are becoming increasingly important in many different engineering fields. In literature we can find different defini- tions of multi-agent system, they can be described [22] as a set of subsystems that are, at least partially, autonomous: each agent has its own behaviour or dynamics depending on the context. The main characteristics of Multi- Agent Systems (MAS) are [23]:
• Sociability: ability to share and request information from other agents.
• Autonomy: Each agent can take action independently.
• Proactivity: Each agent uses its history, sensed parameters and in- formation of the other agents.
MAS can be classified depending on their feature[23]:
• Leadership: MAS can be leaderless, a configuration in which each agents acts to reach its own objective, or leader-follower in which there are one or more agents that are leaders and the other chase their behaviour. In this latter case, leader(s) can be predefined or collaboratively chose by the agents. In this work, particular attention is posed on leader-follower configurations with one leader .
• Decision function: This feature can be linear or non-linear. In the first case the decision function of each agent is proportional to the parameters sensed from the environment. Clearly in the non-linear case the relation is not a simple proportionality.
• Hetrogeneity: In homogeneous MAS, all the agents have the same identical characteristics, while in heterogenous MAS, agents are differ- ent. In this work the focus is on heterogenous agents
• Delay: The time delay that occurs when sharing information among the agents can be taken in consideration or not, in this thesis, time delay is neglected.
• Topology: topology refers to reciprocal locations and relations among agents. It can be static or dynamic, up to section 4 static topologies are considered, in section 5 some cases with switching topologies are
The overall system is studied in order to find more efficient ways of schedul- ing, path finding, obstacle avoidance etc. In a physical context, MAS are used to control swarms of physical objects such as robots or satellites, in 1996 the first article that approached the problem of coordination among a set of robots was published [24]. In [25] we can find the definitions of the two main problems:
• Coordination among robots
• Planning trajectory
In this thesis, the main field of interest is the Aerospace, in particular con- sidering sworms of satellites, and the main objective is the coordination, in particular the reach of consensus. Consensus is a condition in wich each agent in the MAS has a common charachteristic with the others, for ex- ample position and/or velocity. In this context an attempt to find better coordination laws is made, in order to reduce the global energy consumpion of the system and obtain better performances to reach consensus.
Figure 1: Concept of a group of satellites orbiting around the earth.
Satellites orbiting around the earth are used for many different purposes such as pollution control, disasters monitoring (earthquakes, forest fires...), communications, space observation and so on [14]. For all these purposes, they ususally need an high pointing accuracy (the variables of interest are considered to be angular displacement and velocity) as we can find in [1],[2], and to be optimized in terms of costs. In [26], [27] and [28] we can find some conrol laws for fisrt order dynamics MAS, considering time delays,
and graph properties are shown. Satellites are considered to have a rigid body described by Newton‘s law, and a flexible appendage, that could be, for example, a solar panel, described by a second order differential equa- tion coupled with the rigid body equation that can be found from different sources in literature ([15],[16],[17] and [18]). In this way the model is more accurate, higher pointing accuracy is obtained and unwanted flexible parts excitments are avoided. For all these purposes, a background of graph the- ory and algebraic graph theory was studied starting from some reference books as [10],[11],[12] and [13], then some new methods to tune the tran- sient of such systems using directed topologies are presented starting from the ideas found in [6], [7] and [8]. In particular, a subcase for a one-leader- follower MAS consensus under directed topologies is demonstrated using a parameter inequality already present in [3], then it is extended to the flexi- ble dynamics case and a method to reduce the global control input without lowering performances is shown. In [4] we can find a resume of the tho- eretical results for first order MAS in continous and discrete time, also with switching topologies.
Figure 2: Concept of a CubeSat with flexible appendages.
Moreover, most relevant external disturbances found in Low Earth Orbit are modeled following [19],[20] and [21]. Since often satellites are not equipped with gyroscopes, and, otherwise, to take in account possible failures, the absence of a velocity measure is also considered by translating the MAS in discrete time and using differentiators to estimate the velocity.
1.2 Thesis outline
This work is divided in four main sections:
• Section 2: This section is dedicated to the mathematical introduction, with particular focus on graph theory and algebraic graph theory. The basic notions needed to understand succeding sections are introduced such as basic definitions and properties about graphs and related ma- trices. Moreover some of the ”less common” matrix properties are shown with some simple proofs.
• Section 3: this section provides an overview of the problem starting from the work already present in literature. Consensus of second or- der heterogeneous multi-agent systems with flexible appendages and undirected communication topologies is considered. At first velocity is supposed to be measurable, so each agent is assumed to be equipped with instrumentation able to perform the measure. Then a control law able to stabilize the system also without velocity measures is presented.
Some numerical simulations with different communication topologies among the agents are shown.
• Section 4: this section are present the main results of the work. Di- rected topologies are taken into account in order to propose methods to better tune the transient of the system and reduce the number of com- munication. In this section leader-follower control is considered, so all the agents have to reach the same state (consensus) of an agent called Leader. Consensus reachability over directed topologies is prooved for first and second order dynamics, also with flexible dynamics. The sys- tem is translated in discrete time to involve differentiators to estimate velocity in case it is not measurable. At last, external disturbances models are presented and numerical simulations are performed.
• Section 5: this section deals with the possible failure of one or more of the agents, the communication topology is checked to be still capable reaching consensus and it is recomputed if it‘s not. Some simulations with switching topologies are presented.
Section 6 and 7 are dedicated to conclusions and references.
2 Mathematical tools
This section introduces the main mathematical tools used in the succeeding sections.
2.1 Graph theory
A graph G consists of a finite set of Vertices V(G) and a set of Edges E(G).
We take V(G) to be {1,2,...,n} and E(G) to be {e1, e2, ..., em}. An edge ek = {i, j} connects the i − th and j − th vertices. The following figure shows a simple graph:
Figure 3: Simple Graph
Now some of the graphs main properties are listed.
Connected graph: a graph is said to be connected if there exist a path from any vertex to any other. For example:
(a) Connected graph (b) Unconnected graph
The graph in figure (b) is not connected because does not exist a path from vertex 4 to the others.
not connect {j,i} in general. In other words, the edges have a direction:
Figure 5: Directed Graph
In this example the edge connecting 2 to 1 does not connect 1 to 2. A directed graph is said to be weakly connected if the underlying undirected graph is connected. This is obtained replacing each directed edge with an undirected one. The graph in Figure 3 is an example of weakly connected graph.
Self loop graph: this graphs has at least one edge connecting a vertex to itself:
Figure 6: Self loop Graph
A graph with no self loops is called loopless.
A source is a vertex from which all the edges are pointing out. For example in the next figure vertex 1 is a source.
Figure 7: Graph with a source
If on the contrary a vertex has all the edges pointing in, it is called a sink.
Weighted graph: a weighted graph is a directed graph in whch a positive real number ae is associated to each edge: G = (V (G), E(G), {ae}e∈E(G)) Note that if the edge connecting vertex i to vertex j is not present, it can be interpreted as a 0 weigth associated to that edge. An unweighted graph has ai= 1 ∀i. The following picture is an example of weighted graph:
Figure 8: Weighted Graph
2.2 Algebraic graph theory
Let‘s see now how to manipulate graphs and their properties using matrices.
The first important definition is the Adjacency Matrix A. In general it is an n × n matrix (n number of vertex) defined as follows:
A =
(aij if {i, j} ∈ E(G) 0 otherwise
So it is a matrix where all the entries are equal to the weight of the edge connecting vertex i to vertex j. Clearly if an edge does not exist its corre- spondent weight is 0. For example:
Figure 9: Weighted Directed Graph
The graph in Figure 7 is associated to the following adjacency matrix:
A =
0 0.2 9.3 0 0
0 0 0 5 0
0 0 0 1.5 10
4.4 0 0 0 0
0 0 0 3.2 1
Notice that the transpose of A is the matrix that has as entries the weights of the edges connecting vertex j to vertex i, so an interpretation is that the rows of A represent the information that the correspondent vertex is giving to the others, and the colums (so the rows of AT) the information tha the correspondent vertex is receiving from the others. Some properties can be extrapolated from this definition:
• Loopless graph: the adjacency matrix of a loopless graph has all the diagonal entries equal to 0 since there is no edge from a vertex to itself.
Figure 10: Weighted Directed Graph
A =
0 0.2 9.3 0 0
0 0 0 5 0
0 0 0 1.5 10
4.4 0 0 0 0
0 0 0 3.2 0
• Undirected graph: the adjacency matrix of an undirected graph is symmetric since the edge connecting i to j also connects j to i with the same weight.
Figure 11: Undirected Graph
A = AT =
0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0
• Unconnected graph: an unconnected (undirected) graph has the k − th row and column all set to 0, where the k − th vertexes are the not connected once. This is because they are not giving or receiving information.
• Graph with a source(or a sink): a graph with a source has the correspondent column set to 0 since that vertex is only giving infor- mation to the others. The dual of the source is the sink, in that case the correspondent row is 0 since it only receives information from the
For example the graph in Figure 5 has a source and two sinks, so the adjacency matrix is:
A =
0 1 1 0 0 0 0 0 0
• Complete graph: a graph is said to be complete if all the entries of the adjacency matrix are not 0. This means that exist an edge from all vertex to any other, themselves included.
Another important definition is the Degree matrix . In general it can be defined in two ways:
Dout= diag(A1n) = row-sum of A Din= diag(AT1n) = column-sum of A
where 1n is the column vector of all 1. The first is the out-degree matrix, that isa a diagonal matrix in which any entry is the sum of the weights of the edges pointing out the correspondent vertex. The second is the same but each entry is the sum of the weights of the edges pointing in the corre- spondent vertex.Clearly if the graph is not weighted the sum of the weights corresponds to the number of edges. The graph in Figure 8 has the following degree matrices:
Dout =
9.5 0 0 0 0
0 5 0 0 0
0 0 11.5 0 0
0 0 0 4.4 0
0 0 0 0 3.2
Din =
4.4 0 0 0 0
0 0.2 0 0 0
0 0 9.3 0 0
0 0 0 9.7 0
0 0 0 0 10
Notice that if the graph is undirected A is symmetric, so Dout = Din since
Now we can define the Laplacian Matrix. In general the Laplacian of a graph is a matrix defined as:
L = Dout− A
So the off-diagonal elements are the opposite of the weights and if the graph is loopless the diagonal ones are the absolute value of the sum of the off diagonal on the same row:
L = [lij] =
(−aij for i 6= j
Pn
h=1,h6=iaih for i = j
For example:
Figure 12: Directed loopless graph
L =
19.4 −10 −1.2 −8.2
0 0 0 0
0 0 4 −4
−0.1 0 0 0.1
It follows from the properties of the Laplacian that:
• L1n= 0 : the row-sum is always 0.
• If the graph is undirected L is symmetric, so L = LT and 1TL = 0.
This latter identity can be obtained computing the transpose of L1n= 0
• [Lx]i = dout(i)(xi− weighted-evrage(xj) for all j neighbour of i if the graph is loopless.
• The diagonal elements are always non-negative, while the off diagonal are always non-positive.
• All the eigenvalues λi(L) have non-negative real part.
This latter property can be easily prooved using the first Gershgorin theo- rem: The theorem states that, given a square n × n matrix A = [aij] and calling
Kir= {z ∈ C : |z − aii| <= Rri} Kic= {z ∈ C : |z − aii| <= Rci} where aii is a diagonal element of A and
Rri =
n
X
j,j6=i
|aij| row-sum
Rci =
n
X
j,j6=i
|aji| column-sum
all the eigenvalues of A are inside the intersection between the union of all the Kir and the union of all the Kic.
So if
Kr=[
i
Kir and Kc=[
i
Kic λi(A) ∈ Kr∩ Kc ∀i
In our case A = L so by definition Rri =
n
X
j,j6=i
|aij| = aii ∀i
So this means that all the Kir are circles in the Gauss plane centered in (Rir, 0) with radius Rri:
Figure 13: Row-Ghershgorin circles
So Kr, which is the union of alla the circles, corresponds to the biggest one and can be written as
Kr= {z ∈ C : |z − kLk∞
2 | ≤ kLk∞ 2 }
Since the intersection of Kr with any other set is either empty or inside Kr itself, we can conclude that the real part of the eigenvalues of a Laplacian matrix are all non negative.
We can define as a generalized Laplacian any L such that:
L =
li,j < 0 if i 6= j and i adjacent to j
li,j = 0 if i 6= j and i is not adjacent to j any number otherwise
This can be useful in some cases, for example if we consider L = Din− AT
L is a generalized Laplacian (notice that it corresponds to the Laplacian obtained inverting the direction of the edges in the graph). In this way the quantity Lx can be seen as the difference between the information of each node and the information that it receives from the others, for example:
Figure 14: Graph example
L =
2 −1 0 0 −1
−1 1 0 0 0
−1 0 1 0 0
0 0 −1 2 −1
0 0 0 0 0
Lx =
2x1− x2− x5 x2− x1 x3− x1 2x4− x3− x5
0
2.3 Some properties of matrices
In this section some matrix properties that will be used in the next sections are given.
Block matrix determinant: considering a block matrix as H =A B
C D
we can factorize it as:
H =
I 0
CA−1 I
A 0 0 S
I A−1B
0 I
= H1H2H3
where S is the Schur‘s complement of H, S = D − CA−1B. It holds that det(H) = det(H1)det(H2)det(H3) and since det(H1) = det(H2) = 1, det(H) = det(H2). So now we can write that:
det(H) = det(A 0 0 S
) = det(A)det(S) = det(A)det(D − CA−1B)
Matrix pseudo-inverse: given any A ∈ Rn,m ,it is defined A†such that:
• AA†A = A
• A†AA†= A†
• AA† and A†A symmetric
A† is called the Moore-Penrose inverse of A, or pseudo-inverse of A. Some properties of the pseudo inverse are:
• If A is invertible A†= A−1
• (A†)†= A
• (αA)†= α1A†
• If λi is an eigenvalue of A and λi 6= 0, then λ1
i is an eigenvalue of A†
• If λi is an eigenvalue of A and λi = 0, then also the correspondent eigenvalue of A† is 0.
2.4 Kronecker Product
Given any two matrices A = [ai,j] ∈ Rp,q and B = [bi,j] ∈ Rn,m, the Kro- necker product is defined as:
A ⊗ B =
a11B ... a1qB ... ... ...
ap1B ... apqB
So it is always doable and the result is a matrix ∈ Rpn,qm. For example:
1 2 2 5
⊗0 7 1 −1
=
0 7 0 14
1 −1 2 −2
0 14 0 35
2 −2 5 −5
Some properties:
• A ⊗ (B + C) = A ⊗ B + A ⊗ C
• A ⊗ B 6= B ⊗ A in general
• (αA) ⊗ B = A ⊗ (αB) = α(A ⊗ B)
An useful concept that will be used later is the Kroneker product between a Laplacian matrix and a diagonal matrix. Let‘s consider an example:
L = L1⊗ R
where L1 =
1 −1 0
−1 2 −1
0 −1 1
and R =1 0 0 2
. So we get
L =
1 0 −1 0 0 0
0 2 0 −2 0 0
−1 0 2 0 −1 0
0 −2 0 4 0 −2
0 0 −1 0 1 0
0 0 0 −2 0 2
L1 is related to the following graph:
Figure 15: L1 graph
While L is related to the following one:
Figure 16: L graph
So basically the result is a set of disjointed graphs with all the weights scaled by the correspondent diagonal entry of R. Notice that, even if the Kroneker product is not commutative in general, the effect on the graph topology is the same inverting the product order. We just get a different nodes enumeration.
Lc= R ⊗ L1=
1 −1 0 0 0 0
−1 2 −1 0 0 0
0 −1 1 0 0 0
0 0 0 2 −2 0
0 0 0 −2 4 −2
0 0 0 0 −2 2
That corresponds to the following graph:
Figure 17: Lc graph
2.5 Differential equations canonical form
Any linear ordinary differential equation of order n can be reduced to a system of n linear ordinary differential equations of order 1. Given:
any(t)(n)+ an−1y(t)(n−1)+ ... + a2y(t) + a¨ 1y(y) + a˙ 0y(t) = g(t) we ca call:
x(t) =
x1(t) x2(t) ...
xn(t)
=
y(t)
˙ y(t)
...
y(n−1)(t)
; x(t)˙
˙ y(t)
¨ y(t)
...
y(n)(t)
So the equation can be written as:
anx˙n+ an−1xn+ ... + a1x2+ a0x1 = g(t)
˙ x1= x2
...
˙
xn−1= xn
The latter systme can be written in a compact matrix form:
A ˙x(t) + Bx(t) = C(t) where:
A =
1 0 ... 0 0 1 ... 0 ... ... ... ...
0 0 ... an
; B =
0 −1 0 0 ... 0
0 0 −1 0 ... 0
0 0 0 −1 ... 0
... ... ... ... ... ...
a0 a1 a2 a3 ... an−1
C(t) =
0 ...
g(t)
If aiare scalar then A is always invertible and we can reduce to a simpler form ˙x(t) + Ax(t) = g(t), if ai are matrices the method can still be used, we will have I (identity matrix) instead of 1 and A, B will be block matrices.
3 Undirected graphs case
In this section the problem of controlling a MAS under undirected connected topologies is faced analyzing the main methods found in literature. In par- ticular, the problem is applied in the aerospace field in which each agent represents a satellite orbiting in Low-Earth Orbit and the graph topology the capability of agents to share information on angular position and/or velocity. The set of equations describing the single agent dynamic is the following [1],[2]:
(Jiθ¨i(t) + δTi η¨i(t) = ui(t)
δiθ¨i(t) + ¨ηi(t) + Ciη˙i(t) + Kiηi(t) = 0
These equations describe the rotational motion of a rigid body with flexible appendages. Considering the rotations in a 3-dimensional space, θi(t) ∈ R3 is the vector of rotations around the three axes and Ji is the inertia matrix.
Vector ηi(t) ∈ Rmj is the modal coordinates vector representing the flexible modes of the appendages, mj is the number of modes. Ci ∈ Rmj,mj is the damping coefficients matrix and Ki∈ Rmj,mj the stiffness matrix. δi∈ R3,mj is the coupling matrix between the space of θi(t) and the space of ηi(i). At last, the control input is ui(t) ∈ R3.
Considering a set of N agents, i = 1, 2, ..., N , so we have a set of 2N equations. It can be grouped using block matrices:
θ(t) =θ(t)T1 θ(t)T2 ... θ(t)TNT
η(t) =η(t)T1 η(t)T2 ... η(t)TNT
u(t) =u(t)T1 u(t)T2 ... u(t)TNT
and
J = blockdiag(J1, J2, ..., JN) C = blockdiag(C1, C2, ..., CN) K = blockdiag(K1, K2, ..., KN)
∆ = blockdiag(δ1, δ2, ..., δN)
where θ(t) ∈ R3N, η(t) ∈ RmtotN, with mtot=P
jmj, u(t) ∈ R3N, J ∈ R3N,3N, C ∈ Rmtot,mtot, K ∈ Rmtot,mtot, ∆ ∈ Rmtot,3N.
The set of equations can be written as:
(J ¨θ(t) + ∆Tη(t) = u(t)¨
∆¨θ(t) + ¨η(t) + C ˙η(t) + Kη(t) = 0 In addition, coefficients matrices have some properties:
J = JT > 0; C = CT > 0; K = KT > 0;
J ∆T
∆ I
> 0
This latter property is found in literature [1],[2], and the necessity of it is also prooved in section 4.4. ”>” stands for positive definite matrix. Matrices Ci and Ki can be defined from the natural frequency ωj and the damping coefficient ζj of each fexible mode in the following way:
Ci= diag(2ζjωj); Ki = diag(ω2j) ∀ j
So also C and K are diagonal matrices. The following table reports ans example used as a reference for next sections:
Figure 18: Table 1
The modes are considered to be 4 for all the agents and a random variance added from the nominal values in Table 1. So Ci ∈ R4,4 and Ki ∈ R4,4
3.1 Measurable velocities
In this first case, angular velocity and displacement are considered to be measurable by the agents, so they are supposed to be equipped with gyro- scopes. For now, the objective is considered to be the reach of consensus without the presence of a leader (reference), that will be introduced later.
Formally, consensus is:
t→∞lim ||θi(t) − θj(t)|| = 0 ∀ i, j
t→∞lim || ˙θi(t) − ˙θj(t)|| = 0 ∀ i, j
meaning that all the agents reach the same state, or the same position and velocity.
The proposed control law is the following:
ui(t) = −g
N
X
j
pijR( ˙θi(t) − ˙θj(t)) −
N
X
j
qijR(θi(t) − θj(t))
R is, at least, a positive definite matrix, that in general should be considered also diagonal for sake of simplicity. pij, qij and g are the control parameters.
It is well known from literature [9], that, if pij = pji, qij = qji and g > 0, consensus is reached, and the final value of the angular positions and veloc- ities is the average among the initial conditions (time averaging consensus).
This control law can be better understood in matrix form: calling
Lv = [lij]v = (P
jpij i = j
−pij i 6= j ; Ld= [lij]d= (P
jqij i = j
−qij i 6= j ; the control law is:
u(t) = −(gLv⊗ R) ˙θ(t) − (Ld⊗ R)θ(t)
Hence, it can be seen as a PD-like (Proportional Derivative) controller.
Matrices Lv and Ldare the Laplacian matrices corresponding to the graph of the communication topology of angular velocities and displacements. Since pij = pji and qij = qji, the graph is undirected and Lv = LTv ≥ 0, Ld = LTd ≥ 0.
It is easier to understand now the role of matrix R since, as explained in
Some simulations are now performed with different topologies:
Simulation 1
A total of N = 5 agents is considered. The communication topology is considered to be the same for angular velocities and displacements, so Lv = Ld= L. L = D − A corresponds to the following graph:
Figure 19: Simulation 1 graph
The simulation parameters are:
L = 100
1 −1 0 0 0
−1 2 −1 0 0
0 −1 2 −1 0
0 0 −1 2 −1
0 0 0 −1 1
; g = 4
The initial displacements are set at random between −1 and 1, while initial velocities are set to 0 as the initial conditions of the modal vectors. C and K are defined randomly starting from Table 1. J and ∆ are also defined randomly starting from:
J0=
100 3 4
3 280 10 4 10 190
; δ0=
6.4564 1.2781 2.1563
−1.2562 0.9176 −1.6726 1.1169 2.4890 −0.8367 1.2364 −2.6581 −1.1250
while the matrix R are set as the identity matrix.
The following Figures (20-21) show the transient of the roations around the y − axis and the space of phases of x − y positions and velocities:
Figure 20: y-axis rotations of agents 1 to 5, Simulation 1
Figure 21: x-y plane of rotations (left) and velocities (right)
As expected, angular positions reach consensus to the average among the initial positions (Figure 20). In the phase space plots (Figure 21), we can also see how velocities start and finish at 0, so the paths are closed.
Flexible modes all converge to 0 since K > 0 and C > 0.
Simulation 2
In this simulation N = 7 agents are considered:
Figure 22: Simulation 2 topology, 7 agents
The simulation setting are the same as in simulation 1, but in this case velocities are also set at random value, different from 0. The following Figures (23-24) show the velocity and displacements transients and the x-y plane portraits:
Figure 23: y-axis rotations and velocities of agents 1 to 7, Simulation 2
Also in this case both velocities and displacements reach consensus. With respect to the previous situation, in this case positions trend is to diverge as ramps with a slope equal to the average initial velocity.
Figure 24: x-y plane portraits, Simulation 2
L = 100
2 −1 −1 0 0 0 0
−1 2 0 −1 0 0 0
−1 0 2 −1 0 0 0
0 −1 −1 4 −1 −1 0
0 0 0 −1 2 0 −1
0 0 0 −1 0 2 −1
0 0 0 0 −1 −1 2
3.2 Non-measurable velocities
Often satellites are not equipped with gyroscopes, so they are not able to get measure of angular velocity. For this reason, the control law in section 3.1 can be modified [1] as follows:
(ui(t) = −zi(t) − gPN
j pijR(θi(t) − θj(t))
˙zi(t) = −gzi(t) − gPN
j (gpij − qij)R(θi(t) − θj(t))
Also in this case we can use block matrices to write the equations ∀ i:
(u(t) = −z(t) − (gLv⊗ R)θ(t)
˙
z(t) = −gz(t) − g((gLv− Ld) ⊗ R)θ(t) In this case, z(t) =z1(t)T z2(t)T ... zN(t)TT
is the controller state that changes dynamically following the second equation in the set. In this case the parameter g has a lower bound, and in literature [1] we can find that always exists a g sufficiently large such that the system reaches consensus.
Simulation 2 of section 3.1 is reproposed with this modified control law, initial velocities are set to 0, g = 100, Lv = 4Ld= 4L
Figure 25: y-axis rotations transient, Simulation 2
Also in this case consensus is reached, parameters can be tuned to trade between settling time and control input, or to avoid chattering. For sake of completeness, the transient of the modal vectors is shown in the next Figure (26):
Figure 26: modal coordinates transient
Now a last case is analyzed introducing the concept of leader. The leader in undirected topologies is an agent, that can be a real physical object like others or equivalently just a signal, that acts as a reference for the others.
So in this case consensus is the reaching of the same state of the leader:
t→∞lim ||θi(t) − θleader(t)|| = 0 ∀ i
t→∞lim || ˙θi(t) − ˙θleader(t)|| = 0 ∀ i
As found in [29], control laws are able to guarantee consensus also in the presence of a leader. To make the leader a constant reference we set its dynamic to be:
Jleaderθ¨leader(t) = 0; ηleader(t) = 0
A simulation is now presented with the following topology. The leader is
Figure 27: Directed topology with the presence of a leader
set as a convention in the last position in the enumeration (Agent 7, circled in red). Since the leader is not moving, its state is constant and equal to the initial conditions, the other agents should converge to it. In this example leader‘s initial conditions are:
θleader(0) =0.7684 0 0.224T; ˙θleader(0) =0 0 0T
The following figure shows the transient of the rotations around the x-axis:
Figure 28: Directed topology with the presence of a leader
4 Directed graph cases
In this section directed topology cases are be introduced, the main results of this work and related proofs are shown.
4.1 Eigenprojections in dynamic systems
To introduce the main results eigenprojections and their applications in dynamic systems are shown. In general the eigenprojection of a matrix A is an idempotent matrix A+ that satisfies:
Range(A+) = N ull(Aν) Range(Aν) = N ull(A+)
where ν is the smallest natural number such that rank(Aν) = rank(Aν+1).
Since A+ is idempotent, it is completely determined by its range and null space. Let‘s take an example:
A =
2 −1 −1
0 1 −1
0 0 0
A+=
0 0 1 0 0 1 0 0 1
In this case rank(A0) 6= rank(A1),rank(A1) = rank(A2) so ν = 1. A basis of the range of A can be {
2 1 0
,
1 1 0
} and a basis of the null space is
1 1 1
.
So the dimension of null(A) is 1, that will correspond to the dimension of range(A+), while the dimension of range(A) is 2, that will correspond to the dimension of null(A+). This means that rank(A+) = 1. It is a property of idempotent matrices to have the trace equal to the rank [6] so trace(A+) = rank(A+) = 1. Combining this with range(A+) = span(
1 1 1
) we get:
A+ =
0 0 1 0 0 1 0 0 1
Notice that the non-zero column must be the third otherwise null(A+) 6=
range(A). From this example we can see a useful property of eigenprojec- tions: if a square matrix A such that rank(A) = rank(A2) has a row all set
to 0, its eigenprojection is a matrix with the correspondent column set to 1 and all other entries set to 0.
It is a property of eigenprojections that:
A+= lim
|τ |→∞(I + τ Aν)−1
that can be used to link eigenprojections with dynamic systems. To this end, let‘s consider the following differential equation:
˙
x + Ax = 0 and its Laplace transform:
sx(s) − x0+ Ax(s) = 0 → x = (sI + A)−1x0
We know that the solution in time domain is x(t) = e−Atx0, so using final value theorem if limt→∞x(t) exists and is finite we can write:
s→0lims(sI + A)−1x0 = lim
t→∞e−Atx0
Since in general (CB)−1= B−1C−1, if C = sI + A and B = 1sI:
s→0lims(sI + A)−1= lim
s→0[(sI + A)1
sI]−1 = lim
s→0(I +1 sA)−1 Now calling τ = 1s and if ν = 1:
t→∞lim e−Atx0 = lim
|τ |→∞(I + τ A)−1x0 = A+x0
So we can conclude that if the solution of a first order differential equation like ˙x + Ax = 0 has a finete limit to infinity, it is equal to A+x0if rank(A) = rank(A2). We can now apply this to some simple cases involving Laplacians.
Let‘s consider
˙
x + Lx = 0
where L = Din− AT is the generalized Laplacian associated to a general directed graph one source(leader) and a directed spanning tree starting from it, for example:
Figure 29: Graph example
L =
2 −1 −1
0 1 −1
0 0 0
L+=
0 0 1 0 0 1 0 0 1
Since the graph has a source, the correspondent third row is 0. This means that, since rank(L) = rank(L2), the eigenprojection of L has the third column set to 1 and all other entries set to 0, as already shown. Moreover the 0 eigenvalue of L is simple, so since other eigenvalues are all positive, the solution converges. This means that:
t→∞lim x(t) = L+x0 =
x0(3) x0(3) x0(3)
meaning that all the agents will converge to the source‘s (leader) initial condition (consensus).
Figure 30: First order transient example
This latter example can be generalized for all directed graphs with a source, since rank(L) = rank(L2) holds in general. To show it let‘s take the Jordan form of such Laplacian:
L = T J T−1; J =
J0 ... 0 0 0 J1 ... 0 ... ... ... 0 0 0 ... Jn
where Ji is the Jordan block associated to the ith eigenvalue of L. Now taking the square of L: L2 = LL = T J T−1T J T−1 = T J2T−1. Since T is full-rank, the rank of L2 is the same of J2.
J2=
J02 ... 0 0 0 J12 ... 0 ... ... ... 0 0 0 ... Jn2
Consider in a slightly more general case d as the number of sources in the graph, rank(L) = n − d, moreover d is also the number of rows set to 0 in the Laplacian (if d = 0 then rank(L) = n − 1 since we have the 1 vector that is a basis of null(L), but the reasoning is the same). This means that the algebraic multiplicity of the 0 eigenvalue is always equal to geometric multiplicity, this can be shown writing g (geometric multiplicity) as g = dim{null(L − 0I)} = dim{null(L)} that is equal to the number of zero rows of L. This means that the 0 eigenvalue is semisimple and that the correspondent Jordan blocks are of dimension 1. All other Jordan blocks are full-rank so this implies that rank(J2) = rank(J ). For example:
L =
2 −1 −1 0
0 0 0 0
0 0 0 0
0 0 0 0
J =
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
rank(L2) = rank(L) = rank(J ) = rank(J2).
Let‘s now analyze the second order case, starting from a general case like:
¨
xc+ gL ˙xc+ Lxc= 0
where g ≥ 0 is a real number. We can transform the system in a first order one as in (2.5):
˙
x + Ax = 0 where A = 0 −I
L gL
and x = xc
˙ xc
. In this case rank(A) 6= rank(A2) so we can‘t use the same approach as for the first order dynamics. Let‘s at first study the sign of the eigenvalues of the system: using block matrices properties (2.3) we can write that:
det(H1 H2 H3 H4
) = det(H1)det(H4− H3H1−1H2) and apply it to A − sI:
det(−sI −I L gL − sI
) = det(−sI)det{gL − sI − L(−1
sI)(−I)} =
= det(−sI)det(gL − sI − 1
sL) = det(−sI)det((g − 1
s)L − sI) =
= det(−sI)det(L − s g − 1sI) So if λi = si
g−1
si
is an eigenvalue of L, si is an eigenvalue of A. We can now solve the latter equation to find the eigenvalues of A as function of those of L:
s2i − gλis + λi= 0 s1,2i =
gλi±q
g2λ2i − 4λi 2
If all the eigenvalues of L are real, we know that λi ≥ 0, so if g2λ2i < 4λi
the square root is complex and Re{si} = gλi ≥ 0 since g ≥ 0. If g2λ2i ≥ 4λi the square root is a real number, but
q
g2λ2i − 4λi ≤ gλi so also in this case si ≥ 0. If the eigenvalues of L are in general complex, a more strict bound for g that guarantees the eigenvalues si to have non negative real part can be found in literature [3], in particular
g2 > Im2(λi)
∀ i|λi 6= 0
If the two Laplacians matrices are not the same, the explicit computation of eigenvalues is not trivial and can be done using numerical tools. This shows that all the eigenvalues of the system are non-negative, but still we have to proove consensus.
To this end, let‘s consider the solution in the time domain x(t) = e−Atx0. The exponential can be replaced by its Taylor series:
e−At= I + (−A)t + (−A)2t2
2 + (−A)3t3 3!+ ...
Now substituting the canonical Jordan form of A = T J T−1 we get:
e−At = I + (−T J T−1)t + (−T J T−1)2t2
2 + (−T J T−1)3t3 3! + ...
Since all the powers can be written as (T J T−1)n = T JnT−1, the whole exponential can be rewritten as:
e−At = T e−JtT−1
From now on, let‘s consider A as (−A) for sake of simplicity, so all the eigenvalues of A are non-positive. The Jordan matrix J can be written as J = diag(J0, J1, ..., Jn) where Ji is the Jordan block associated to the i − th eigenvalue. If we consider J0 as the Jordan block of the 0 eigenvalue, since it has algebraic multiplicity 2 and geometric multiplicity 1, it is equal to:
J0 =0 1 0 0
Moreover ediag(ji)= diag(eJi) so we can write:
eJ t=eJ0 0 0 eF t
where F is the block matrix containing all the non-zero eigenvalues of A.
Notice that J0n= 0 for any natural n > 1 so:
eJ t=I + J0t 0 0 eF t
Let‘s now consider the final value taking the limit:
t→∞lim eJ t≈I + J0t 0
0 0
Now we can say that
t→∞lim eAt ≈ TI + J0t 0
0 0
T−1 = T
1 t 0 1
0
0 0
T−1
T is a matrix whose columns are the right generalized eigenvectors of A, while T−1 is a matrix whose rows are the left generalized eigenvectors of A. Since in J we put the two zero eigenvalues in the first to places, the correspondent left and right eigenvectors will be in the first two columns and rows of T−1 and T that are respectively l1 = 1 0 0 .. 0T and l2=0 1 0 .. 0T, r1 =1 0 1 0..T and 0 1 0 1..T. This can be intuitively seen considering that if we take a vector v that has all zero entries exept one set to 1, vTA = 0 if the 1 is in the same place of the 0 row of L. Moreover if we take a vector v with half of the entries set to 1, and the other half set to 0 (0 0 0 1 1 1T for instance), Av = 0. Then Jordan form ”rearrange” variables in order to have the alternation of xi and ˙xi, so also the entries of the eigenvectors will follow that pattern. Now, calling xl
and ˙xl the initial conditions of the leader, we can compute:
t→∞lim eAtx0≈ T
1 t 0 1
0
0 0
T−1x0=
xl+ ˙xlt
˙ xl
xl+ ˙xlt
˙ xl ...
where x0 =xl x˙l xc0(1) x˙c0(1) xc0(2) x˙c0(2) ...T
is the initial con- ditions vector with the initial position and velocity alternated for each agent.
This establishes consensus since the positions and velocities of all the agents (leader included) are the same. Moreover notice that position diverges as a ramp, and that if ˙xl = 0 all the agents converge to the same constant position. At last it can be useful write this latter result as
t→∞lim eAtx0 ≈L+ L+t 0 L+
x00
where x00 =xc(0)
˙ xc(0)
.
4.2 Rigid dynamics, continuous time
Goin back in the aerospace context, let‘s start with simple cases, so flexi- ble dynamics and external disturbances will be neglected. Considering N agents, we can write the single agent dynamic as Jiθ¨i = ui where Ji is the inertia matrix of the i-th agent, θi= [θixθiyθiz]T and ui = [uix uiyuiz]T.
We can apply to the dynamic system the following control law:
(J ¨θ = u
u = −gL ˙θ − Lθ
where J = blkdiag{J1, J2, ..., JN}, θ = [θT1, θ2T, ..., θNT]T and L = L1⊗ R with R a diagonal positive matrix.
L1represents the communication topology between the agents and L = L1⊗ R splits in 3 identical graphs that do not share information each other, one for each coordinate, as explained in section 2.4. In general the comunication topology among the agents is considered to have one Leader wich is a source and a directed spanning tree. The Laplacian is a generalized one computed as L = Din− AT.
As before (referring to section 3, not done yet), consensus is reached if:
t→∞lim ||θi(t) − θj(t)|| = 0 ∀ i, j
t→∞lim || ˙θi(t) − ˙θj(t)|| = 0 ∀ i, j
Since J is positive definite, also J−1 is and ¨θ + gJ−1L ˙θ − J−1Lθ = 0 re- spects all the hypothesis used in section (4.1) since multiplying by a positive definite matrix doesn‘t change the sign of the eigenvalues, so consensus is reached. The g parameter and the weights in the communication graph can be changed to tune the system behaviour as shown in the following numerical examples.
Example 1: in this first simulation 4 agents and a leader are considered.
System parameters are the following:
L1 = (Din− AT) = 200
1 0 0 0 −1
−1 1 0 0 0
0 −1 1 0 0
0 0 0 1 −1
0 0 0 0 0
; J0=
350 3 4
3 280 10 4 10 190
;
The leader is considered to be, as a convention, the last in the agents enumeration.
θ(0) θ(0)˙
=
rand(12, 1) θf
0 0 ...
So the initial positions of the agents are random except for the leader that has θ5(0) = θf = [0.7684, 0, 0.224]T that will be the reference for other agents. The g parameter is set to 2. The following Figures(31-32) shows the graph topology and the transient of the θy and ˙θy for all the agents:
Figure 31: Graph topology for rigid dynamics, agent 5 (red) is the leader
Figure 32: y-axis rotation for rigid dynamics
Notice that L has all real eigenvalues, so in this case g > 0 is sufficient to guarantee consensus. In Figure 34 a comparison with different values of g is shown.
Figure 33: y-axis angular velocity fo rigid dynamics
Figure 34: g values comparison
We can notice that as g increases, the oscillatory behaviour decreases.
For very small values of g we get a long transient with great oscillations.
Let‘s now perform the same simulation with the Leader‘s initial velocity different from 0, we expect the final value of the angular position of all the agents to diverge as a ramp with a slope equal to the Leader‘s initial velocity.
Figure 35: Leader‘s initial velocity different from 0
As expected the position of all the agents goes to infinity trying to follow the leader‘s one. In this case the initial condition ˙θ5(0) = 0.1rad/s. Let‘s now analyze more complicated topologies, as the example in the next figure:
Figure 36: Graph topology, agent 8 (red) is the leader
In this case, to get a more realistic simulation, an input saturation is added to the model, that for small satellites can be around 0.02 Nm, so umax= 0.02, umin = −0.02. The initial conditions and physical parameters are the same as the previous simulation, obviously adding 3 agents.
The generalized laplacian L1= Din− AT in this case is:
L1= 200
2 −1 0 0 0 0 0 −1
0 1 −1 0 0 0 0 0
0 0 1 −1 0 0 0 0
0 0 0 1 −1 0 0 0
−1 0 0 0 1 0 0 0
0 0 0 −1 0 1 0 0
0 0 0 0 0 −1 1 0
0 0 0 0 0 0 0 0
Since the eigenvalues are not all real, the lower bound of g is: gmin = 0.0065. Above this value, we can tune g to tune the transient, the following simulation was performed with g = 2.5.
The following Figure(37) shows the transient of the rotations around the y-axis:
Figure 37: y-axis rotations for agents from 1 to 8, rigid dynamics
Consensus is reached in a reasonable time also in the presence of strong lim- itations on the input saturation. Now a different way to tune the transient is shown. Until now, the entire Laplacian matrix has been multiplied by a scalar factor , giving the same weight to all the arcs in the graph. However, the weights of the arcs can be tuned arbitrarely, so the idea is to lower the value of and giving a weight to each arc that is proportional to the distance in the graph between the node that it reaches and the Leader. Taking as an
giving to the arcs different weights as in the following figure:
Figure 38: Graph topology with modified weights
So now the graph Laplacian can be written as:
L1 = Dw(Din− AT); Dw = diag(d); d =1 5 4 3 2 4 5 0
The diagonal matrix Dw depends on the vector d that contains the distances as said before. The previous case can be seen as a subcase where d =
1 1 1 1 1 1 1 0 and = 200, to get similar performance in the two cases, we can set the quantity ||d||1 to be the similar, so since in the first case ||d||1 = 7, can be set to 58 in this second case. The following Figure(39) shows the comparison between the two cases:
Figure 39: Case 1 above, Case 2 below
4.3 Rigid dynamics, discrete time
In this section the discrete time equivalent of the system in section 4.2 is studied. This can be useful to compute an estimate of the angular velocity in case it is not measurable. Let‘s start considering:
˙ x(t) =
θ(t)˙ θ(t)¨
=
0 I
−gJ−1L −J−1L
θ(t) θ(t)˙
= Ax(t) We can use the Euler‘s method to discretize ˙x(t) = Ax(t):
˙
x(t) ≈ x(t + k) − x(t) k
x(t + k) ≈ (kA + I)x(t) kA + I =
I kI
−kgJ−1L −kJ−1L + I
So we can say that:
θ(t + k) ≈ θ(t) + k ˙θ(t) θ(t) ≈˙ θ(t + k) − θ(t)
k
This means that the velocity is approximated with the average velocity between two time instants, t and t + k. Clearly limk→0θ(t+k)−θ(t)
k = ˙θ(t) so the approximation is consistent. Now an upper bound for k must be computed to guarantee the convergence of the solution. Recalling that for a discrete LTI system the eigenvalues of the associated matrix must be in the unit circle, we can write:
eig(kA + I) = 1 − k
gλi±q
g2λ2i − 4λi 2
where λi is an eigenvalue of J−1L. Calling sj = gλi±
√
g2λ2i−4λi
2 and re-
calling (4.1) that if g2> Re(λIm2(λi)
i)||λi||2 , Re(sj) > 0 for all non zero eigenvalues.
Let‘s call Remin the minumum real part among the real parts of all the non zero sj, all the non zero eigenvaluea of A lie in a circular segment:
sj ∈ Θ = {X : X = a + ib; a2+ b2≤ k||sj||max; a ≥ kRemin}
So 1 − ksj for k = 1 lies in a circular segment that is flipped with respect to Θ and translated by 1, in the following Figure (40) represented by the green area:
Figure 40: Visual proof
In this Figure (40) smax = ||sj||max is the maximum modulus among all the eigenvalues. The distance BC is BC = 1 − Remin. Reducing k both the radius of Θ and the distance from point C = (1,0) are reduced. To ensure Θ ⊂ U where U is the unit circle (grey circle with dashed edge), segment AB for a generic k must be less or equal to segment ED.
AB =p
k2s2max− (1 − kRemin)2, ED =p
1 − (1 − kRemin)2 AB ≤ ED → k2s2max− (1 − kRemin)2≤ 1 − (1 − kRemin)2
k ≤ 1
s ↔ k ≤ 1
||s || ∀ j : sj 6= 0
