Decentralized Coverage Control Problems for Mobile Robotic Sensor and Actuator Networks

Andrey Savkin is a professor and Research Chair of Electrical Engineering and Telecommunications at the University of New South Wales, Australia since 2000. He received his MS from Leningrad State University, Russia and is currently a part-time PhD student at the same institution . His areas of research include, but are not limited to, robust control and filtering, hybrid dynamical systems, communication networks, biomedical signal processing, and navigation and control of mobile robotics. Professor Savkin has co-authored several research monographs, and approximately 180 journal papers published by top international journals.

This book introduces various coverage control problems for mobile sensor networks including barrier, sweep and blanket. Unlike many existing algorithms, all of the robotic sensor and actuator motion algorithms developed in the book are fully decentralized or distributed, computationally efficient, easily implementable in engineering practice and based only on information on the closest neighbours of each mobile sensor and actuator and local information about the environment. Moreover, the mobile robotic sensors have no prior information about the environment in which they operation. These various types of coverage problems have never been covered before by a single book in a systematic way.
 
Another topic of this book is the study of mobile robotic sensor and actuator networks. Many modern engineering applications include the use of sensor and actuator networks to provide efficient and effective monitoring and control of industrial and environmental processes. Such mobile sensor and actuator networks are able to achieve improved performance and efficient monitoring together with reduction in power consumption and production cost.

This book introduces various coverage control problems for mobile sensor networks including barrier, sweep and blanket.

Preface ix
 
1 Introduction 1
 
1.1 Distributed Coverage Control of Mobile Sensor and Actuator Networks 1
 
1.2 Overview of the Book 4
 
1.3 Some Other Remarks 6
 
2 Barrier Coverage between Two Landmarks 9
 
2.1 Introduction 9
 
2.2 Problem of Barrier Coverage between Two Landmarks 10
 
2.3 Distributed SelfDeployment Algorithm for Barrier Coverage 12
 
2.4 Illustrative Examples 14
 
3 Multi-level Barrier Coverage 17
 
3.1 Introduction 17
 
3.2 Problem of KBarrier Coverage 18
 
3.3 Distributed Algorithm for KBarrier Coverage 22
 
3.4 Mathematical Analysis of the KBarrier Coverage Algorithm 25
 
3.5 Illustrative Examples 28
 
4 Problems of Barrier and Sweep Coverage in Corridor Environments 33
 
4.1 Introduction 33
 
4.2 Corridor Coverage Problems 34
 
4.2.1 Barrier Coverage 35
 
4.2.2 Sweep Coverage 37
 
4.3 Barrier Coverage in 1D Space 38
 
4.4 Corridor Barrier Coverage 39
 
4.5 Corridor Sweep Coverage 42
 
4.6 Illustrative Examples 43
 
5 Sweep Coverage along a Line 57
 
5.1 Introduction 57
 
5.2 Problem of Sweep Coverage along a Line 60
 
5.3 Sweep Coverage along a Line 63
 
5.4 Assumptions and the Main Results 68
 
5.5 Illustrative Examples 72
 
5.5.1 StraightLine Sweeping Paths 73
 
5.5.2 Comparison with the Potential Field Approach 73
 
5.5.3 Sweep Coverage along Nonstraight Lines 74
 
5.5.4 Scalability 75
 
5.5.5 Measurement Noises 76
 
5.5.6 Sea Exploration 77
 
5.6 Proofs of the Technical Facts Underlying Theorem 5.1 79
 
6 Optimal Distributed Blanket Coverage Problem 87
 
6.1 Introduction 87
 
6.2 Blanket Coverage Problem Formulation 88
 
6.3 Randomized Coverage Algorithm 90
 
6.4 Illustrative Examples 93
 
7 Distributed Self-Deployment for Forming a Desired Geometric Shape 97
 
7.1 Introduction 97
 
7.2 SelfDeployment on a Square Grid 98
 
7.3 Illustrative Examples: Square Grid Deployment 103
 
7.4 SelfDeployment in a Desired Geometric Shape 104
 
7.5 Illustrative Examples: Various Geometric Shapes 105
 
7.5.1 Circular Formation 106
 
7.5.2 Ellipse Formation 106
 
7.5.3 Rectangular Formation 108
 
7.5.4 Ring Formation 108
 
7.5.5 Regular Hexagon Formation 112
 
8 Mobile Sensor and Actuator Networks: Encircling, Termination and Hannibal's Battle of Cannae Maneuver 113
 
8.1 Introduction 113
 
8.2 Encircling Coverage of a Moving Region 115
 
8.3 Randomized Encircling Algorithm 117
 
8.4 Termination of a Moving Region by a Sensor and Actuator Network 119
 
8.5 Illustrative Examples 120
 
9 Asymptotically Optimal Blanket Coverage between Two Boundaries 129
 
9.1 Introduction 129
 
9.2 Problem of Blanket Coverage between Two Lines 133
 
9.3 Blanket Coverage Algorithm 137
 
9.3.1 Description 138
 
9.3.2 Control Laws 138
 
9.3.3 Algorithm Convergence 144
 
9.4 Triangular Blanket Coverage between Curves 145
 
9.5 Illustrative Examples 148
 
9.6 Proof of Theorem 9.2 149
 
10 Distributed Navigation for Swarming with a Given Geometric Pattern 157
 
10.1 Introduction 157
 
10.2 Navigation for Swarming Problem 159
 
10.3 Distributed Navigation Algorithm 161
 
10.3.1 First Stage 161
 
10.3.2 Second Stage 165
 
10.3.3 Behavior of the Proposed Algorithm 168
 
10.4 Illustrative Examples and Computer Si