Graph Theoretic Methods in Multiagent Networks

Mehran Mesbahi, Magnus Egerstedt

• Publisher: Princeton University Press
• Year: 2010
• ISBN:
  9781400835355
• Topic: Matemáticas
• Subtopic: Matemática aplicada

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

PART 1
FOUNDATIONS

Chapter One

Introduction

“If a man writes a book,
let him set down only what he knows.
I have guesses enough of my own.” — Goethe

In this introductory chapter, we provide a brief discussion of networked multiagent systems and their importance in a number of scientific and engineering disciplines. We particularly focus on some of the theoretical challenges for designing, analyzing, and controlling multiagent robotic systems by focusing on the constraints induced by the geometric and combinatorial characters of the information-exchange mechanism.

1.1 HELLO, NETWORKED WORLD

Network science has emerged as a powerful conceptual paradigm in science and engineering. Constructs and phenomena such as interconnected networks, random and small-world networks, and phase transition nowadays appear in a wide variety of research literature, ranging across social networks, statistical physics, sensor networks, economics, and of course multi-agent coordination and control. The reason for this unprecedented attention to network science is twofold. On the one hand, in a number of disciplines-particularly in biological and material sciences-it has become vital to gain a deeper understanding of the role that inter-elemental interactions play in the collective functionality of multilayered systems. On the other hand, technological advances have facilitated an ability to synthesize networked engineering systems-such as those found in multivehicle systems, sensor networks, and nanostructures-that resemble, sometimes remotely, their natural counterparts in terms of their functional and operational complexity.

A basic premise in network science is that the structure and attributes of the network influence the dynamical properties exhibited at the system level. The implications and utility of adopting such a perspective for engineering networked systems, and specifically the system theoretic consequences of such a point of view, formed the impetus for much of this book.¹

1.2 MULTIAGENT SYSTEMS

Engineered, distributed multiagent networks, such as distributed robots and mobile sensor networks, have posed a number of challenges in terms of their system theoretic analysis and synthesis. Agents in such networks are required to operate in concert with each other in order to achieve system-level objectives, while having access to limited computational resources and local communications and sensing capabilities. In this introductory chapter, we first discuss a few examples of such distributed and networked systems, such as multiple aerospace vehicles, sensor networks, and nanosystems. We then proceed to outline some of the insights that a graph theoretic approach to multiagent networks is expected to provide, before offering a preview of the book’s content.

1.2.1 Boids Model

The Reynolds boids model, originally proposed in the context of computer graphics and animation, illustrates the basic premise behind a number of multiagent problems, in which a collection of mobile agents are to collectively solve a global task using local interaction rules. This model attempts to capture the way social ...