Local Gathering of Mobile Robots in Three Dimensions

M. Braun, J. Castenow, F. Meyer auf der Heide, in: Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO), Springer, 2020.

Download
Restricted localGathering.pdf 505.71 KB
Conference Paper | English
Abstract
In this work, we initiate the research about the Gathering problem for robots with limited viewing range in the three-dimensional Euclidean space. In the Gathering problem, a set of initially scattered robots is required to gather at the same position. The robots' capabilities are very restricted -- they do not agree on any coordinate system or compass, have a limited viewing range, have no memory of the past and cannot communicate. We study the problem in two different time models, in FSYNC (fully synchronized discrete rounds) and the continuous time model. For FSYNC, we introduce the 3D-Go-To-The-Center-strategy and prove a runtime of $\Theta(n^2)$ that matches the currently best runtime bound for the same model in the Euclidean plane [SPAA'11]. Our main result is the generalization of contracting strategies (continuous time) from [Algosensors'17] to three dimensions. In contracting strategies, every robot that is located on the global convex hull of all robots' positions moves with full speed towards the inside of the convex hull. We prove a runtime bound of $O(\Delta \cdot n^{3/2})$ for any three-dimensional contracting strategy, where $\Delta$ denotes the diameter of the initial configuration. This comes up to a factor of $\sqrt{n}$ close to the lower bound of $\Omega (\Delta \cdot n)$ which is already true in two dimensions. In general, it might be hard for robots with limited viewing range to decide whether they are located on the global convex hull and which movement maintains the connectivity of the swarm, rendering the design of concrete contracting strategies a challenging task. We prove that the continuous variant of 3D-Go-To-The-Center is contracting and keeps the swarm connected. Moreover, we give a simple design criterion for three-dimensional contracting strategies that maintains the connectivity of the swarm and introduce an exemplary strategy based on this criterion.

Best Student Paper Award
Publishing Year
Proceedings Title
Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO)
Conference
SIROCCO 2020
Conference Location
Paderborn
Conference Date
2020-06-29 – 2020-07-01
LibreCat-ID

Cite this

Braun M, Castenow J, Meyer auf der Heide F. Local Gathering of Mobile Robots in Three Dimensions. In: Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO). Springer; 2020. doi:10.1007/978-3-030-54921-3_4
Braun, M., Castenow, J., & Meyer auf der Heide, F. (2020). Local Gathering of Mobile Robots in Three Dimensions. In Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO). Paderborn: Springer. https://doi.org/10.1007/978-3-030-54921-3_4
@inproceedings{Braun_Castenow_Meyer auf der Heide_2020, title={Local Gathering of Mobile Robots in Three Dimensions}, DOI={10.1007/978-3-030-54921-3_4}, booktitle={Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO)}, publisher={Springer}, author={Braun, Michael and Castenow, Jannik and Meyer auf der Heide, Friedhelm}, year={2020} }
Braun, Michael, Jannik Castenow, and Friedhelm Meyer auf der Heide. “Local Gathering of Mobile Robots in Three Dimensions.” In Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO). Springer, 2020. https://doi.org/10.1007/978-3-030-54921-3_4.
M. Braun, J. Castenow, and F. Meyer auf der Heide, “Local Gathering of Mobile Robots in Three Dimensions,” in Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO), Paderborn, 2020.
Braun, Michael, et al. “Local Gathering of Mobile Robots in Three Dimensions.” Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO), Springer, 2020, doi:10.1007/978-3-030-54921-3_4.
Main File(s)
File Name
localGathering.pdf 505.71 KB
Access Level
Restricted Closed Access
Last Uploaded
2020-07-31T08:22:16Z


Export

Marked Publications

Open Data LibreCat

Sources

arXiv arXiv:2005.07495

Search this title in

Google Scholar