Über die Autorin bzw. den Autor

Francesco Bullo is professor of mechanical engineering at the University of California, Santa Barbara. Jorge Cortés is associate professor of mechanical and aerospace engineering at the University of California, San Diego. Sonia Martínez is assistant professor of mechanical and aerospace engineering at the University of California, San Diego.

Von der hinteren Coverseite

"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 Louvain

Aus dem Klappentext

"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 Louvain

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Distributed Control of Robotic Networks

PRINCETON UNIVERSITY PRESS

Contents

Preface...........................................................................ixChapter 1. An introduction to distributed algorithms..............................11.1 Elementary concepts and notation..............................................11.2 Matrix theory.................................................................61.3 Dynamical systems and stability theory........................................121.4 Graph theory..................................................................201.5 Distributed algorithms on synchronous networks................................371.6 Linear distributed algorithms.................................................521.7 Notes.........................................................................661.8 Proofs........................................................................691.9 Exercises.....................................................................85Chapter 2. Geometric models and optimization......................................952.1 Basic geometric notions.......................................................952.2 Proximity graphs..............................................................1042.3 Geometric optimization problems and multicenter functions.....................1112.4 Notes.........................................................................1242.5 Proofs........................................................................1252.6 Exercises.....................................................................133Chapter 3. Robotic network models and complexity notions..........................1393.1 A model for synchronous robotic networks......................................1393.2 Robotic networks with relative sensing........................................1513.3 Coordination tasks and complexity notions.....................................1583.4 Complexity of direction agreement and equidistance............................1653.5 Notes.........................................................................1663.6 Proofs........................................................................1693.7 Exercises.....................................................................176Chapter 4. Connectivity maintenance and rendezvous................................1794.1 Problem statement.............................................................1804.2 Connectivity maintenance algorithms...........................................1824.3 Rendezvous algorithms.........................................................1914.4 Simulation results............................................................2004.5 Notes.........................................................................2014.6 Proofs........................................................................2044.7 Exercises.....................................................................215Chapter 5. Deployment.............................................................2195.1 Problem statement.............................................................2205.2 Deployment algorithms.........................................................2225.3 Simulation results............................................................2335.4 Notes.........................................................................2375.5 Proofs........................................................................2395.6 Exercises.....................................................................245Chapter 6. Boundary estimation and tracking.......................................2476.1 Event-driven asynchronous robotic networks....................................2486.2 Problem statement.............................................................2526.3 Estimate update and cyclic balancing law......................................2566.4 Simulation results............................................................2666.5 Notes.........................................................................2686.6 Proofs........................................................................2706.7 Exercises.....................................................................275Bibliography......................................................................279Algorithm Index...................................................................305Subject Index.....................................................................307Symbol Index......................................................................313

Chapter One

Graph theory, distributed algorithms, and linear distributed algorithms are a fascinating scientific subject. In this chapter we provide a broad introduction to distributed algorithms by reviewing some preliminary graphical concepts and by studying some simple algorithms. We begin the chapter with one section introducing some basic notation and another section stating a few useful facts from matrix theory, dynamical systems, and convergence theorems based on invariance principles. In the third section of the chapter, we provide a primer on graph theory with a particular emphasis on algebraic aspects, such as the properties of adjacency and Laplacian matrices associated to a weighted digraph. In the next section of the chapter, we introduce the notion of synchronous network and of distributed algorithm. We state various complexity notions and study them in simple example problems such as the broadcast problem, the tree computation problem, and the leader election problem. In the fifth section of the chapter, we discuss linear distributed algorithms. We focus on linear algorithms defined by sequences of stochastic matrices and review the results on their convergence properties. We end the chapter with three sections on, respectively, bibliographical notes, proofs of the results presented in the chapter, and exercises.

1.1 ELEMENTARY CONCEPTS AND NOTATION

1.1.1 Sets and maps

We assume that the reader is familiar with basic notions from topology, such as the notions of open, closed, bounded, and compact sets. In this section, we just introduce some basic notation. We let x [member of] S denote a point x belonging to a set S. If S is finite, we let [absolute value of S] denote the number of its elements. For a set S, we let P(S) and F(S) denote the collection of subsets of S and the collection of finite subsets of S, respectively. The empty set is denoted by 0. The interior and the boundary of a set S are denoted by int(S) and S, respectively. If R is a subset of or equal to S, then we write R [subset] S. If R is a strict subset of S, then we write R [subset or not equal to] S. We describe subsets of S defined by specific conditions via the notation

{x [member of] S | condition(s) on x}.

Given two sets [S.sub.1] and [S.sub.2], we let [S.sub.1] [union] [S.sub.2], [S.sub.1] [intersection] [S.sub.2], and [S.sub.1] x [S.sub.2] denote the union, intersection, and Cartesian product of [S.sub.1] and [S.sub.2], respectively. Given a collection of sets [{[S.sub.a]}.sub.a]member of]A] indexed by a...