Graph Theoretic Methods in Multiagent Networks

✍ Scribed by Mehran Mesbahi; Magnus Egerstedt

• Publisher: Princeton University Press
• Year: 2010
• Tongue: English
• Leaves: 423
• Series: Princeton Series in Applied Mathematics; 33
• Edition: Course Book
• Category: Library

✦ Synopsis

This accessible book provides an introduction to the analysis and design of dynamic multiagent networks. Such networks are of great interest in a wide range of areas in science and engineering, including: mobile sensor networks, distributed robotics such as formation flying and swarming, quantum networks, networked economics, biological synchronization, and social networks. Focusing on graph theoretic methods for the analysis and synthesis of dynamic multiagent networks, the book presents a powerful new formalism and set of tools for networked systems.

The book's three sections look at foundations, multiagent networks, and networks as systems. The authors give an overview of important ideas from graph theory, followed by a detailed account of the agreement protocol and its various extensions, including the behavior of the protocol over undirected, directed, switching, and random networks. They cover topics such as formation control, coverage, distributed estimation, social networks, and games over networks. And they explore intriguing aspects of viewing networks as systems, by making these networks amenable to control-theoretic analysis and automatic synthesis, by monitoring their dynamic evolution, and by examining higher-order interaction models in terms of simplicial complexes and their applications.

The book will interest graduate students working in systems and control, as well as in computer science and robotics. It will be a standard reference for researchers seeking a self-contained account of system-theoretic aspects of multiagent networks and their wide-ranging applications.

This book has been adopted as a textbook at the following universities:
?

• University of Stuttgart, Germany


• Royal Institute of Technology, Sweden


• Johannes Kepler University, Austria


• Georgia Tech, USA


• University of Washington, USA


• Ohio University, USA

✦ Table of Contents

Contents
Preface
Notation
PART 1. FOUNDATIONS
Chapter 1. Introduction
1.1 Hello, Networked World
1.2 Multiagent Systems
1.3 Information Exchange via Local Interactions
1.4 Graph-based Interaction Models
1.5 Looking Ahead
Chapter 2. Graph Theory
2.1 Graphs
2.2 Variations on the Theme
2.3 Graphs and Matrices
2.4 Algebraic and Spectral Graph Theory
2.5 Graph Symmetries
Chapter 3. The Agreement Protocol: Part I–The Static Case
3.1 Reaching Agreement: Undirected Networks
3.2 Reaching Agreement: Directed Networks
3.3 Agreement and Markov Chains
3.4 The Factorization Lemma
Chapter 4. The Agreement Protocol: Part II–Lyapunov and LaSalle
4.1 Agreement via Lyapunov Functions
4.2 Agreement over Switching Digraphs
4.3 Edge Agreement
4.4 Beyond Linearity
Chapter 5. Probabilistic Analysis of Networks and Protocols
5.1 Random Graphs
5.2 Agreement over Random Networks
5.3 Agreement in the Presence of Noise
5.4 Other Probabilistic Models of Networks
PART 2. MULTIAGENT NETWORKS
Chapter 6. Formation Control
6.1 Formation Specification: Shapes
6.2 Formation Specification: Relative States
6.3 Shape-based Control
6.4 Relative State-based Control
6.5 Dynamic Formation Selection
6.6 Assigning Roles
Chapter 7. Mobile Robots
7.1 Cooperative Robotics
7.2 Weighted Graph-based Feedback
7.3 Dynamic Graphs
7.4 Formation Control Revisited
7.5 The Coverage Problem
Chapter 8. Distributed Estimation
8.1 Distributed Linear Least Squares
8.2 Pulsed Intercluster Communication
8.3 Implementation over Wireless Networks
8.4 Distributed Kalman Filtering
Chapter 9. Social Networks, Epidemics, and Games
9.1 Diffusion on Social Networks–The Max Protocol
9.2 The Threshold Protocol
9.3 Epidemics
9.4 The Chip Firing Game
PART 3. NETWORKS AS SYSTEMS
Chapter 10. Agreement with Inputs and Outputs
10.1 The Basic Input-Output Setup
10.2 Graph Theoretic Controllability: The SISO Case
10.3 Graph Theoretic Controllability: The MIMO Case
10.4 Agreement Reachability
10.5 Network Feedback
10.6 Optimal Control
Chapter 11. Synthesis of Networks
11.1 Network Formation
11.2 Local Formation Games
11.3 Potential Games and Best Response Dynamics
11.4 Network Synthesis: A Global Perspective
11.5 Discrete and Greedy
11.6 Optimizing the Weighted Agreement
Chapter 12. Dynamic Graph Processes
12.1 State-dependent Graphs
12.2 Graphical Equations
12.3 Dynamic Graph Controllability
12.4 What Graphs Can Be Realized?
12.5 Planning over Proximity Graphs
Chapter 13. Higher-order Networks
13.1 Simplicial Complexes
13.2 Combinatorial Laplacians
13.3 Triangulations and the Rips Complex
13.4 The Nerve Complex
Appendix A
A.1 Analysis
A.2 Matrix Theory
A.3 Control Theory
A.4 Probability
A.5 Optimization and Games
Bibliography
Index
A
B
C
D
E
F
G
H
I
K
L
M
N
O
P
Q
R
S
T
U
V