Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
We consider the distributed setting of <i>N</i> autonomous mobile robots that operate in <i>Look-Compute-Move</i> (LCM) cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem of gathering <i>N</i> autonomous robots on...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
MDPI AG
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/f1393ec326364293bc945b7c7da90c5f |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | We consider the distributed setting of <i>N</i> autonomous mobile robots that operate in <i>Look-Compute-Move</i> (LCM) cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem of gathering <i>N</i> autonomous robots on a plane, which requires all robots to meet at a single point (or to position within a small area) that is not known beforehand. We consider limited visibility under which robots are only able to see other robots up to a constant Euclidean distance and focus on the time complexity of gathering by robots under limited visibility. There exists an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msub><mi>D</mi><mi>G</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> time algorithm for this problem in the fully synchronous setting, assuming that the robots agree on one coordinate axis (say north), where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>D</mi><mi>G</mi></msub></semantics></math></inline-formula> is the diameter of the visibility graph of the initial configuration. In this article, we provide the first <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msub><mi>D</mi><mi>E</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula> time algorithm for this problem in the asynchronous setting under the same assumption of robots’ agreement with one coordinate axis, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>D</mi><mi>E</mi></msub></semantics></math></inline-formula> is the Euclidean distance between farthest-pair of robots in the initial configuration. The runtime of our algorithm is a significant improvement since for any initial configuration of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>N</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula> robots, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>D</mi><mi>E</mi></msub><mo>≤</mo><msub><mi>D</mi><mi>G</mi></msub></mrow></semantics></math></inline-formula>, and there exist initial configurations for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>D</mi><mi>G</mi></msub></semantics></math></inline-formula> can be quadratic on <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>D</mi><mi>E</mi></msub></semantics></math></inline-formula>, i.e., <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>D</mi><mi>G</mi></msub><mo>=</mo><mo>Θ</mo><mrow><mo>(</mo><msubsup><mi>D</mi><mi>E</mi><mn>2</mn></msubsup><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Moreover, our algorithm is asymptotically time-optimal since the trivial time lower bound for this problem is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>Ω</mo><mo>(</mo><msub><mi>D</mi><mi>E</mi></msub><mo>)</mo></mrow></semantics></math></inline-formula>. |
|---|