Description
Book SynopsisIntroduces the distributed control of robotic networks. This book presents a set of tools for understanding coordination algorithms, determining their correctness, and assessing their complexity. It analyzes various cooperative strategies for tasks such as consensus, rendezvous, connectivity maintenance, deployment, and boundary estimation.
Trade Review"This book covers its subject very thoroughly. The framework the authors have established is very elegant and, if it catches on, this book could be the primary reference for this approach. I don't know of any other book that covers this set of topics."
—Richard M. Murray, California Institute of Technology"The authors do an excellent job of clearly describing the problems and presenting rigorous, provably correct algorithms with complexity bounds for each problem. The authors also do a fantastic job of providing the mathematical insight necessary for such complex problems."
—Ali Jadbabaie, University of Pennsylvania"The order of presentation makes much sense, and the book thoroughly covers what it sets out to cover. The algorithms and results are presented using a clear mathematical and computer science formalism, which allows a uniform presentation. The formalism used and the way of presenting the algorithms may be helpful for structuring the presentation of new algorithms in the future."
—Vincent Blondel, Université catholique de LouvainTable of ContentsPreface ix Chapter 1. An introduction to distributed algorithms 1 1.1 Elementary concepts and notation 1 1.2 Matrix theory 6 1.3 Dynamical systems and stability theory 12 1.4 Graph theory 20 1.5 Distributed algorithms on synchronous networks 37 1.6 Linear distributed algorithms 52 1.7 Notes 66 1.8 Proofs 69 1.9 Exercises 85 Chapter 2. Geometric models and optimization 95 2.1 Basic geometric notions 95 2.2 Proximity graphs 104 2.3 Geometric optimization problems and multicenter functions 111 2.4 Notes 124 2.5 Proofs 125 2.6 Exercises 133 Chapter 3. Robotic network models and complexity notions 139 3.1 A model for synchronous robotic networks 139 3.2 Robotic networks with relative sensing 151 3.3 Coordination tasks and complexity notions 158 3.4 Complexity of direction agreement and equidistance 165 3.5 Notes 166 3.6 Proofs 169 3.7 Exercises 176 Chapter 4. Connectivity maintenance and rendezvous 179 4.1 Problem statement 180 4.2 Connectivity maintenance algorithms 182 4.3 Rendezvous algorithms 191 4.4 Simulation results 200 4.5 Notes 201 4.6 Proofs 204 4.7 Exercises 215 Chapter 5. Deployment 219 5.1 Problem statement 220 5.2 Deployment algorithms 222 5.3 Simulation results 233 5.4 Notes 237 5.5 Proofs 239 5.6 Exercises 245 Chapter 6. Boundary estimation and tracking 247 6.1 Event-driven asynchronous robotic networks 248 6.2 Problem statement 252 6.3 Estimate update and cyclic balancing law 256 6.4 Simulation results 266 6.5 Notes 268 6.6 Proofs 270 6.7 Exercises 275 Bibliography 279 Algorithm Index 305 Subject Index 307 Symbol Index 313
