Name
Title | ||
|---|---|---|
The Impact of the Gabriel Subgraph of the Visibility Graph on the Gathering of Mobile Autonomous Robots. |
Abstract | ||
|---|---|---|
In this work, we reconsider the well-known Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering in the plane n autonomous mobile robots with limited viewing range. The above authors have introduced it as a discrete, round-based algorithm and proved its correctness. In [8], by Degener et al. it is shown that the algorithm gathers in Theta (n(2)) rounds. Remarkably, this algorithm exploits the fact, that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is o.k. under the assumption, those robots have no extent. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center (GTC) strategy in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O (n(2)) for gathering in two-dimensional Euclidean space, and Theta (n) for the one-dimensional case. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robots w.r.t. the Gabriel subgraph of the visibility graph (GTGC). We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the GTC and the GTGC strategy: Whereas lots of collisions occur during a run of the GTC strategy, typically only one, namely the final collision occurs during a run of the GTGC strategy. We can prove this "collisionless property" of the GTGC algorithm for the one-dimensional case. In the case of the two-dimensional Euclidean space, we conjecture that the "collisionless property" holds for almost every initial configuration. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-53058-1_5 | ALGORITHMS FOR SENSOR SYSTEMS (ALGOSENSORS 2016) |
Field | DocType | Volume |
Visibility graph,Random graph,Computer science,Correctness,Exploit,Robot,Mobile robot,Distributed computing | Conference | 10050 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shouwei Li | 1 | 1 | 2.04 |
| Friedhelm Meyer auf der Heide | 2 | 1744 | 238.01 |
| Pavel Podlipyan | 3 | 1 | 2.04 |