Format:
1 Online-Ressource (xiii, 171 Seiten)
,
Illustrationen
Edition:
Electronic reproduction; Available via World Wide Web
ISBN:
9781608456871
Series Statement:
Synthesis lectures on distributed computing theory #10
Content:
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
Content:
1. Introduction -- 1.1 Distributed computing and mobility -- 1.2 Mobile robots and obliviousness -- 1.3 Structure of book --
Content:
2. Computational models -- 2.1 General capabilities -- 2.2 Behavior -- 2.3 Activation and operation schedule -- 2.4 Visibility -- 2.5 Memory -- 2.6 Movements and collisions -- 2.7 Geometric agreement and accuracy -- 2.8 Reliability and fault tolerance -- 2.9 Geometric definitions and terminology --
Content:
3. Gathering and convergence -- 3.1 Basic results -- 3.2 Rendezvous -- 3.3 Gathering with unlimited visibility -- 3.4 Convergence and gathering with limited visibility -- 3.5 Near-gathering -- 3.6 Gathering with inaccurate measurements -- 3.7 Gathering with faulty robots --
Content:
4. Pattern formation -- 4.1 Views and symmetricity -- 4.2 Arbitrary pattern formation -- 4.3 Pattern formation and initial configuration -- 4.4 Circle formation -- 4.5 Forming a sequence of patterns in SSYNC --
Content:
5. Scatterings and coverings -- 5.1 Removing dense points -- 5.2 Uniform covering of the line -- 5.3 Uniform covering of the ring -- 5.4 Filling of orthogonal spaces --
Content:
6. Flocking -- 6.1 Definitions and general strategy -- 6.2 Guided flocking in ASYNC -- 6.3 Guided flocking: the intruder problem -- 6.4 Homogeneous flocking in ASYNC -- 6.5 Homogeneous flocking with obstacles --
Content:
7. Other directions -- 7.1 Computing with colors -- 7.2 Solid robots -- 7.3 Oblivious computations in discrete spaces --
Content:
Bibliography -- Authors' biographies -- Index
Note:
Includes bibliographical references and index
,
Abstract freely available; full-text restricted to subscribers or individual document purchasers
,
Part of: Synthesis digital library of engineering and computer science
,
1. Introduction -- 1.1 Distributed computing and mobility -- 1.2 Mobile robots and obliviousness -- 1.3 Structure of book
,
2. Computational models -- 2.1 General capabilities -- 2.2 Behavior -- 2.3 Activation and operation schedule -- 2.4 Visibility -- 2.5 Memory -- 2.6 Movements and collisions -- 2.7 Geometric agreement and accuracy -- 2.8 Reliability and fault tolerance -- 2.9 Geometric definitions and terminology
,
3. Gathering and convergence -- 3.1 Basic results -- 3.2 Rendezvous -- 3.3 Gathering with unlimited visibility -- 3.4 Convergence and gathering with limited visibility -- 3.5 Near-gathering -- 3.6 Gathering with inaccurate measurements -- 3.7 Gathering with faulty robots
,
4. Pattern formation -- 4.1 Views and symmetricity -- 4.2 Arbitrary pattern formation -- 4.3 Pattern formation and initial configuration -- 4.4 Circle formation -- 4.5 Forming a sequence of patterns in SSYNC
,
5. Scatterings and coverings -- 5.1 Removing dense points -- 5.2 Uniform covering of the line -- 5.3 Uniform covering of the ring -- 5.4 Filling of orthogonal spaces
,
6. Flocking -- 6.1 Definitions and general strategy -- 6.2 Guided flocking in ASYNC -- 6.3 Guided flocking: the intruder problem -- 6.4 Homogeneous flocking in ASYNC -- 6.5 Homogeneous flocking with obstacles
,
7. Other directions -- 7.1 Computing with colors -- 7.2 Solid robots -- 7.3 Oblivious computations in discrete spaces
,
Bibliography -- Authors' biographies -- Index.
,
Electronic reproduction; Available via World Wide Web
,
System requirements: Adobe Acrobat Reader.
,
Mode of access: World Wide Web.
Additional Edition:
ISBN 9781608456864
Additional Edition:
Erscheint auch als Druck-Ausgabe Distributed Computing by Oblivious Mobile Robots
Language:
English
DOI:
10.2200/S00440ED1V01Y201208DCT010
Author information:
Flocchini, Paola
