Project Topics
Get Complete Project Material File(s) Now! »
Environments
The first work considering swarms of robots [136, 137] consider that robots evolve in the plane: robots are able to move in the whole two-dimensional Euclidean space. Then, in order to constrain the possible locations where the robots may be, some work consider discrete static environments modeled by graphs [113, 75]. In these graphs, the nodes represent the locations of the plane where the robots may be, and the edges represent the paths to go from one location to another one. More recently, graphs are used to represent dynamic environments. In these environments the nodes and edges may appear and disappear with time. These dynamic graphs are useful to represent unstable environments that may change over time, like for instance, a transportation network, a building in which doors are closed and open over time, or streets that are closed over time due to work in process or traffic jam in a town.
In this section, we first present the literature dealing with robots in continuous space, then we present the state of the art about robots evolving in discrete static environment, and finally, we describe the literature about robots evolving in discrete dynamic environment.
Continuous space. In the literature, robots may evolve in the continuous space. While con-sidering the continuous space, some articles deal with robots evolving in a line (one-dimensional Euclidean space) [45, 37], some others study robots evolving in the plane (two-dimensional Eu-clidean space) [72, 36, 43, 50, 56, 4], some focus on robots evolving in the three-dimensional Euclidean space [139, 143, 121]. More recently an article deals with robots evolving in N dimen-sional Euclidean space, with N ∈ N [123].
When evolving in the continuous space, robots are endowed with captors with an infinite precision: during the Look phase, the robots are able to see the points of the continuous space where the other robots of the system are located. Moreover, to move in the continuous space, the robots need to have an infinite precision of computation (to designate the point in the continuous space they want to reach). Hence, during the Compute phase, robots are able to compute with infinite precision. During the Move phase, they move in straight line to the destination point they computed during the Compute phase. The movements of the robots are said to be rigid if the robots succeed to reach, during their Move phase, the destination point they have computed during their previous phase [95, 143, 6]. In some models, the Move phase of a robot is aborted before it reaches its destination point [95, 139, 102]. More precisely, there exists a value δ > 0 such that if the destination point is at distance less than δ, then the robot reaches its destination point; otherwise it moves of δ units of length towards its destination point.
Moreover, while considering the continuous space, robots are generally dimensionless, i.e., viewed as points in this space [72, 36, 43]. However, there exists some articles where the robots are considered to be fat, i.e., robots are viewed as disks [50, 56, 4].
Discrete static environment. In order to restrict the computational precision of the robots and the locations where the robots may be, some articles study robots that evolve in discrete static environments, i.e., static graphs. In these graphs, the nodes represent the locations where the robots may be located, and the edges represent the possibilities for a robot to move from one location to another one.
Generally, each robot is able to cross at most one edge at each L-C-M cycle. Most of the articles consider undirected graphs [113, 85]: in these graphs the edges are bidirectional. However, it exists some articles dealing with directed graphs [17, 96] in which edges can be crossed only in one direction. Generally, the graphs in which robots evolve are composed of anonymous nodes [64, 55], i.e., robots are not able to distinguish the nodes.
While considering discrete static graphs, multiple topologies are studied: chains [85], rings [83, 55, 21], trees [84, 135], grids [63, 81], multidimensional grids [13], tori [64] and arbitrary graphs [69, 51].
In the literature, many work consider ring-shaped graphs. These graphs are the simplest ones with symmetry. Most of the time the difficulty of problems comes from this topology and the idea of the solution in ring-shaped graphs can be extended to more general graphs.
Discrete dynamic environment. More recently, robots are considered to evolve in discrete dynamic environments, i.e., dynamic graphs. As indicated in Section 2.1, dynamic graphs permit to model unstable systems such as wireless networks, environments in which a natural disaster has occurred, etc. In the literature, the dynamic graphs in which robots evolve are graphs such that the set of nodes is fixed, but the edges may appear and disappear with time.
Similarly as in static graphs, the nodes of the graphs represent the locations where the robots may be located and the presence of an edge at a given time represents the possibility for a robot to move from one location to another one at this time.
In all the articles of the state of the art dealing with robots evolving in dynamic graphs, each robot crosses at most one edge at each L-C-M cycle. Some articles study undirected dynamic graphs where the edges are bidirectional [142, 3], while some others focus on directed dynamic graphs where the edges are directed (i.e., edges can be crossed only in one direction) [105, 90]. Some articles deal with anonymous nodes [142, 3], while some others consider non-anonymous nodes. Among the last category of articles, some consider that nodes of the graphs have distinct identifiers [105, 90], some others just consider that some nodes are identically marked [122], while some others assume that there is one marked node (i.e., node that is distinguishable from the other nodes) [125].
Most of the articles dealing with robots in dynamic graphs consider ring-shaped graphs [110, 142, 106, 125, 122, 3, 128], however, some study arbitrary graphs [105, 90], while some others focus on specific graphs like cactus (i.e., tree of cycles) graphs [104] or torus graphs [99].
Multiple kinds of dynamics are considered. Indeed, some articles consider AC graphs (graphs connected at each instant time) [106, 104, 125, 122, 99]. Some articles study graphs in which all the edges appear infinitely often, with [106] or without [110] a bound on their time of appearance, while some others consider dynamic graphs where the edges appear periodically [105, 90]. There is a work that focuses on dynamic graphs in which the edges appear in a random way [142]. Some authors focus on the most dynamic graphs (of the classification of Casteigts et al. [40, 38]) possessing a recurrent temporal connectivity, i.e., they focus on COT graphs [128]. Finally, some authors introduce another kind of dynamics, called vertex permutation, such that the topology of the graph at each instant time is maintained but the edges between the (fixed set of) nodes may change [3]. For instance, at each instant time, the topology is a ring, but at a time t the node u may be adjacent to a node v and a node w and the next instant time the node u may be adjacent to two different nodes. Agarwalla et al. [3] also study AC graphs with vertex permutation. For the case of the ring, this implies that at each instant time the topology of the graph is either a ring or a chain, and at each instant time the connections between the nodes may change.
Refer to Section 5.2 and Section 8.2 for more details about existing work studying robots in dynamic graphs.
Hierarchy of Models
We have presented, in Chapter 2, a hierarchy of dynamic graphs (refer to Figure 2.2 and Fig-ure 2.5). In this section, we present a hierarchy of models of robots. A model of robots includes the computational model of robots (refer to Section 3.1.1 that presents three computational mod-els of robots: FSYNC, SSYNC and ASYNC) and a set of capacities that robots can possess (refer to Section 3.1.3 that describes the main capacities possessed by robots in the state of the art). It is important to define a hierarchy of models of robots in order to be able to compare multi-ple algorithms written in different models: this hierarchy of models has deep consequences on calculability, refer to Section 4.1 for more details.
Formally, the computational model of robots corresponds to the subset of executions among all the possible executions that satisfy the synchronization of the phases of the L-C-M cycles of the robots considered. A computational model x is stronger than (denoted ) a computational model y if the set of allowed executions induced by x includes the set of allowed executions induced by y. In the case of the three computational models that we have presented in the state of the art (see Section 3.2), we have: the ASYNC model is stronger than the SSYNC and the FSYNC models, and the SSYNC model is stronger than the FSYNC model. To sum up, we have: FSYNC SSYNC ASYNC. Similarly, each of the capacities presented in Section 3.1.3 corresponds to the subset of execu-tions among all the possible executions that satisfy the properties induced by these capacities. In the same way, some capacities are stronger than others: a capacity x is stronger than (denoted ) a capacity y, if the set of allowed executions induced by x includes the set of allowed executions induced by y. For instance, the anonymous assumption on robots is stronger than the identified assumption on robots. Indeed, if an algorithm solves a problem thanks to anonymous robots, it obviously solves the same problem in the same model except that robots are identified.
Formally, a model of robots is the intersection of the computational model of the robots and of all the capacities possessed by the robots. A model M is stronger than (denoted B) a model M0 if it is included in M. As an example, the model composed of asynchronous, anonymous, oblivious robots without chirality is stronger than the model composed of fully-synchronous, identified robots with persistent memory and with chirality.
Note that the relation between the models is a partial order. Indeed, some models are not comparable: for instance, the model composed of asynchronous and identified robots is not com-parable to the one constituted of fully-synchronous and anonymous robots. Refer to Figure 3.5 for an illustration of a hierarchy of models of robots. In this figure, the models of robots Mgathering, Mexploration, and Mself−stabilizing exploration are models that we use in this thesis respectively in Chapter 6, in Chapter 9, and in Chapter 10.
Towers
In this section, we present some formations of the robots that we used to prove the correctness of our algorithms.
When a robot is alone on its current node, we say that it is isolated. At the opposite, if there are multiple robots on a same node, we say that they form a tower. Intuitively, a tower captures the simultaneous presence of all robots of a given set on a node at each time of a given interval. We require either the set of robots or the time interval of each tower to be maximal. Note that the tower is not required to be on the same node at each time of the interval (robots of the tower may move together without leaving the tower).
Definition 3.1 (Tower). A tower T is a couple (S, θ), where S is a set of robots (|S| > 1) and θ = [ts, te] is an interval of N, such that all the robots of S are located at the same node at each We distinguish two kinds of towers according to the agreement of their robots on the global direction to consider at each time there exists an adjacent edge to their current location (exclud-ing the last one). If they agreed, the robots form a long-lived tower while they form a short-lived tower in the contrary case. This implies that a short-lived tower is broken as soon as the robots forming the tower are edge-activated, while the robots of a long-lived tower move together at each edge-activation of the tower (excluding the last one). Refer to Figure 3.6 for an example of a long-lived tower and a short-lived tower.
Definition 3.2 (Long-lived tower). A long-lived tower T = (S, [ts, te]) is a tower such that there is at least one edge-activation of all robots of S in the time interval [ts, te[.
Implications of Models and Classes of Dynamic Graphs’ Hi-erarchies
Thanks to the hierarchy of models of robots and the hierarchy of dynamic graphs, we are able to compare multiple solutions solving a same problem. When studying distributed systems, the classical approach is to determine the necessary and sufficient conditions to solve a problem. In this thesis, we adopt the same approach but applied to robot networks evolving in dynamic graphs. All the definitions and properties presented in this paragraph are crucial since they per-mit to determine the strongest combination of models of robots and of classes of dynamic graphs in which a problem can be solved. Note that, since some models of robots are not compara-ble and some classes of dynamic graphs are not comparable, it is possible to have multiple such combinations. We present below definitions permitting to determine the strongest combinations of models of robots and of classes of dynamic graphs in which a problem can be solved.
Definition 4.1 (Specification of a problem). The specification of a problem P, denoted SEP, is the set of all the executions that satisfy P.
There exists an infinity of specifications, this is why this notion is defined thanks to a set of executions induced by some properties. Note that, some problems are comparable (i.e., some problems are stronger than others): a problem P is stronger than a problem P0 if SEP ⊂ SEP0 . For instance, the gathering problem in dynamic graphs is stronger than the near-gathering problem without termination in dynamic graphs. Indeed, in an execution where the gathering problem is satisfied, all the robots terminate their execution on a same node of the graph in finite time. This execution also satisfies the near-gathering problem without termination. However, in an execution where the near-gathering problem without termination is satisfied, all the robots must end up on two adjacent nodes of the graph without necessarily terminating their execution. This execution does not satisfy the gathering problem.
Before presenting the fundamental notions of this section (i.e., which are the necessary and sufficient conditions to solve a problem), we need to introduce the meaning of “an execution of an algorithm under a model of robots.” It corresponds to the intersection of the possible executions of the algorithms with the possible executions induced by the models of robots.
Definition 4.2 (Algorithm satisfying a problem in a class of evolving graphs under a model of robots). An algorithm A, starting from a set of initial configurations , satisfies the problem P (specified by SE P) in a class of evolving graphs C under a model of robots M, if and only if any execution of A, starting from any initial configuration γ0 ∈ , under M in any evolving graph G ∈ C belongs to SEP.
Definition 4.3 (Problem impossible in a class of evolving graphs under a model of robots). A problem P is impossible to solve in a class of evolving graphs C under a model M of robots if for any algorithm A, starting from a set of initial configurations , there exists an execution of A, starting from an initial configuration γ0 ∈ , under M in an evolving graph G ∈ C that does not belong to SEP.
As indicated in Section 2.1.2 and as shown on Figure 2.2, there exists a hierarchy of classes of dynamic graphs. This hierarchy permits to deduce some important properties:
Corollary 4.1. If a problem P is impossible in a class of dynamic graphs C under a model M of robots, then P is impossible under M in any class of dynamic graphs C0 such that C ⊂ C0.
Corollary 4.2. If an algorithm A satisfies a problem P in a class of dynamic graphs C under a model M of robots, then A satisfies P under M in any class of dynamic graphs C0 such that C0⊂C.
Similarly, as indicated at the beginning of this section, there exists a hierarchy in the models of robots. This hierarchy permits to deduce the following properties:
Corollary 4.3. If a problem P is impossible in a class of dynamic graphs C under a model of robots M, then P is impossible in C in any model of robots M0 such that M C M0.
Corollary 4.4. If an algorithm A satisfies a problem P in a class of dynamic graphs C under a model of robots M, then A satisfies P in C in any model of robots M0 such that M0 C M.
A General Framework for Impossibilities in Dynamic Graphs
In static graphs there are problems that are impossible. For instance, the consensus problem (in which processes have to decide, in finite time, the same value among a set of values proposed by each of the processes) is impossible in asynchronous systems even when at most one process may crash [82]. When considering dynamic systems, obviously, the number of impossibility results increases due to the dynamics.
To prove that a problem is impossible in dynamic graphs, we have to prove that, for each algorithm A, it exists a dynamic graph where A does not succeed to satisfy the specification of the problem. We can construct this dynamic graph by recurrence: construct a dynamic graph Gi until a time ti, prove that until time ti the specification of the problem is not (always) satisfied in Gi, and then construct another dynamic graph Gi+1 until a time ti+1 (with ti+1 > ti) such that Gi+1 is identical to Gi until time ti and prove that between time ti and ti+1 the specification of the problem is still not (always) satisfied, . . . Thanks to the recurrence, we are able to build a sequence of dynamic graphs in which the execution of any algorithm does not satisfy the specification of the problem on ever-growing bounded prefixes. To end the impossibility proof, we want to reach the limit, with the intuition that the execution of the algorithm on the limit of the sequence shares a common growing prefix with the executions in every graph of the sequence (and hence violates infinitely often the specification of the problem).
Braud-Santoni et al. [34] prove that this intuition is true. Indeed, they propose a generic framework to prove formally impossibilities in dynamic systems. This framework is designed for the message passing model. However, it is general enough to be used in other models. It is based on a theorem that ensures that, if we take a sequence of evolving graphs with ever-growing com-mon prefixes (that hence converges to the evolving graph that shares all these common prefixes), then the sequence of corresponding executions of any deterministic algorithm also converges. Moreover, the execution to which it converges is the execution of this algorithm in the evolving graph to which the sequence converges.
As indicated, even if this generic framework is designed for the message passing model, it is general and may be used in other models. Indeed, the proof of the theorem of this framework only relies on the determinism of algorithms and indistinguishability of dynamic graphs. These arguments are translatable in multiple models. In particular, this framework can be used in our model (see Sections 2.2 and 3.2). Hence all along this thesis, we will use this framework in order to prove formally our impossibility results.
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
