Time-Optimal Gathering under Limited Visibility with One-Axis Agreement

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Pavan Poudel, Gokarna Sharma
Formato: article
Lenguaje:EN
Publicado: MDPI AG 2021
Materias:
distributed algorithms
mobile robots
classic oblivious robot model
gathering
time complexity
visibility
Information technology
T58.5-58.64
Acceso en línea:https://doaj.org/article/f1393ec326364293bc945b7c7da90c5f
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
id oai:doaj.org-article:f1393ec326364293bc945b7c7da90c5f
record_format dspace
spelling oai:doaj.org-article:f1393ec326364293bc945b7c7da90c5f2021-11-25T17:58:28ZTime-Optimal Gathering under Limited Visibility with One-Axis Agreement10.3390/info121104482078-2489https://doaj.org/article/f1393ec326364293bc945b7c7da90c5f2021-10-01T00:00:00Zhttps://www.mdpi.com/2078-2489/12/11/448https://doaj.org/toc/2078-2489We 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>.Pavan PoudelGokarna SharmaMDPI AGarticledistributed algorithmsmobile robotsclassic oblivious robot modelgatheringtime complexityvisibilityInformation technologyT58.5-58.64ENInformation, Vol 12, Iss 448, p 448 (2021)
institution DOAJ
collection DOAJ
language EN
topic distributed algorithms
mobile robots
classic oblivious robot model
gathering
time complexity
visibility
Information technology
T58.5-58.64
spellingShingle distributed algorithms
mobile robots
classic oblivious robot model
gathering
time complexity
visibility
Information technology
T58.5-58.64
Pavan Poudel
Gokarna Sharma
Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
description 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>.
format article
author Pavan Poudel
Gokarna Sharma
author_facet Pavan Poudel
Gokarna Sharma
author_sort Pavan Poudel
title Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
title_short Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
title_full Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
title_fullStr Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
title_full_unstemmed Time-Optimal Gathering under Limited Visibility with One-Axis Agreement
title_sort time-optimal gathering under limited visibility with one-axis agreement
publisher MDPI AG
publishDate 2021
url https://doaj.org/article/f1393ec326364293bc945b7c7da90c5f
work_keys_str_mv AT pavanpoudel timeoptimalgatheringunderlimitedvisibilitywithoneaxisagreement
AT gokarnasharma timeoptimalgatheringunderlimitedvisibilitywithoneaxisagreement
_version_ 1718411777844183040

Ejemplares similares