Summary: In this work, we reconsider the well-known Go-To-The-Center algorithm due to H. Ando, I. Suzuki and M. Yamashita [“Formation and agreement problems for synchronous mobile robots with limited visibility”, in: Proceedings of tenth international symposium on intelligent control, 1995. Los Alamitos, CA: IEEE Computer Society. 453–460 (1995; doi:10.1109/ISIC.1995.525098)] 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 [B. Degener et al., “A tight runtime bound for synchronous gathering of autonomous robots with limited visibility”, in: Proceedings of the twenty-third annual ACM symposium on parallelism in algorithms and architectures, SPAA ’11. New York, NY: Association for Computing Machinery (ACM). 139–148 (2011; doi:10.1145/1989493.1989515)], it is shown that the algorithm gathers in \(\varTheta \left( n^2\right) \) 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\left( n^2\right) \) for gathering in two-dimensional Euclidean space, and \(\varTheta \left( n\right) \) 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.
For the entire collection see [Zbl 1355.68013].