Graph Theoretic Methods in Multiagent Networks (Princeton Applied Mathematics) - Hardcover

Mesbahi, Mehran; Egerstedt, Magnus

Hardcover

ISBN 10: 0691140618 ISBN 13: 9780691140612

Verlag: Princeton University Press, 2010

Inhaltsangabe

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

Über diesen Titel

Über die Autorin bzw. den Autor

Mehran Mesbahi is associate professor of aeronautics and astronautics at the University of Washington. Magnus Egerstedt is associate professor of electrical and computer engineering at Georgia Institute of Technology.

Von der hinteren Coverseite

"This well-organized book is an extensive and complete introduction to graph theoretic methods in the context of multiagent and multivehicle cooperative networks. The presentation of the material is elegant and in addition to basic results, the book includes new topics not commonly found in the literature. Ideal for graduate students and researchers, the book represents a significant contribution to the emerging field of cooperative control and consensus."--Randy Beard, Brigham Young University

"This comprehensive overview of multiagent coordination brings together the existing literature on the subject and presents it in a clean, pedagogical fashion. The book will be useful to those in the areas of control theory, signal processing, and related disciplines."--Ali Jadbabaie, University of Pennsylvania

"This book focuses on graph theoretic techniques in multiagent systems, with a strong emphasis on agreement problems. It covers a good selection of issues and will make a solid textbook for advanced courses in the field."--Richard Murray, California Institute of Technology

Aus dem Klappentext

"This well-organized book is an extensive and complete introduction to graph theoretic methods in the context of multiagent and multivehicle cooperative networks. The presentation of the material is elegant and in addition to basic results, the book includes new topics not commonly found in the literature. Ideal for graduate students and researchers, the book represents a significant contribution to the emerging field of cooperative control and consensus."--Randy Beard, Brigham Young University

"This comprehensive overview of multiagent coordination brings together the existing literature on the subject and presents it in a clean, pedagogical fashion. The book will be useful to those in the areas of control theory, signal processing, and related disciplines."--Ali Jadbabaie, University of Pennsylvania

"This book focuses on graph theoretic techniques in multiagent systems, with a strong emphasis on agreement problems. It covers a good selection of issues and will make a solid textbook for advanced courses in the field."--Richard Murray, California Institute of Technology

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Graph Theoretic Methods in Multiagent Networks

By Mehran Mesbahi Magnus Egerstedt

PRINCETON UNIVERSITY PRESS

Copyright © 2010 Princeton University Press
All right reserved.
ISBN: 978-0-691-14061-2

Contents

Preface.............................................................................xiNotation............................................................................xvPART 1. FOUNDATIONS.................................................................1Chapter 1. Introduction.............................................................3Chapter 2. Graph Theory.............................................................14Chapter 3. The Agreement Protocol: Part I-The Static Case...........................42Chapter 4. The Agreement Protocol: Part II-Lyapunov and LaSalle.....................72Chapter 5. Probabilistic Analysis of Networks and Protocols.........................90PART 2. MULTIAGENT NETWORKS.........................................................115Chapter 6. Formation Control........................................................117Chapter 7. Mobile Robots............................................................159Chapter 8. Distributed Estimation...................................................191Chapter 9. Social Networks, Epidemics, and Games....................................226PART 3. NETWORKS AS SYSTEMS.........................................................251Chapter 10. Agreement with Inputs and Outputs.......................................253Chapter 11. Synthesis of Networks...................................................293Chapter 12. Dynamic Graph Processes.................................................319Chapter 13. Higher-order Networks...................................................344Appendix A..........................................................................362Bibliography........................................................................379Index...............................................................................399

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 multiagent 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 animals and birds align themselves in swarms, schools, flocks, and herds. In the boids flocking model, each "agent," in this case a computer animated construct, is designed to react to its neighboring flockmates, following an ad hoc protocol consisting of three rules operating at different spatial scales. These rules are separation (avoid colliding with neighbors), alignment (align velocity with neighbors' velocities), and cohesion (avoid becoming isolated from neighbors). A special case of the boids model is one in which all agents move at the same constant speed and update their headings according to a nearest neighbor rule for group level alignment and cohesion. It turns out that based on such local interaction rules alone, velocity alignment and other types of flocking behaviors can be obtained. An example of the resulting behavior is shown in Figure 1.1.

1.2.2 Formation Flight

Distributed aerospace systems, such as multiple spacecraft, fleets of autonomous rovers, and formations of unmanned aerial vehicles, have been identified as a new paradigm for a wide array of applications. It is envisioned that distributed aerospace technologies will enable the implementation of a spatially distributed network of vehicles that collaborate toward a single collective scientific, military, or civilian goal. These systems are of great interest since their distributed architecture promises a significant cost reduction in their design, manufacturing, and operation. Moreover, distributed aerospace systems lead to higher degrees of scalability and adaptability in response to changes in the mission goals and system capabilities.

An example of a multiple platform aerospace system is space-borne optical interferometry. Space interferometers are distinguished by their composition and operational environment. They are composed of separated optical instruments, leading to a so-called sparse aperture. Although optical interferometers can, in principle, function on the earth's surface, there are many advantages in operating them in space. Space-borne interferometers have greater optical sensitivity and resolution, wider field of view, and greater detection capability. The resolution of these interferometers, as compared with space telescopes (e.g., Hubble), is dictated by the separation between the...

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2010
• Sprache: Englisch
• ISBN 10: 0691140618
• ISBN 13: 9780691140612
• Einband: Gebundene Ausgabe
• Anzahl der Seiten: 403
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Nicht verfügbar