Distributed Control of Robotic Networks

A Mathematical Approach to Motion Coordination Algorithms

The entire book is freely available for download. The latest version of the book is from March 10, 2009


You are allowed to freely download, share, print, or photocopy the book.

You are not allowed to modify, sell, or claim authorship of any part of the book.

We thank you for any feedback information, including suggestions, evaluations, error descriptions, or comments about teaching or research uses


Book contents

Chapter 1: An introduction to distributed algorithms [PDF]

  • Elementary concepts and notation

    • Distance functions

    • Matrix theory

  • State machines and dynamical systems

    • Stability and attractivity notions

    • Invariance principles

    • Notions and results for set-valued systems

    • Notions and results for time-dependent systems

  • Graph theory

    • Connectivity notions

    • Weighted digraphs

    • Distances on digraphs and weighted digraphs

    • Graph algorithms

    • Algebraic graph theory

  • Distributed algorithms on synchronous networks

    • Physical components and computational models

    • Complexity notions

    • Broadcast and BFS tree computation

    • Leader election

    • Shortest-paths tree computation

  • Linear distributed algorithms

    • Linear iterations on synchronous networks

    • Averaging algorithms

    • Convergence speed of averaging algorithms

    • Algorithms defined by tridiagonal Toeplitz and tridiagonal circulant matrices

  • Notes

  • Proofs

  • Exercises

Chapter 2: Geometric models and optimization [PDF]

  • Basic geometric notions

    • Polygons and polytopes

    • Nonconvex geometry

    • Geometric centers

    • Voronoi and range-limited Voronoi partitions

  • Proximity graphs

    • Spatially distributed proximity graphs

    • Proximity graphs over tuples of points

    • Spatially distributed maps

  • Geometric optimization problems and multicenter functions

    • Expected-value multicenter functions

    • Worst-case and disk-covering multicenter functions

    • Sphere-packing multicenter functions

  • Notes

  • Proofs

  • Exercises

Chapter 3: Robotic network models and complexity notions [PDF]

  • A model for synchronous robotic networks

    • Physical components

    • Control and communication laws

    • Agree and pursuit control and communication law

  • Robotic networks with relative sensing

    • Kinematics notions

    • The physical components

    • Relative-sensing control laws

    • Equivalence between communication and relative-sensing laws

  • Coordination tasks and complexity notions

    • Coordination tasks

    • Complexity notions

    • Invariance under rescheduling

  • Complexity of direction agreement and equidistance

  • Notes

  • Proofs

  • Exercises

Chapter 4: Connectivity maintenance and rendezvous [PDF]

  • Problem statement

  • Connectivity maintenance algorithms

    • Enforcing range-limited links

    • Enforcing network connectivity

    • Enforcing range-limited line-of-sight links and network connectivity

  • Rendezvous algorithms

    • Averaging control and communication law

    • Circumcenter control and communication laws

    • Correctness and complexity of circumcenter laws

    • Circumcenter law in nonconvex environments

  • Simulation results

  • Notes

  • Proofs

  • Exercises

Chapter 5: Deployment [PDF]

  • Problem statement

  • Deployment algorithms

    • Geometric-center laws

    • Geometric-center laws with range-limited interactions

    • Correctness and complexity of geometric-center laws

  • Simulation results

  • Notes

  • Proofs

  • Exercises

Chapter 6: Boundary estimation and tracking [PDF]

  • Event-driven asynchronous robotic networks

  • Problem statement

    • Linear interpolations for boundary estimation

    • Network model and boundary estimation task

  • Estimate update and cyclic balancing law

    • Single-robot estimate update law

    • Cooperative estimate update law

    • Cyclic balancing algorithm for equidistance task

    • Correctness of the estimate update and cyclic balancing law

  • Simulations results

  • Notes

  • Proofs

  • Exercises

References [PDF]

Indices [PDF]