The Gathering problem for a swarm of robots asks for a distributed algorithm that brings such entities to a common place, not known in advance. We consider the well-known \(\mathcal {OBLOT}\) model with robots constrained to move along the edges of a graph, hence gathering in one vertex, eventually. Despite the classical setting under which the problem has been usually approached, we consider the ‘hostile’ case where: i) the initial configuration may contain multiplicities, i.e. more than one robot may occupy the same vertex; ii) robots cannot detect multiplicities. As a scheduler for robots activation, we consider the ‘favorable’ round-robin case, where robots are activated one at a time. Our objective is to achieve a complete characterization of the problem in the broad context of non-vertex-transitive graphs, i.e., graphs where the vertices are partitioned into at least two different classes of equivalence. We provide a resolution algorithm for any configuration of robots moving on such graphs along with its correctness. Furthermore, we analyze its time complexity.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Gathering in Non-vertex-Transitive Graphs Under Round Robin

  • Serafino Cicerone,
  • Alessia Di Fonso,
  • Gabriele Di Stefano,
  • Alfredo Navarra

摘要

The Gathering problem for a swarm of robots asks for a distributed algorithm that brings such entities to a common place, not known in advance. We consider the well-known \(\mathcal {OBLOT}\) model with robots constrained to move along the edges of a graph, hence gathering in one vertex, eventually. Despite the classical setting under which the problem has been usually approached, we consider the ‘hostile’ case where: i) the initial configuration may contain multiplicities, i.e. more than one robot may occupy the same vertex; ii) robots cannot detect multiplicities. As a scheduler for robots activation, we consider the ‘favorable’ round-robin case, where robots are activated one at a time. Our objective is to achieve a complete characterization of the problem in the broad context of non-vertex-transitive graphs, i.e., graphs where the vertices are partitioned into at least two different classes of equivalence. We provide a resolution algorithm for any configuration of robots moving on such graphs along with its correctness. Furthermore, we analyze its time complexity.