Graph Theoretic Methods in Multiagent Networks - Rilegato

Mesbahi, Mehran; Egerstedt, Magnus

Rilegato

ISBN 10: 0691140618 ISBN 13: 9780691140612

Casa editrice: Princeton Univ Pr, 2010

Riassunto

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

Su questo libro

Informazioni sull?autore

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.

Dalla quarta di copertina

"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

Dal risvolto di copertina interno

"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

Estratto. © Ristampato con autorizzazione. Tutti i diritti riservati.

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 light collecting elements (called the baseline) rather than their size. Consequently, as the achievable imaging resolution of a space telescope is dictated by advanced manufacturing techniques, the size of the launch vehicle, and the complex deployment mechanism, the capability of a space-borne optical interferometer is limited by how accurately the operation of separated optical elements can be coordinated. These space-borne optical interferometers can be mounted on a single large space structure, composed of rigid or semirigid trusses or even inflatable membranes. In this case, the structural dynamics of the spacecraft plays a major role in the operation and the success of the mission. An alternate approach is to fly the interferometer on multiple physically separated spacecraft, that is, a distributed space system. An example of such a mission is the Terrestrial Planet Finder (TPF) shown in Figure 1.2.

Another important set of applications of networked aerospace systems is found in the area of unmanned aerial vehicles of various scales and capabilities. These vehicle systems provide unique capabilities for a number of mission objectives, including surveillance, synthetic aperture imaging, mapping, target detection, and environmental monitoring.

1.2.3 Sensor Networks

A wireless sensor network consists of spatially distributed autonomous devices that cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, or pressure. Each node in a sensor network is equipped with a wireless communication device as well as an energy source-such as a battery-that needs to be efficiently utilized. The size, cost, and fidelity of a single sensor node can vary greatly, often in direct correspondence with its energy use, computational speed, and the ease by which it can be integrated within the network. Each sensor exchanges information on its local measurements with other nodes in the network in order to reach an accurate estimate of the physical or environmental variable of interest. We note that the efficiency requirement on the utilization of the energy source for each sensor often dictates a geometry on the internode communication for the sensor network.

1.2.4 Nanosystems

Recently, there has been a surge of interest by material scientists in organic compounds that are interconvertible via chemical reactions; this process is often referred to as tautomerization. These chemical reactions can be used for constructing molecular switches, where a molecule is steered between two or more stable states in a controlled fashion. Other electronic components such as diodes and transistors can be made that rely on similar induced transitions between structural isomers. Such molecular devices can then be put together, leading to the possibility of designing molecular circuits, networks, and more generally, molecular dynamic systems. An example of a molecular switch is a hydrogen tautomerization employed to manipulate and probe a naphthalocyanine molecule via low-temperature scanning tunneling microscopy. The properties and functionality of the corresponding molecular machines and networks are highly dependent on the inter-molecular bonds that can generally be manipulated by techniques such as electron beam lithography and molecular beam epitaxy.

1.2.5 Social Networks

Social networks are comprised of social entities, such as individuals and organizations, with a given set of interdependencies. The interaction between these entities can assume a multitude of relations, such as financial, social, and informational. Such networks are of great interest in a variety of fields, including theoretical sociology, organizational studies, and sociolinguistics. In fact, the structure of social networks has always been of fundamental importance for understanding these networks. More recently, the notion of manipulating the network structure has been contemplated as a viable means of altering the network behavior. For example, the concept of a change agent refers to a network entity that intentionally or indirectly causes or accelerates social, cultural, or behavioral change in the network.

1.2.6 Energy Networks

Complex, large-scale energy systems, delivering electrical and mechanical energy from generators to loads via an intricate distribution network, are among the most useful engineered networked dynamic systems. These systems often consist of a heterogeneous set of dynamic systems, such as power electronics and switching logics, that evolve over multiple timescales. Dynamics, stability, and control of individual power system elements (e.g., synchronous machines) or their interconnections (e.g., multi-machine models) have extensively been examined in the literature. However, as the need for more efficient generation and utilization of energy has become prevalent, distributed and network architectures such as the "smart grid" have gained particular prominence.

1.2.7 The Common Thread

The examples above, sampled from distinct disciplines, share a set of fundamental system theoretic attributes with a host of other networked multiagent systems. In a nutshell, such systems consist of (1) dynamic units, potentially with a decision making capability and means by which they can receive and transmit information among themselves, and (2) a signal exchange network, which can be realized via wired or wireless protocols in engineering, biochemical reactions in biological systems, and psychological and sociological interactions in the context of social networks.

The fundamental feature of networked systems, distinguishing them from systems that have traditionally been considered in system theory, is the presence of the network and its influence on the behavior of the overall system. Consequently, a successful "system theory for networked systems" has to blend the mathematics of information networks with paradigms that are at the core of dynamic system theory (stability, controllability, optimality, etc.). One of the challenging aspects facing such an interdisciplinary marriage in the context of system theory is that many network properties, for example, the network geometry, have a logical or combinatorial character.

1.3 INFORMATION EXCHANGE VIA LOCAL INTERACTIONS

In order to have a concrete model of "local interactions," in this section, we delineate the local nature of information exchange mechanisms for robotic networks.

1.3.1 Locality in Communication

One way in which agents can share information with their surroundings is through communication channels. But transmitting and receiving information requires energy, which is typically a sparse commodity in many networked applications, such as sensor networks and mobile ad hoc communication networks. Hence, only agents within a limited communication range can exchange information directly, forcing information to propagate through the network over intermediary nodes. Another communication constraint pertains to the available bandwidth. If a large collection of agents simultaneously broadcast large amounts of data, the communication channels saturate and lead to sharp deterioration of the communication system. Thus, in large networks, the information exchange should be maintained and kept parsimonious in order to satisfy the bandwidth limitations.

1.3.2 Locality in Sensing

Direct communications aside, agents can also infer information about each other and their environment through sensors. But every sensor has its own limitations in terms of range and resolution. Some of the most common sensors and their corresponding constraints are:

Vision-based sensors: Cameras typically have long effective range (at least monocular vision), but they cover only a particular wedge-shaped region, as seen in Figure 1.3(a).

Range sensors: The most common range sensors include sonars, infrared sensors, and laser scanners. These range sensors have very different sensing resolutions, ranging from very short range (e.g., low-cost infrared sensors) to covering hundreds of meters (e.g., high-quality laser-scanners). These sensors emit rays along a single direction but are typically ring-mounted to provide omnidirectional sensing capabilities (e.g., sonar and infrared rings) or have moving mirrors to provide scans across a larger area (e.g., laser scanners). This is shown in Figure 1.3(b).

A number of other sensing modalities are also widely used, with their own geometric constraints, as seen in Figure 1.3(c - d). However, as will be discussed throughout this book, this geometry will be subsumed by a graph theoretic interpretation of interactions as edges in the so-called proximity graphs, in which the existence of an edge indicates that neighboring nodes are within sensing range of each other.

1.4 GRAPH-BASED INTERACTION MODELS

The interaction geometry will indeed play an important role in the analysis and synthesis of networked multiagent systems regardless of whether the information exchange takes place over a communication network or through active sensing, or for that matter whether it assumes a wireless, chemical, physical, or sociological character. It turns out, however, that making the interaction protocol and its geometry explicit in the system-level analysis and control synthesis is far from trivial. In this direction, it becomes judicious to treat interactions as essentially combinatorial-at least initially-to codify whether an interaction exists and to what degree. An example of this abstraction is seen in Figure 1.4, in which the interaction geometry is defined by omnidirectional range sensors. As we will see throughout this book, such an abstraction, which cuts through the particular realization of the interaction, allows us to highlight the role of the interconnection topology, not only in the analysis of these systems but also in their synthesis.

1.4.1 Static, Dynamic, and Random Networks

If the edges in graphs are to be interpreted as enabling information to flow between the vertices on the corresponding edge, these flows can be directed as well as undirected. In other words, it is possible that the information will flow only in one direction. This would, for example, be the case if the vertices correspond to sensor agents, and agent i can sense agent j, while agent j can not sense agent i, for instance, due to different sensing modalities. In that case, the edge would be directed, with [v.sub.j] as its "tail" and [v.sub.i] as its "head." We will pictorially depict this as an arrow originating from [v.sub.j] and ending at [v.sub.i]. If the edge is undirected, we will simply drop the arrow and draw the edge as a line between the vertices.

(Continues...)

Excerpted from Graph Theoretic Methods in Multiagent Networksby Mehran Mesbahi Magnus Egerstedt Copyright © 2010 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Dettagli dell'edizione

• Editore: Princeton Univ Pr
• Data di pubblicazione: 2010
• Lingua: Inglese
• ISBN 10: 0691140618
• ISBN 13: 9780691140612
• Rilegatura: Copertina rigida
• Numero di pagine: 403
• Contatto del produttore: non disponibile
• Persona responsabile: non disponibile