Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms (Princeton Series in Applied Mathematics) - Hardcover

Bullo, Francesco; Cortes, Jorge; Martinez, Sonia

Hardcover

ISBN 10: 0691141959 ISBN 13: 9780691141954

Verlag: Princeton University Press, 2009

Inhaltsangabe

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

Über diesen Titel

Ü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

A Mathematical Approach to Motion Coordination AlgorithmsBy Francesco Bullo Jorge Corts Sonia Martnez

PRINCETON UNIVERSITY PRESS

Copyright © 2009 Princeton University Press
All right reserved.
ISBN: 978-0-691-14195-4

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

An introduction to distributed algorithms

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...

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2009
• Sprache: Englisch
• ISBN 10: 0691141959
• ISBN 13: 9780691141954
• Einband: Gebundene Ausgabe
• Anzahl der Seiten: 320
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Buchbär; info@buchbaer.de; ; Weberstr. 67; Osnabrück; 49084; Deutschland