(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
I Context
1 Introduction
1.1 Robot Networks in Dynamic Environments
1.2 Contributions and Outline of the Thesis
2 Dynamic Graphs
2.1 State of the Art
2.1.1 Repesentations of Dynamic Graphs
2.1.2 Classification of Casteigts et al. [40, 38]
2.2 Model
3 Robots
3.1 State of the Art
3.1.1 Computational Model
3.1.2 Environments
3.1.3 Robot Capacities
3.1.4 Classical Problems
3.2 Model
3.2.1 Assumptions
3.2.2 Execution of an Algorithm
3.2.3 Hierarchy of Models
3.2.4 Towers
4 Satisfiability and Impossibility Results
4.1 Implications of Models and Classes of Dynamic Graphs’ Hierarchies
4.2 A General Framework for Impossibilities in Dynamic Graphs
II Graceful Degradation
5 Introduction
5.1 Graceful Degradation
5.1.1 Definition
5.1.2 State of the Art
5.2 State of the Art About Gathering in Dynamic Graphs
5.2.1 Towards Dynamic Graphs
5.2.2 Dynamic Rings
5.3 Motivation for a Gracefully Degrading Gathering Algorithm
6 Gathering
6.1 Impossibility Results
6.2 Gracefully Degrading Gathering: Algorithm GDG
6.2.1 Overwiew
6.2.2 Algorithm
6.3 Proofs of correctness of GDG
6.3.1 GDG solves GEW in COT rings
6.3.2 What about GDG executed in AC, RE, BRE and ST rings?
6.4 Summary
7 Conclusion on Graceful Degradation
III Speculation
8 Introduction
8.1 Speculation
8.1.1 Definition
8.1.2 State of the Art
8.2 State of the Art About Exploration in Dynamic Graphs
8.2.1 Periodic-edges Dynamic Graphs
8.2.2 T-interval connected Graphs
8.3 Contributions
9 Perpetual Exploration Without Fault
9.1 With Three or More Robots
9.1.1 Presentation of the Algorithm
9.1.2 Proof of Correctness
9.2 Speculative Aspect of PEF_3+
9.3 With Two Robots
9.3.1 COT Rings of Size 4 or More
9.3.2 COT Rings of Size 3
9.4 With One Robot
9.5 Summary
10 Perpetual Exploration With Transient Faults
10.1 Self-Stabilization
10.1.1 Definition
10.1.2 State of the Art
10.2 Necessary Number of Robots
10.2.1 Highly Dynamic Rings of Size 4 or More
10.2.2 Highly Dynamic Rings of Size 3 or More
10.3 Sufficiency of Three Robots for n 4
10.3.1 Presentation of the algorithm
10.3.2 Preliminaries to the Correctness Proof
10.3.3 Tower Properties
10.3.4 Correctness Proof
10.4 Speculative Aspect of SS_PEF_3
10.5 Sufficiency of Two Robots for n = 3
10.6 Summary
11 Conclusion on Speculation
11.1 Generalization: Exploration in arbitrary Highly Dynamic Graphs
11.2 Perspectives
IV Conclusion of the Thesis
12 Concluding Remarks
12.1 Sum Up of the Main Parts
12.2 Perspectives of the Thesis
V Appendix
A Approach in the Plane or Rendezvous in an Infinite Grid
A.1 State of the Art about the Approach in the Plane
A.2 Our Approach in the Plane
B Résumé français de la thèse
B.1 Contexte
B.2 Approche progressivement dégradante
B.3 Approche spéculative
B.4 Conclusion
Bibliography
