Muutke küpsiste eelistusi

Distributed Computing by Oblivious Mobile Robots [Pehme köide]

, ,
Teised raamatud teemal:
Distributed Computing by Oblivious Mobile RobotsSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9781608456864.html
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
Acknowledgments xiii
1 Introduction
1(6)
1.1 Distributed Computing and Mobility
1(1)
1.2 Mobile Robots and Obliviousness
2(1)
1.3 Structure of Book
3(4)
2 Computational Models
7(10)
2.1 General Capabilities
7(1)
2.2 Behavior
8(1)
2.3 Activation and Operation Schedule
8(1)
2.4 Visibility
9(2)
2.5 Memory
11(1)
2.6 Movements and Collisions
12(1)
2.7 Geometric Agreement and Accuracy
13(1)
2.8 Reliability and Fault Tolerance
14(1)
2.9 Geometric Definitions and Terminology
14(3)
3 Gathering and Convergence
17(48)
3.1 Basic Results
17(5)
3.1.1 Gathering in Fsync
17(1)
3.1.2 Limits to Gathering in Ssync: n = 2
18(1)
3.1.3 Limits to Gathering in Ssync: n > 2
18(3)
3.1.4 Gathering with Consistent Compasses
21(1)
3.2 Rendezvous
22(3)
3.2.1 Basic Results
22(1)
3.2.2 Rendezvous with Tilted Compasses
22(3)
3.3 Gathering with Unlimited Visibility
25(13)
3.3.1 Convergence in Async
26(2)
3.3.2 Gathering in Async with Multiplicity Detection
28(7)
3.3.3 Gathering in Ssync: Tilted Compasses
35(2)
3.3.4 Gathering in Ssync: Dense Initial Configurations
37(1)
3.4 Convergence and Gathering with Limited Visibility
38(9)
3.4.1 Convergence in Ssync
38(2)
3.4.2 Convergence in Fsync in Non-Convex Regions
40(1)
3.4.3 Convergence in Async
41(1)
3.4.4 Gathering with Consistent Compasses in Async
42(3)
3.4.5 Gathering with Unstable Compasses in Ssync
45(2)
3.5 Near-Gathering
47(4)
3.5.1 Near-Gathering with Unlimited Visibility
48(1)
3.5.2 Near-Gathering with Limited Visibility
48(1)
3.5.3 Near-Gathering with Limited Visibility in Async
48(3)
3.6 Gathering with Inaccurate Measurements
51(3)
3.6.1 Impossibility of Gathering
51(1)
3.6.2 Possibility of Convergence with Unlimited Visibility
52(2)
3.6.3 Possibility of Convergence with Limited Visibility
54(1)
3.7 Gathering with Faulty Robots
54(11)
3.7.1 Crash Faults
55(3)
3.7.2 Byzantine Faults: Impossibility in Ssync
58(2)
3.7.3 Byzantine Faults: Gathering in Fsync
60(1)
3.7.4 Byzantine Faults in Unidimensional Space
61(4)
4 Pattern Formation
65(38)
4.1 Views and Symmetricity
65(3)
4.2 Arbitrary Pattern Formation
68(12)
4.2.1 Arbitrary Patter Formation and Leader Election
68(3)
4.2.2 Arbitrary Pattern Formation and Compasses
71(7)
4.2.3 Landmarks Covering: Formation of Visible Patterns
78(2)
4.3 Pattern Formation and Initial Configuration
80(4)
4.3.1 Impossibility
80(1)
4.3.2 Possibility
81(3)
4.4 Circle Formation
84(12)
4.4.1 Forming a Circle
84(2)
4.4.2 Convergence Toward a Uniform Circle in Ssync
86(1)
4.4.3 Biangular Circle Formation in Ssync
87(2)
4.4.4 From Biangular to Uniform Circle
89(5)
4.4.5 Uniform Circle Formation in Ssync
94(1)
4.4.6 Uniform Circle Formation in Async
94(2)
4.5 Forming a Sequence of Patterns in Ssync
96(7)
4.5.1 Anonymous Robots
97(2)
4.5.2 Robots with Distinct Visible Identities
99(1)
4.5.3 Robots with Invisible Distinct Identities
100(3)
5 Scatterings and Coverings
103(14)
5.1 Removing Dense Points
103(2)
5.1.1 Removing Dense Points: Unlimited Visibility
104(1)
5.1.2 Removing Dense Points: Limited Visibility
105(1)
5.2 Uniform Covering of the Line
105(2)
5.3 Uniform Covering of the Ring
107(5)
5.3.1 Definitions
108(1)
5.3.2 Impossibility Without Chirality
108(3)
5.3.3 Uniform Covering with Limited Visibility
111(1)
5.3.4 Convergence to Uniform Covering
111(1)
5.4 Filling of Orthogonal Spaces
112(5)
5.4.1 Impossibility Without Memory
113(1)
5.4.2 Filling in Ssync
114(3)
6 Flocking
117(18)
6.1 Definitions and General Strategy
118(2)
6.2 Guided Flocking in Async
120(3)
6.2.1 The Flocking Algorithm
120(2)
6.2.2 Experimental Results
122(1)
6.3 Guided Flocking: The Intruder Problem
123(4)
6.3.1 Limitations
124(1)
6.3.2 An Algorithmic Approach
125(1)
6.3.3 A Heuristic Approach
126(1)
6.3.4 Experimental Results
126(1)
6.4 Homogeneous Flocking in Async
127(5)
6.4.1 First Module: Leader Election
128(1)
6.4.2 Second Module: Setting a Moving Formation
129(2)
6.4.3 Third Module: Flocking
131(1)
6.5 Homogeneous Flocking With Obstacles
132(3)
6.5.1 The 2D Case
132(1)
6.5.2 The 3D Case
133(2)
7 Other Directions
135(18)
7.1 Computing with Colors
135(3)
7.1.1 Colored Async versus Ssync
135(2)
7.1.2 Colored Async versus Fsync
137(1)
7.2 Solid Robots
138(7)
7.2.1 Gathering Solid Robots
138(5)
7.2.2 Uniform Circle of Solid Robots
143(2)
7.3 Oblivious Computations in Discrete Spaces
145(8)
7.3.1 Gathering
146(3)
7.3.2 Exploration with Stop
149(2)
7.3.3 Perpetual Exploration
151(1)
7.3.4 Uniform Deployment in the Ring
152(1)
Bibliography 153(14)
Authors' Biographies 167(2)
Index 169