Autonomous Mobile Robots: Refining the Computational Landscape
Autonomous Mobile Robots: Refining the Computational Landscape
复制标题
自主移动机器人：完善计算环境
DOI：
10.1109/ipdpsw52791.2021.00091
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
K. Wada
中科院分区：
文献类型：
--
作者：
K. Buchin;P. Flocchini;I. Kostitsyna;T. Peters;N. Santoro;K. Wada
在分布式计算中，对在欧几里得空间中运行的相同的移动的计算实体（称为机器人）的分布式系统的研究是相当广泛的。当一个机器人被激活时，它会执行一个看-计算-移动的循环：它拍摄环境的快照（看）;通过这个输入，它计算它的目的地（计算）;然后它向那个目的地移动（移动）。机器人被激活的时间以及它的周期持续多久的选择是由一个公平的（但对抗）调度器;通常考虑三种调度器：全同步（Fsync），半同步（Ssync）和异步（Async）。在所有这些调度器下，在四种模型中进行了广泛的研究，对应于机器人的不同级别的计算和通信能力：（最弱的），（最强的），和两个中间模型。针对具体问题的许多结果提供了关于模型之间的关系以及关于激活因子的见解。最近，这些关系的全面表征已经提供了相对于Fsync和Ssync双线性，然而，在一些情况下，得到的结果下，一些限制性的假设（手性和/或刚性）。在本文中，我们通过删除这些假设来改进表征，为这些机器人提供了一个精确的计算环境地图。我们还建立了一些初步的结果与异步调度。
Within distributed computing, the study of distributed systems of identical mobile computational entities, called robots, operating in a Euclidean space is rather extensive. When a robot is activated, it executes a Look-Compute-Move cycle: it takes a snapshot of the environment (Look); with this input, it computes its destination (Compute); and then it moves towards that destination (Move). The choice of the times a robot is activated and how long its cycle lasts is made by a fair (but adversarial) scheduler; three schedulers are usually considered: fully synchronous (Fsync), semi-synchronous (Ssync), and asynchronous (Async).Extensive investigations have been carried out, under all those schedulers, within four models, corresponding to different levels of computational and communication powers of the robots:(the weakest),(the strongest), and two intermediate modelsand. The many results for specific problems have provided insights on the relationships between the models and with respect to the activation schedulers. Recently, a comprehensive characterization of these relationships has been provided with respect to the Fsync and Ssync schedulers; however, in several cases, the results were obtained under some restrictive assumptions (chirality and/or rigidity). In this paper, we improve the characterization by removing those assumptions, providing a refined map of the computational landscape for those robots. We also establish some preliminary results with respect to the Async scheduler.
登录
查看更多内容
Oblivious 移动机器人的分布式计算
DOI：
10.2200/s00440ed1v01y201208dct010
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
P. Flocchini;G. Prencipe;N. Santoro
通讯作者：
N. Santoro
带灯的不透明机器人群的均匀圆圈形成
DOI：
10.1007/978-3-030-03232-6_21
发表时间：
2018
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
Caterina Feletti;C. Mereghetti;Beatrice Palano
通讯作者：
Beatrice Palano
DOI：
10.1137/050645221
发表时间：
2004
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Noam Agmon;D. Peleg
通讯作者：
D. Peleg
发光机器人相互可见而不会发生碰撞
DOI：
10.1016/j.ic.2016.09.005
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Giuseppe Antonio Di Luna;P. Flocchini;S. Chaudhuri;Federico Poloni;N. Santoro;G. Viglietta
通讯作者：
G. Viglietta
带灯机器人
影响因子：
1.1
作者：
Giuseppe Antonio Di Luna;G. Viglietta
通讯作者：
G. Viglietta