Distributed Control of Robotic Networks : A Mathematical Approach to Motion Coordination Algorithms

by Bullo, Francesco; Cortes, Jorge; Martinez, Sonia

• ISBN13: 9781400831470
• ISBN10: 1400831474
• Copyright: 2009-07-26
• Publisher: Princeton Univ Pr

Summary

This self-contained introduction to the distributed control of robotic networks offers a distinctive blend of computer science and control theory. The book presents a broad set of tools for understanding coordination algorithms, determining their correctness, and assessing their complexity; and it analyzes various cooperative strategies for tasks such as consensus, rendezvous, connectivity maintenance, deployment, and boundary estimation. The unifying theme is a formal model for robotic networks that explicitly incorporates their communication, sensing, control, and processing capabilities--a model that in turn leads to a common formal language to describe and analyze coordination algorithms.Written for first- and second-year graduate students in control and robotics, the book will also be useful to researchers in control theory, robotics, distributed algorithms, and automata theory. The book provides explanations of the basic concepts and main results, as well as numerous examples and exercises. Self-contained exposition of graph-theoretic concepts, distributed algorithms, and complexity measures for processor networks with fixed interconnection topology and for robotic networks with position-dependent interconnection topology Detailed treatment of averaging and consensus algorithms interpreted as linear iterations on synchronous networks Introduction of geometric notions such as partitions, proximity graphs, and multicenter functions Detailed treatment of motion coordination algorithms for deployment, rendezvous, connectivity maintenance, and boundary estimation

Table of Contents

Preface	p. ix
An introduction to distributed algorithms	p. 1
Elementary concepts and notation	p. 1
Matrix theory	p. 6
Dynamical systems and stability theory	p. 12
Graph theory	p. 20
Distributed algorithms on synchronous networks	p. 37
Linear distributed algorithms	p. 52
Notes	p. 66
Proofs	p. 69
Exercises	p. 85
Geometric models and optimization	p. 95
Basic geometric notions	p. 95
Proximity graphs	p. 104
Geometric optimization problems and multicenter functions	p. 111
Notes	p. 124
Proofs	p. 125
Exercises	p. 133
Robotic network models and complexity notions	p. 139
A model for synchronous robotic networks	p. 139
Robotic networks with relative sensing	p. 151
Coordination tasks and complexity notions	p. 158
Complexity of direction agreement and equidistance	p. 165
Notes	p. 166
Proofs	p. 169
Exercises	p. 176
Connectivity maintenance and rendezvous	p. 179
Problem statement	p. 180
Connectivity maintenance algorithms	p. 182
Rendezvous algorithms	p. 191
Simulation results	p. 200
Notes	p. 201
Proofs	p. 204
Exercises	p. 215
Deployment	p. 219
Problem statement	p. 220
Deployment algorithms	p. 222
Simulation results	p. 233
Notes	p. 237
Proofs	p. 239
Exercises	p. 245
Boundary estimation and tracking	p. 247
Event-driven asynchronous robotic networks	p. 248
Problem statement	p. 252
Estimate update and cyclic balancing law	p. 256
Simulation results	p. 266
Notes	p. 268
Proofs	p. 270
Exercises	p. 275
Bibliography	p. 279
Algorithm Index	p. 305
Subject Index	p. 307
Symbol Index	p. 313
Table of Contents provided by Publisher. All Rights Reserved.