Distributed Computing by Oblivious Mobile Robots (Paperback)

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

研究由一組自主移動機器人可以計算的領域，最初起源於機器人學和人工智慧，現在在理論計算機科學（尤其是分散計算）中越來越受歡迎，已成為對移動實體的可計算性研究的一部分。這些機器人是位於空間宇宙中的相同計算實體，能夠移動；它們在沒有明確通信的情況下運作，通常無法記住過去；它們非常簡單，資源有限，個體上相當脆弱。然而，這些機器人集體能夠執行複雜任務，形成具有可靠容錯和自我穩定特性的系統。研究關注這些系統的計算方面，特別是關注機器人在解決問題時應具備的最低能力。

本書專注於分散計算中關於遺忘過去的移動機器人的最新算法結果。在介紹計算模型及其細節後，我們專注於基本的協調問題：模式形成、聚集、散開、選舉領導者，以及群體行為等動態任務。對於每個問題，我們提供了現有算法結果的概述。在此過程中，我們概述解決技術，並分析不同假設對機器人的計算能力的影響。

目錄：引言 / 計算模型 / 聚集和收斂 / 模式形成 / 散開和覆蓋 / 群體行為 / 其他方向