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

Copyright

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

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

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

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

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

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

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