Local Gathering of Mobile Robots in Three Dimensions

M. Braun, J. Castenow, F. Meyer auf der Heide, ArXiv:2005.07495 (2020).

Download
No fulltext has been uploaded.
Preprint | 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.
Publishing Year
Journal Title
arXiv:2005.07495
LibreCat-ID

Cite this

Braun M, Castenow J, Meyer auf der Heide F. Local Gathering of Mobile Robots in Three Dimensions. arXiv:200507495. 2020.
Braun, M., Castenow, J., & Meyer auf der Heide, F. (2020). Local Gathering of Mobile Robots in Three Dimensions. ArXiv:2005.07495.
@article{Braun_Castenow_Meyer auf der Heide_2020, title={Local Gathering of Mobile Robots in Three Dimensions}, journal={arXiv:2005.07495}, 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.” ArXiv:2005.07495, 2020.
M. Braun, J. Castenow, and F. Meyer auf der Heide, “Local Gathering of Mobile Robots in Three Dimensions,” arXiv:2005.07495. 2020.
Braun, Michael, et al. “Local Gathering of Mobile Robots in Three Dimensions.” ArXiv:2005.07495, 2020.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar