Coordinated Control and Maneuvering of a
Network of Micro-satellites in Formation
DISSERTATION
submitted to the
Faculty of Electrical Engineering
Computer Science and Mathematics
University of Paderborn
by
Arvind Krishnamurthy
in partial fulfillment of the requirements for the degree of
doctor rerum naturalium
(Dr. rer. nat.)
Paderborn, Germany
August 9, 2007
First, inevitably, the idea, the fantasy, the fairy tale. Then, the scientific calculation.
Ultimately, fulfillment crowns the dream.
-Konstantin Tsiolkovsky, 1926.
c
2007
Arvind Krishnamurthy
All rights Reserved
To my beloved wife, Malavika
Acknowledgements
I would like to start by thanking my advisor, Prof. Dr. Michael Dellnitz, as this thesis
would not have been possible without his kind support, his probing questions, and his
remarkable patience. I cannot thank him enough for his invaluable guidance throughout
my time of research at Paderborn.
I am also grateful to my co-advisor, Prof. Dr. Franz Josef Rammig, who, ever cheerfully
and jovially motivated me during this research. I am indebted to him for always lending a
helpful hand.
I would also like to thank Prof. Dr. Joachim Lueckel for providing helpful insights on
this thesis. I am grateful to Dr. Martin Ziegler and Dr. Kai Gehrs for accepting to be on
my examination board
I am ever grateful for the insightful inputs from Prof. Dr. Oliver Junge (presently in
Technical University of Munich) and Dr. Robert Preis, whose doors were always open for
any discussion.
I am indebted to the entire working group of Prof. Dellnitz for making my tenure at
Univeristy of Paderborn both pleasurable and resourceful. In particular, I would like to
thank Mirko Hessel-von Molo, Sina Ober-Bloebaum and, Stefan Sertl for their constant
support and engaging discussions.
I thank my colleagues from the working group of Prof. Rammig for their support. My
exciting joint work here, with Johannes Lessmann, is worth a special mention. We still
have many exciting projects in mind for the future!
My heartfelt gratitude to my ever supportive and patient wife Malavika, who endured
my long absence from home, late night university trips, and my constant bikering about
the satellites, with a beautiful smile. This thesis is hard to imagine without her help. I am
also thankful to my parents and brother, for their support and constant encouragement of
my plans to pursue a Ph.D.
Finally, this thesis is a blessing of my lord, Bhagwan Sri Sathya Sai Baba.
4
Board of reviewers
•Prof. Dr. Michael Dellnitz
•Prof. Dr. Franz Rammig
•Prof. Dr. Joachim Lueckel
Defended on August 9, 2007
Abstract
Several currently planned space missions consist of a set of micro-satellites flying in a for-
mation. This enables a much higher functionality of the mission compared to missions
consisting of only a single large satellite. On the other hand, this introduces several new
problems, especially in the handling of the formation. Besides their geometric structure, the
formation of micro-satellites also has a communication network among the micro-satellites
which is the basis for the cooperative behavior of the micro-satellites in order to accomplish
the overall aim of the mission.
The first part of the research has resulted in the development of a new control law for the
controlled formation flight of micro-satellites in the halo-orbit proximity. In this process,
we also address the issue of stability of the formation based on the Laplacian eigenvalues,
modified stability radius, and hence, evaluate their performance. The central problem
addressed by this thesis is the problem of constructing an efficient non-linear control law
while considering the topology of the communication network of the micro-satellites. The
topology of this communication network can be a bottleneck in the operation of the forma-
tion because the transmission of information and the efficient coordination of the formation
relies on this topology. This is particularly the case for a large number of micro-satellites
in the network. We consider the modified and a new developed structured stability radius
for the formation of micro-satellites to analyze their behavior in response to some destabi-
lizing factors which are the case in the most realistic scenarios where the micro-satellites
are deployed. Finally, we achieve the non-linear control law which includes the “formation
keeping control” and “leader follower control” to achieve the efficient controlled formation
flight in a periodic orbit which is a result of solving the Hill’s equation.
In the second part, we derive a multi-level multi-metric clusterization technique to solve
the problem of accommodating larger number of micro-satellites in the formation while
maintaining the required small distances for optical interferometry. We consider the sensor
network of the micro-satellites which result due to the inter-micro-satellite sensing and also
the sensing of the outer-space data by the space telescopes. We derive a hierarchical multi-
metric algorithm for the clusterization of the micro-satellites in the formation. We achieve
the desired goal of hexagon of hexagons and further on if required by our clusterization
algorithm and compare it with the traditional greedy algorithms to show it efficiency.
6
Zussamenfassung
Mehrere gegenwrtig geplante Raumfahrtmissionen sehen eine Menge von Mikrosatelliten
vor, die in einer Formation fliegen. Dies ermglicht eine weit grere Funktionalitt verglichen
mit einer Mission, in der nur ein einziger groer Satellit eingesetzt wird. Auf der anderen
Seite bringt dies mehrere neue Probleme mit sich, insbesondere was die Handhabung
der Formation angeht. Auer durch ihre geometrische Struktur ist eine Mikrosatelliten-
Formation durch ein Kommunkationsnetzwerk gekennzeichnet, das die Basis fr das koop-
erative Verhalten der Mikrosatelliten ist, welches fr das Gesamtziel der Mission erforderlich
ist. Der erste Teil der Forschungsarbeit hat zur Entwicklung eines neuen Kontrollgesetzes
fr den kontrollierten Formationsflug der Mikrosatelliten in Halo-Umlaufbahn Nhe gefhrt.
Dabei wird auch der Aspekt der Formationsstabilitt auf der Basis der Laplace Eigenwerte,
des modifizierten Stabilittsradius bercksichtigt und somit ihre Leistungsfhigkeit untersucht.
Das zentrale Problem, das in dieser Arbeit behandelt wird, ist das Problem der Konstruk-
tion eines effizienten nicht-linearen Kontrollgesetzes unter Bercksichtigung der Topologie
des Kommunikationsnetzwerks der Mikrosatelliten. Die Topologie dieses Kommunikation-
snetzwerks kann ein Flaschenhals im Betrieb der Formation sein, da die bertragung von
Informationen und die effiziente Koordination der Formation von dieser Topologie abh-
ngt. Das ist insbesondere fr eine grere Anzahl von Mikrosatelliten im Netzwerk der Fall.
Wir betrachten den modifizierten und einen neu entwickelten strukturierten Stabilittsra-
dius fr Mikrosatelliten-Formationen und analysieren ihr Reaktionsverhalten auf einige
destabilisierende Faktoren, welche in den realistischsten Einsatzgebieten von Mikrosatel-
liten vorkommen. Schlielich erhalten wir das nicht-lineare Kontrollgesetz, welches die
”Formationserhaltungs-Kontrolle” und die ”Leiter-Nachfolger-Kontrolle” enthlt, um einen
effizienten kontrollierten Formationsflug in einer periodischen Umlaufbahn zu erreichen,
die das Resultat der Lsung der Hill-Gleichungen ist.
Im zweiten Teil entwickeln wir eine Multi-Metrik Mehrschicht Cluster-Bildungs-Technik,
um das Problem grerer Zahlen von Mikrosatelliten in einer Formation zu lsen, wobei die er-
forderlichen kleinen Distanzen fr optische Interferometrie aufrechterhalten werden mssen.
Wir betrachten das Sensor Netzwerk aus Mikrosatelliten mit Inter-Satelliten-Messungen
und Messungen des Alls durch Weltraumteleskope. Wir entwickeln einen hierarchischen
Multi-Metrik Algorithmus zur Cluster- Bildung der Mikrosatelliten in der Formation.
Wir erreichen das gewnschte Ziel der Hexagonen von Hexagonen (und, falls von unserem
Cluster-Bildungs-Algorithmus gefordert, darber hinaus) und vergleichen es mit einem tra-
ditionellen Greedy-Algorithmus, um die Effizienz zu zeigen.
7
Contents
1 Introduction 12
1.1 Formation of Vehicles: Micro-satellites . . . . . . . . . . . . . . . . . . . . 12
1.2 OutlineoftheThesis.............................. 17
1.2.1 Formation of Micro-satellites in the Halo Orbit Proximity . . . . . . 18
1.2.2 Implementation............................. 21
1.3 ChapterContributions ............................. 23
2 A Standard Approach: Linear Modeling of the Formation 26
2.1 Introduction................................... 26
2.2 TheModel.................................... 27
2.2.1 GraphLaplacian ............................ 27
2.2.2 The Dynamics of the Formation . . . . . . . . . . . . . . . . . . . . 29
2.2.2.1 Inter-microsatellite Spacing . . . . . . . . . . . . . . . . . 30
2.2.2.2 Entire Formation Dynamics . . . . . . . . . . . . . . . . . 30
2.3 StabilityAnalysis ............................... 31
2.4 Examples .................................... 31
2.4.1 Formation of Three Micro-satellites . . . . . . . . . . . . . . . . . . 31
2.4.2 Formation of Four and Five Micro-satellites . . . . . . . . . . . . . 32
2.4.3 Formation of Six Micro-satellites . . . . . . . . . . . . . . . . . . . 32
2.5 Extensionofthemodel............................. 34
2.6 Conclusion.................................... 35
3 Analysis of the Role of Communication Topologies in the Stability of a
Formation 39
3.1 Introduction................................... 39
3.2 Basic Results on the Laplacian Matrix . . . . . . . . . . . . . . . . . . . . 40
3.3 Role of the Communication Topologies in an Autonomous Setting . . . . . 41
3.4 Role of the Communication Topologies in a Non Autonomous Setting . . . 43
3.4.1 Minimal Laplacian Eigenvalues . . . . . . . . . . . . . . . . . . . . 44
3.4.2 Robustness of Communication Graphs . . . . . . . . . . . . . . . . 44
3.5 An Example: The Topologies of the Formation of Six Micro-satellites . . . 45
3.5.1 Inferences ................................ 46
3.6 Conclusion.................................... 48
8
4 Stability Radius 49
4.1 Introduction................................... 49
4.2 Theoretical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.1 Mathematic Formulation of Stability Radius . . . . . . . . . . . . . 50
4.2.2 Minimal Singular Value . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.3 (Complex) Stability Radius . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Modification of Stability Radius . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Structured Stability Radius . . . . . . . . . . . . . . . . . . . . . . 54
4.3.2 Robustness of a Communication Topology using the Stability Radius 56
4.4 Example..................................... 57
4.5 Inferences .................................... 60
4.6 Robustness: Minimal Laplacian Eigenvalues vs Stability Radius . . . . . . 60
4.7 Conclusion.................................... 61
5 Formation of Micro-satellites: A Non-Autonomous Model 63
5.1 Introduction................................... 63
5.2 Formation Keeping Control . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.1 Example................................. 66
5.3 The Non-Autonomous Model . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.3.1 Hill’sModel............................... 70
5.3.2 Leader Follower Strategy . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3.3 StabilityAnalysis............................ 75
5.4 Single Leader Multiple Followers . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5 Formation of Micro-satellites in the Proximity of the Halo Orbit . . . . . . 79
5.5.1 Formulation of the Follower Dynamics Relative to the Halo Orbit . 79
5.5.2 Extension of the Formation Keeping Control . . . . . . . . . . . . . 81
5.5.3 Equation of Motion for Controlled Formation Flight Around the
Halo-orbit................................ 82
5.6 Measure of the Deviation of the Formation . . . . . . . . . . . . . . . . . . 83
5.6.1 Example................................. 83
5.7 StabilityAnalysis................................ 87
5.8 Conclusion.................................... 93
6 Micro-satellite Formation, a Mobile Sensor Network in Space 94
6.1 Introduction................................... 94
6.2 Formation of Micro-satellites as a Wireless Sensor Network . . . . . . . . . 95
6.2.1 Factors for an Ideal Sensing Structure (Robustness) . . . . . . . . . 96
6.2.1.1 Definitions .......................... 97
6.2.1.2 Example............................ 97
6.2.2 Intelligent Maneuvering . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2.3 Valency of every node . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.3 Satellite Formation - A Wireless Sensor Network of Space Telescopes . . . 100
6.3.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9
6.3.2 Definitions................................ 104
6.4 Multi-level Multi-metric Topology Construction . . . . . . . . . . . . . . . 105
6.5 Simulations ................................... 107
6.6 Conclusion.................................... 110
7 Conclusion 114
7.1 Summary of our contributions and future work . . . . . . . . . . . . . . . . 114
10
Chapter 1
Introduction
The explorations of man for the quest of “answers” have always resulted in more questions
than solutions he originally sought for. One of the most debated and arguable questions
of all time: “Are we alone in the universe ?” has still intrigued mankind to research more
into the outer space. This eternal question has not only been posed by the scientists and
the researchers but it also has played in the wild imaginations of the artists, philosophers
and great thinkers of all times. The discoveries of Galileo and Kepler of the 17th century
are just the basic building blocks for the modern space explorations. The plethora of
theories and discoveries about outer space was initiated by the first detection of a so-
called “hot Jupiter” [1] in 1995. Since then, more than 110 planets like in [2], have been
discovered as orbiting other starts like the sun. With many such exciting breakthroughs,
the missions involving finding extra-terrestrial planets and human like life started to receive
more attention and importance. Many space exploration satellites like Galileo, Figure 1.1,
launched by National Aeronautics and Space Administration (NASA) in 1989 which was
quite successful in studying the atmosphere of Jupiter atmosphere, moons, and surrounding
magnetosphere, were able to just able to explore and study the nearby planets and stars.
Using a single, approximately 2,000 kg orbiter spacecraft equipment, carrying 10 scientific
instruments tested to be not so effective for far long life outer space missions. Hence, the
research is focused on missions involving more than a single smaller satellite, distributing
and sharing the duties of a single large satellite, resulting in a concept called Formation
flying.
1.1 Formation of Vehicles: Micro-satellites
As “Nature is the best teacher”, the motivation to look beyond one vehicle is the formation
of migrating birds. The birds in their migratory route, travel in a formation which makes
them travel longer distance at a stretch and avoid obstacles together, efficiently. As shown
in the Figure 1.2, the birds form a perfect “V” formation as they fly. This requires a per-
fect communication strategy between the birds, a perfect collision avoidance mechanism
(Internal and external), a good pre-route planning and various other factors to maintain
12
Figure 1.1: Galileo satellite launched in 1989.
their formation and achieve their goal. In general, a formation of vehicles involves more
than a single vehicle collaborating and communicating amongst each other, to realize the
functions collectively. Specifically, the term vehicles, based on the applications, can refer
to AUV’s (Autonomous Underwater Vehicles), UAV’s (Unmanned Aerial Vehicles) Fig-
ure 1.3, micro-satellites, etc. The formation of vehicles is used for performing some specific
tasks more effectively and robustly than a single vehicle.
The formation of Autonomous Underwater Vehicles are popular for scientific research
activities in the remote ocean beds, defense applications and various other commercial
applications ([3] and [4]). The formation of AUV’s face various challenges from the unpre-
dictable ocean waves, the marine life and other dynamic obstacles.
The formation of Unmanned Aerial Vehicles is also a popular area of scientific research
due to its military and commercial applications. The development of remote test and con-
trol methods have advanced the applications of the formation of AUV’s. Many defense
applications through the formation of AUV’s are discussed in [5] and [6]. The complexity
of the formation of the UAV’s are reduced in the formation of the AUV’s due to the less
dynamic environment but the unpredictability of the climate, enemy arsenals, birds, etc,
make it challenging enough.
13
Figure 1.2: Formation of birds.
Another application of the concept of formation flying and the main focus of this the-
sis, is the formation of micro-satellites, as shown in the Figure 1.4. Instead of a traditional
heavy single satellite deployed for research and study in space, small identical satellites
called the micro-satellites perform the duties collectively of the single satellite. This clus-
ter of micro-satellites adapt the concepts of formation flying. Each of the micro-satellite
has some limited knowledge of the other micro-satellite. Many recent missions planned by
the various space agencies use the concept of formation of micro-satellites.
The scientists have just begun to understand the full potential of space vehicle forma-
tion flying. In the last few years, this technology has gone from a space oddity - and a
high risk one at that - to a concept fully embraced by earth and space scientists around
the world. Prior to the selection of the New Millennium Program Earth Orbiter-1 (EO-1)
mission in 1996 (the first autonomous formation flying earth science mission), NASA had
only one or two formation flying concepts under consideration. Now 35 mission sets fill
that list [7].
The main advantages of using formation of vehicles over just an individual vehicle, in
specific to the formation of micro-satellites, are:
Nulling Interferometry: This technique, which was outlined by Bracewell and McPhie
[8], and advantageous for observation and collection of data of far away planets around a
star, can be achieved through formation flying of micro-satellites. This concept involves
combining light collected by separated telescopes on each of the micro-satellites in forma-
14
Figure 1.3: Formation of UAV’s and AUV’s.
tion such that the resulting light intensity is zero for on-axis sources. Only the on-axis
sources are cancelled while the off-axis sources produce a signal intensity. This can be
thought of as a transmission grid on the sky (or focal plane) [9][18][19], with transparent
and opaque areas. The transmission grid of a nulling interferometer has an opaque area,
or null, in the center of the grid where the light interferes destructively. The star, beyond
which the planets are to be observed, is placed under this null so that light can be collected
from the planets around the star, without suffering from the brightness of the star. Nulling
interferometry can be achieved only through formation of micro-satellites and not with a
single satellite. Hence, for observation of outer space for extra-terrestrial life and planets,
the formation of micro-satellites is the hot topic of research.
Cost and fuel efficiency: With the cost playing an vital role in all the mission launches,
the micro-satellites are cost efficient in their production due to the identical nature and
their identical mountability on a single payload. On the contrary, a single large satellite is
function specific and is more costly to produce with a specific payload costing exuberantly.
The fuel required for a single satellite for a long mission is very high compared to the
minimal fuel consumption of the individual micro-satellites and hence, the entire formation
of the micro-satellite. Therefore, the economic fuel costs result in economic missions for
the formation of micro-satellites compared to a single satellite mission costs.
Functionality: Formation of micro-satellite increases the functionality. The expand func-
tionality, due to the ability to generalize the duties of the formation, is an advantage com-
pared to the single satellite which is function specific. For any change in functionality of
for any expansion, in a single satellite, the entire structure has to be changed which is very
costly.
15
Figure 1.4: Formation of micro-satellites in space.
Robustness and life expectancy: In a single satellite environment, as the entire function-
ality and the control activity is concentrated in just one node, the probability of failure of
the entire mission is very high. The robustness is extremely sensitive to the failure of the
single satellite. Hence, due to various dynamic factors and obstacles, the life expectancy
of the costly mission is quite less which is highly disadvantageous. In the use of a forma-
tion, the control and the functionality is distributed among all the micro-satellites. This
increases the robustness of the system. If one of the micro-satellite fails, the remaining
formation compensates for the loss and hence the mission is not abandoned. Hence, the
life expectancy is very high for a formation of micro-satellites compared to a single satellite
system.
With all the advantages, this concept also introduces several new challenges with respect to
the design of the missions. When the number of micro-satellites increase in the formation,
the system becomes more complex. There are several requirements for the success of the
formation in terms of its functionality. Energy-efficient trajectories have to be computed
and ensured for the micro-satellites such that the functionality is guaranteed. Another
important factor about the computation of energy-efficient trajectories is that it should
also maximize the life expectancy of the entire formation. The formation should be devoid
of permanent control and instructions from the earth control station. This has to be en-
sured by the information flow between the micro-satellites. The communication between
the micro-satellites play an important role. The communication should be ensured that it
is not global but distributed to make the formation more robust. The formation goals or
functionality can be changed after sometime. The provision for the reconfiguration of the
formation should be allowed for the formation to reorient and change its functionality. The
16
reconfiguration results in a new direction of the formation. Another important requirement
for the proper functioning of the formation, is the error management. The technical errors
or the errors resulting due to the external forces have to be analyzed and rectified in real
time. A proper collision avoidance has to be incorporated within the framework for a long
span and the reconfigurations.
Several currently planned missions include the concept of formation flying of micro-satellites.
The EO-1 and Landsat-7 satellites are currently formation flying in Low Earth Orbit
(LEO) to provide high resolution images of the Earth’s environment. The United States
Air Force (USAF) mission TechSat-21, European Space Agency (ESA) missions DARWIN
and SMART-2, and National Aeronautics and Space Administration (NASA) missions
ST3:Starlight, ST5: Nanosat Trailblazer and Terrestrial Planet Finder (TPF) are few of
the popular planned formation flying missions.
The TechSat-21 mission [20] consists of formation of micro-satellites along a lattice of
points for imaging of high resolution quality. The mission is still an investigatory process
for the efficiency of the formation ability to perform the high-resolution imaging.
The TPF mission consists of four micro-satellites each supporting 3.5-m telescope, and a
separate micro-satellite for the combiner as shown in the Figure 1.5. The mission would in-
vestigate and search for extra-terrestrial planets around sun like stars. The micro-satellites
are positioned along a line oriented normal to the direction of observation and collector
telescopes relay the data to the combiner so as to maintain the optical paths through the
system equal to few cms ([21], [22],[23], [24]). The TPF mission has a proposed launching
period of the year 2015.
The DARWIN mission is to find more Earth like planets with signs of life. The DAR-
WIN mission [25] uses the technique of infrared nulling interferometry through six free
flying 1.5m telescopes mounted on micro-satellites, which transmit their input beams to a
combiner micro-satellite (Figure 1.5). A transmission map can be produced, allowing the
search for a planet in a specific zone (e.g. where water is in the liquid phase) around a
star. At present TPF/DARWIN missions are in the technology readiness and architectural
planning phase. DARWIN is planned to enter into the launch phase by the year 2014.
The results presented in this thesis can be related to the architectures of TPF and DAR-
WIN.
1.2 Outline of the Thesis
Formation flying concepts, while increasing the functionality, can introduce several new
challenges with respect to the design of the mission. This thesis focuses on the multi-faced
technological challenges that face an efficient deployment of a formation of micro-satellites.
There are two facets discussed in this thesis: Establishing coordinated control of formation
17
Figure 1.5: An artist’s conception of TPF (left) and DARWIN (right)
of satellites deployed in a halo orbit in the Sun-Earth system and the discusion on the
software implementation of the control with the depiction of the formation as a distributed
sensor network. In the first aspect, we apply concepts from graph theory, control theory
and some applied concepts from astro-physics. In the implementation of the algorithms, we
use the concepts of distributed computing, parallel systems and a sensor network modeler
OPNET.
In the remaining sections, we introduce each of the facets of this thesis in detail and
further discuss the content overview for each of the following chapters.
1.2.1 Formation of Micro-satellites in the Halo Orbit Proximity
The main aim of the formation of vehicles is the successful deployment in the appropriate
application environment with the maximum life expectancy. There have been eminent
contributions in some application fields of formation of vehicles. For e.g., in the field of the
formation of robots, there have been inspiring results and achievements [26]. The specific
application for the formation of micro-satellites has several approaches for the determi-
nation and application of the formation control. A leader follower control strategy has
been implemented again in robots in [27]. Here, a designated robot behaves as a leader
and transmits control signals to the other robots to achieve a formation collectively based
on the leader. This control strategy relies heavily on the leader for all the computations.
This heavy reliance is a major drawback in terms of robustness cite. If the leader fails,
then all the vehicles are unable to compute their trajectories as it is the leader that defines
the reference trajectories for each of the follower. Hence, the leader follower approach is
definitely not suitable as the control strategy for the formation of micro-satellites, due to
the demand for longer life expectancy proportionate to the cost of the mission.
18
Extending the leader follower approach, is the “virtual leader” control strategy. This
control strategy has been discussed in detail in [32] and [33]. In this strategy, instead of
assigning a vehicle as a leader, the vehicles collectively decide and assign a virtual leader
and its trajectory. This virtual leader then decides the relative trajectory of the entire
formation of followers. This technique is far better than the leader follower approach be-
cause there is no designated vehicle and so the system is less prone to failures related
to the leader vehicle failure. However, this technique induces a large communication and
instruction overload on each of the vehicles due to the complexity involved in collectively
synthesizing to the virtual leader.
Another control strategy is the more robust distributive control strategy adopted in [49]
and [68]. This strategy has been implemented on simple linear models. Here, the decen-
tralized control ensures that the vehicles, with their identical local feedback, achieve the
formation goal collectively while always ensuring the formation constantly kept around a
formation center. This formation keeping control ensures that the vehicles always are com-
puting individually their trajectories relative to the other vehicles that it is communicating
with. This strategy shows that the formation stabilizing control laws can be derived for
the individual satellite that rely only on the local information. This strategy is useful for
formation keeping.
The main aim of this thesis is to determine a control strategy for the formation of micro-
satellites in space for certain observation and data collection duties. An obvious question,
is the possible and efficient place for deployment for longer and stable mission life. It is
efficient for the formation to operate at some orbit around the L2Lagrange point in the
Sun-Earth system ([66]). This deployment position can be justified because, at the L2
point, the gravitational forces balance, leaving the formation almost completely still in the
Sun-Earth space. In addition to this, the proximity to the L2position makes it possible
to apply passive radiative pre-cooling for temperatures larger than ≈30K, a temperature
impossible to reach for low Earth orbits or geo-stationary orbits [34].
For the determination of the control strategy for such a deployment, we use a distributed
control customized for the specific halo orbit around L2deployment. We combine this
strategy with a virtual leader strategy. We determine the distributed feedback control law
that achieves formation as a formation keeping control. Then, we compute the center of
mass of the formation. This center of mass is placed on a selected halo orbit. Along with
the formation keeping control, a virtual leader control strategy is now applied on the center
of mass. To be precise, the center of mass of the formation is made the virtual leader of
the formation and is placed on the halo orbit of consideration. The remaining follower
micro-satellites compute their relative trajectories based on the center of mass trajectory.
The formation control strategy ensures that, at every time, the follower micro-satellites are
concentrated and are in formation around the center of mass. The virtual leader control
ensures that the center of mass virtually determines and hence, allows the formation of
19
micro-satellite followers to follow the center of mass. This collective strategy ensures an
efficient deployment of the entire formation of micro-satellites in the proximity of a halo
orbit with its center on the orbit.
In the Chapter 2, we develop a simple linear model from [50] along with the decentral-
ized feedback control law which acts on the similar individual local control to stabilize
the entire formation of micro-satellites. Here, we explain the importance of the Laplacian
and we elaborate on the discussion in which the Laplacian is included in the equations of
dynamics of the formation. This stabilizing control strategy is a formation keeping control
strategy. We revise the control strategy proposed in the above model and then discuss
the model proposed in [69]. We then perform the stability analysis which is, analyzing
the placement of eigenvalues of the dynamics equation of the formation of micro-satellites.
The decentralized formation keeping control stabilizes the entire formation towards the
formation center. A reference vector is then defined which proposes the wanted distance
between the micro-satellites and the formation center. It also acts as an internal collision
avoidance mechanism.
The communication between the micro-satellites is represented by the Laplacian and is
incorporated into the dynamics of the formation for the determination of the control strate-
gies. The role of the communication topologies is variant and is dependent on the model
of description. We are considering the mission design with the objective of injecting the
micro-satellites into the Libration orbit around the Lagrange point L2. Close to this orbit,
a time-dependent linear model can be used to describe the motion of the micro-satellites.
Firstly, we restrict ourselves to a time-independent model in the Chapter 3. Here, we can
prove here that the communication topologies are not so relevant i.e., we can definitely find
a stabilizing decentralized feedback control law for a time-independent model as long as the
communication topology is connected. In the more realistic case of the non-autonomous
modeling, we show the dependence of the stability of the formation of the micro-satellites
on the communication topologies. In this chapter, we analyze the robustness of certain
communication topologies with respect to the removal of edges (i.e., the failure of the com-
munication links due to some unavoidable reasons). The role of Laplacian eigenvalues were
first identified as very important in synchronization [35]. Here, we also study the role of
minimum eigenvalues of the Laplacian of the communication topologies in the stability of
the formation of the micro-satellites.
In Chapter 4, we study the more appropriate method of stability analysis for more com-
plicated situations. We propose an adapted version of the concept of stability radius of a
linear system in order to measure the robustness. The stability radius concepts are more
reliable and justified for the analysis of stability rather than the placement of eigenval-
ues. The defined stability radius is computed for some communication topology failures
(removal of edges). The stability radius results is used to determine the robustness and
is used to design the formation communication topology based on the required application.
20
In the main Chapter 5, the control strategy is developed for the efficient and stable de-
ployment of the formation of micro-satellites in the proximity of a halo orbit around the
Lagrange point L2. For this control determination, we follow three steps as described
below:
A leader follower control strategy is developed for a single micro-satellite and tested for
the formation stability in the proximity of the halo orbit [36]. A virtual leader is placed
on the halo orbit and a follower micro-satellite is controlled relative to the leader. A
preliminary test is performed for more than one follower micro-satellite and we show that
a coupling is required between the micro-satellites to maintain the formation. Without
the coupling, the individual micro-satellites follow the imaginary leader on the halo orbit
independent of the time and state of the other micro-satellites.
From a leader follower strategy, we move on to a formation keeping control. This for-
mation keeping control already introduced in Chapter 2, is modified and adapted to the
case for which the formation is in the halo orbit proximity. The formation keeping control
ensures that the micro-satellites are bound to their center. The distance from the center,
at each point of time, is fixed as the reference vector. This coupling between the micro-
satellites basically ensures that there is a formation existing and the goal of the mission is
achieved collectively through the formation collaboration.
The most challenging part is the merger of the different control strategies. Firstly, the
center of mass of the formation is computed. Then, the dynamics of the center of mass is
formulated such that it is placed on the halo orbit. Further, the formation keeping control
strategy is applied for all the follower micro-satelites. The reference vector is specified in
such a way that, the micro-satellites are positioned, initially in a regular hexagon (micro-
satellites in the corners of the hexagon) with the center of formation i.e., the center of
mass on the halo orbit. At each point of time, the formation keeping control keeps the
micro-satellites around the center of mass. Now, the leader follower strategy is applied
such that the center of mass becomes a follower of a virtual leader on the halo orbit.
The stability analysis is performed and in order to determine the efficiency of this control
strategy, we perform some error analysis. We measure the deviation of the formation from
it trajectory on application of both the control strategies. We find that the deviation is
not more than an acceptable amount which might have been a result of the linearization
errors. Hence, this control strategy is proven to be an efficient control strategy for the
formation of micro-satellites in the proximity of a halo orbit of the Sun-Earth system.
1.2.2 Implementation
We turn our attention from the mathematical and control theoretic aspects in the design
of a stabilizing formation control to the realization of the formation of micro-satellites with
21
the computer scientific point of view. In Chapter 6, we apply the concepts of real-time, dis-
tributed systems to achieve some results on the behaviour of a formation of micro-satellites
in space.
We design the formation of micro-satellites as a Distributed Spacecraft System (Dis-
tributed (micro) Satellite System) or DSS [76]. Each of the micro-satellite is identical
and is equipped with sensors for various functionalities. The Autonomous Formation Flyer
(AFF) sensor, incorporated in the Deep Space 3 (DS3) mission for optical space interferom-
etry and formation flying, and DarWin AstRonFringe Sensor (DWARF) to be incorporated
in the DARWIN mission ([37], [38], [39]), are a few examples of sensors incorporated in
the micro-satellite distributed system. The GPS sensing technologies can also be tested
for formation flying as in [47].
The micro-satellites deployed in space are mounted with AFF sensor for inter-micro-
satellite sensing and also each of the micro-satellite is mounted with a space telescope
for gathering or sensing the outer space data and the sharing and communicating between
each other. Hence, this forms a wireless sensor network in space. In a general sense, we
study the formation of micro-satellites in space as a distributed network of sensors. We
discuss the various attributes of a distributed sensor network and its behaviour with the
specific application of the formation of micro-satellites in mind.
For the effective coordination of the distributed sensor network, the communication be-
tween the micro-satelites are very important. The sensing between the micro-satellites
can be portrayed using a sensing graph. The sensors favour bi-way communication and
sensing and hence we restrict ourselves to the sensing graphs of the regular degree having
undirected edges. The question arises about the ideal structure to be used for the sensing
graph. We define some factors required for determining the ideal sensing structure for the
effective distributed sensor network. The main factors are Robustness, Intelligent Maneu-
vering and Regularity of the sensing graph.
The robustness of this distributed sensor network is the ability of the formation to re-
gain the stability when a node failure occurs and distorts the formation. The node failure
is assumed to be temporary and its services can be restored after a while. We define a
measure called Node recovery penalty which basically measures the penalty the formation
has to pay to gain back to the original structure after a node failure occurs. Based on
this measure of the node recovery penalty, we define an universal measure for each sensing
structure called the Robustness factor. The sensing structure having the least robustness
factor is the most robust structure as the cost and the penalty paid for the formation in
losing the functionality of a node individually and overall all the nodes and gaining all of
them back, is the least.
Another important factor for the determination of an ideal sensing structure is the concept
of Intelligent maneuvering. This concept actually involves the collision avoidance methods
22
where the formation of micro-satellites, the distributed system, has to avoid the obstacles
either in coming or just while maneuvering. This involves a lot of distributed comput-
ing and sharing of a lot of information between the micro-satellite nodes. The formation
should disperse avoiding the obstacle and then reconfigure itself back to the original phys-
ical structure with the previous existing sensing structure. The collision detector sensors
play a crucial role in this functionality. The information and the communication has to be
passed throughall the nodes in real time to take an immediate disperse action. For this,
we need more communication possibilities between the micro-satellites.
Regularity of the sensing graph (Valency of every node) is an important factor in achiev-
ing long term efficient results of the formation of the micro-satellites. If the regularity is
more, it means that the communication between the micro-satellites has to be through
switching of the communication channels. More the regularity, more is the load on each
micro-satellite in terms of the hardware required. There is more load on the processor
and there is a lot of load on each micro-satellite which is already constrained by size to
switch more between the communication channels. This decreases the efficiency in the
performance of the network.
Based on these factors, the possibility of selecting an ideal structure is based on the ap-
plication requirements. It is a multi-objective optimization problem. The weight on each
of the factors is varied for various mission requirements. We demonstrate and explain
each of the factors with an example of six micro-satellite network. This sensor network of
six-micro-satellite has five sensing graphs of regular degree and of undirected nature.
Further, inorder to introduce scalability, we use the concept of Hierarchical clustering
for the modeling of micro-satellites which are high in number. We develop a distributed
multi-level multi-metric algorithm for some varying metrics. The results of the modeling
and clustering are compared with a traditional greedy algorithm and shown to be more
efficient. The experiments are performed in an event based network modeler named ShoX.
We also extend the existing control laws to show the final clustered formation of micro-
satellites.
1.3 Chapter Contributions
In this section, we give an outline of the contents and contributions in each of the chapters
to follow.
In Chapter 2, we discuss a standard approach linear model for a formation of micro-
satellites. We also define the communication between the micro-satellites in terms of a
Laplacian matrix. We incorporate this Laplacian matrix with the communication informa-
tion into the dynamics of the formation of micro-satellites. We define the offset vector in
this model to include a linear internal collision avoidance. We discuss further, by focussing
23
on the extension of this model, which defines a reference vector for the formation to be
centered around the formation center. We display the results of a few simulations based
on an example. Later, we also discuss the stability analysis for an efficient stable linear
decentralized feedback control strategy.
In Chapter 3, we discuss the role of communication topologies in the stability of the for-
mation of micro-satellites. We first focus on the autonomous model. Then, we consider a
non-autonomous system, and consider the dependence of the stability of the model on the
minimal eigenvalues of the Laplacian matrix of the communication topology. We discuss
the robustness derived from the inferences of the minimal eigenvalues. The robustness of
the formation of micro-satellites is discussed with respect to the minimal eigenvalues. The
discussion is again illustrated with an example.
In Chapter 4, we discuss a more general setting to analyze the robustness of the com-
munication topologies. Here, a more systematic approach using control theoretic concepts
are given and also introduce the concept of stability radius. We modify the stability radius
and define a new variant of stability radius for the formation of micro-satellites. Analyzing
this stability radius for various communication failures, we determine the robustness of
the communication structures. We also use an example to illustrate the communication
robustness and its determination using the stability radius.
In Chapter 5, we determine the formation keeping strategy for a formation of satellites.
The micro-satellites are centered around the formation center by this formation keepping
control. Further, we discuss the non-autonomous modeling of the dynamics of the for-
mation of micro-satellites. This is to implement the formation of micro-satellites in the
proximity of a halo orbit in space in the Sun-Earth system around the Lagrange point
L2. The formation control is varied and extended for the application in the proximity of
the halo orbit. A leader follower strategy is explained for a single micro-satellite following
a virtual leader on the halo orbit. This leader follower control strategy is extended to
more than one follower micro-satellite and the need for a coupling is demonstrated. A new
control strategy including the formation keeping control strategy and the leader follower
strategy is determined. Here, the formation center of mass acts as a follower of a virtual
leader which is on a halo orbit. Then the formation keeping control is simultaneously
applied at each time, so that the formation stays around the formation center of mass. the
stability analysis shows that the new control strategy is efficient in stabilizing a formation
of micro-satellites in the halo orbit proximity. The deviation of the formation after the
application of the control strategy is measured, to demonstrate the efficiency of the strategy.
In Chapter 6, we discuss the formation of micro-satellites as a distributed sensor net-
work in space. The factors for determination of an ideal sensing structure are determined
and the results are shown with an example. A novel distributed multi-level varying multi-
metric algorithm is developed and tested for clustering the micro-satellites. The results
are shown using a network modeler ShoX.
24
In the final Chapter 7, we summarize the results presented in the thesis and also introduce
the prospects of extending this research in the future.
25
Chapter 2
A Standard Approach: Linear
Modeling of the Formation
2.1 Introduction
In this chapter, we present a control strategy through the discussion of a standard linear
model approach, introduced in [50]. The development of this control strategy involves
the application of concepts from graph theory and control theory. An efficient control
strategy for the formation of micro-satellites depends on the communication between the
micro-satellites. This control strategy is a decentralized feedback control which acts on
the individual micro-satellites which have an identical local control. This decentralized
feedback control drives the entire formation of micro-satellites to their intended relative
positions. We emphasize the importance of the inclusion of the communication informa-
tion into the dynamics of the formation. We represent the communication information
using a communication graph and translate this communication information into a matrix
format called as a Laplacian matrix. The role of this matrix and its importance in the
maintenance of the formation of the micro-satellites would be discussed in the future chap-
ters. Based on this model, we present the stabilization issues and the stability criterion for
the formation of micro-satellites, to have a wider functionality and longer life expectancy.
With an example of six micro-satellites, we demonstrate this decentralized control and
the stabilization for two and three dimensional models using the mathematical modeling
software: MATLAB (7.0).
Extending this model further, we discuss some results from [69]. We define a reference
vector, such that, the entire formation is centered around the formation center depending
on the size of the reference vector. The stability analysis is discussed for the formation of
micro-satellites.
The structure of this chapter is given as follows. In the first section, Section 2.2, we
introduce the model. Further, we discuss the communication graph and establish the
26
Laplacian of the communication graph. We derive the dynamics of a single micro-satellite.
We then discuss the dynamics of the formation of micro-satellites with the inclusion of the
Laplacian matrix. In the following section, we perform the stability analysis for the model.
We then observe the results and the decentralized control behaviour with an example. In
the Section 2.5, we observe the extension of the results from the above model, which this
thesis uses throughout as a standard approach.
2.2 The Model
In this section, we present an standard linear approach for the determination of a decen-
tralized stabilizing control for a formation of micro-satellites. The main aim of most of
the important missions, like the TPF and DARWIN, is the proposal to inject the forma-
tion of the micro-satellites in the Libration orbit around the Lagrange point L2. Close to
this orbit, a time-dependent linear model may be used to describe the dynamics of the
micro-satellites. For the purpose of just introducing this decentralized control, we restrict
ourselves to a time-independent autonomous model.
The communication between the micro-satellites play a crucial role in the formation achieve-
ment. For this purpose, we have to discuss the modeling of the communication between the
micro-satellites. We use the graph theoretic concepts to represent the communication infor-
mation. We represent the communication, which means some sensing and communicating
information between the satellites, in the form of a graph called the communication graph.
This communication graph comprises of nodes represented by the micro-satellites. The
edges represent the communication between the micro-satellites. The communication graph
is just an indicative of the communication between the communicating micro-satellites and
do not, in any way, represent the actual physical alignment of the micro-satellites in space
after deployment. In the following parts of the section, we derive the Laplacian matrix of
the communication graph.
2.2.1 Graph Laplacian
We consider some characteristic requirements of the communication graph for the formation
of micro-satellites. They are elaborated in the following paragraphs.
Due to the deployment of many sensors, like the Autonomous Formation Flyer (AFF)
sensor on each of the micro-satellite, a bi-way communication or sensing is established
between the communicating micro-satellites. This facilitates for the edges to be bi-way
communicating or to be undirected edges. In the realization of communication, the micro-
satellites establish multiplexing of the communication channels and the communication is
through channel switching.
27
Each of the micro-satellites is structurally and functionally identical. This identical
functionality and the bi-way communication between the micro-satellites, encourage us
to employ a kind of symmetric nature in the graph. It is for the sake of simplicity of
modeling and the functionality that we require the communication graph to have every
micro-satellite of a regular degree. That is, each micro-satellite communicates with exactly
the same number of micro-satellites. Hence, we have a graph of regular nature.
Another important but basic requirement for the communication graph is, that it should
always be connected. No node or the micro-satellite should be isolated at anytime without
being able to receive any communication or instruction from the other micro-satellites.
A communication graph Gconsists of finite set Vof nodes (micro-satellites) and a fi-
nite set Eof edges. As we have explained earlier, consider that the communication graph
has undirected edges, i.e., (a, b)∈E=⇒(b, a)∈E. We now explain the construction
of the Laplacian matrix of the communication graph G.
The Laplacian matrix has always aroused interest amongst the mathematicians and has
been studied extensively, for example, in [40], [41] and [42]. The role of the Laplacian
matrix is to embed the communication information in to the dynamics of the formation,
which would be dealt with in the future. So, it makes sense to define the Laplacian in
terms of the adjacency matrix.
Let Sbe the set of all the pairs of nodes (micro-satellites) which are communicating
amongst each other. The adjacency matrix of the Laplacian matrix L(or in general any
matrix), depicted by Aj, can be defined as Aj
ij = 1 when (ai,aj)∈Sand Aj
ij = 0, when
(ai,aj)/∈S. There can be many adjacency matrices for a matrix but all are similar
to each other with the definition of a permutation matrix. Apart from this adjacency
matrix, we need another matrix to specify the degree of every node (micro-satellite), i.e.,
the number of other micro-satellites that each micro-satellite communicates with. Let Ao
represent the matrix for each micro-satellite degree along the diagonal. There are various
variations for the definition of the Laplacian of a matrix. Some specific applications require
the definition of the Laplacian as L=Ao−Aj. In a case where the Laplacian has to be
defined for a directed graph, we use the transpose of the adjacency matrix.
Here, we define the Laplacian Lof the communication graph Gas the normalized form of
the adjacency matrix as
L=Ao−1(Ao−Aj).(2.1)
The formulation of the Laplacian matrix for a formation of Nmicro-satellites is given in
the following discussion.
Let Si⊂ {1, . . . , N}\i, for the index i∈[1, ..., N], represent the set of micro-satellites that
the micro-satellite ican communicate with. As discussed previously, the Laplacian of the
communication graph of the formation of micro-satellites should incorporate the commu-
28
nication information into the matrix.
The Laplacian matrix of the communication graph for a formation of Nmicro-satellites
can be given as
Lij =
1 : i=j
−1
|Si|:j∈Si
0 : j /∈Si
.(2.2)
From the above definition of the Laplacian of the communication graph by (2.2), we get
the information about the communicating neighbours of each of the micro-satellites. The
communication neighbours are just the neighbours in terms of communication and are not
physical state neighbours or position neighbours in space.
2.2.2 The Dynamics of the Formation
For the formulation of the dynamics of the formation of micro-satellites, we introduce some
terms.
Let xi∈R2pbe the state of each micro-satellite ifor the dimension p(2 or 3). Let ui∈Rp
for the dimension p, be the control of each micro-satellite i. Let Aand B, be real matrices
of appropriate sizes. Using these above defined terms, we formulate the dynamics of a
single micro-satellite, which is identical to all the others, as
˙xi=Axi+Bui, i = 1, . . . , N. (2.3)
We have that the Laplacian matrix of the communication graph embodies the communica-
tion information. We need to incorporate the Laplacian matrix into these set of equations
for the formation of micro-satellites. We represent the communication information for each
micro-satellite, with the set Si⊂ {1, . . . , N}\i, representing the set of micro-satellites that
the micro-satellite ican communicate with, as
zij =C(xi−xj), j ∈Si.(2.4)
In (2.4), the value zij represents the relative measurements of each micro-satellite to the
other micro-satellites that it is communicating with. To obtain the relative information
means that, each of the micro-satellite must have some information regarding the states of
the other micro-satellites, at each point of time.
The relative error measurements are integrated into a single error measurement
zi=1
|Si|X
j∈Si
zij .(2.5)
A decentralized control law Kis developed, which acts on the identical local control law,
(ui), in each of the micro-satellites [50]. The identical dynamics, with the incorporation of
the decentralized control using (2.3) and (2.4), for each of the micro-satellites, is given as
˙xi=Axi+BKzi.(2.6)
29
2.2.2.1 Inter-microsatellite Spacing
As relative positioning of the micro-satellites is important, it is required to introduce an
offset vector to maintain a specified inter-microsatellite distance. We define hi, with the
same dimensions of zi, to be the offset vector measurement of each micro-satellite. Such
vectors, similar to the offset vector, have been defined in different forms. This offset vector
defines the relative position of each micro-satellite to an arbitrary reference. This individual
offsect vector for each micro-satellite can be collectively represented as hsuch that
h=
h1
.
.
.
hN
.
In (2.6), we substitute zifrom the definition of the Laplacian in (2.2). Hence, we get the
dynamics of each micro-satellite with the inclusion of the communication information as
˙xi=Axi+BKLC(xi).(2.7)
The dynamics from (2.7) is now included with the desired positions, i.e., the offset vectors.
Now, the modified dynamics for each of the micro-satellites is given as
˙xi=Axi+BKLC(xi−hi).(2.8)
2.2.2.2 Entire Formation Dynamics
We have the identical linear dynamics for each of the micro-satellites, given by (2.8). From
the definition of a formation, we have that all the micro-satellite collectively achieve their
functionality. For this, we need to extend a single micro-satellite dynamics to the entire
system dynamics, involving all the micro-satellites.
For the entire formation system of Nmicro-satellites, we define the Kronecker products
for the matrices in (2.8). The Kronecker products are given as the “hatted” notation by
repeating the matrices Ntimes along the diagonal: ˆ
A=IN⊗A,ˆ
B=IN⊗B,ˆ
C=IN⊗C
and ˆ
K=IN⊗K. Given nas the dimension of xi, for the Laplacian matrix L, the Kro-
necker product is given as ˆ
L=L⊗In. Let xrepresent the states of all the micro-satellites,
given as
x=
x1
.
.
.
xN
.
Considering the system of Nmicro-satellites, using the Kronecker products, we define the
dynamics of the entire formation as
˙x=ˆ
Ax +ˆ
Bˆ
Kˆ
Lˆ
C(x−h).(2.9)
30
The Equation (2.9), represents the entire formation of Nmicro-satellites, which is driven
to their desired relative positions, at each point of time, by the decentralized control law
K. The communication information between the micro-satellites is also embedded in the
form of the Laplacian matrix. It is now required to see whether the decentralized control
law drives the entire system to stability.
2.3 Stability Analysis
In [49], the results depicts the role of the Laplacian and its eigenvalues in the formation
stability. It is required to show in (2.9), that the decentralized control establishes the
desired relative positioning of all the micro-satellites, while stabilizing the formation in the
sense of Lyaponov stability.
The Equation (2.9) is a first order ordinary differential equation. It is clear that for the
stability analysis of the entire formation it is required to analyze the matrix
ˆ
A+ˆ
Bˆ
Kˆ
Lˆ
C. (2.10)
The eigenvalue placement of the matrix 2.10 determines whether the decentralized control
law drives all the micro-satellites to stability. If the eigenvalues of the above matrix lie on
the left-hand side of the complex plane, then the system is stable.
We have determined the stability criterion for (2.9) through the analysis of the matrix 2.10.
We now illustrate the discussed concepts of the considered model through an example in
the following sections.
2.4 Examples
The simulations are presented based on the application of TPF, DARWIN and other
planned missions, involving only a fewer number of vehicles. In our examples, we consider
two formations individually, one with three and another with six micro-satellites, to be de-
ployed by a payload and their acquisition of the desired formation, using the decentralized
control law, as discussed in the previous section. We also perform the stability analysis to
verify the efficiency of the decentralized control law. The simulations are performed using
the MATLAB software.
2.4.1 Formation of Three Micro-satellites
We simulate the decentralized control on the formation consisting of three micro-satellites,
with identical dynamics and functionalities. The individual identical dynamics for each
micro-satellite is given through the (2.8). The decentralized control law Kis introduced
to act on the individual control law uiof each micro-satellite. We simulate the position
31
Figure 2.1: Formation Acquisition of Three Micro-satellites.
trajectories of each of the satellite as they come into the formation.
The Figure 2.1, shows the three different position trajectories, starting at three differ-
ent points marked as ’x’ and converging as a formation of a triangle with the end points
on the corners. The communication graphs which are possible, are just two distinct graphs
because of their properties of being regular graphs and having undirected edges.
2.4.2 Formation of Four and Five Micro-satellites
Another similar example is the simulation of the trajectories of four and five micro-
satellites. It is shown in the Figure 2.2 and Figure 2.3, that the decentralized control
law drives the formation into the desired position.
2.4.3 Formation of Six Micro-satellites
The six micro-satellites have identical sizes and identical functionalities. The communica-
tion protocol is basically decided following the explanation given in the Section 2.2.1. The
communication between the micro-satellites is depicted by a communication graph. The
communication graph has undirected edges and is of regular nature.
32
Figure 2.2: Formation Acquisition for Four Micro-satellites.
For the formation of six micro-satellites, the possible communication graphs which are
undirected and of regular nature are illustrated in the Figure 2.4, [72]. These five figures
are the possible communication graphs used for this model. The choice of one single com-
munication graph from the five graphs, depends on various factors and applications and are
discussed in the future chapters. The individual identical dynamics for each micro-satellite
is given through (2.8).
The decentralized control law, K, is introduced to act on the individual control law, ui, of
each micro-satellite. We now integrate the single system dynamics into the entire system
dynamics, consisting of Nmicro-satellites, by taking the Kronecker products of the ap-
propriate matrices, as shown in the Section 2.2.2.2. In the Figure 2.5, the dencentralized
control law establishes the formation in the form of a hexagon. The communication graph
used in the simulation is that of a complete graph. In order to analyse the stability of
the system, we plot the spectrum of the matrix 2.10. We see in the Figure 2.6, that all
the eigenvalues are placed on the left-hand side of the complex plane indicating that the
decentralized control law stabilizes the formation of six micro-satellites. The formation
of micro-satellites start with different initial velocities when the decentralized control law
stabilizes their position trajectories. In their relative final position, as the micro-satellites
attain relative stability as a formation, their relative velocities become zero as illustrated
in the Figure 2.7.
33
Figure 2.3: Formation Acquisition for Five Micro-satellites.
2.5 Extension of the model
We now present the form of the model, which is an extension of the model presented
previously, as shown in [68]. We use this model in this thesis to develop new results in
the coming chapters. In this model, the dynamics of each of the micro-satellites, similar
to (2.3), is given by
˙xi=Avehxi+Bvehui, i = 1, . . . , N, (2.11)
where xi∈R6is the state and ui∈R3is the control input. Denoted by
h=
h1
.
.
.
hn
is the reference state vector, with hi∈R6, and Sistands for the set of micro-satellites that
ican communicate with.
There are error output functions ziused to express the relative displacement of the neigh-
34
Figure 2.4: All non-isomorphic connected regular undirected graphs with six nodes.
bouring vehicles. Each vehicle computes the error output function
zi= (xi−hi)−1
|Si|X
j∈Si
(xj−hj) (2.12)
and sets ui=Fvehzifor some feedback matrix Fveh. As a result, the output vector zcan
be written as z=L(x−h) where Lis the Laplacian of the communication graph shown
in the Equation 2.2. Now, for the entire system dynamics, taking the Kronecker products
over the Nvehicles, we get
˙x=ˆ
Ax +ˆ
Bˆ
Fˆ
L(x−h).(2.13)
where ˆ
A=IN⊗Aveh,ˆ
B=IN⊗Bveh and ˆ
F=IN⊗Fveh. The feedback matrix Fcan be
found such that the entire system is driven to stability, z→0. In physical terms it means
that, all the micro-satellites are relatively positioned in their desired positions and their
displacement from the intended positions is zero.
This form of decentralized feedback control law is chosen through out the thesis, with
this model for keeping the formation of micro-satellites around their formation center.
This is illustrated further in the Chapter 4.
2.6 Conclusion
In this chapter, we introduced the standard approach through the description of a linear
model. We defined the Laplacian matrix as the embedded form of communication infor-
mation. We also have defined the decentralized control law which acts on each of the
individual control law in each micro-satellite. The individual dynamics are then extended
to the entire system dynamics by using the Kronecker products. The decentralized control
is shown to stabilize the formation as their position trajectories are traced. An offset vec-
tor is defined to specify the distance between the micro-satellites. The stability analysis is
discussed.
The concepts of the model are then shown with examples of three, four, five and six
35
Figure 2.5: Formation Acquisition of Six Micro-satellites.
micro-satellites. The simulations of the position trajectories for all the example formations
demonstrate that the decentralized control law drives the trajectories of the micro-satellites
to their desired positions and stabilizes them. The simulation of the spectrum, for the anal-
ysis of the stability of the formation, is also shown.
Further, we extend the model to define the model we use in the rest of thesis. The reference
vector is defined so that the formation is stabilized around the center of the formation, at
every point of time.
36
Figure 2.6: Eigenvalue Placement for the Matrix Representing the Formation of Six Micro-
satellites.
37
Figure 2.7: Relative Velocities of the Six Micro-satellites.
Figure 2.8: Reference Vector with respect to the Formation Center.
38
Chapter 3
Analysis of the Role of
Communication Topologies in the
Stability of a Formation
3.1 Introduction
In this chapter, we discuss the role played by the communication topologies in the sta-
bility of the formation, and also establishing longer life expectancy of the formation of
micro-satellites. The concept of formation flying of micro-satellites has two key charac-
teristics, namely, increased functionality and robustness of the mission. The topology of
the communication network of the micro-satellites or the communication topology, can be
a bottleneck in the operation of the formation because, the transmission of information
and the coordination of the formation relies on it. We consider the basic setting, that
the communication topology is always connected, i.e., the communication graph is always
connected. In the previous Chapter 2, it has been shown that formation-stabilizing control
laws can be derived for the individual micro-satellite that rely on local information only.
The key idea is that, together with the stability properties of the dynamics of the individ-
ual micro-satellite, the spectrum of the Laplacian associated to the graph, that describes
which micro-satellites communicate with which other micro-satellite, plays a crucial role
in the design of this control law.
Further, we define the property of robustness of the communication topologies, specific
to this setting. We consider the possibilities of micro-satellite failures and the commu-
nication link failures which are the results of some realistic circumstances. Under these
failures, we try to find the best communication topologies which sustain such failures and
prevent the loss of the functionalities. We study the robustness of certain communication
graphs with respect to the removal of edges (i.e., the failure of some communication links).
For this, we establish the link between the minimal eigenvalues of the Laplacian matrix of
the communication graph and the stability analysis for various number of communication
39
failures. We illustrate the role of the minimal eigenvalues of the Laplacian matrix using an
example of six micro-satellites. The results presented in this chapter are an elaboration of
the results of the paper [11], for which the author has contributed substantially.
The contents of this chapter are organized as follows. We start in the Section 3.2 with a
basic discussion on the properties of the communication graph with respect to the Lapla-
cian matrix.
In the Section 3.3, we discuss the inconsequential role of the communication topologies
in determining the stability of the formation of micro-satellites. We develop the results
based on [68] that, as long as the communication graph is connected, in an autonomous
setting of a formation of micro-satellites, we can definitely find a decentralized feedback
control law which can drive the formation to stability. In the Section 3.4, we extend the
results of the communication topologies in a non-autonomous modeling of the formation.
We discuss the role played by the communication topologies in determining the stability.
Further in this section, we discuss some general properties of the Laplacian matrix. The
reasons and the importance of considering the minimal Laplacian eigenvalues are elabo-
rated. We present the role of the minimal eigenvalues in determining the stability of the
formation in case of the communication link failures. Then, we illustrate the results with
the example of the communication topologies of six micro-satellites in formation. Finally,
we present the summary of the chapter in the conclusion Section 3.6.
3.2 Basic Results on the Laplacian Matrix
In this section, we discuss some elementary results from graph theory applied on the
Laplacian matrix discussed in [40]. We defined the communication graph and the Laplacian
matrix of this communication graph in the previous chapter. The results on the spectral
properties of the Laplacian matrix can be found in [43] and [42]. We present below some
basic spectral properties of the Laplacian matrix.
If the communication graph is undirected (esp. in our model), the eigenvalues of the
Laplacian matrix are all real.
Zero is one of the eigenvalues of the Laplacian matrix. This can be inferred from the
fact that the rows of the Laplacian matrix always sum to zero (by the construction of the
Laplacian matrix).
The multiplicity of the zero eigenvalue is equal to one when the communication graph
is connected.
40
All the eigenvalues of the Laplacian matrix lie in a disk of radius 1 centered at 1 + 0jin
the complex plane (Perron-Frobenius theorem) [44]. So, in the case of undirected commu-
nication graphs, all the eigenvalues are real numbers which are less than or equal to 2.
In the following section, we discuss the influence of the Laplacian matrix of the com-
munication graphs on the formation of micro-satellites, in an autonomous setting.
3.3 Role of the Communication Topologies in an Au-
tonomous Setting
The communication topology for a formation, represented by the communication graphs,
are widely studied for their role in influencing the entire system. The results of changing
the communication graphs and observing the results on the systems are performed in [51],
[31], and [52]. The plan of most of the formation missions is, to be deployed into a Li-
bration orbit around the Lagrange point L2. Close to this orbit, a time-dependent linear
model may be used in order to describe the motion of the spacecraft [66]. Firstly, we start
with a time-independent model (as an autonomous system), to describe the formation of
micro-satellites. We study the impact of the communication topologies in this framework.
We use the model from [68], described in the previous chapter 2, to describe the dynamics
of the micro-satellites. Each micro-satellite is described by (2.11). With the introduction
of the decentralized control law and the communication information in the form of the
Laplacian matrix, we write the entire system of Nvehicles compactly as,
˙x=ˆ
Ax +ˆ
Bˆ
Fˆ
L(x−h),(3.1)
with the “hatted” matrices representing the Kronecker products, which are shown in the
Section 2.5, in the Chapter 2. It is required to find the decentralized feedback control
law such that the error measurement becomes zero (z→0) or the micro-satellites have
attained the desired positions in the formation.
The entire system equation, for a system of Nmicro-satellites, can be analyzed further
for its structure. The Kronecker product of a matrix basically results in the matrix N
times along the diagonal. The block structure of the matrices ˆ
Aand ˆ
Bwould result in the
decentralized control law ˆ
F, also to be found in the form such that it acts the same on all
the vehicles, i.e., it is the same for all the micro-satellites. It has to be in the form of
ˆ
F=IN⊗Fveh.(3.2)
Remark: The eigenvalues of the matrix
ˆ
A+ˆ
Bˆ
Fˆ
L, (3.3)
41
from the Equation 3.1, are the same as that of the eigenvalues of
Aveh +λBvehFveh,(3.4)
which are derived from the individual micro-satellite dynamics (2.11). λis an eigenvalue
of the Laplacian matrix L.
This remark can be proved by using the Schur transformation techniques [44]. We
consider a matrix U, to be the Schur transformation of the Laplacian matrix L. We have
T=U−1LU (3.5)
such that the matrix Tis upper triangular. All the eigenvalues of Lare the diagonal entries
of the matrix T.
We have described the block diagonal nature of the matrices ˆ
A,ˆ
B, and ˆ
F. Using this
special form of these matrices we have
(U−1⊗In)( ˆ
A+ˆ
Bˆ
Fˆ
L)(U⊗In) = IN⊗Aveh +T⊗BvehFveh.(3.6)
From (3.6), we can analyze the right hand side of the formulation. We see that the right
hand side is block upper triangular whose diagonal blocks are of the form
Aveh +λBvehFveh.(3.7)
Each eigenvalue (λ), of the Laplacian, is present in a corresponding block. This implies
that the eigenvalues of the matrix ˆ
A+ˆ
Bˆ
Fˆ
L(3.3), are the eigenvalues of the matrix
Aveh +λBvehFveh (3.4), for an eigenvalue λof the Laplacian L.
Proposition 1 Let Fveh =In⊗(f1f2). Suppose that, the matrix Aveh +λBvehFveh is stable
for each non-zero eigenvalue λof the communication graph Laplacian L. Then,
L(x−h)→0.(3.8)
Proof: See [68].
In [68], it is shown that the vehicles are in formation if and only if ˆ
L(x−h) = 0 and
(under certain assumptions) that, if the matrix Aveh +λBvehFveh is stable, for each nonzero
eigenvalue λof L, then ˆ
L(x(t)−h)→0 as t→ ∞, i.e., the vehicles asymptotically attain
the desired formation. For a given communication graph, this result thus gives a criterion
on how to design the feedback matrix F. In fact, under certain assumptions on the un-
controlled dynamics of a single system, i.e. on the matrix A, one can show that for every
connected graph one can find a feedback matrix Fwhich renders the closed loop system
stable.
We have the proposition,
42
Proposition 2 Given the matrices ˆ
Aand ˆ
B, as in (3.3), and a connected communication
graph with a Laplacian matrix L, there exists Fveh, such that
Aveh +λBvehFveh,(3.9)
is stable for each non-zero λ, in the spectrum of L.
Proof: See [68].
From the Proposition 2, it is clear the feedback matrices can in fact be constructed which
render the system stable regardless of how the communication graph is chosen – as long
as it is connected. This means, in the autonomous setting for the formation of micro-
satellites, the communication topologies should be connected at each point of time. Then,
every formation, under these circumstances, can be stabilized by a decentralized feedback
law, as long as the communication graph or the communication topology is connected. The
role of the communication topologies, hence, is minimal in this setting.
3.4 Role of the Communication Topologies in a Non
Autonomous Setting
In the previous section, we noticed that as long as the communication graph is connected,
a decentralized feedback can be found to stabilize the formation of micro-satellites. We
now shift our focus towards a more realistic non-autonomous setting. The choice of the
feedback matrix Fveh will depend on the single system dynamics (i.e. the matrix Aveh) and,
in particular in our application context, in a non-autonomous setting it may happen that
Ais changing in such a way that the overall system dynamics becomes unstable. In this
case, the question arises which communication topology is best suited in the sense that it
will ensure stability of the formation for the largest “range” of single system dynamics.
In order to make these considerations more precise, we focus on the following basic set-
ting: we assume that each coordinate of the system is modelled by the same second order
dynamics, i.e., we have
Aveh =I3⊗0 1
0a22 (3.10)
and
Bveh =I3⊗0
1.(3.11)
Using F=I3⊗(f1f2) as the feedback matrix, our goal will thus be to render the matrix
Hλ=0 1
0a22 +λ0 0
f1f2(3.12)
43
stable for each nonzero eigenvalue λof the Laplacian L.
The matrix Hλwill be stable if and only if
a22 +λf2<0 (3.13)
and
λf1<0.(3.14)
3.4.1 Minimal Laplacian Eigenvalues
We analyze the stability criterion by considering the conditions in the Equations 3.13 and
3.14. For these conditions to be satisfied, we have to ensure that:
In the condition 3.14, f1has to be chosen negative. From the Section 3.2, we know that
all the eigenvalues of the Laplacian of the communication graph lie between 0 and 2, i.e.,
λ∈[0,2], for all eigenvalues of L. Hence, for the condition (3.14) to be satisfied, f1has
to be chosen negative.
The choice of the λof Lhas to be the minimal eigenvalue of L. We have already stated
that in the case of the non-autonomous setting of the formation of micro-satellites, the
single system dynamics (in the basic setting) becomes unstable, i.e., in (3.10), a22 >0.
Hence, the eigenvalue λof Lwhich is closest to zero determines how the value f2has to
be chosen, in order to render the overall system stable. Therefore, we analyze the system
stability for the formation of micro-satellites with respect to the minimal eigenvalues of
the Laplacian of the communication graph.
The minimal eigenvalues of the Laplacian matrix of the communication graph has to be
considered to determine and compare the stability of the formations. When comparing the
minimal eigenvalues from the corresponding two Laplacians, the choice of the communi-
cation graph having the largest minimal nonzero eigenvalue is the best. This is because,
the largest minimal eigenvalue, for a fixed f2, allows for the largest value for a22, in the
condition (3.13), which implies that, the larger minimal eigenvalue allows for the larger
stability range for the changing a22 or the unstable dynamics.
3.4.2 Robustness of Communication Graphs
Due to the adversity of the environment in which the formation of micro-satellites operate,
there might be many reasons for the communication links to fail. This is a great danger
for the mission goal. The communication link failure might result in the total vulnerability
of the mission to fail. What is more, taking into account that communication links may
fail, the question is which topology is most robust with respect to such failures, i.e., the
topology which ensures stability of the system even when a certain number of links fail.
Hence, we need to consider the concept of robustness of the formations.
44
Definition 1 Robustness of a formation (of a communication topology) is the ability of
the communication graph to ensure stability of the system even with a certain number of
communication link failures.
The communication topology should sustain the stability as long as the graph is connected
as this gives the measure of the robustness of the formation. A communication link failure
results in the change of the Laplacian matrix and hence the minimum eigenvalue changes
again. We find that the minimum eigenvalue decreases as the communication link fails.
If we need to choose the communication graph to start with, we should compare the
decrease in the minimal eigenvalues for a definite number of communication link failures.
If the decrease of the minimal eigenvalues is minimal, it means the formation with that
particular starting communication graph is the most robust, i.e., it can sustain stability
for a larger number of communication link failures, as long as the graph is connected.
3.5 An Example: The Topologies of the Formation of
Six Micro-satellites
In this section, using an example of six micro-satellites, we elaborate on the concepts of
minimal eigenvalues of the Laplacian and its use in determining the robustness of the
formation communication topology. The possible communication topologies (defined by
the model), are given in Section 4.4 of the Chapter 2. All the possible non-isomorphic
connected regular undirected graphs with six nodes are given in the Figure 3.1. The five
possible communication topologies, as described by the model, are used for analyzing the
role of minimal eigenvalues, in determining their robustness.
Each of the communication topologies in the Figure 3.1, have their original Laplacian
matrices. The minimal eigenvalues are considered for each of the Laplacian matrices and
are seen in the Table 3.5. The first column describes the minimal eigenvalues for each of
the Laplacian matrices of the communication topologies (except for the 2-regular topology
which becomes disconnected as soon as more than one communication link is removed).
It is seen that, the complete graph has the highest minimal eigenvalue amongst the other
communication topologies. This implies that, for a fixed value of f2, the largest value of
a22 is allowed in the condition 3.13 which allows for stability for the largest range of single
system dynamics. Hence, as expected, the complete graph is the best choice.
In terms of robustness, we need to consider communication link failures for the origi-
nal communication topologies of the Figure 3.1. We consider the change in the Laplacian
matrices as we remove certain number of edges from each of the communication topology.
The removal of communication links or the edges from the communication graphs might
result in the graph being disconnected after a certain number of removals. We consider the
possible structures, where the graph is not disconnected and also consider the eigenvalues
for a certain removal being minimized over all the possible same-number removals. As
45
# of edge failures 0 1 2 3 4
3 regular (1) 0.6670 0.4226 0.2047 0.1960 0.1910
3 regular (2) 1.0000 0.6670 0.5286 0.2929 0.1910
4 regular 1.0000 0.8104 0.6670 0.4610 0.2727
5 regular 1.2000 1.0000 0.8911 0.8000 0.7180
Table 3.1: The minimal nonzero eigenvalues for the communication graphs under consid-
eration in dependence on the number of edge failures.
mentioned earlier, we do not consider the communication topology of 2-regular graph be-
cause it becomes disconnected when more than a single communication link fails. In the
Figure 3.1: All non-isomorphic connected regular undirected graphs with six nodes (Orig-
inal topologies without any communication link failures).
Table 3.1, we have the values of the minimal eigenvalues in each of the columns correspond-
ing to a certain number of communication link failures. We plot in the Figure 3.2, for the
possible communication link failures, the corresponding normalized minimal eigenvalues.
3.5.1 Inferences
From the Table 3.1 and the Figure 3.2, we see that for the original topologies presented
in the Figure 3.1, the complete graph has the highest minimal eigenvalue. This complete
graph, as expected, is the best choice of communication topology. In terms of robustness
of the communication topologies when faced with the communication link failures, we infer
that, the complete graph has the least decrease in the minimal eigenvalues. It can be seen
from the Table 3.1 that, on certain removals of the communication links, the complete
graph has the highest minimal eigenvalue, after each removal. In the Figure 3.2, we see the
normalized minimal eigenvalues and see that the complete graph has the least decrease in
the eigenvalues, with the increase in the number of communication link failures. It is not a
46
Figure 3.2: The plot of normalized λmin.
47
suprising or an extra-ordinary observation that the complete graph is found to be the most
robust topology. What is interesting to note by this methodology, from the Figure 3.2, is
that the communication topology 4-Regular is very close to the behaviour of the complete
graph till about two communication failures, but after that, the normalized minimal eigen-
value decreases drastically. After three communication failures, we see that the 3-regular-1
communication topology being more stable than the 4-regular. It is interesting to note
that the 3-regular-2 graph has the least stability compared to the other topologies.
3.6 Conclusion
In this chapter, we have seen the role of the communication topologies in the stability of
the formation of micro-satellites. Firstly, we discuss the modeling of the communication
information as the Laplacian matrix and the important properties of the Laplacian matrix.
We then discuss the role of the communication topologies in an autonomous setting. We
see that, any formation can be stabilized with a decentralized feedback law as long as the
communication topology is described by a communication graph which is always connected.
Further extending into the non-autonomous setting, we have described the role of the
minimal eigenvalues in determining the stability of the communication topologies. We also
discuss the concept of robustness and the role of minimal eigenvalues in determining the
robustness of the communication topologies when there are communication link failures.
Finally, we illustrate the concepts of the role of the minimal eigenvalues in determin-
ing the stability and the robustness of the formation of micro-satellites with an example
of six micro-satellites. We derive some unique observations from the results.
48
Chapter 4
Stability Radius
4.1 Introduction
In the Chapter 3, we have been using the minimal eigenvalues for the determination of the
robustness for the communication topologies of the formation of micro-satellites. A simple
linear model was being used in order to analyze the role of the communication topologies
under various scenarios. The eigenvalue method does not precisely indicate the stability
of the formation. The placement of the eigenvalues on the complex plane does not give an
accurate measure of the stability. If the “strength” of stability of a formation has to be
measured and studied for the longer mission-life of a formation, then studying the place-
ment of eigenvalues is not the precise method.
Previously, we have been considering a simple model in order to analyze robustness prop-
erties of certain communication topologies. In a more general setting, it will be necessary
to approach this question in a more systematic way. To this end, we propose to use the
concept of the stability radius from control theory, see [62]. In this chapter, we introduce
the concept of stability radius. Firstly, we present the traditional definition and concepts of
stability radius. We present a theoretical background of stability radius and state various
results appropriate for the determination of robustness of the formation of micro-satellites.
We then modify the concept of the traditional stability radius and define the stability
radius with the specific setting of the communication topologies of the formation of micro-
satellites. We discuss the concept of the structured stability radius and determine the
robustness of the communication topologies with an optimization problem. We consider
some communication link failures and then measure the robustness of the communication
topology using the stability radius. We compare the robustness aspect measured using the
stability radius and the results derived using the method of minimal eigenvalues of the
Laplacian matrix. Further, we present the concepts of stability radius using an example of
the communication topologies of a formation of six micro-satellites. We consider the com-
munication link failures of the topologies in this case and determine the robustness using
the modified stability radius. The results based on the modified stability radius presented
49
in this chapter, is elaborated from [11] where it was introduced, for which, the author has
contributed substantially.
The organization of the results in this chapter is as follows. In the Section 4.2, we present
the basic theoretical background on stability radius. We present some important results
on the classical definition of stability radius. In the Section 4.3, we present the new modi-
fied definition of stability radius for the setting involving the study of the communication
topologies of formation of micro-satellites. We define the concept of robustness and de-
termine the robustness of a communication topology using the modified stability radius.
We establish the results for structured stability radius. Further, in the Section 4.4, we
elaborate the results in the previous sections with an example of the formation of six
micro-satellites. We determine the robustness for the communication topologies for this
formation of six micro-satellites. Finally, we conclude with the summary of the chapter.
4.2 Theoretical Background
In the recent years, the problem of robustness has regained a prominent position in sys-
tems theory. In particular, the robustness measures have been introduced and analyzed
extensively in the research presented in [53], [54], [55], and [56]. The concept of stability
radius for the analysis of robustness of various systems was introduced by Hinrichsen and
Pritchard in [61] and [62]. The concept of stability radius has been developed over the
recent years to a comprehensive robustness analysis of linear state space system and poly-
nomials; see [57], [58], [59], [60], etc. In this section, we discuss some preliminary results
on the stability radius based on the results from Hinrichsen and Pritchard.
It is not enough if we just study the spectral placement and conclude about the stability
of the formation for that concerned communication topology. It is important to measure
the distance of that system or the formation from instability.
4.2.1 Mathematic Formulation of Stability Radius
Definition 2 In classical control theory, the distance from instability is referred to as
Stability radius ([62]).
For K=Ror C, we denote by Un(K), the set of unstable n×nmatrices over K:
Un(K) = {U∈Kn×n;σ(U)∩C+6=∅ } (4.1)
where C+is the closed right half complex plane.
We define for K=Ror C, the stability radius as the distance from instability as:
rK(A) = inf{ k A−Uk;U∈Un(K)}, A ∈Kn×n.(4.2)
50
This gives rise to two stability radius measures: real stability radius (rR) and complex
stability radius (rC).
4.2.2 Minimal Singular Value
The Singular Value Decomposition (SD) of a rectangular matrix A, is a decomposition of
the form
A=WSV T(4.3)
where, Wand Vare orthogonal matrices and Sis a diagonal matrix. The columns, wiand
vi, of Wand Vare called the left and right singular vectors, respectively, and the diagonal
elements, siof S, are called the singular values. The singular vectors form orthonormal
bases and the important relation, Avi=siwi, shows that each of the right singular vectors
is mapped onto the corresponding left singular vector, and the “magnification factor” is
the corresponding singular value.
For any A∈Kn×n, we denote the operator norm of Aby
kAk=max{k Az k;z∈Kn,kzk= 1}.(4.4)
Let the singular values of the matrix Abe denoted by
s1(A)≥s2(A)≥s3(A)≥. . . ≥sn(A).(4.5)
The minimum of all the singular values is given as
sn(A) = min{k Az k;z∈Kn,kzk= 1}.(4.6)
The smallest singular value measures the distance of a matrix from singularity (with re-
spect to the operator norm). Hence, we present the definition of the smallest singular value.
Definition 3 The smallest singular value of a matrix A, where the matrix Sis a singular
matrix, is given by
sn(A) = min{k A−Sk,S∈Rn×n,0∈σ(S)}, A ∈Rn×n.(4.7)
From the formulation of the smallest singular value, from definition 3, we have the follow-
ing proposition.
Proposition 3 For a matrix Awith a complex stability radius rC(A), the real stability
radius rR(A), and the smallest singular value sn(A), we have
0≤rC(A)≤rR(A)≤sn(A), A ∈Rn×n.(4.8)
From the Proposition 3, it is seen that the measure of the complex stability radius rC(A),
for a matrix Ais the least amongst all the other measures. Hence, it makes more sense to
concentrate on the definition and the properties of the complex stability radius.
51
4.2.3 (Complex) Stability Radius
Based on the inequality of (4.8), the complex stability radius is derived, with some gener-
alizations.
Proposition 4 For a stable matrix A, the complex stability radius can be given as
rC(A) = minω∈Rsn(iwI−A).(4.9)
Proof: See [62].
This measure of complex stability radius would be used for the determination of robustness
in the application of the formation of micro-satellites. This measure would be generally
referred as stability radius instead of complex stability radius. Now, we discuss some
properties of the stability radius.
Proposition 5 Let A∈Cn×nbe stable and normal with eigenvalues λj=−αj+iωj,
α1, . . . , αnare positive and in decreasing order, then rC(A) = αn.
The Proposition 5 shows that, for normal matrices, A∈Rn×n, the distance of Afrom
instability is measured by the distance of its spectrum from the imaginary axis. If Ais not
normal, the distance of σ(A) from the imaginary axis can be a very misleading indicator
of the robustness of stability of A.
For example, for any k > 0, let
A=−k k3
0−k
be a matrix which is not normal and is stable with the eigenvalues on the left side of the
complex plane. The value of kdetermines, how far left, the eigenvalues are placed on the
left side of the complex plane. However far the eigenvalues are placed on the left, with a
slight perturbation, in the form of
P=1/k 0
1/k 1/k ,
they are immediately dispersed to the right side of the complex plane, destabilizing the ma-
trix A. Hence, the placement of the eigenvalues is not an accurate measure of the strength
of the stability of a system. Hence, we have the stability radius to be more accurate about
the stability and robustness properties of the system.
We now modify this formulation of stability radius for the robustness analysis for a forma-
tion of micro-satellites.
52
4.3 Modification of Stability Radius
In order to establish the stability strengths of the formation of micro-satellites, we propose
a modified version of the stability radius. Firstly, we define the concept of robustness in
terms of the stability radius. Higher the stability radius, more stable is the system. For a
formation of micro-satellites, amongst the communication topologies, the communication
topology which results in a higher stability radius ensures greater distance of the system,
describing the formation, from instability.
When a communication link failure occurs, the communication topology changes, influenc-
ing the dynamics of the entire formation equation. The entire formation stability depends
on the basic system settings given by (3.9), in the Chapter 3, i.e.,
Aveh +λBvehFveh,(4.10)
is stable for each non-zero λ, in the spectrum of L. Now, from (4.9), we have the stability
radius for any stable matrix Mas
rC(M) = minω∈Rsn(iωI −M).(4.11)
From the single system dynamics in (4.10), we now set
M=Aveh +λBvehFveh.
Let L(G) be the Laplacian associated with a given communication graph G= (V, E), where
Vrepresents the set of nodes (micro-satellites) and Erepresents the set of communication
edges. The new modified stability radius for the formation of Nmicro-satellites, that we
propose, is appropriately dependent on the matrices Aveh,Bveh, the feedback Fveh and the
communication graph (G) from which the Laplacian is derived.
The modified stability radius is given for a stable M=Aveh +λBvehFveh as
rC(Aveh, Bveh, Fveh, G) = min
λ6=0,λ∈σ(L(G)) rC(Aveh +λBvehFveh),(4.12)
where
rC(Aveh +λBvehFveh) = minω∈Rsn(iωI −(Aveh +λBvehFveh)).(4.13)
In (4.12), the stability radius is computed for a communication graph where λis an eigen-
value of the Laplacian matrix of the graph. This measure of stability radius for a particular
communication graph is used for comparison with the stability radius measures of other
communication graphs. The higher the stability radius, more stable is the formation having
the communication topology, as higher is the distance from instability.
53
4.3.1 Structured Stability Radius
In the previous section, we discussed the stability radius for the unstructured system: for
the system ˙x=Ax. We now consider the structured perturbations of the nominal system
˙x=Ax, given by
˙x= (A+BDC)x, (4.14)
where D∈Cm×pis the disturbance matrix and B∈Cn×mand C∈Cp×n, are scal-
ing matrices. The stability radius for the stable matrix A∈Cn×nwith respect to the
perturbations of a given structure, is given as ([61])
rC(A) = inf{k Dk;σ(A+BDC)∩C+6=∅}.(4.15)
We now present the structured stability radius for the micro-satellite motions around the
halo-orbit.
For a stable M=ˆ
A+ˆ
Bˆ
Fˆ
L, we consider the perturbation matrix as just Dand hav-
ing the same structure as ˆ
Bˆ
Fˆ
L. Then, from (4.15), we have the structured stability radius
formulation, for the micro-satellites, as
rC(M) = inf{k Dk;σ(M+D)∩C+6=∅}.(4.16)
We now present the construction of the perturbation matrix of a certain structure. The
perturbation is created by making one or more links fail. The perturbation of some link
removals is added in the form of the Laplacian. The removal of some links results in a new
Laplacian: ˆ
Lf. The perturbation matrix is computed for each of the valid ˆ
Lf (the graph
remaining connected).
For a valid ˆ
Lf1of ˆ
L, we add each destabilizing feedback, from all the possible desta-
bilizing feedback in the set F1, to the existing stabilizing feedback and create the range of
perturbed feedback as −→
F1=ˆ
F+ˆ
F1.(4.17)
where each ˆ
F1∈F1. The cardinality of the set F1, is usually infinity, but in the realization
of the Nelder-Mead optimization, which would be described later, we assume this set to
be finite.
The perturbed system of M=ˆ
A+ˆ
Bˆ
Fˆ
L, for ˆ
Lf1of ˆ
L, is given by
−→
M1=ˆ
A+ˆ
B(ˆ
F+ˆ
F1)ˆ
Lf1.(4.18)
Hence, we get −→
M1=ˆ
A+ˆ
B(−→
F1)ˆ
Lf1.(4.19)
The perturbation matrix, is then computed as
D11=−→
M1−M. (4.20)
54
Hence,
D11=ˆ
B(−→
F1ˆ
Lf1−ˆ
Fˆ
L).(4.21)
We also have,
kD11k=kˆ
B(−→
F1ˆ
Lf1−ˆ
Fˆ
L)k.(4.22)
For ˆ
Lf1, we have the perturbation set as D1for some sgiven by
D1={D1, . . . , Ds}.(4.23)
Similarly, for another valid perturbation (removal of two edges) of ˆ
L:ˆ
Lf2, we have
D21=ˆ
B(−→
F2ˆ
Lf2−ˆ
Fˆ
L).(4.24)
For ˆ
Lf2, we have the perturbation set as D2given by
D2={D21, . . . , D2s}.(4.25)
Hence for some m, for ˆ
Lfm,
Dm1=ˆ
B(−→
Fmˆ
Lfm−ˆ
Fˆ
L).(4.26)
For ˆ
Lfm, we have the perturbation set as Dm, given by
Dm={Dm1, . . . , Dms}.(4.27)
Hence, for some m= 1, . . . , r, where ris the number of valid perturbations of ˆ
L, we have
D={
r
[
m=1
Dm}.(4.28)
We now define the structured stability radius for the stable matrix M=ˆ
A+ˆ
Bˆ
Fˆ
L, for
some mas,
rC(M)m=infDm∈D{k Dmk;σ(−→
Mm)∩C+6=∅, m = 1, . . . , r}.(4.29)
The stability radius of a particular topology, i.e., for a particular ˆ
L, as given in (4.29), is
determined by solving ridentical discrete optimization problems, where ris the number
of valid perturbation of ˆ
L. By solving for each perturbation, we get the stability radius for
each edge disruption.
We now present the characterization of the optimization problem that we solve to de-
termine the stability radius.
55
We first discuss the characterization for a particular ˆ
Fmof ˆ
L. We have the entire sys-
tem given by a stable M=ˆ
A+ˆ
Bˆ
Fˆ
L. We look at the construction of the perturbed
feedback: ˆ
Fm, shown in (4.17). We have that
ˆ
Fm=IN⊗Fvehm,(4.30)
where Fvehmis the perturbation feedback for the decentralized stabilizing feedback for
each vehicle (described in the previous chapters). Fvehmis constructed in the basic form
as:
Fvehm=I3⊗fm.(4.31)
fm= [f1mf2m]
So, basically ˆ
Fmis a function of f1mand f2mof fm. The destabilizing feedback should be
determined such that the perturbed matrix becomes unstable. The problem can be defined
for (4.29), as
rC(M) = inffm∈Skˆ
B(−→
Fmˆ
Lfm−ˆ
Fˆ
L)k.(4.32)
The set Sis defined as
S={max(real(σ(ˆ
B(−→
Fmˆ
Lfm−ˆ
Fˆ
L)(fm)))) >0}.(4.33)
The problem in (4.32), is approximated from computing the infimum to computing the
minimum. As we have two variables in fm, for the computation of the set of destabilizing
feedback for each ˆ
Lf, we use the Nelder-Mead optimization problem.
The Nelder-Mead method is a simplex method for finding a local minimum of a func-
tion of several variables (see [63]). It’s discovery is attributed to J. A. Nelder and R. Mead.
For two variables, a simplex is a triangle, and the method is a pattern search that compares
function values at the three vertices of a triangle.
The optimization variables are f1mand f2mfor some m= 1, . . . , r, where ris the number
of valid ˆ
Lf. The Nelder-Mead optimization is implemented, for each valid ˆ
Lf, in Mat-
lab using a function called “fminsearch”. The minimum is found for each ˆ
Lf by solving
roptimization problems. The stability radius measure is the minimum of each of the r
measures.
4.3.2 Robustness of a Communication Topology using the Sta-
bility Radius
In order to study the robustness properties of a communication topology, it is important
to consider communication failures in the topology. When the communication link failures
occur in a communication topology, it results in the change of the communication graph
and hence a change in the Laplacian matrix.
Definition 4 Robustness. It is the ability of the formation to perform the required func-
tionalities inspite of the communication link failures. The higher the stability radius, the
more robust is the formation of micro-satellites with the communication topology.
56
4.4 Example
We illustrate the robustness properties using the stability radius with the example of the
formation of six micro-satellites. The formation of six micro-satellites has five possible
communication topologies as defined by the model. We perform the robustness analysis
for these communication topologies using the stability radius concepts and determine the
robust communication topologies.
The Figure 4.1 shows the five possible communication topologies for a formation consist-
ing of six micro-satellites. We neglect the 2-regular communication topology as it becomes
disconnected after just one communication link failure. The Table 4.1 depicts the stabil-
ity radius values as defined in (4.12), only for the original topologies. The values in the
columns represent the (unstructured) stability radius for the four original topologies. The
Figure 4.2 depicts the stability radius computed for the original topologies. The structured
stability radius computation is performed for various communication link failures and also
for only valid communication graphs : that which are not disconnected, and is depicted in
the Table 4.1. The columns in the table depict the number of failures in the communication
links. The Figure 4.3 depicts the structured stability radius for various communication link
failures.
Figure 4.1: All non-isomorphic connected regular undirected graphs with six nodes (Orig-
inal topologies without any communication link failures).
# of edge failures 0
5 regular 0.5350
4 regular 0.4454
3 regular-2 0.4898
3 regular-1 0.3719
Table 4.1: The stability radius for the original communication graphs under consideration.
57
Figure 4.2: The stability radius for the original communication topologies (unstructured
stability radius).
# of edge failures 1 2 3 4
5 regular 4.6756 4.5557 3.9008 3.4230
4 regular 6.0136 4.5258 3.7764 3.3161
3 regular-2 3.6373 3.2404 2.3884 2.1159
3 regular-1 3.1756 3.1035 2.1819 1.8308
Table 4.2: The structured stability radius for the communication graphs under considera-
tion, with the perturbation of the failure of some number of edges.
58
Figure 4.3: The structured stability radius for the perturbed communication graphs.
59
4.5 Inferences
The stability radii for the original communication topologies of the Figure 4.1, are presented
in the Table 4.1. The columns in the table represent the stability radii for the original com-
munication topologies. We observe that, for the original communication topologies (zero
link failures), the stability radius of the complete graph is the highest. In the Figure 4.2, the
gradual decrease in the stability radii measures are shown for each of the original topologies.
We now observe the structured stability radius from the Table 4.2. We observe an in-
teresting fact that, for the 4-regular graph, the stability radius computed for a single
communication link failure results in a higher stability radius than for a single communi-
cation link failure for the complete graph (see Figure 4.3). It is also worth observing that,
the stability radius decreases with the occurrence of the communication link failures, in
each of the communication topologies. The decreasing stability measures imply that the
communication link failures increases the instability in the formation of micro-satellites.
From the Definition 4, we know that the most robust communication topology is that
which has the least decrease in the stability radius measures with some communication
link failures. Hence, we have the already established fact that the complete graph is the
most robust communication topology for a formation consisting of six micro-satellites as
it has the least decrease in the stability radius measure. The aim of this experiment is to
observe the behaviour of the remaining communication topologies. It is interesting to note
the behaviour of the 4-regular communication topology. It is noticed that the complete
graph and 4-regular communication topologies have similar stability radius curves with the
increase in the number of communication link failures.
What does this imply? In the mission design, if the formation of micro-satellites are
to deployed in a highly sensitive location in space where it is almost sure of a single or
more communication link failure to occur, then 4-regular communication topology has
more probability to be chosen even though the complete graph original topology might be
more stable than the 4-regular communication topology, as shown in the Figure 4.3. It
has to be noted that the complete graph might not be chosen eventhough it is most robust
since it might lead to high communication and hardware overload which results, when all
the micro-satellites try to communicate with every other micro-satellite.
4.6 Robustness: Minimal Laplacian Eigenvalues vs
Stability Radius
In the previous Chapter 3, we defined the robustness concepts using the minimal eigen-
values of the Laplacian matrix of the communication topology (communication graph).
We have already seen that the minimal Laplacian eigenvalue method is not an accurate
methodology for the determination of the robustness of a communication topology. The
60
more accurate method using the control theory concepts is by using the stability radius as
presented earlier.
In this section, we compare the results of robustness determination of both the meth-
ods, using an example of six micro-satellites. For a formation of six micro-satellites, the
left plot of the Figures 4.4, shows the normalized minimal eigenvalues plot for each of the
communication topologies with some communication link failures.
Figure 4.4: The plot of normalized λmin.
4.7 Conclusion
In this chapter, we have introduced an alternate method of determining the robustness
of communication topologies: using the stability radius. This method, using the control
theoretic concepts, is more accurate than the minimal Laplacian eigenvalues method. We
have defined the stability radius in the classical control theoretic manner. We have also
shown some results based on the stability radii: real stability radius and complex stabil-
ity radius. We use the complex stability radius for the application of formation flying of
micro-satellites. The stability radius is derived for a stable matrix.
Further, we modify the classical definition of the stability radius to the application of
formation of micro-satellites. We define a new stability radius depending on the single
system dynamics. The modified stability radius depends on the feedback and the commu-
nication topology. Higher the measure of the stability radius, more stable is the formation
with the particular communication topology. We define the concept of robustness of a
communication topology based on the modified stability radius. The Laplacian of the
communication topology changes for every communication link failure. Hence, we com-
pute the stability radius for each of the derived communication topologies (Laplacians)
from the original topology (Laplacian). The analysis of the stability radius for the all the
61
valid communication topologies of an original topology determines the robustness of the
original communication topology.
Finally, we elaborate the results based on an example of a formation of six micro-satellites.
We observe the robustness properties of the communication topologies for the six micro-
satellites. In the end, we compare the observations made from the stability radius analysis
to the robustness observations of the method using the minimal Laplacian eigenvalues.
62
Chapter 5
Formation of Micro-satellites: A
Non-Autonomous Model
5.1 Introduction
In the previous chapters, we developed results based on a simple linear model. In this
chapter, with the aim of dealing with the most realistic scenario, we develop a non-linear
non-autonomous model of describing the formation of micro-satellites, in some specific or-
bit in space. For achieving this, we start with dealing with the linear model in depth and
customizing to the application of the deployment of the formation in a specific orbit in
space. Further, we develop a non-linear model with the description of the dynamics of the
micro-satellites using the Hill’s model. Developing on this model, we describe a leader sin-
gle follower control strategy. Extending this control strategy, we aim to develop a control
strategy for the deployment of the formation of micro-satellites in a halo-orbit proximity.
For this purpose, we use the two models together: the extended linear model describing the
“Formation-keeping control” and the “Leader-follower strategy”. The concept is, to place
the initial center of mass of the formation on the halo-orbit. Then, the formation keeping
control is applied to keep the micro-satellites centered around the center of mass. Then a
leader follower control strategy is applied, with the imaginary leader on the halo-orbit and
the follower being the center of mass of the formation. With the simultaneous application
of both these control strategies, we have the formation center of mass on the halo-orbit and
the micro-satellites in a formation around the formation center of mass in the halo-orbit
proximity. The definition of the reference state vector ensures the size and the spread of
the formation.
Such non-autonomous modeling of formation flight have been discussed in works pub-
lished in [28], [29] and [31]. We elaborate on the linear model introduced in the Chapter 2
and establish it as a formation keeping control. We determine the decentralized feedback
control law which keeps the micro-satellites centered around the center of formation. We
then shift to a non-linear model in which the micro-satellites are defined by the Hill’s equa-
63
tions of motion. We derive a leader-follower control strategy with an imaginary leader on
the halo-orbit and with a follower in the proximity. Inorder to place the entire formation
of micro-satellites in the proximity of the halo-orbit, we place the formation center of mass
on the halo orbit. Then applying the formation keeping control we try to keep the entire
formation centered around the center of mass. Now, we need to apply the leader follower
control with the center of mass as the follower to the imaginary leader on the halo-orbit.
Hence, at each time, we have both the control strategies acting together to keep the for-
mation controlled in the proximity of the halo-orbit.
We analyze the stability of this control strategy by analyzing the monodromy matrix. The
floquet multipliers from the monodromy matrix determine whether the control strategy
is stabilizing or not. Inorder to critically analyze the performance of the control strat-
egy in maintaining the formation of micro-satellites in the proximity of the halo-orbit, we
determine the deviation measure of the formation from the desired position. Lesser the
deviation, more efficient is the control strategy. We verify the control strategy with an
example of a formation of six micro-satellites. We have the reference vector defined at
each time in such a way that the center of mass is the center of a regular hexagon with
the micro-satellites placed at corners. We observe various results with some interesting
observations.
The results in this chapter are organized as follows. In the Section 5.2, we present the
elaboration of the linear model presented in the Chapter 2. We show that this decen-
tralized control strategy is the formation keeping control strategy which keeps all the
micro-satellites centered around the formation center. We also illustrate this decentralized
control with an example of six micro-satellites.
In the Section 5.3, we introduce the non-linear non-autonomous model and describe the
dynamics of the micro-satellites by the Hill’s model. A leader follower control strategy is
introduced, as presented in [36]. A stability analysis is performed using the monodromy
matrices and by plotting the floquet multipliers. We extend this leader follower control
strategy to more than one follower micro-satellite in the Section 5.4. We establish that
the single leader multiple follower control strategy is not exactly a formation, but indi-
vidual micro-satellites following the leader independent of the other micro-satellites. In
the Section 5.5, we establish a coupling between the micro-satellites along with the leader
follower control, inorder to establish formation flying of micro-satellites. We aim to make
the center of mass of the formation, as the follower in the leader follower control strategy.
We formulate the follower dynamics in the proximity on the halo-orbit. Further, we extend
the linear model of formation keeping control strategy to the case of the proximity of the
halo-orbit. Finally, after applying the formation keeping control and the leader follower
control strategy, we formulate the equation of motion for the formation of micro-satellites
in the halo-orbit proximity. In the Section 5.6, we present the method of computing the
deviation of the formation from the desired relative positions. We illustrate the results
with an example of a formation of six micro-satellites. We conclude this chapter with the
64
summary in the Section 5.8.
5.2 Formation Keeping Control
In this section, we will formally establish the linear decentralized control, introduced in
the Chapter 2, as a formation keeping control. To describe the dynamics of each of the
micro-satellites, we have xi∈R6as the state of each vehicle. Let ui∈R3be the control
input for each micro-satellite. The identical individual micro-satellite dynamics for each of
the Nmicro-satellites is given by
˙xi=Avehxi+Bvehui, i = 1, . . . , N. (5.1)
We consider the basic 2 ×2 matrix for Aveh, where Aveh =I3⊗ˆa,
ˆa=0 1
0a22 .(5.2)
For the matrix Bveh, the basic 2 ×2 matrix is given as
ˆ
b=0
1,(5.3)
with Bveh =I3⊗ˆ
b.
For i= [1, N], denote h∈R6Nas the reference state vector. It is represented as
h=
h1
.
.
.
hn
.(5.4)
The communication between the micro-satellites is depicted by a communication graph.
The communication information is incorporated into the dynamics through the Laplacian
matrix of the communication graph depicted in the Equation 2.2 in the Chapter 2.
The decentralized feedback that steers the formation of micro-satellites into the desired
formation is computed. Each micro-satellite ican generate its own control ui, from the
determination of its state relative to the states of some subset, Si⊂ {1, . . . , N}of all
vehicles (obtained by communicating with the vehicles in Si).
Each micro-satellite computes
zi= (xi−hi)−1
|Si|X
j∈Si
(xj−hj),(5.5)
65
for some subset Si.
A decentralized feedback control which is the formation keeping control law, is given by
the matrix Fveh. The basic form of the formation keeping control matrix is given by
ˆ
f=f1f2.(5.6)
Here,
Fveh =I3⊗ˆ
f. (5.7)
Each vehicle sets the local control, for some feedback matrix Fveh, as
ui=Fvehzi.(5.8)
Entire System Dynamics
We have from (5.1), that the single system dynamics for each vehicle, i= [1, N], are
identical for all the micro-satellites. As it it is required to analyze the entire formation, we
need to combine the individual dynamics into a single entire system dynamics. We take
the Kronecker products over the number of micro-satellites for the matrices and we get
ˆ
A=IN⊗Aveh,ˆ
A=IN⊗Aveh,ˆ
L=Lveh ⊗In, and ˆ
F=IN⊗Fveh. As explained in the
Chapter 2, the output vector zcan be denoted as
z=L(x−h),(5.9)
where Lis the Laplacian of the communication graph.
The entire system dynamics for a formation of Nmicro-satellites is given by
˙x=ˆ
Ax +ˆ
Bˆ
Fˆ
L(x−h).(5.10)
5.2.1 Example
We now present the formation keeping control with the example of six micro-satellites.
Each of the micro-satellites are identical in structure and have identical individual dy-
namics given by (5.1). The communication topology that we use is the complete graph.
The Laplacian is incorporated into the dynamics. The formation keeping control is then
determined for the entire system dynamics given by (5.10). We present two cases: firstly,
where the decentralized formation keeping control converges each of the micro-satellites
into a formation and secondly, a case where the supposed formation keeping control does
not succeed in the formation keeping but results in the diverging of the formation.
66
Figure 5.1: The relative trajectories of the six micro-satellites driven into a circular forma-
tion by the decentralized formation keeping control.
67
Figure 5.2: The relative trajectories of the six micro-satellites diverging from their initial
positions.
In the Figure 5.1, the formation keeping control in the basic form of ˆ
f= [−2,−2] and
the basic matrix of Aveh is given in (5.2). This formation keeping control drives the for-
mation into a circular formation.
In the Figure 5.2, the decentralized control is unable to get the trajectories of the micro-
satellites in the desired formation. Here, the micro-satellites diverge from their initial
positions and the desired formation is not achieved. It is similar in the Figure 5.3, where
the micro-satellites do not attain the desired formation. In both the cases, the basic ma-
trix ˆaresults in the diverging property of the formation. In this section, we have seen the
design of the formation keeping control. This formation keeping control would be used in
the future with respect to the formation flying in the proximity of the halo-orbit.
68
Figure 5.3: The relative trajectories of the six micro-satellites diverging from the initial
points and not into a formation.
69
5.3 The Non-Autonomous Model
In the previous section, we studied a simple linear model to describe a formation keeping
control strategy. In this section, we study a leader follower strategy with a realistic non-
linear non-autonomous description of the micro-satellites in the proximity of a halo orbit
in space. The leader and the follower micro-satellite are described by the non linear Hill’s
model of equations. There are other non-linear models of expressing the dynamics, like
the Circular Restricted Three-Body Problem (CR3BP), explained in detail in [65]. The
CR3BP is a simple non-linear model which describes the dynamics of a massless object
(e.g., a satellite around a planet) attracted by two point masses (Sun and the planet of
the satellite) revolving around each other in a circular orbit. Specifically, this model gives
a good description of the dynamics around a satellite of a planet, like in the Sun-Earth
system. In the Sun-Earth system for the CR3BP, the smaller Earth is the primary and the
bigger Sun is the secondary. For this system, the origin lies in the center of mass of the
primary and the secondary.
In the case of describing the dynamics of a micro-satellite in the proximity of Earth, i.e.,
the dynamics close to the primary (Earth), the Hill’s model also gives a good description.
The Hill’s model with its simpler set of equations compared to the CR3BP, is a restricted
case of the CR3BP. In the following section, we describe the Hill’s model.
5.3.1 Hill’s Model
In the Hill’s model, unlike the CR3BP, the description covers the dynamics of two smaller
bodies (e.g., Earth and its satellite) in a circular orbit around the bigger secondary (e.g.,
Sun) [64]. Being more general in description, the Hill’s model is used in our study to
describe the dynamics of the micro-satellites.
In CR3BP, the origin of the system lies in the center of mass of the primary and the
secondary. In the Hill’s model, the origin of the system lies in the center of the primary
(Earth). Unlike the CR3BP, where the mass of the primary (Earth) is a considerable fac-
tor, in the Hill’s model, both the primary (Earth) and the orbiter around the primary are
considered to be point masses compared to the secondary (Sun). Here, the mass ratio of
the primary to the secondary is zero. The equations are then scaled to remain finite. This
method, however, describes the way in which the Hill’s model can be obtained from the
CR3BP.
As shown in the Figure 5.4, the origin of the model lies in the center of the primary.
The model, now describes the dynamics in the proximity of the primary. The x axis of
the coordinate system is along the line joining the primary and the secondary. The y axis
is along the direction of the tangent to the orbit revolution of the primary around the
secondary. The z axis is the perpendicular to both x and y. We present the formulation of
the Hill’s equations of motion in the following section.
70
Figure 5.4: Hill’s model of three body problem.
Hill’s Equations of Motion
We present the formulation of the Hill’s equations. We present the Hill’s equations of mo-
tion. We desire the micro-satellites to follow the dynamics described by the Hill’s model.
As mentioned earlier, the center of the coordinate system is taken to be at the center of
the primary (Earth). We define few terms and constants for the equations of motion.
In three dimensions:
r=px2+y2+z2,
wis the mean motion of the central attracting body (Earth) about the perturbing body
(Sun),
µis the gravitational attraction of the central body (Earth), and
Vis the force potential.
71
The equations of motion are given by
¨x−2w˙y=δV
δx (5.11)
¨y+ 2w˙x=δV
δy (5.12)
¨z=δV
δz (5.13)
V=µ
r+1
2w2[3x2−z2] (5.14)
The solution to the Hill’s equations gives a family of periodic orbits. We choose a particular
periodic orbit solution of the Hill’s equations- a halo orbit. This orbit is an object of
consideration for the strategy we like to derive finally. In the next section, we derive a
leader follower strategy designed on the halo-orbit.
5.3.2 Leader Follower Strategy
In this section, we present the leader follower control strategy (see [36]). We choose a
particular periodic orbit solution of the Hill’s equations- a halo orbit for the leader micro-
satellite. The follower micro-satellite is placed in the proximity of the halo orbit. The
goal is now to stabilize the relative trajectory of the follower with respect to the leader
micro-satellite and achieve the leader follower configuration. Hence, we establish the leader
follower control strategy.
Let R(t;R0,V0) represent the halo periodic orbit trajectory. The leader micro-satellite
is on this trajectory. V=˙
Rrepresents the velocity of the leader micro-satellite and let
r(t;r0,v0) represent the trajectory of the follower micro-satellite with v=˙
rbeing the
velocity of the follower micro-satellite.
Let x(t)=[r,v] and X(t)=[R,V] be the respective solutions, and δx=x−Xis
assumed to be very small. The linearization of the Hill’s equations is presented below:
Let F(X) represent the dynamics function corresponding to the Hill’s equations:
F(X) = V
Vr+ 2wJV,(5.15)
where
J=
0 1 0
−100
0 0 1
.(5.16)
Linearizing the halo orbit at each point of time, i.e., linearizing F(X(t)), we get
−→
A(t) = 0 I
Vrr(R(t)) 2wJ .(5.17)
72
The leader follower control law is defined in such a way that it acts on the force potential
(Vrr(R)). The steps for the leader follower control law determination are:
Firstly, the relative position vector (δr) is projected on to the stable and the unstable
manifolds.
Further, it is multiplied with a gain constant (G) and is applied along the stable and
the unstable manifolds, respectively.
The steps are formulated and is indicated as the leader follower control as
C=Cδr, (5.18)
where the matrix Cis given by
C=−σ2G(u+uT
++u−uT
−).(5.19)
Here, +σand u+are the eigenvalues and eigenvectors computed from
(σ2I−2wσJ −Vrr)u+= 0 (5.20)
and
(σ2I+ 2wσJ −Vrr)u−= 0.(5.21)
The leader follower control is then applied onto the force potential, i.e., the control matrix
Cfrom the Equation 5.19, is introduced into the linearization in (5.17), at each point of
time.
Hence, we get the new linearized matrix, at each point of time, as given by
A(t) =0 I
Vrr −C2wJ .(5.22)
The leader follower control law consists of a reshaping of the local force structure by
application of proper thrusting.
Simulation
In the Figure 5.5, we simulate the leader follower control strategy with the imaginary leader
having its trajectory on a halo-orbit and the following micro-satellite in the proximity.
In the simulation, in the Figure 5.5:
The value of the gravitational constant µ= 0.39863371e06 km3/sec2;
The orbit angular rate of the sun-earth system w= 2*π/(8766*86400) rad/sec;
The value of the Gain constant G= 0.4.
73
Figure 5.5: Leader Follower Micro-satellite Trajectories
74
5.3.3 Stability Analysis
It is required to determine whether the leader follower control described in the previous
section stabilizes the relative trajectory. The leader and the follower micro-satellites are
defined by the Hill’s equations of motions. The solutions for the leader and the follower
micro-satellite motions are represented respectively by, x(t) = [r,v] and X(t) = [R,V]. If
the distance between the two solutions is relatively small, the relative trajectory can be
approximated using the linearized equations of motion.
The difference in the solutions is given by δx=x−X.
The dynamics of δxare
δ˙
x=˙
x−˙
X(5.23)
δ˙
x≈−→
Aδx.(5.24)
The solution to the relative motion is given as
δx=φ(t, t0)δx0(5.25)
˙
φ(t, t0) = −→
A(t)φ(t, t0),(5.26)
with
φ(t0, t0) = I, (5.27)
where, φis the transition matrix computed about the periodic orbit with the initial con-
ditions of the periodic orbit as δx0.
After application of the control law from (5.19), the matrix Ais considered. Hence, we
have
˙
φ(t, t0) = A(t)φ(t, t0),(5.28)
with
φ(t0, t0) = I. (5.29)
Considering the transition matrix φ(t0+t, t0), the monodromy matrix is evaluated by
considering the transition matrix over one period, i.e., φ(t0+T, t0).
The monodromy matrix is analyzed and the eigenvalues of the monodromy matrix, called
the floquet multipliers are studied. The placement of the floquet multipliers determine the
stability of the leader follower control strategy. If the floquet multipliers have the magni-
tude of 1, then the system is stable.
We perform the simulations with the control strategy by varying the gain parameter G.
In our experiments, we find that the gain parameter stabilizes for some gain, with all the
floquet multipliers having the magnitude 1, and for some gain parameters, the floquet
multipliers do not have the magnitude 1, and hence the system is not stable.
75
Simulation
The transition matrix consists of 36 equations and the integration of the periodic orbit
consists of 6 more of them. The integration is performed using MATLAB and the total
number of equations are 42. In our simulation for the determination of stability of the
system, we plot the floquet multipliers for a varying gain. We note the gain values for
which all the floquet multipliers have a magnitude 1. As seen from the Figure 5.6, the
floquet multipliers for the gain ranging from 0.4-0.8, seem to stabilize the relative trajec-
tory, as the magnitudes of all the floquet multipliers in that range of the gain are 1. In the
Figure 5.6: Floquet Multipliers with Varying Gain
Figure 5.7, similar experiment is performed for a larger range of the gain parameter. The
gain parameter is varied from a range of 0.8 to 2.6. Again it is noted that, for the gain
range of 1.3 to 1.5, the floquet multipliers have a magnitude of 1.
Hence, we can choose an appropriate gain parameter for a stabilizing leader control law
for an imaginary leader on the halo-orbit and a follower micro-satellite in the halo-orbit
76
Figure 5.7: Floquet Multipliers with Varying Gain
proximity.
5.4 Single Leader Multiple Followers
As we have established a leader follower control strategy for a single micro-satellite fol-
lowing an imaginary leader on the halo-orbit, it makes immediate sense to look at more
than one micro-satellite as a follower. Hence, we adapt the single follower micro-satellite
to multiple followers of an imaginary leader.
The leader follower control law is applied to each of the follower micro-satellites indi-
vidually. Each of the follower micro-satellites start close to each other and follow the
imaginary leader on the halo-orbit. They are independent of each other. The Figure 5.8
77
shows the followers following the leader independent of each other. It is seen that as the
Figure 5.8: single Leader Multiple-follower Micro-satellite Trajectories
multiple follower micro-satellites independently follow the imaginary leader, there exists
no formation. The entire functionality to be achieved as a formation of micro-satellites
cannot be achieved in this single leader and multiple independent follower scenario. For
the formation to exist, there should be a coupling between the micro-satellites inorder to
make the functionalities to be achieved as a formation. Hence, in the following sections,
we discuss the need for such coupling between the micro-satellites to enable a successful
formation of micro-satellites.
78
5.5 Formation of Micro-satellites in the Proximity of
the Halo Orbit
We have seen in the previous section that the leader follower control can be stabilized
individually for more than one follower in the proximity of a leader micro-satellite on the
halo orbit. This is not a formation as the individual micro-satellites do not have any cou-
pling between them. The micro-satellites are independent of the existence of the other. We
need to introduce some coupling to make the individual satellites together into a formation.
In this section, we merge the two separate worlds: the model of formation keeping and the
leader follower model. The main aim is the formation of micro-satellites in the proximity
of the halo orbit. For this purpose, it is required to merge the separate models in such
a way that the stabilizing control from both the models are used. We first discuss the
formulation of the follower dynamics for each individual follower so that it can be coupled
with all the other follower micro-satellites. We then modify the formation keeping control
to suit the needs of the entire formation in the proximity of the halo orbit. Further, we
formulate the equation of motion for the formation based on the merger of the separate
models. Inorder to critically analyze the new formation control that we have derived, we
perform some experiments and measure the deviation of the formation under the influence
of the new control.
For the design of the new control, we first determine the center of mass of the forma-
tion which is achieved through the formation keeping control. At the initial time, we make
this center of mass to start on the halo-orbit considered. This center of mass is made the
follower of an imaginary leader on the halo-orbit. The leader follower control is applied to
control the follower center of mass at each point of time. The reference vector decides the
size of the formation (spread from the center), and also the shape. Hence, the application
of both the controls: the leader follower control and the formation keeping control, ensures
the stabilization of the entire formation of micro-satellites in the halo-orbit proximity.
5.5.1 Formulation of the Follower Dynamics Relative to the Halo
Orbit
In the Section 5.3.2, we have described the relative trajectory stabilization for a follower
micro-satellite in the proximity of an imaginary leader on the halo orbit. The aim is to
make the center of mass of the formation as the follower of an imaginary leader. The
dynamics of the center of mass (follower) is formulated.
The leader and any micro-satellite follower is described the Hill’s equations described in
the Section 5.3.1. Let x(t) = [r,v] and X(t) = [R,V] represent the solutions of the follower
and the leader respectively. The formation center of mass is computed and initially, the
formation center of mass is placed on the halo orbit to be the follower of an imaginary
79
leader.
We compute the formation center of mass for the Nspacecraft at each time tas
m(t) = 1
NX
i=1
Nxi(t).(5.30)
We employ the leader follower control strategy on the center of mass with the imaginary
leader on the halo-orbit. Hence, we apply the leader follower control and get the linearized
matrix, at each point of time, given in (5.22).
The dynamics of the center of mass m(t) is then formulated as
˙m(t) = ˙
X+A(t)(m(t)−X).(5.31)
The aim is to compute the dynamics for each follower micro-satellite such that the for-
mulation involves all the micro-satellites. The next step is to compute the difference at
each time tbetween the each of the followers and the center of mass, for i= 1, ..., N
micro-satellites, given by
ˆ
xi(t) = xi(t)−m(t).(5.32)
Let F(X) represent the dynamics function corresponding to the Hill’s equations as ex-
plained in Section 5.3.1:
F(X) = V
Vr+ 2wJV.(5.33)
We place the center of mass m(t) initially on the halo-orbit and by linearizing F(X) with
the center of mass m(t), we get
−→
A(t) = δF
δX(m(t)).(5.34)
The goal is to formulate the dynamics of the follower micro-satellite with respect to the
halo-orbit and the center of mass being the follower of the imaginary leader on the halo-
orbit. The dynamics of the follower micro-satellite can be now formulated with the lin-
earization at every time, t, with the difference of each of the micro-satellite from the center
of mass and also using the dynamics of the center of mass of the formation, given by the
Equation 5.31.
We now know the trajectory of the leader as the imaginary leader is on the halo orbit.
We also know the position of each of the follower micro-satellite. We formulate the dy-
namics of the follower micro-satellite given the trajectory of the leader and the position of
the follower.
For each micro-satellite i, the dynamics of the follower micro-satellite is given as
˙
xi(t) = ˙m(t) + −→
A(t)ˆ
xi(t).(5.35)
80
5.5.2 Extension of the Formation Keeping Control
In the previous section, we have established the control which stabilizes a follower (center
of mass of the formation) on the halo orbit. The center of mass of the formation is made
the follower of the imaginary leader on the halo orbit. The center of mass follows the
leader but we have to establish the formation keeping control such that it stabilizes all the
micro-satellites to maintain a formation around its center or the center of mass at each
time. This would enable the entire formation of micro-satellites cruising in the proximity
of the halo orbit with its center of mass following an imaginary leader. Hence, we need
to formulate the formation keeping control to this case of the formation in the halo orbit
proximity. We need to extend the linear formation keeping control, discussed in the Chap-
ter 2, to the case of the proximity of the halo-orbit.
The linear system described in the Chapter 2, describes the dynamics of each of the micro-
satellites by
˙xi=Avehxi+Bvehui, i = 1, . . . , N. (5.36)
Let F(X) represent the dynamics function corresponding to the Hill’s equations:
F(X) = V
Vr+ 2wJV.(5.37)
The Aveh, in (5.36), is derived at each point of time by setting Aveh =−→
A(t) where −→
A(t) is
derived by linearizing F(X) with the center of mass m(t), given as,
−→
A(t) = δF
δX(m(t)).(5.38)
For the matrix Bveh in (5.36), the basic 2 ×2 matrix is given as
b=0
1,(5.39)
with Bveh =I3⊗b.
The communication between the micro-satellites is given by the Laplacian of the com-
munication graph described in the Chapter 2. Let the micro-satellites communicate in the
form of a complete graph. Let Si⊂ {1, . . . , N}\i, for the index i∈[1, ..., N], represent the
set of micro-satellites that the micro-satellite ican communicate with. The Laplacian is
defined as
Lij =
1 : i=j
−1
|Si|:j∈Si
0 : j /∈Si
(5.40)
81
The goal now, is to find the a decentralized feedback matrix, the formation keeping control,
given by Fveh. The basic feedback matrix of the formation keeping feedback control is given
by ˆ
f=f1f2,(5.41)
with Fveh =I3⊗ˆ
f.
For each λ, the eigenvalue of the communication graph L, the basic matrix
Aveh +λBvehFveh,(5.42)
is analyzed for stability (see Chapter 3). We determine the appropriate Fveh for which the
eigenvalues of the matrix given by (5.42), are in the left side of the complex plane for each
eigenvalue λof L.
Inorder to decide the spread of the formation of micro-satellites from the center of for-
mation, we define the reference vector. It is given by
h(t) =
h1(t)
.
.
.
hN(t)
.(5.43)
Having Fveh,Bveh and L, we determine the Kronecker products over Nmicro-satellites,
for each of these matrices. ˆ
B, ˆ
Fand ˆ
Lare computed by the Kronecker products over N
micro-satellites. This enables us to formulate the dynamics for the entire global forma-
tion. The difference of each follower micro-satellite from the center of mass is given by the
Equation 5.32.
We compute the control component for the formation keeping of all the Nmicro-satellites
in the vicinity of the halo orbit as
ˆ
Bˆ
Fˆ
L(ˆ
x−h).(5.44)
Hence, we have formulated in the formation keeping control component which keeps the
micro-satellites in a formation around its formation center which is the center of mass of
the formation.
5.5.3 Equation of Motion for Controlled Formation Flight Around
the Halo-orbit
We have established the leader follower control in the Section 5.5.1, with the center of
mass of the formation as the follower to an imaginary leader on the halo-orbit. In the
82
Section 5.5.2, we have established the formation keeping control for the formation of
micro-satellites in the halo-orbit proximity. This formation keeping control ensures the
micro-satellites centered around the center of mass of the formation. It is now required to
merge the two controls to enable the formation flight in the proximity of the halo-orbit. In
this section, we formulate the equation of motion for the controlled formation flight around
the halo-orbit.
For each micro-satellite i, the dynamics of the follower micro-satellite is given as
˙
xi(t) = ˙m(t) + −→
A(t)ˆ
xi(t).(5.45)
For each micro-satellite i, control component for the formation keeping is given as
(ˆ
Bˆ
Fˆ
L(ˆ
x−h))i.(5.46)
By merging the (5.45) and (5.46), we formulate the final dynamics of each of the follower
micro-satellites as
˙
xi(t) = ˙m(t) + −→
A(t)ˆ
xi(t)+(ˆ
Bˆ
Fˆ
L(ˆ
x−h))i.(5.47)
The above equation of motion is integrated over time for all the Nmicro-satellites.
5.6 Measure of the Deviation of the Formation
It is require to test the new control strategy for the formation flight of micro-satellites in
the proximity of the halo-orbit. To measure the error and the efficiency of the new strategy,
it is required to measure the deviation of the formation from the desired formation at every
time t. The h(t) is the reference vector which decides that the desired formation position,
i.e., the relative position of each of the micro-satellites at each time t.
The measure of deviation is computed as the deviation from the desired positions of the
micro-satellites given as The deviation of the formation is given as
d(t) = ||ˆ
x(t)−h(t)||2.(5.48)
The measure d(t) in (5.48), is the deviation determined by taking the second norm of the
difference from the desired positions, at each point of time. If the measured deviation, at
each point of time, is considerably small, then the new control strategy is quite efficient
in controlling the formation of micro-satellites in the proximity of the halo-orbit with the
center of mass of the formation on the halo-orbit.
5.6.1 Example
We consider an example of a formation consisting of six micro-satellites. We have to design
the new control for these micro-satellites in the proximity of the halo-orbit with the merger
83
of the leader follower control strategy and the decentralized formation keeping control. We
use the complete graph (shown in the Figure 3.1 in the Chapter 3) for the communication
topology between the micro-satellites. The Laplacian of the complete graph is incorporated
into the formation dynamics.
The goal is to place each of the micro-satellites in each of the corner of a regular hexagon
around the formation center of mass which is placed on the halo-orbit initially. The refer-
ence vector ensures that the micro-satellites are in a hexagon with the formation center of
mass being the center of the hexagon on the halo-orbit at initial time.
The formation keeping control is applied which ensures that the micro-satellites in the
hexagon are always centered around the formation center of mass. The formation cen-
ter of mass is the follower of an imaginary leader on the halo-orbit. Hence, both these
control strategies together applied result in the new control for the formation flight of
micro-satellites around the halo-orbit. Firstly, we study the need for the formation keep-
ing control, i.e., we include the leader follower control with the center of the formation
initially on the halo-orbit and following the imaginary leader on the halo-orbit, but there
is no binding coupling or the formation keeping control.
As there is no formation keeping control, the micro-satellites, after the initial time, do
not remain in a hexagon or be centered around the halo-orbit anymore. This can be ob-
served in the Figure 5.9, at some time t, the micro-satellite positions are captured and
indicated by a circle. The micro-satellites are no more in the hexagon position but ran-
domly scattered because of the non-existence of the formation keeping control. As we have
seen that without the formation keeping control, the micro-satellites do not maintain the
formation, we apply both the control strategies and hence, obtain the new control strat-
egy. Each of the micro-satellites follow the equation of motion given by (5.47). With the
equations integrated over Nvehicles, we perform the experiment to study the new control.
In the Figure 5.11, we see the new control strategy. The formation of micro-satellites
start in a hexagon with the formation center of mass on the halo-orbit. The formation
keeping control is applied along with the leader follower control for the formation cen-
ter of mass. We see a snapshot of the initial positions in the Figure 5.11, starting in a
hexagon position. After the application of the new control strategy, we observe the posi-
tions of the micro-satellites at a later time. We again look at a snapshot of the positions
of the micro-satellites at some time t. We observe in the Figure 5.12, that the new control
strategy has maintained the hexagon shape. The micro-satellites are still centered around
the formation center of mass. The new control strategy seems to maintain the hexagon
formation of micro-satellites in the proximity of the halo-orbit. The more accurate way
to determine whether the control strategy is efficient in the formation flight control in the
halo-orbit proximity is to measure the deviation of the formation from the desired position.
As described in the Section 5.6, the deviation is measured by considering the deviation
84
Figure 5.9: Positions of the micro-satellites at some time, without the formation keeping
control.
from the desired position indicated by the reference vector. We measure the deviation of
the formation from the hexagon formation at each point of time. This measure gives a clear
indication of the efficiency of the new control strategy. The deviation is given by (5.48).
Firstly, we observe the measure of deviation for the formation of six micro-satellites with
only the leader follower control applied on the formation center of mass and without the
formation keeping control. We observe in the Figure 5.13, that the deviation is consider-
ably high at some times, which indicate that the formation is not kept and the formation
is scattered from the desired position rendering it highly useless to perform any formation
duties.
We now measure the deviation for the new control strategy which involves both the control
strategies of leader follower control and the formation keeping control. In the Figure 5.14,
the deviation for the formation of six micro-satellites is measured for the new control strat-
egy, at each time. We see that, for a short time interval, the deviation is zero, which means
85
Figure 5.10: Trajectories of the micro-satellites with the merger of the controls.
86
Figure 5.11: Initial micro-satellite positions snapshot.
the formation is perfectly in the desired hexagon position throughout the time interval.
We measure the deviation for a longer interval of time and see that the new control
strategy is very efficient as the deviation is minimal magnitude. It can be seen in the
Figure 5.15 that the deviation is very small for a large time interval.
5.7 Stability Analysis
In the previous section, we have introduced a new control strategy for the formation flight
of micro-satellites in the proximity of the halo-orbit. It is required to perform the stability
analysis to determine whether the control strategy drives the formation to stability. The
Equation of motion for each micro-satellite is given from (5.47). The above equation of
motion is integrated over time for all the Nmicro-satellites.
The stability analysis is similar to the method presented in the Section 5.3.3. The study of
87
Figure 5.12: Micro-satellite positions snapshot at a later time.
88
Figure 5.13: Deviation measured without the formation keeping control.
the monodromy matrix from the integrated Equation 5.47 over Nmicro-satellites, deter-
mines the stability of the new control strategy. The floquet multipliers are the eigenvalues
of the monodromy matrix. If the magnitude of the floquet multipliers are equal to 1, then
the corresponding gain stabilizes the entire formation of micro-satellites in the proximity
of the halo-orbit.
We perform the stability analysis with the application of the new control to a forma-
tion of six micro-satellites. The Figure 5.16 shows the magnitude of the floquet multipliers
as we vary the gain parameter. We observe that for some gain values (for e.g., 0.7-0.9), all
the floquet multipliers have the magnitude 1. For such gain values, the control strategy
effectively stabilizes a formation of micro-satellites in the proximity of a halo-orbit.
89
Figure 5.14: Deviation measured for a short interval of time.
90
Figure 5.15: Deviation measured for a long interval of time.
91
Figure 5.16: Floquet multipliers for the varying gain.
92
5.8 Conclusion
In this chapter, we model a new control strategy for the controlled formation flight of micro-
satellites in the halo-orbit proximity. To develop this control strategy, we first describe the
linear modeling of the micro-satellites with the formation keeping control, in specific to the
halo-orbit scenario. Further, we describe the non-autonomous non-linear model using the
Hill’s equations. We develop this model and establish a leader-follower control strategy in
the halo-orbit proximity. Extending this leader-follower control strategy, we establish the
need for a merger of the two separate models: the linear formation keeping control and the
non-linear leader-follower control strategy.
We compute the center of mass of the formation and at the initial time, we place the
center of mass of the formation on the halo-orbit. We apply the leader-follower control
to the center of mass with the imaginary leader on the halo-orbit. Simultaneously, we
apply the formation keeping control, such that the micro-satellites are centered around the
formation center of mass. Hence, applying the two control strategies, we develop the new
equation of motion for the follower micro-satellites. We calculate the deviation measure
to determine the effectiveness of the control strategy in maintaining the desired positions
of the micro-satellites in the formation. We also perform the stability analysis by con-
sidering the monodromy matrix and its floquet multipliers. We illustrate the new control
strategy with an example of six micro-satellites in the controlled formation flight in the
halo-orbit proximity, with a hexagon shape around the center of mass, with each of the
micro-satellites on the corners of the hexagon.
93
Chapter 6
Micro-satellite Formation, a Mobile
Sensor Network in Space
6.1 Introduction
Till the previous chapters, we have formulated an efficient control law for a formation
of micro-satellites and validated it through some stability analysis. In this chapter, we
consider a different but an important dimension of micro-satellite formations. We shift
our view from the entire control theoretic perspective to an near-implementation computer
science point of view. The sensors present in each of the micro-satellites enable sens-
ing themselves. Each of the micro-satellites is also mounted with a telescope (sensor) to
gather data from the outer space. Hence, a micro-satellite formation results in an array of
space telescopes to scan the nearby universe looking for signs of life. One satellite acts as
a communications hub which aggregates the data and sends them to a receiving station.
Evidently, a micro-satellite formation can be regarded as a wireless sensor network in space.
The Autonomous Formation Flying Sensors (AFF) facilitate in bi-way sensing between
the micro-satellites. Firstly, we consider this sensor network and with the established con-
trol laws derive some additional factors for determining a good sensing structure. Further,
we consider a more realistic wireless sensor network formed by the sensing and the shar-
ing of the data by the telescopes. With this perspective, we also consider an important
aspect of formation flying which is larger number of the micro-satellites. The concept of
formation flying requires for the micro-satellites to be in close precise deterministic rela-
tive positions. The control laws which we developed in the previous chapters are more
suitable for a smaller number of micro-satellite as for a larger number it does not satisfy
the conditions of “closeness” as required for the successful mission. Additionally, when
the formation is required to be reconfigured because of obstacle avoidance or a change in
the mission goal, a lot of communication is required to coordinate the individual necessary
micro-satellite movements. Both aspects of maintaining close distances and communica-
tion overhead make traditional control laws for micro-satellite formations difficult to scale
94
for larger number of micro-satellites. In order to tackle these problems, we apply the con-
cept of clustering which is well-known in the sensor network community to the domain
of micro-satellite formations. Establishing a multi-level hierarchy of micro-satellite clus-
ters, each having a limited member count, allows us to extend the existing control laws
to a large number of micro-satellites in the formation without producing undesirable large
inter-satellite distances.
The contents of this chapter is organized as follows. In the Section 6.2, we give the basic
theory of considering the formation of micro-satellites as a wireless sensor network. In the
Section 6.2.1, we discuss the factors which are considered for an ideal sensing structure,
based on the derived control laws. Using the factors, we determine the robustness of the
sensing structures. To elaborate our points, we present an example with the formation of
six micro-satellites. Further, we consider the sensor network of the telescopes and their
data sharing. We present the shortcomings of the existing control laws over their handling
of the larger number of micro-satellites. Hence, we propose a multi-level hierarchical dis-
tributed algorithm based on some weighted metrics which are varying, for micro-satellite
clustering. The results presented from this Section 6.3, is an elaboration of our papers
[12, 13, 14, 15]. In the Section 6.5, we substantiate our algorithm with an example and
we also derive the comparisons to traditional greedy algorithms. We conclude this chapter
with the summary in the Section 6.6.
6.2 Formation of Micro-satellites as a Wireless Sensor
Network
A sensor network generally consists of a collection of wireless devices which are equipped
with one or multiple sensors to gather and aggregate some desired data. Examples that are
typically considered are in the field of distributed fire detection, animal observation, traffic
control, military, and so on. The micro-satellites are deployed to be a efficient formation
in space for various mission goals as described in earlier chapters. It should be noted that
a precise close distance have to be maintained between the micro-satellites to ensure the
high quality and also accuracy of the data aggregated through “optical interferometry” [45].
The micro-satellites are fitted with space telescopes [47], which gather data from the outer
space and aggregate it in the central hub satellite which transfers the data to a station in
the earth or to the International Space Station (ISS). This sensing of outer space data and
sharing among the micro-satellites allows us to clearly treat the formation of satellites as a
wireless network in space. This provides us with a novel application of the field of wireless
sensor networks. It is easier to maintain close and precise distance when the number of
micro-satellites are smaller. We first consider a small number of micro-satellites like in [46].
Each of the micro-satellites are identical in relation to their size, functionality and fuel
95
consumption. As introduced earlier, each of micro-satellite dynamics are given by
˙xi=Avehxi+Bvehui, i = 1, . . . , N, (6.1)
where xi∈R6is the state and ui∈R3is the control input. With the AFF sensors,
the micro-satellites perform inter-satellite sensing to share and pass on the inter-satellite
distances, control information, etc. The inter-micro-satellite sensing is depicted by a Lapla-
cian matrix. The formulation of the Laplacian matrix for a formation of Nmicro-satellites
is as follows. Let Si⊂ {1, . . . , N}\i, for the index i∈[1, ..., N], represent the set of
micro-satellites that the micro-satellite ican sense. The Laplacian of the formation of
micro-satellites should incorporate the sensing information into the matrix.
The Laplacian matrix of the sensing graph for a formation of Nmicro-satellites can be
given as
Lij =
1 : i=j
−1
|Si|:j∈Si
0 : j /∈Si
.(6.2)
From the above definition of the Laplacian of the sensing graph by (6.2), we get the
information about the sensing neighbours of each of the micro-satellites. The sensing
neighbours are just the neighbours in terms of sensing and are not physical state neighbours
or position neighbours in space. As elaborated in 2, taking the Kronecker products over
the Nvehicles, we get
˙x=ˆ
Ax +ˆ
Bˆ
Fˆ
L(x−h),(6.3)
where, ˆ
F=IN⊗Fveh is the decentralized feedback that can be found to stabilize the
micro-satellite formation. ˆ
A=IN⊗Aveh,ˆ
B=IN⊗Bveh and ˆ
L=L⊗In.
We just introduce this concept of sensing in terms of the control laws again to show
that the decentralized feedback stabilize the micro-satellite formations such that they are
aligned in a formation around the formation center. It is shown in 3, that as long as a
graph is connected, a stabilizing feedback can be found.
6.2.1 Factors for an Ideal Sensing Structure (Robustness)
We now define some factors for an ideal sensing structure from the possible connected sens-
ing graphs for some number of micro-satellites. In the outer-space environment where there
are a lot of floating particles of varying sizes and also because of the varying atmospheric
behaviours, it might result in a micro-satellite failure or isolation from the others in the
formation. We assume that this kind of failure is temporary and the lost micro-satellite can
be restored to the formation. This reconfiguration when a micro-satellite fails is studied
by defining “Robustness” which determines the ideal sensing factors.
96
6.2.1.1 Definitions
Robustness: The ability of the formation to gain back the stability when a node failure
occurs and distorts the formation.
Node recovery penalty (pi): When a micro-satellite node ifails, the penalty piof the
formation is defined as the minimum number of edges needed to be changed (added and/or
removed) in acquiring a new sensing structure of a regular degree plus an equivalent penalty
in transforming from that intermediate temporary structure back to the original structure
when the node recovers.
When a node fails, the edges or the sensing links associated with that node are lost. This
distorts the graph and creates irregularity in the sensing graph. Therefore, edges are added
and deleted to get to the next nearest regular graph which is the intermediate structure.
The intermediate structure is retained until the lost node recovers. Then, again the added
edges are removed and the recovered node links are automatically added to get to the
original structure. The total number of edges added and deleted, both from the original
to the intermediate and from the intermediate to the original structure gives the measure
of the node recovery penalty of that node. The node recovery penalty is given as:
pi= (a+d)+(a0+d0) (6.4)
where, arefers to the number of edges added or number of bi-way sensing channels added
with other nodes to get to intermediate structure.
drefers to the number of edges removed or bi-way sensing channels blocked to reach the
intermediate structure.
a0refers to the number of edges added or number of bi-way sensing channels added with
other nodes to get from the intermediate structure to the original structure.
d0refers to the number of edges removed or bi-way sensing channels blocked to reach from
the intermediate structure to the original.
On the r.h.s. of the (6.4), the first part is called the intermediate penalty (penalty to acquire
the intermediate structure) and the right part is called the restoration penalty (penalty to
restore the original structure of the formation from the intermediate structure). It is pos-
sible to introduce some factors to weight the intermediate and the restoration penalty
individually, but for now we consider an equal penalty weight for all added and deleted
edges in both transformation steps.
6.2.1.2 Example
Let us consider an example with six micro-satellites. This wireless sensor network is small
and the control laws used produces a hexagon formation for the optical interferometry. The
possible sensing topologies are given in Figure 3.1. As our important goal is to determine
a good sensing topology out of the five topologies. We illustrate the node penalty on the
3-regular-1 graph. We compute p1which is the node recovery penalty of node number
1 that is node 1 fails with all its links. This example is illustrated in Figure 6.1. The
97
Figure 6.1: For the 3-regular-1 sensing structure: computation of p1for node-1 failure.
Regularity p1p2p3p4p5p6R.f.
2-regular 2 2 2 2 2 2 12
3-regular -1 2 2 2 2 2 2 12
3-regular -2 6 6 6 6 6 6 36
4-regular 4 4 4 4 4 4 24
5-regular 0 0 0 0 0 0 0
Table 6.1: The R.f. of the sensing topologies.
intermediate structure is attained by deleting one edge (d= 1, a= 0) and the original
structure from the intermediate structure is attained by adding one edge (a0= 1, d0= 0).
The value we computed is just for one node failure.
Robustness factor (R.f.) The sum of the individual node recovery penalties of all Nnodes
is called the robustness factor of the formation, i.e.
R.f. =
N
X
i= 1
pi.(6.5)
Clearly, topologies with a small robustness factor are preferable. Thus, we compute the
R.f. by computing the sum of the node recovery penalties of all nodes. In the example from
the Figure 6.1, we can see that it is R.f. = 6∗p1= 12. We similarly compute the R.f. of all
sensing topologies depicted in Figure 6.1. The results are listed in Table 6.1. We decipher
from the Table 6.1, that concerning the Robustness, the complete graph(5-regular) is most
preferable. The 2-regular and 3-regular-1 sensing topologies closely follow behind. The
following remark is a simple but important observation.
Remark:
For a graph with Nvertices and a regular degree of N−1 it holds pi= 0 for all 1 ≤i≤N
and, consequently, R.f. = 0.
98
6.2.2 Intelligent Maneuvering
Intelligent maneuvering refers to the ability of the geometric formation deployed to effec-
tively maneuver avoiding incoming obstacles on its formation flight path. The collision
detector sensors sense the presence of any obstacle and immediately trigger a control op-
eration (to avoid the obstacle) which is mostly for the formation to disperse itself. Then
the formation has to intelligently maneuver back to the original geometric formation after
the obstacle is avoided. The sensing topology comes into play here to effectively avoid the
collision of the geometric formation with the obstacle. The higher the number of edges in
the sensing graph, the more control information between the micro-satellites is passed and
hence they can more effectively avoid obstacles.
In our example of six micro-satellites, in 2-regular the control information exists only
between the neighbors, and hence is more difficult to maneuver the formation to avoid
obstacles. The rest of the regular graphs are comparatively better as each micro-satellite
can pass control information to more than just one or two other micro-satellites.
6.2.3 Valency of every node
Definition: The valency of a node in a graph is defined as the sum of the edges joined to it.
Valency plays an important role in the sensing topology selection. The higher the va-
lency is, the higher is the hardware constraint on the node as there is more switching
between the satellites to be sensed and hence, more communication load on the processor.
The sensing between the nodes facilitates communication which is by message passing and
only one node can interact at a time even though it is bi-way communication. It is more
like half duplex communication. So, the higher the valency is, the higher is the complexity
involved in time-multiplexing for a fair distribution of messages. Hence, the valency of a
node makes it preferable to have 2-regular graph and, in contrast, less preferable to have
the 5-regular graph.
With the analysis of the stable sensing topologies with Robustness, Intelligent maneu-
vering and Valency, the determination of the more preferable structure can be formulated
as a multi-objective optimization problem. The choice of the ideal sensing topology for
the formation of micro-satellites also depends on the type of the mission and the mis-
sion goals. Since most of the missions emphasize mostly for extended mission life and an
efficient recovery from micro-satellite recovery, the most proferred criterion for an ideal
sensing structure would be the robustness. Hence, the complete sensing graph would be
ideal. But to balance the message overload and message complexity that is the valency
and the robustness, the 4 regular is an ideal choice for sensing structure.
99
6.3 Satellite Formation - A Wireless Sensor Network
of Space Telescopes
Till now we were concerned about the inter-micro-satellite sensing. One of the most diffi-
cult challenges when trying to take images of outer space is that minor objects are easily
outshined by bright stars in the vicinity by a factor of millions. A single micro-satellite
deployed to image the outer planets cannot overcome this problem because of its limited
telescope diameter. The Hubble Space Telescope, e.g., has only a telescope of diameter
2.3 meters, while approximately 30 meters would be required [45], which is far beyond the
current limits of technology. An efficient way of solving this issue is to exploit a technique
known as interferometry [46] where a number of small satellites with smaller telescopes
is used to combine the individual signals to mimic a much larger telescope. Each micro-
satellite is fitted with space telescopes (sensors) to enable sensing of photometric data from
outer space. Using optical interferometry, the data from the individual micro-satellite sen-
sors is collected at a designated micro-satellite which requires communication between the
micro-satellites, giving rise to a mobile sensor network in space. In order to gain most
accurate data, the micro-satellites must be kept in deterministic close relative positions,
otherwise, the aggregated data is invalidated.
Generally, the study of formation of satellites has been a hot topic of research in the
control and the engineering community. One of the most challenging issues is to keep
each of the satellites in the formation at a precise relative postion. Additionally, when
the formation is required to be reconfigured because of obstacle avoidance or a change in
the mission goal, a lot of communication is required to coordinate the individual neces-
sary satellite movements. Both aspects of maintaining close distances and communication
overhead make traditional control laws for satellite formations difficult to scale for larger
number of satellites.
Current control laws to establish reliable formations of micro-satellites face many chal-
lenges especially for larger numbers of micro-satellites. Many current control laws like
discussed in [10] employ the concept of a virtual center around which the formation is
aligned. This implies that when the number of satellites in the formation increases largely,
close relative distances are difficult to be maintained. The control laws established in pre-
vious chapters stabilize a small number (six) micro-satellites around a formation center.
For six micro-satellites, the ideal formation would be in the shape of a hexagon for the
perfect data aggregation quality. This is depicted in the snapshot of the simulation for
six micro-satellites (6.2) in Satellite Tool Kit (STK) from AGI Inc., USA., where the six
micro-satellites in a hexagon formation move in an orbit. The camera-angle suggests that
it is mounted on the communication-hub micro-satellite.
In order to tackle these problems, we apply the concept of clustering which is well-known in
the sensor network community to the domain of micro-satellite formations. Establishing a
100
Figure 6.2: The snapshot of the micro-satellite formation centered on the periodic orbit
using STK.
Figure 6.3: Hierarchically clustered vs. flat satellite formation (partly visible)
multi-level hierarchy of micro-satellite clusters, each having a limited member count, allows
us to extend the existing control laws to a large number of micro-satellites in the formation
without producing undesirable large inter micro-satellite distances. Figure 6.3 depicts the
idea of a hierarchically clustered micro-satellite formation (hexagon of hexagons) in con-
trast to a flat brute-force extension in a single level, leading to an inefficient micro-satellite
formation in an expanding circle. The application of clustering techniques to the domain of
micro-satellite formation is novel in itself. Still, we will show in this section, that existing
approaches for constructing the required multi-level hierarchy are not applicable to our
problem due to various limitations explained later.
6.3.1 Problem Description
Initially, after the micro-satellites are collectively launched from a spacecraft, they are scat-
tered in random positions. The desired goal is to arrange the formation into clusters with
at most cmax members. On the lowest level, a member is a single satellite, on higher levels,
clusters are composed of (at most cmax) lower level clusters. On one hand we have a larger
101
Figure 6.4: a) Desired Satellite Arrangement. b) Required Movements with Bad Leader.
c) Required Movements with Better Leader.
Figure 6.5: Required movements for different selected leaders. (a) initially requires least
movements on level 0, but consumes more movements than (c) overall.
number of micro-satellites in the formation and on the other hand we have a preferred
limited cmax due to the limited nature of existing control laws which generally results in a
hierarchy of multiple levels. For example, If we assume a cmax of 6 and a deployed volume
of 50 satellites, a hierarchy of dlog650e= 3 levels is required.
In order to establish the hierarchy, a cluster leader election must take place on each level.
The leader of a micro-satellite cluster is responsible to ensure the precise maintenance of the
required relative postions of the micro-satellites (or micro-satellite clusters) in its cluster
according to standard control laws. One of the features of micro-satellite formations is the
identical nature of all the micro-satellites in terms of size, capabilities, fuel, etc. Hence, the
most important criterion which qualifies a particular micro-satellite for a certain rank in
the hierarchy is the sum of necessary movements which is required for the basic formation
structure to be established. To understand the relationship between leadership election
and the implied sum of micro-satellite movements, consider the simple example presented
in Figure 6.4. Figure 6.4a) shows a sample formation of 9 satellites where the desired
ultimate configuration is a quadratic grid of micro-satellites and cmax = 3. To achieve
this, each cluster arranges its members in a line of three. The leader of each cluster is the
central micro-satellite of its line. On level 1, the leaders of level 0 are in turn aligned in
a horizontal line. Let us now consider an initial micro-satellite distribution as shown in
Figures 6.4(b) and 6.4(c).
Let us assume that the two right clusters (marked by the ellipsis) are already established,
102
only the leader election for the left three micro-satellites is still pending. When we make
the grey node leader as in 6.4(b), the necessary following micro-satellite movements are
depicted by the arrows. Specifically, a sum of 3 distance units would have to be travelled
to achieve the desired grid configuration presented in Figure 6.4(a). As opposed to that,
when we choose as in Figure 6.4(c), only one satellite would have to move. The sum of
distance units in this case would be only √22+ 12= 2.24. Hence, choosing as in Figure
6.4(c) is obviously preferable, since the amount of consumed fuel would be reduced. This
implies that the selection of leaders has to be done carefully based on the necessary sum of
micro-satellite movements (and thus fuel consumption) which that selection brings about.
Figure 6.5 illustrates that it is actually problematic to determine the optimal leader can-
didates for every level with only local knowledge. The only indicator which can be locally
computed by every candidate in the leader election process is the sum of movements of the
micro-satellites which the candidate would claim for its cluster provided it became leader in
the current level. The lesser this value, the more suitable is a micro-satellite for leadership.
However, the sum of movements implied by a particular constellation of leaders cannot be
foreseen for higher levels. The optimality of a selected constellation of leaders in terms of
micro-satellite movements on the leader level can only be evaluated once a set of leaders
is given.
Figure 6.5, like Figure 6.4, shows a two-level formation hierarchy with the two right
clusters already established. Traditional greedy algorithms to construct multi-level hi-
erarchies as known from the wireless network domain would compute the sum of move-
ments required to align the remaining three micro-satellites in a row for each of the three
leader candidates. For the leader configuration in Figure 6.5(a), this would amount to
√12+ 12= 1.41, for configuration 6.5(b), it is √12+ 12+ 1 = 2.41 and for configuration
6.5(c), it is √22+ 12= 2.24. Hence, existing approaches would greedily select the leader
as in configuration 6.5(a). However, as we have shown in Figure 6.4, this configuration is
inferior to 6.5(c), since 6.5(a) requires an additional shift of all cluster nodes to achieve
the desired grid configuration. Thus, although configuration 6.5(a) seems to be optimal
from a greedy perspective in level 0, it turns out to be suboptimal considering the sum
of movements on all levels. This means, that existing clustering approaches will lead to
suboptimal micro-satellite formations.
Regarding larger number of micro-satellites in the formation, our goal is to construct a
recursive dominating set topology based on weighted metrics, which can be reduced to the
well-known Maximum Weight Dominating Set Problem. Since this problem is NP-hard,
many algorithms have been published to approximate it. Examples for distributed algo-
rithms which try to present solutions in the domain of wireless networks can be found
in [77], [79], [80] and [81]. In all these works, only a two-level case is considered (where
the problem of unpredictable metric values is not relevant), the multi-level case is always
regarded to be just a recursive application of the leader election algorithm. We show in the
following section that this assumption cannot be generally made, and that our algorithms
103
yields better results in multilevel topologies with unpredictable metric values. To the best
of my knowledge, we are the first to address this problem.
We will refer to previous approaches like the ones cited above as the “greedy algorithms”.
This is just meant to be a simplification for saying that these algorithms, in each leader
election round (normally there is just one!), greedily determine the single best candidate
which is then allowed to compete for leadership in higher levels. As opposed to that, our
solution also allows suboptimal nodes to participate in the leader election in higher levels.
Even our algorithm is greedy in the sense that ultimately, the single node with the highest
utility is elected.
We generalize our problem to the case of constructing multi-level hierarchies of nodes
based on weighted metrics, whose values develop unpredictably in higher levels. Elabo-
rated generalized results are presented in another paper [14], of which this candidate is one
of the authors. We present in the following section some required important definitions for
the construction of our algorithm.
6.3.2 Definitions
We generalize our problem to the case of constructing multi-level hierarchies of nodes
based on weighted metrics, whose values develop unpredictably in higher levels. With
“unpredictability”, we do not refer to values of metrics which are unpredictable by their
very nature like, for example, the current link quality of the micro-satellite communication
channel. It is clear, that metrics with this kind of unpredictability should never form the
basis of leader election. Instead, we mean metrics like “sum of movements”, “number of
neighbors”, etc., which cannot be foreseen for higher levels as illustrated in Section 6.3.1.
We present a novel distributed algorithm to approximate an optimal recursive dominating
set based topology. Our algorithm introduces two fitness functions for every node, namely:
a utility and a utility estimate.
The utility describes the fitness of a particular node to become leader in the current level.
The utility estimate represents an “expected” fitness of a particular node to become leader
in some higher level. In the iterative leadership election process, nodes may advance to
the next round based on the utility estimate. The greedy nature of traditional algorithms
would discard a node just based on its current performance even though it might consider-
ably improve at a later level. The computation of the utility estimate and the introduction
of two special thresholds in our method prevent the elimination of such “good” leader
candidates which might outperform competing nodes later. The simulations in the end
clearly demonstrate the vast performance gains which can be achieved in comparison to
traditional algorithms.
We consider a graph with Llevels and Nnodes (micro-satellites). Let mil be a set of
Mmetrics which are used to calculate our hierarchy and let wil be a set of Mweights
104
that determine the importance of each metric. Here, i∈ {0, . . . , M −1}is the index of
our metrics and l∈ {0, . . . , L −1}represents the level. As said above, the values of our
weights will generally (albeit not necessarily) depend on the level l. Both weights and met-
rics are assumed to be normalized, i.e. ∀i∈ {0, . . . , M −1}, l ∈ {0, . . . , L −1}:wil, mil ∈
{0,...,1}. Additionally, the sum of weights for all metrics at any given level must be
1 : ∀l∈ {0, . . . , L −1}:Pi∈{0,...,M−1}wil = 1. The weighted sum of all metrics in level lis
called ml, given by
ml:= X
i∈{0,...,M−1}
mil wil.(6.6)
We also define the utility of a node as
sl:= 1
l+ 1 X
i∈{0,...,l}
mi,(6.7)
which represents a node’s applicability for leadership in level l. For every metric, we define
its average weighted metric value for a level las
aml:= X
i∈{0,...,M−1}
amil wil,(6.8)
where
amil := 1
l+ 1 X
k∈{0,...,l}
mik (6.9)
is its average value over the first llevels. Further, we define a utility estimate el, that is
used as a rough estimate for the weighted sum of all metrics of levels 0 to l0based on the
real metric values for levels 0 to land the average metric values for levels l+ 1 to l0as
el:= 1
l0+ 1(X
i∈{0,...,l}
mi+X
i∈{l+1,...,l0}
ami),(6.10)
where l0:= 1
2bL−1+ lcis the arithmetic mean of the highest and current level. The usage
of eland l0is described in the next section. Finally, we define the network utility as the
sum of utility values of all nodes. As such, it represents a measure for the performance of
the network in terms of the desired metrics.
6.4 Multi-level Multi-metric Topology Construction
In our topology construction approach, we consider a case where nodes do not move (much).
This is sufficient, because during the leader election process the micro-satellites do not have
to move and after that, once a stable formation is achieved, the relative micro-satellite
movements are negligible. The pseudo code for the parameterized topology construction
is given in Figure 6.6. The algorithm in Figure 6.6 is executed as PMLTC(0) locally by
105
every node in the network. In order to distinguish between variables of different nodes,
the variable names are extended by a superscript node variable. The expression en
l, for
example, stands for the variable elof node n, while eself
lstands for variable elfrom the
node that executes the algorithm itself. Starting from level 0, each node computes its
PMLTC(layer l)
1 if l≥Lend
2 broadcast EXPLORE message on layer l
3 wait until timeout t
4 broadcast eself
lon layer l
5 wait until timeout t
6 wait for 1 - eself
lseconds
7max := nwith en
lis greatest of all neighbors
8 if at most m TCFL messages have arrived so far
. and eself
l>(1 −d)emax
l
9 broadcast TCFL message on layer l
10 if no TCFL message has arrived so far
11 tlself
l:= 1
12 PMLTC(l+ 1)
13 for i=Ldownto 0
15 broadcast CFL message on layer l
16 establish links to the best cmax members of layer i
Figure 6.6: PMLTC: Parameterized Multi-level Topology Control Algorithm executed
locally by each micro-satellite as PMLTC(0)
applicability for leadership. If that is at most d% worse than that of the best candidate
and at most mcandidates are better, the node competes for leadership in the next higher
level.
Ultimately, the candidate with highest utility becomes leader in each level. Line 1 of
PMLTC asserts that the recursion ends. In line 2 and 3, self explores its neighborhood
(which is necessary to compute the metric values). It then selects the best cmax neighbors
in terms of the sum of movements which they had to make to establish a valid local forma-
tion if self became leader in the current level. In line 4 and 5, self broadcasts its utility
estimate to all nodes on the current level and collects utility estimate values broadcast by
other nodes as a reply. Then each node waits for a time which is at most one second long
and depends on the node’s utility estimate (line 6). The greater the estimate, the shorter
is the time that a node has to wait. This is to ensure that the nodes claim a temporary
leadership (TCFL) in the order of their decreasing utility estimate, i.e. suitability for lead-
ership. A node is only allowed to advance to the next leader election round if a maximum
of mnodes are better than itself and its utility estimate is not below the threshold d(line
8). We refer to mas the candidature threshold and das the confidence threshold. These
106
parameters can be tuned according to different requirements.
Generally, high values for mand dallow many nodes to advance leading to an increased
message overhead and a longer leadership election process on the one hand, but also a
higher overall network utility on the other hand since many nodes which might perform
poorly on lower levels still get the chance to outperform nodes at higher levels.
Note that the waiting phase in line 6 of PMLTC requires the participating nodes to
be synchronized. However, the synchronization accuracy is not an issue at all, since the
utility estimate values can be distributed over an arbitrarily large time interval, not nec-
essarily of one second length. What is more, PMLTC is just a (not necessarily optimal)
sample implementation of our proposed concept of using a utility estimate and a set of
thresholds to improve the network performance. Other algorithms which exploit the same
concept are also imaginable.
Once a node advances, it sends a temporary claim for leadership (a TCFL message) on
the current level (line 9). If it was the first to send such a message (i.e., it has received no
TCFL messages from nodes as none of them woke up earlier), it can safely assume that it
has the highest utility estimate among its level-lneighbors which is memorized by setting
the array tllto 1 (lines 10 and 11). Next, it competes on the next higher level (line 12).
Ultimately, starting from the the highest level where their tllflag is set to 1, the nodes send
final leadership claim (CFL) messages to their neighbors and establish links to the best
cmax members in each level (lines 12 to 16). What is not shown in the Figure 6.6 is that,
whenever a node receives a CFL message from a node with higher utility, it invalidates its
tllflag for that level.
6.5 Simulations
To substantiate the issues which we theoretically introduced in the previous sections and
to explore their relevance in practical scenarios we did extensive simulations using the sim-
ulator ShoX, which is particularly targeted towards wireless networks. ShoX is an event
based simulator which is developed on java platform and is extensively worked upon in
the University of Paderborn. It is particularly interesting to examine the relevance of the
case where a micro-satellite performs worse than its competitors in lower levels but has an
overall better utility in higher levels.
We compared PMLTC with a traditional approach of greedily taking the best candi-
date in each level. We used the two metrics “number of neighbors” (in layer l) and “sum
of movements” described in Section 6.3.1. We simulated PMLTC in networks with 50
micro-satellites which were randomly distributed over an area of 100 ×200 meters. To
simulate the most realistic scenario in a micro-satellite formation environment, we con-
sider a signal propagation model with varying disk radii. This is in accordance with the
107
surroundings of a micro-satellite formation which might encounter different signal propa-
gation characteristics depending on the position of the deployed orbit. In the Ionosphere
and Stratosphere, there might be a considerable signal attenuation while in outer space,
transmissions will be near loss-less. Our simulations clearly validate our propositions and
the suitability of our solutions.
The First simulation is to depict the clusterization of the micro-satellites using PMLTC
after they are intially deployed. In the Figure 6.7, 50 micro-satellites in their initial po-
sitions are shown in their clusters. The candidature threshold is relaxed so that all the
micro-satellites can raise to higher levels. Ultimately, the 50 micro-satellites land in a
distribution of 3 levels. There are 2 second level nodes namely 3 and 45, represented by
a triangle. The micro-satellites 3 and 45 claim level one micro-satellites represented by a
filled-in circle forming their respective clusters while claiming level 0 micro-satellites for
themselves. The level one micro-satellites again in turn claim lowest level zero micro-
satellites, differentiated by various shapes based on the level one clusters they belong to.
In the Figure 6.7, the clusterization is just of the initial positions. After the clusters
are formed using PMLTC, the control laws are deployed driving the micro-satellites to
their final cluster positions. The final micro-satellite cluster trajectories are shown in the
Figure 6.8. The curves in the trajectories are because of the linear control laws deployed.
We see that the level one nodes in the dark curves claim their level zero micro-satellites in
a hexagon joined by a small thin line to show the hexagon. The level one micro-satellites
are themselves in a hexagon. The final positions of the micro-satellites are shown in the
Figure 6.9. Here, the crosses denote the final positions of the micro-satellites which is
depicted as a hexagon of hexagons which was our desired goal. Many simulation runs are
performed for efficiency. The Figure 6.10 shows the final distribution of failed and successful
levels for the micro-satellites after the leader election process in a network of 50 micro-
satellites defined by PMLTC resulted by another simulation run. Each micro-satellite is
represented by a bar whose height depicts the final rank of the satellite in the hierarchy.
The grey parts of a bar represent those levels where a micro-satellite was outperformed
by some other micro-satellite in its vicinity, the dark parts stand for levels in which the
micro-satellite had the highest utility among its neighbors. To prevent a cluttered image,
the bars are only drawn up to the maximum level (rank) of the micro-satellite, all levels
above the bar top would theoretically have to be drawn grey.
As one can see clearly in Figure 6.10, more than one third of all leader micro-satellites
were not the best leader candidates on the lower levels. Node 48 was even worse than
its competitors in the first two levels, before it eventually improved. Consider the vast
performance loss that traditional algorithms produce in cases like this. Please note that
the final rank of the micro-satellites is based on the actual utility values, not on their
estimates. Besides, the utility and the utility estimate value represent the overall fitness of
a particular micro-satellite for leadership not only in one specific level, but also in all the
levels below. When we say that a micro-satellite eventually outperforms other satellites,
108
Figure 6.7: Multi-level clusters of 50 micro-satellites still in original positions. The first
number in the legend is the level, the second one is the leader ID for the particular shape.
this implies that its overall fitness has surpassed that of its rivals, not just its fitness for
one particular higher level.
Following the discussion in the previous section, it is not surprising that PMLTC leads to
a considerable network utility improvement compared to greedy algorithms. We simulated
a greedy election based algorithm and compared its performance to that of an “optimal”
greedy algorithm where all the micro-satellites are allowed to advance up to the highest
level in order to decide their final rank. Actually, the former is just a specialization of the
approach presented in this section. In the greedy variant, only the best leader candidate
is permitted to advance to the next election round which is nothing but PMLTC with
m= 1. In the optimal greedy case, mwould be ∞and dwould be 1.
In the Figure 6.11, we show the network utility achieved by our algorithm in compari-
son to a greedy algorithm. As explained above the greedy case is achieved such that only
109
Figure 6.8: The trajectories followed by each of the 50 micro-satellite to attain their final
positions in the formation.
one micro-satellite is allowed to go to higher level based on the utility values. It is clearly
shown that this achieves a sub-optimal network utility in comparison to our algorithm as it
blocks out some of the micro-satellites which might perform better at a later stage. In the
6.11, the first three seconds are utilized for the election phase among all the micro-satellites
and hence the large variance and then later it settles down.
6.6 Conclusion
In this chapter, we introduce a very novel concept of treating a formation of micro-satellites
in space as a wireless sensor network. This is an unexplored application area of the sensor
network community which has already established a wide application domain. We first dis-
cuss the inter-micro-satellite sensing using the AFF sensors. We determine the robustness
factors and introduce various factors which determine the ideal sensing structure for the
formation of these micro-satellites. The various concepts introduced are then elaborated u
110
Figure 6.9: The final position and the formation for the 50 micro-satellites clustered using
PMLTC (Hexagon of hexagons).
111
Figure 6.10: The distribution of failed and successful levels for the 50 micro-satellites.
Figure 6.11: Network utility of PMLTC compared to a greedy approach. The first 3
seconds represent the election phase after which the utility settles.
112
sing an example of six micro-satellite formation.
Further, we discuss the sensor network resulting through the space telescopes mounted
on each of the micro-satellites to gather data from the outer space. We then consider the
problem of scaling of the existing control laws to a larger number of micro-satellites in the
formation. We emphasize the requirement for the micro-satellites to maintain precise and
close distances in spite of the larger number of the micro-satellites. To deal with this re-
quirement, we introduce the concept of hierarchical clustering and we present a multi-level
multi-metric topology construction algorithm for varying metrics.
We elaborate and substantiate our results with an example of 50 micro-satellites. We
compare the performance of our algorithm called the PMLTC to a traditional greedy
approach.
113
Chapter 7
Conclusion
During this thesis, we have studied the concept of formation of micro-satellites at various
levels. Our main objectives were to develop efficient control laws for a formation of micro-
satellite in a halo-orbit proximity, analyze their stability and also examine their ability to
scale for a large number of micro-satellites in the formation. In the Section 7.1, we present
the short form of the contributions in this thesis. Further in this section, we present some
possible future extensions and ideas for the existing work.
7.1 Summary of our contributions and future work
In this thesis, we consider the formation of micro-satellites and develop control laws for
efficiently maneuvering them from two points of view. We start with the linear control
laws to elaborate the concept of stability. We discuss the modeling u sing the examples of
three, four, five and six micro-satellites (Chapter 2).
We use this linear model and establish the importance of considering the communication
topologies in the stability of the formation of micro-satellites. We establish the role of the
eigenvlaues of the Laplacian matrix and their importance in the non-autonomous setting
of the formation. We compute and compare the eigenvalues of the Laplacian matrices for
various communication topologies. We elaborate the results with an example (Chapter 3).
Further, we extend the existing stability radius results to the formation of micro-satellites.
We accordingly modify the definition of the stability radius for the formation. We use
the extended particular concept of structured stability radius. We define a new structured
stability radius for the formation of micro-satellites. We compute the structured stability
radius for an example of six micro-satellites (Chapter 4).
We develop a non-linear control law by combining the previously established linear center-
ing control law and the non-linear leader follower control law. We derive the new control
and observe that the formation of micro-satellites can be initially centered in a hexagon
114
from on a point on a halo-orbit. We perform extensive experiments to show that the devia-
tion of the formation of the micro-satelllites is in fact negligible emphasizing the efficiency
of the derived new control. The stability of the formation established by the new control
law is also introduced and studied by the properties of the monodromy matrix. We can
see that our derived control law can stabilize the formation of micro-satellited around a
halo-orbit (Chapter 5).
We now take an interesting implementative perspective of the formation of micro-satellites.
We introduce the novel application of sensor networks - formation of micro-satellites. We
establish the formation of micro-satellites in space as a wireless sensor network gathering,
sharing and relaying data. We consider the inter-micro-satellite sensing and define the
ideal sensing structure using some introduced concepts. We elaborate the results with an
example of sic micro-satellites. We also study the impact of the increase of number of
micro-satellites in the formation and the need to maintain close distances for the optical
interferometry. Hence, we develop a distributed multi-level hierarchical multi-metric algo-
rithm for the clustering of the micro-satellites. We study the impact of the new algorithm
and compare it to the traditional greedy algorithm in terms of performance and network
utility. We hence solve the scalability issue for the traditional control laws which are ap-
plicable for a smaller number of micro-satellites (Chapter 6).
This thesis has various leads and questions to consider in the future. The developed
control law has to be incorporated with various reconfiguration strategies. The forma-
tion of micro-satellites has to be considered for maneuvers which involve splitting and
recombination to avoid an on-coming collision. Inter-microsatellite collision avoidance al-
gorithms have to incorporated in to the new control law. With respect to the hierarchical
clustering, a dynamic approach can be considered in the future where the micro-satellites
are really mobile (fast) to achieve some scientific purposes. We also have to extend the
linear control laws for final formation clustering to the non-linear real world scenario after
the initial clustering of the micro-satellites.
115
List of Figures
1.1 Galileo satellite launched in 1989. . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Formationofbirds................................ 14
1.3 Formation of UAV’s and AUV’s. . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Formation of micro-satellites in space. . . . . . . . . . . . . . . . . . . . . . 16
1.5 An artist’s conception of TPF (left) and DARWIN (right) . . . . . . . . . 18
2.1 Formation Acquisition of Three Micro-satellites. . . . . . . . . . . . . . . . 32
2.2 Formation Acquisition for Four Micro-satellites. . . . . . . . . . . . . . . . 33
2.3 Formation Acquisition for Five Micro-satellites. . . . . . . . . . . . . . . . 34
2.4 All non-isomorphic connected regular undirected graphs with six nodes. . . 35
2.5 Formation Acquisition of Six Micro-satellites. . . . . . . . . . . . . . . . . 36
2.6 Eigenvalue Placement for the Matrix Representing the Formation of Six
Micro-satellites.................................. 37
2.7 Relative Velocities of the Six Micro-satellites. . . . . . . . . . . . . . . . . 38
2.8 Reference Vector with respect to the Formation Center. . . . . . . . . . . . 38
3.1 All non-isomorphic connected regular undirected graphs with six nodes (Orig-
inal topologies without any communication link failures). . . . . . . . . . . 46
3.2 The plot of normalized λmin........................... 47
4.1 All non-isomorphic connected regular undirected graphs with six nodes (Orig-
inal topologies without any communication link failures). . . . . . . . . . . 57
4.2 The stability radius for the original communication topologies (unstructured
stabilityradius).................................. 58
4.3 The structured stability radius for the perturbed communication graphs. . 59
4.4 The plot of normalized λmin........................... 61
5.1 The relative trajectories of the six micro-satellites driven into a circular
formation by the decentralized formation keeping control. . . . . . . . . . . 67
5.2 The relative trajectories of the six micro-satellites diverging from their initial
positions. .................................... 68
5.3 The relative trajectories of the six micro-satellites diverging from the initial
points and not into a formation. . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 Hill’s model of three body problem. . . . . . . . . . . . . . . . . . . . . . . 71
116
5.5 Leader Follower Micro-satellite Trajectories . . . . . . . . . . . . . . . . . . 74
5.6 Floquet Multipliers with Varying Gain . . . . . . . . . . . . . . . . . . . . 76
5.7 Floquet Multipliers with Varying Gain . . . . . . . . . . . . . . . . . . . . 77
5.8 single Leader Multiple-follower Micro-satellite Trajectories . . . . . . . . . 78
5.9 Positions of the micro-satellites at some time, without the formation keeping
control. ..................................... 85
5.10 Trajectories of the micro-satellites with the merger of the controls. . . . . . 86
5.11 Initial micro-satellite positions snapshot. . . . . . . . . . . . . . . . . . . . 87
5.12 Micro-satellite positions snapshot at a later time. . . . . . . . . . . . . . . 88
5.13 Deviation measured without the formation keeping control. . . . . . . . . . 89
5.14 Deviation measured for a short interval of time. . . . . . . . . . . . . . . . 90
5.15 Deviation measured for a long interval of time. . . . . . . . . . . . . . . . . 91
5.16 Floquet multipliers for the varying gain. . . . . . . . . . . . . . . . . . . . 92
6.1 For the 3-regular-1 sensing structure: computation of p1for node-1 failure. 98
6.2 The snapshot of the micro-satellite formation centered on the periodic orbit
usingSTK. ................................... 101
6.3 Hierarchically clustered vs. flat satellite formation (partly visible) . . . . . 101
6.4 a) Desired Satellite Arrangement. b) Required Movements with Bad Leader.
c) Required Movements with Better Leader. . . . . . . . . . . . . . . . . . 102
6.5 Required movements for different selected leaders. (a) initially requires least
movements on level 0, but consumes more movements than (c) overall. . . 102
6.6 PMLTC: Parameterized Multi-level Topology Control Algorithm executed
locally by each micro-satellite as PMLTC(0) ................ 106
6.7 Multi-level clusters of 50 micro-satellites still in original positions. The first
number in the legend is the level, the second one is the leader ID for the
particularshape. ................................ 109
6.8 The trajectories followed by each of the 50 micro-satellite to attain their
final positions in the formation. . . . . . . . . . . . . . . . . . . . . . . . . 110
6.9 The final position and the formation for the 50 micro-satellites clustered
using PMLTC (Hexagon of hexagons). . . . . . . . . . . . . . . . . . . . . 111
6.10 The distribution of failed and successful levels for the 50 micro-satellites. . 112
6.11 Network utility of PMLTC compared to a greedy approach. The first 3
seconds represent the election phase after which the utility settles. . . . . . 112
117
List of Tables
3.1 The minimal nonzero eigenvalues for the communication graphs under con-
sideration in dependence on the number of edge failures. . . . . . . . . . . 46
4.1 The stability radius for the original communication graphs under consider-
ation........................................ 57
4.2 The structured stability radius for the communication graphs under consid-
eration, with the perturbation of the failure of some number of edges. . . . 58
6.1 The R.f. of the sensing topologies. . . . . . . . . . . . . . . . . . . . . . . 98
118
Bibliography
[1] M. Mayor and D. Queloz. A Jupiter-Mass Companion to a Solar-Type Star. Nature,
1995, Vol.378, p 355.
[2] G. W. Marcy and R. P. Butler. A Planetary Companion to 70 Virginis. Astrophysics
Journal Letters, 1996, 464, L147.
[3] T. B. Curtin, J. G. Bellingham, J. Catipovic, and D. Webb. Autonomous oceanographic
sampling networks. Oceanography, 1993, 6:86-94.
[4] A. J. Healey. Application of formation control for multi-vehicle robotic minesweeping.
In the Proceedings of the 40th IEEE Conference on Decision and Control, 2001.
[5] T. W. Mclain and R. W. Beard. Trajectory planning for coordinated rendezvous of
unmanned air vehicles. In the Proceedings of the AIAA Conference on Guidance,
Navigation, and Control, 2000.
[6] T. W. Mclain, P. R. Chandler, and M. Pachter. A decomposition strategy for optimal
coordination of unmanned air vehicles. In the Proceedings of the American Control
Conference, 2000, 369-373.
[7] K. Lau et al. An innovative deep space application of GPS technology for formation
flying spacecraft. In the Proceedings of the AIAA Conference on Guidance, Navigation,
and Control, 1996, AIAA 96-3819.
[8] R. N. Bracewell, and R. H. McPhie. Searching for nonsolar plantes. Icarus 38, 1979,
136-147.
[9] A. Karlsson, and B. Mennesson. The Robin Laurence nulling interferometers. SPIE
4006, 2000, 871-880.
[10] A. Krishnamurthy and R. Preis Satellite Formation, a Mobile Sensor Network in
Space. In 5th IEEE International Workshop on Algorithms for Wireless, Mobile, Ad
Hoc and Sensor Networks in conjunction with IPDPS 2005. Denver, Colorado, April
4-8, 2005.
119
[11] M. Dellnitz, O. Junge, A. Krishnamurthy, and R. Preis. Stable Communication
Topologies of a Formation of Satellites. In 4th AIAA International Workshop on Satel-
lite Constellations and Formation Flying, INPE Space centre, Brazil, Feb 2005.
[12] A. Krishnamurthy, and J. Lessmann. Hierarchical Clustering for a Sensor Network
of Satellites in Space. In IEEE International Conference on Sensor Technologies and
Applications-SENSORCOMM 2007. Valencia, Spain, Oct 2007.
[13] J. Lessmann and A. Krishnamurthy. Parameterized Hierarchical Layer Topology Con-
struction for Wireless Networks. The Second IEEE International Conference on Systems
and Networks Communications (ICSNC 2007), French Riviera, France. August 25-31,
2007.
[14] J. Lessmann and A. Krishnamurthy. Distributed Construction of a Multi-level Topol-
ogy with Unpredictable Metric Values for Wireless Networks. In 3rd IEEE Interna-
tional Conference on Wireless and Mobile Computing, Networking and Communica-
tions (WiMob 2007), New York, U.S.A. Oct 8-10 2007.
[15] J. Lessmann and A. Krishnamurthy. Applying Multi-level Topology Control to Satel-
lite Formations - A Mobile Sensor Network in Space. The Ninth IFIP/IEEE Interna-
tional Conference on Mobile and Wireless Communications Networks,(MWCN 2007).
Cork, Ireland. Sept 19-21, 2007.
[16] M. Dellnitz, O. Junge, A. Krishnamurthy, S. Ober-Blbaum, K. Padberg, and R. Preis.
Efficient Control of Formation Flying Spacecraft In New Trends in Parallel and Dis-
tributed Computing, Heinz Nixdorf Institut Verlagsschriftenreihe 181, pp. 235-247,
2006.
[17] M. Dellnitz, O. Junge, A. Krishnamurthy, and R. Preis. Stable Communication
Topologies of a Formation of Satellites. Nonlinear Dynamics and Systems Theory,
4(6), pp.337-342, 2006.
[18] O. Absil. Nulling Interferometry with DARWIN: Detection and Characterization of
Earth-like Exoplanets. University de Liege, 2000.
[19] J. M. Mariotti and B. Mennesson. Array configurations for space infrared nulling
interferometer dedicated to the search for Earth-like extrasolar planets. Icarus 128,
1997, 202-212.
[20] R. Burns et al. TechSat21: Formation design, control, and simulation. In the Pro-
ceedings of the IEEE Aerospace Conference, 2000, 19-25.
[21] Jet Propulsion Laboratory. TPF-Terrestrial Planet Finder. Origin of Stars, Planets,
and Life, ed. by C. A. Beichman, N. .J. Woolf, and C. A. Lindensmith, JPL Publication
99-3, U.S. Government Printing Office, Washington, D.C., 1999.
120
[22] Jet Propulsion Laboratory. Summary Report on Architecture Studies for the Ter-
restrial Planet Finder, ed. by C. A. Beichman, D. Coulter, C. A. Lindensmith, and
P. Lawson, JPL Publication 02-011, U.S. Government Printing Office, Washington,
D.C., 2002.
[23] Jet Propulsion Laboratory. Technology Plan for the Terrestrial Planet Finder, ed. by
C. A. Lindensmith, JPL Publication 03-007, U.S. Government Printing Office, Wash-
ington, D.C., 2003.
[24] Jet Propulsion Laboratory. Terrestrial Planet Finder Roadmap for Precursor Sci-
ence, S. C. Unwin, P. Lawson, and C. A. Beichman, JPL Publication 03-XXX, U.S.
Government Printing Office, Washington, D.C., 2003.
[25] DARWIN: The InfraRed Space Interferometer. Concept and Feasibility Report, ESA-
Sci (200) 12, 2000.
[26] Y. U. Cao, A. S. Fukunaga, and A. B. Kahng. Cooperative mobile robotics: An-
tecedents and directions. Autonomous robots, 1997, 4:7-27.
[27] J. Desai, J. P. Ostrowski, and V. Kumar. Modeling and control of formations of
nonholonomic mobile robots. IEEE Transactions on Robotics and Automations, 2001,
17(6):905-908.
[28] E. E. N. Macau Exploiting Unstable Periodic Orbits of a Chaotic Invariant Set for
Spacecraft Control. Celestial Mechanics and Dynamical Astronomy. 87: 291-305, 2003.
[29] J. M. Petit and M. Henon On a Cantor structure in a satellite scattering problem.
Dynamics and Stochastic Process, Springer Verlag, Berlin, 1989.
[30] A. Okubo. Dynamical aspects of animal grouping: swarms, schools, flocks and herds.
Advances in Biophysics, 22:1-94, 1986.
[31] P. Orgen, M. Egerstedt, and X. Hu. A control lyapunov function approach to multi-
agent coordination. In IEEE IRCA, 2003.
[32] M. Egerstedt, X. Hu, and A. Stotsky. Control of mobile platforms using virtual vehicle
approach. IEEE Transactions on Automatic Control, 2001, 46(11):1777-1782.
[33] N. E. Leonard and E. Fiorelli. Virtual leaders, artificial potentials and coordinated
control of groups. In the Proceedings of the 40th IEEE Conference on Decision and
Control, 2001, 2968-2973.
[34] B. Collaudin and N. Rando. Cryogenics in space: a review of the missions and of the
technologies. Cryogenics, 2000, 40:797-819.
[35] J. F. Heagy, T. L. Carroll, and L. M. Pecora. Synchronous chaos in coupled oscillator
systems. Physical Review E, 1994, E, 50(3):1874-1885.
121
[36] D. J. Scheeres, F. Y. Hsiao, and N. X. Vinh. Stabilizing Motion Relative to an Unstable
Orbit: Applications to Spacecraft Formation Flight. Journal of Guidance, Control, and
Dynamics, Jan-Feb 2003, Vol.26, No.1.
[37] A. Karlsson. The technology of DARWIN. In Towards Other Earths, vol. SP-539.
ESA, 2003.
[38] A. Karlsson et al. DARWIN: The InfraRed Space Interferometer. Concept and Fea-
sibility Study Report, ESA-SCI, 2002.
[39] G. Rousset. Wave-front sensors. In Adaptive Optics in Astronomy, ed. by F. Roddier,
chap. 5, 91-130, Cambridge University Press, Cambridge, 1999.
[40] F. R. K. C. Chung. Spectral Graph Theory. Regional Conference Series in Mathe-
matics, American Mathematical Society, vol 92, 1997.
[41] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal,
1973, 23:298-305.
[42] R. Merris. Laplacian matrices of graphs: A survey. Linear Algebra and its Applica-
tions, 1994, 197,198:143-176.
[43] R. Merris. A survey of graph Laplacians. Linear and Multilinear Algebra, 39:19-31,
1995.
[44] R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1985.
[45] http://sci.esa.int/science-e/www/area/index.cfm?fareaid=28
[46] http://www.terrestrial-planet-finder.com/
[47] F. Bauer, K. Hartman, J. How, J. Bristow, D. Weidow, and F. Busse. Enabling
spacecraft formation flying through spaceborne (GPS) and enhanced automation tech-
nologies. In ION-GPS Conference 1999, pages 369-383.
[48] P. Bhatta and N.E. Leonard. Stabilization and Coordination of Underwater Gliders.
In the Proceedings of the 41st IEEE Conference on Decision and Control, 2002, pages
2081-2086.
[49] A.J. Fax. Optimal and Cooperative Control of Vehicle Formations. Ph.D. thesis,
California Institute of Technology, 2002.
[50] A.J. Fax and R.M. Murray. Graph laplacians and stabilization of vehicle formations.
Technical report, California Institute of Technology, CDS, 2001.
[51] N. E. Leonard and P. Orgen. Obstacle avoidance in formation. In IEEE IRCA, 2003.
122
[52] R. O. Saber and R. M. Murray. Consensus protocols for networks of dynamic agents.
In Proceedings of American Control Conference, 2003.
[53] C. Van Loan. How near is a stable matrix to an unstable matrix. Contemporary
Mathematics, 1985, 465-478.
[54] L. Qui and E. J. Davison. New perturbation bounds for the robust stability of linear
state space models. In Proceedings of 25th Conference on Decision and Control, Athens,
Greece, 1986, 751-755.
[55] J. M. Martin and G. A. Hewer. Smallest destabilizing perturbation for linear systems.
International Journal on Control .45, 1987, 1495-1504.
[56] R. M. Biernacki, H. Hwang, and S. P. Bhattacharyya. Robust stability with structured
real parameter perturbations. In IEEE Transactions on Automation and Control, AC-
32, 1987, 495-506.
[57] D. Hinrichsen, A. Ilchmann, and A.J. Pritchard. Robustness of stability of time-
varying systems. Journal of Differential Equations.82, 1989, 219-250.
[58] D. Hinrichsen and M. Motscha. Optimization problems of linear state space systems.
In Approximation and Optimization, LN Mathematics Springer Verlag, 1988, 59-78.
[59] D. Hinrichsen and A.J. Pritchard. An application of state space methods to obtain ex-
plicit formulae for robustness measures of polynomials. In Robustness in Identification
and Control, Torino, 1988.
[60] A.J. Pritchard and S. Townley. Robustness of linear systems. In Journal of Differntial
Equations-77, 1989, 254-286.
[61] D. Hinrichsen and A.J. Pritchard. Stability radius for structured perturbations and
the algebraic Riccati equation. Systems and Control Letters, 8:105–113, 1986.
[62] D. Hinrichsen and A.J. Pritchard. Stability radii of linear systems. Systems and
Control Letters, 7:1–10, 1986.
[63] M. Olsson and S. Lloyd. Nelder-Mead Simplex Procedure For Function Minimization.
Technometrics, v 17, n 1, Feb, 1975, p 45-51, Compendex.
[64] M. Henon and J.M Petit. Series Expansions for Encounter-Type solutions of Hill’s
Problem. Celestial Mechanics and Dynamical Astronomy, 38:No.1, 67–100, 1986.
[65] S. D. Ross. Cylindrical Manifolds and tube dynamics in the restricted three-body
problem. Ph.D. thesis, California Institute of Technology, 2004.
[66] O. Junge, J. Levenhagen , A. Seifried, and M. Dellnitz. Identification of Halo orbits for
energy efficient formation flying. In the Proceedings of the International Symposium
Formation Flying, Toulouse, 2002.
123
[67] A. Howard, M.J. Mataric, and G.S. Sukhatme. Mobile Sensor Network Deployment
using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem.
In Distributed Autonomous Robotic Systems, pages 299–308, H. Asama and T. Arai
and T. Fukuda and T. Hasegawa (eds), Springer, 2002
[68] G. Lafferriere, J. Caughman, and A. Williams. Graph Theoretic Methods in the
Stability of Vehicle Formations. In the Proceedings of the American Control Conference,
pages 3729–3724, July 2004.
[69] A. Williams, G. Lafferriere, J. J. P. Veerman. Stable motions of vehicle formations.
In Proceedings of IEEE, 2005.
[70] D. Lee and P.Y. Li. Formation and Maneuver Control of Multiple Spacecraft. In IEEE
American Control Conference, Denver, Colorado, June 2003.
[71] M. Meshabi and F.Y. Hadeagh. Graphs, Formation Flying Control of Multiple Space-
craft Matrix Inequalities: Graph Theoretic Properties and Switching Schemes. In AIAA
Guidance, Navigation and Control Conference, Boston, August 1999.
[72] R. Preis. Analyses and Design of Efficient Graph Partitioning Methods. Ph.D. thesis,
University of Paderborn, Germany, 2000.
[73] G. Purcell, D. Kuang, S. Lichten, S.-C. Wu, and L. Young. Autonomous Formation
Flyer (AFF) Sensor Technology Development, Technical report, NASA, 1998.
[74] W. Ren and R.W. Beard. Virtual Structure Based Spacecraft Formation Control
With Formation Feedback. In AIAA Guidance, Navigation and Control Conference
and Exhibit, Monterey, California, August 2002.
[75] A. Robertson, G. Inalhan, and J.P. How. Formation Control Strategies for a Separated
Spacecraft Interferometer. In American Control Conference, San Diego, CA, June 1999.
[76] P.A. Stadler, A.A. Chacos, R.J. Heins, G.T. Moore, E.A. Olsen, M.S. Asher, and
J.O. Bristow. Confluence of navigation, communication, and control in distributed
spacecraft systems. In IEEE Aerospace Conference, volume 2, pages 563–578, 2001.
[77] S. Basagni, I. Chlamtac and A. Farago. A Generalized Clustering Algorithm for
Peer-to-Peer Networks. In Proc. of The Workshop on Algorithmic Aspects of Commu-
nication, Bologna, Italy, July 1997.
[78] J. Elson et al. Fine-Grained Network Time Synchronization using Reference Broad-
casts. In Proc. of the Fifth Symposium on Operating Systems Design and Implemen-
tation, Boston, MA, Dec 2002.
[79] S. Basagni et al. Mobility-adaptive protocols for managing large ad hoc networks. In
Proc. IEEE International Conference on Communications 2002, pp. 1539-1543, 2002.
124
[80] S. Basagni. Finding a maximal weighted independent set in wireless networks. In
Telecommunication Systems, Special Issue on Mobile Computing and Wireless Net-
works, 18:155-168, September 2001.
[81] M. G. J. Wu and I. Stojmenovic. On calculating power-aware connected dominating
sets for efficient routing in ad hoc wireless networks. In Proc. International Conference
on Parallel Processing, pp. 346-354, 2002.
[82] H. Nijmeijer and A. van der Schaft. Nonlinear Dynamical Control Systems. Springer-
Verlag, New York, NY, 1990.
[83] M. B. Milam, R. Franz, and R. M. Murray. Real-time constrained trajectory gener-
ation applied to a flight control experiment. In Proceedings of the 15th IFAC World
Congress, 2002.
[84] R. Horn and C. Johnson Matrix Analysis. Cambridge University Press, 1985.
[85] R. Diestel. Graph Theory. Graduate Texts in Mathematics, volume 173, Springer-
Verlag, 1997.
[86] M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal,
23:298-305, 1973.
[87] K. Zhou and J. Doyle. Essentials of Robust Control. Prentice Hall, New Jersey, 1998.
[88] D. Yanakiev and Ioanns Kanellakopoulos. A simplified framework for string stability
analysis in AHS. In Proceedings of 13th IFAC World Congress, vol. Q, pages 177-182,
San Francisco, 1996.
[89] E. M. C. Kong. Optimal trajectories and optimal design for separated spacecraft
interferometry. Masters Thesis, MIT, 1999.
[90] K. Padberg. Numerical Analysis of Transport in Dynamical Systems. PhD Thesis,
University of Paderborn, Germany, 2005.
[91] C. Marchal. The Three-Body Problem. Elsevier, New York, 1990, p.63.
[92] J. M. A. Danby. Fundamentals of Celestial Mechanics. 2nd Ed., Willman-Bell, Rich-
mond, VA, 1992, pp. 343-346.
[93] D. J. Scheeres, M. D. Guman, B. F. Villac. Stability analysis of Planetary Satel-
lite Orbiters: Application to the Europa Orbiter. Journal of Guidance, Control, and
Dynamics, Vol.24, No.4, July-August, 2001.
125
