Acerca del autor

Francesco Bullo is professor of mechanical engineering at the University of California, Santa Barbara. Jorge Cortes is associate professor of mechanical and aerospace engineering at the University of California, San Diego. Sonia Martinez is assistant professor of mechanical and aerospace engineering at the University of California, San Diego.

De la contraportada

"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

De la solapa interior

"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

Fragmento. © Reproducción autorizada. Todos los derechos reservados.

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 set A, we interchangeably denote their Cartesian product by [[Pi].sub.a]member of]A] [S.sub.a] or by [[Pi]{ [S.sub.a] | a [member of] A}. We adopt analogous notations for union and intersection. We denote by [S.sup.n] the Cartesian product of n copies of the same S. The diagonal set diag([S.sup.n]) of [S.sup.n] is given by diag([S.sup.n]) = {(s, ..., s) [S.sup.n] | s [member of] S}. The set [S.sub.1] \ [S.sub.2] contains all points in [S.sub.1] that do not belong to [S.sub.2].

We let N and [Z.sub.[greater than or equal to] 0] denote the set of natural numbers and of non-negative integers, respectively. We let R, [R.sub.>0], [R.sub.[greater than or equal to] 0], and C denote the set of real numbers, strictly positive real numbers, non-negative real numbers, and complex numbers, respectively. The sets [R.sup.d], [C.sup.d], and [S.sup.d] [subset] [R.sup.d+1] are the d-dimensional Euclidean space, the d-dimensional complex space, and the d-dimensional sphere, respectively. The tangent space of [R.sup.d], denoted by [TR.sup.d], is the set of all vectors tangent to [R.sup.d]. Note that [TR.sup.d] can be identified with [R.sup.d] x [R.sup.d] by mapping a vector v tangent to [R.sup.d] at x [member of] [R.sup.d] to the pair (x, v). Likewise, [TS.sup.d] is the set of all vectors tangent to [S.sup.d], and can be identified with [S.sup.d] x [R.sup.d]. The Euclidean space [R.sup.d] contains the vectors [0.sub.d] = (0, . . . , 0), [1.sub.d] = (1, ..., 1), and the standard basis [e.sub.1] = (1, 0, ..., 0), ..., [e.sub.d] = (0, ..., 0, 1). Given a < b, we let [a, b] and ]a, b] denote the closed interval and the open interval between a and b, respectively.

Given two sets S and T, we let f : S [right arrow] T denote a map from S to T, that is, a unique way of associating an element of T to an element of S. The image of the map f : S [right arrow] T is the set image(f) = {f(s) [member of] T | s [member of] S}. Given the map f : S [right arrow] T and a set [S.sub.1] [subset] S, we let f([S.sub.1]) = {f(s) | s [member of] [S.sub.1]} denote the image of the set [S.sub.1] under the map f. Given f : S [right arrow] T and g : U [right arrow] S, we let f x g : U [right arrow] T, defined by f x g (u) = f(g(u)), denote the composition of f and g. The map [id.sub.S] : S [right arrow] S is the identity map on S. Given f : S [right arrow] R, the support of f is the set of elements s such that f(s) [not equal to] 0. Given a subset R [subset or not equal to] S, the indicator map [1.sub.R] : S [right arrow] R associated with R is given by [1.sub.R](q) = 1 if q [member of] R, and [1.sub.R](q) = 0 if q [not member of] R. Given two sets S and T, a set-valued map, denoted by h : S [??] T, associates to an element of S a subset of T. Given a map f : S [right arrow] T, the inverse map [f.sup.-1] : T [??] S is defined by

[f.sup.-1] (t) = {s [member of] S | f(s) = t}.

If f is a real-valued function, that is, a function of the form f : S [right arrow] R, then [f.sup.-1](x) [subset] S, for any x [member of] R, is a level set of f. In what follows, we require the reader to be familiar with some basic smoothness notions for functions. Specifically, we will use the notions of locally and globally Lipschitz functions, differentiable, piecewise differentiable and continuously differentiable functions, and functions that are multiple times differentiable.

Finally, we introduce the so-called Bachmann-Landau symbols. For f, g : N [right arrow] [R.sub.[greater than or equal to] 0], we say that f [member of] O(g) (resp., f [member of] [Omega](g)) if there exist [n.sub.0] N and K [member of] [R.sub.>0] (resp., k [member of] [R.sub.>0]) such that f(n) [less than or equal to] Kg(n) for all n [greater than or equal to] [n.sub.0] (resp., f(n) [greater than or equal to] kg(n) for all n [greater than or equal to] [n.sub.0]). If f [member of] O(g) and f [member of] [Omega](g), then we use the notation f [member of] [Theta](g).

1.1.2 Distance functions

A function dist : S x S [right arrow] [R.sub.[greater than or equal to] 0] defines a distance on a set S if it satisfies: (i) dist(x, y) = 0 if and only if x = y; (ii) dist(x, y) = dist(y, x), for all x, y [member of] S; and (iii) dist(x, y) [less than or equal to] dist(x, z) + dist(z, y), for all x, y, z [member of] S. The pair (S, dist) is usually called a metric space.

Some relevant examples of distance functions include the following:

[L.sup.p]-distance on [R.sup.d]. For p [member of] [1, + [infinity][, consider the [L.sup.p]-norm on [R.sup.d] defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For p = + [infinity], consider the [L.sup.[infinity]]-norm on [R.sup.d] defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Any of these norms defines naturally a [L.sup.p]-distance in [R.sup.d] by [dist.sub.p](x, y) = [||y - x||.sub.p]. In particular, the most widely used is the Euclidean distance, corresponding to p = 2. Unless otherwise noted, it is always understood that [R.sup.d] is endowed with this notion of distance. We will also use the [L.sup.1]- and the [L.sup.[infinity]]-distances. Finally, it is convenient to define the norm [||z||.sub.C] of a complex number z [member of] C to be the Euclidean norm of z regarded as a vector in [R.sup.2].

Geodesic distance on [S.sup.d]. Another example is the notion of geodesic distance on [S.sup.d]. This is defined as follows. For x, y [member of] [S.sup.d], [dist.sub.g](x, y) is the length of the shortest curve in [S.sup.d] connecting x and y. We will use this notion of distance in dimensions d = 1 and d = 2. On the unit circle [S.sup.1], by convention, let us define positions as angles measured counterclockwise from the positive horizontal axis. Then, the geodesic distance can be expressed as

distg(x, y) = min{[dist.sub.c](x, y), [dist.sub.cc](x, y)}, x, y [member of] [S.sup.1],

where [dist.sub.c](x, y) = (x - y) mod 2[pi] is the clockwise distance and [dist.sub.cc](x, y) = (y - x) mod 2[pi] is the counterclockwise distance. Here the clockwise distance between two angles is the path length from an angle to the other traveling clockwise, and x mod 2[pi] is the remainder of the division of x by 2[pi]. On the sphere [S.sup.2], the geodesic distance can be computed as follows. Given x, y [member of] [S.sup.2], one considers the great circle determined by x and y. Then, the geodesic distance between x and y is exactly the length of the shortest arc in the great circle connecting x and y.

Cartesian product distance on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Consider [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] endowed with an [L.sup.p]-distance, p [member of] [1, + [infinity]], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] endowed with the geodesic distance. Given ([x.sub.1], [y.sub.1]), ([x.sub.2], [y.sub.2]) [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], their Cartesian product distance is given by [dist.sub.p]([x.sub.1], [x.sub.2]) + [dist.sub.g]([y.sub.1], [y.sub.2]). Unless otherwise noted, it is understood that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is endowed with the Cartesian product distance ([dist.sub.2], [dist.sub.g]).

Given a metric space (S, dist), the open and closed balls of center x [member of] S and radius [epsilon] [member of] [R.sub.>0] are defined by, respectively,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consider a point x [member of] X and a set S [subset] X. A neighborhood of a point x [member of] X is a subset of X that contains an open ball centered at x. A neighborhood of a set Y [subset] X is a subset of X that, for each point y [member of] Y, contains an open ball centered at y. The open lune associated to x, y [member of] S is B(x, dist(x, y)) [intersection] B(y, dist(x, y)). These notions are illustrated in Figure 1.1 for the plane equipped with the Euclidean distance.

Given a metric space (S, dist), the distance between a point x [member of] S and a set W [subset] S is the infimum of all distances between x and each of the points in W. Formally, we set

dist(x, W) = inf{dist(x, y) | y [member of] W}.

The projection of a point x [member of] S onto a set W [subset] S is the set-valued map [proj.sub.W] : S [??] W defined by

[proj.sub.W] (x) = {y [member of] W | dist(x, y) = dist(x, W)}.

If W is a closed set, then [proj.sub.W] (x) [not equal to] 0 for any x [member of] S. The diameter of a set is the maximum distance between any two points in the set; formally, we set diam(S) = sup{dist(x, y) | x, y [member of] S}. With a slight abuse of notation, we often use diam(P) to denote diam({[p.sub.1], ..., [p.sub.n]}) for P = ([p.sub.1], ..., [p.sub.n]).

1.1.3 Curves

A curve is the image of a continuous map [gamma] : [a, b] [right arrow] [R.sup.d]. The map [gamma] is called a parameterization of the curve. We usually identify a parameterization with the curve it defines. Without loss of generality, any curve can be given a parametrization with a = 0 and b = 1. A curve connects the two points p and q if [gamma](0) = p and [gamma](1) = q. A curve [gamma]: [0, 1] [right arrow] [R.sup.d] is not self-intersecting if [gamma] is injective on (0, 1). A curve is closed if [gamma](0) = [gamma](1).

A set S [subset] [R.sup.d] is path connected if any two points in S can be joined by a curve. A set S [subset] X is simply connected if it is path connected and any not self-intersecting closed curve can be continuously deformed to a point in the set; that is, for any injective continuous map [gamma] : [0, 1] [right arrow] S that satisfies [gamma](0) = [gamma](1), there exist p [member of] S and a continuous map H : [0, 1] x [0, 1] [right arrow] S such that H(t, 0) = [gamma](t) and H(t, 1) = p for all t [member of] [0, 1]. Informally, a simply connected set is a set that consists of a single piece and does not have any holes.

Next, consider a piecewise continuously differentiable curve [gamma] : [0, 1] [right arrow] [R.sup.d]; the length of [gamma] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and its arc-length parameter is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that as the parameter t varies in [0, 1], the arc-length parameter [s.sub.arc](t) varies in [0, length([gamma])]. The arc-length parameterization of the curve is the map [[gamma].sub.arc] : [0, length([gamma])] [right arrow] [R.sup.d] defined by the equation [[gamma].sub.arc]([s.sub.arc](s)) = [gamma](s). With a slight abuse of notation, we will often drop the subindex arc and denote the arc-length parameterization by [gamma] too.

(Continues...)

Excerpted from Distributed Control of Robotic Networksby Francesco Bullo Jorge Corts Sonia Martnez Copyright © 2009 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.