Distributed Computing by Oblivious Mobile Robots
Distributed Computing by Oblivious Mobile Robots
复制标题
Oblivious 移动机器人的分布式计算
DOI：
10.2200/s00440ed1v01y201208dct010
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
N. Santoro
中科院分区：
文献类型：
--
作者：
P. Flocchini;G. Prencipe;N. Santoro
最初在机器人技术和人工智能中开始的关于一组自主移动的机器人可以计算什么的研究，在理论计算机科学（特别是分布式计算）中变得越来越流行，现在它是移动的实体可计算性研究的一个组成部分。机器人是位于空间宇宙中并能够在空间宇宙中移动的相同计算实体;它们在没有明确通信的情况下运行，并且通常无法记住过去;它们非常简单，资源有限，并且个体非常虚弱。然而，机器人集体能够执行复杂的任务，并形成一个系统所需的容错和自稳定性能。该研究一直关注这样的系统的计算方面。特别是，重点是机器人为了解决问题而应该具有的最低能力。这本书的重点是最近的算法结果，在分布式计算领域的遗忘移动的机器人（无法记住过去）。在介绍了计算模型及其细微差别后，我们专注于基本的协调问题：模式形成，聚集，分散，领导者选举，以及动态任务，如群集。对于这些问题中的每一个，我们提供了一个最先进的快照，审查现有的算法结果。在这样做时，我们概述了解决方案的技术，我们分析了不同的假设对机器人的可计算能力的影响。目录（T）：介绍/计算模型/聚集和收敛/图案形成/散射和覆盖/植绒/其他方向
The study of what can be computed by a team of autonomous mobile robots, originally started in robotics and AI, has become increasingly popular in theoretical computer science (especially in distributed computing), where it is now an integral part of the investigations on computability by mobile entities. The robots are identical computational entities located and able to move in a spatial universe; they operate without explicit communication and are usually unable to remember the past; they are extremely simple, with limited resources, and individually quite weak. However, collectively the robots are capable of performing complex tasks, and form a system with desirable fault-tolerant and self-stabilizing properties. The research has been concerned with the computational aspects of such systems. In particular, the focus has been on the minimal capabilities that the robots should have in order to solve a problem. This book focuses on the recent algorithmic results in the field of distributed computing by oblivious mobile robots (unable to remember the past). After introducing the computational model with its nuances, we focus on basic coordination problems: pattern formation, gathering, scattering, leader election, as well as on dynamic tasks such as flocking. For each of these problems, we provide a snapshot of the state of the art, reviewing the existing algorithmic results. In doing so, we outline solution techniques, and we analyze the impact of the different assumptions on the robots' computability power. Table of Contents: Introduction / Computational Models / Gathering and Convergence / Pattern Formation / Scatterings and Coverings / Flocking / Other Directions