Chapter 1
Introduction

1.1 Background

1.1.1 Networked Multi-agent Systems

Most large-scale systems in nature and human societies, such as biological neural networks, ecosystems, metabolic pathways, the Internet, the WWW, and electrical power grids can be described by networks with nodes representing individuals in the system and edges representing the connections between them. Recently, the study of various complex networks and systems has attracted increasing attention from researchers in various fields of physics, mathematics, engineering, biology, and sociology alike [8, 35, 62, 90, 117-119, 123, 142].

In the early 1960s, Erdös and Rényi (ER) proposed a random-graph model, which laid a solid foundation for modern network theory [35]. In a random network, each pair of nodes is connected with a certain probability. In order to describe a transition from a regular network to a random network, Watts and Strogatz (WS) proposed an interesting small-world network model [123]. Then, Newman and Watts (NW) modified the original WS model to generate another version of the small-world model [80]. Meanwhile, Barabási and Albert (BA) proposed a scale-free network model, in which the degree distribution of the nodes follows a power-law form [8]. Since then, small-world and scale-free networks have been extensively investigated worldwide.

Cooperative and collective behaviors in networks of multiple autonomous agents have also received considerable attention in recent years due to the growing interest in understanding the amazing animal group behaviors, such as flocking and swarming, and also due to their emerging broad applications in sensor networks, UAV (unmanned air vehicles) formations, and robotic teams. To coordinate with other agents in a network, every agent needs to share information with its adjacent peers so that all can agree on a common goal of interest, such as the value of some measurement in a sensor network, the heading in a UAV formation, or the target position of a robotic team.

Recently, some progress has been made in analyzing cooperative control for collective behaviors in dynamical multi-agent systems, for which some closely related focal topics are synchronization [90, 117, 118, 142], consensus [15, 57, 77, 81, 98, 99, 101, 115], swarming [44, 45], and flocking [82]. More details can be found in survey papers [4, 17, 84, 120].

1.1.2 Collective Behaviors and Cooperative Control in Multi-agent Systems

Synchronization is a typical collective behavior in nature. Since the pioneering work of Pecora and Carroll [90], chaos control and synchronization have received a great deal of attention due to their potential applications in secure communications, chemical reactions, biological systems, and so on [143, 145]. Typically, there are large numbers of nodes in real-world complex networks. In recent years, a lot of work has been devoted to the study of synchronization in various large-scale complex networks [14, 70, 117, 118, 142]. In [117, 118], local synchronization was investigated by the transverse stability to the synchronization manifold, where synchronization was discussed on small-world and scale-free networks. In [132, 134], a distance from the collective states to the synchronization manifold was defined, and based on this, some results were obtained for global synchronization of coupled systems [14, 70]. A general criterion was derived in [142], where the network sizes can be extended to be much larger than those given in [14, 70]. However, it is still very difficult to ensure global synchronization in general large-scale networks due to the computational complexity. Recently, global pinning synchronization for a class of complex networks with switched topologies was addressed in [130] by using tools from stability analysis of switched systems.

The consensus problem has a long history in the field of computer science especially for distributed computing [74]. The idea of consensus was originated from statistical consensus theory by DeGroot [28], which was revisited two decades later for pattern recognition using multi-sensors [10]. Usually, it refers to the problem of how to reach agreement among a group of autonomous agents in a dynamically changing environment [99]. One of the main challenges in solving such a consensus problem is that an agreement has to be reached by all agents in the whole dynamic network while the information of each agent is shared only locally. Various models have been used to study the consensus problem. Vicsek et al. studied a discrete-time system that models a group of autonomous agents moving in the plane with the same speed but different headings [115]. It was shown, through simulation, that using a distributed averaging rule, agents could eventually move in the same direction without centralized coordination. Vicsek's model by nature is a simplified version of the model proposed earlier by Reynolds [101]. Analysis on Vicsek's model, or its continuous-time version, shows that the connectivity of the time-varying graph that describes the neighboring relationships within the group is key in achieving consensus [15, 57, 81, 77, 98]. In particular, in [81], Olfati-Saber and Murray established the relationship between the algebraic connectivity (also called the Fiedler eigenvalue [37]) and the speed of convergence when the underlying directed graph is balanced. A broader class of directed graphs that may lead to reaching consensus are those that contain spanning trees [98], which are also called rooted graphs [15].

It is interesting to observe that Vicsek's model is similar to a class of models discussed in synchronization of complex networks [14, 70, 117, 118, 134, 142]. In 1998, Pecora and Carroll made use of a master stability function to study the synchronization of coupled complex networks [90]. To date, stability and synchronization of small-world and scale-free networks have been investigated extensively using this master stability function method.

In the literature, most work on the consensus problem considered the case where agents are governed by first-order dynamics [11, 57, 72, 81, 98, 114, 134, 141, 142, 151]. Meanwhile, there is a growing interest in consensus algorithms where all agents are governed by second-order dynamics [50, 51, 82, 93, 95, 97, 146]. More precisely, second-order consensus refers to the problem of reaching an agreement among a group of autonomous agents governed by second-order dynamics. A detailed analysis of second-order consensus algorithms is a key step to bring more realistic dynamics into the model of each individual agent based on the general framework of multi-agent systems, thus it can help control engineers to implement distributed cooperative control strategies for networked multi-agent systems. It has been shown that, in sharp contrast to the first-order consensus problem, consensus may fail to be achieved for agents with second-order dynamics even if the network topology has a directed spanning tree [97].

On the other hand, time delay is ubiquitous in biological, physical, chemical, and electrical systems [11, 114]. In biological and communication networks, time delays are usually inevitable due to the possibly slow process of interactions among agents. It has been observed from numerical experiments that consensus algorithms without considering time delays may lead to unexpected instability. In [11, 114], some sufficient conditions were derived for first-order consensus in delayed multi-agent systems.

Very recently, some higher-order consensus algorithms in cooperative control of multi-agent systems were studied, such as in [100] based on the results derived in [97]. However, only third-order consensus was discussed in detail therein. In this book, a general higher-order consensus protocol is designed and analyzed based on the transverse stability to the consensus manifold, which originates from the study of synchronization in complex networks [117]. A detailed analysis of the higher-order consensus algorithms is a prerequisite to introducing more realistic dynamics into the model of each individual agent.

As validated by biological field studies and engineering robotic experiments, swarm cohesion can be achieved in a distributed fashion despite the fact that each agent may only have local information about its nearest neighbors. An in-depth understanding of the principles behind swarming behaviors will help engineers to develop distributed cooperative control strategies and algorithms for networked dynamical systems, such as formations of UAVs, autonomous robotic teams, and mobile sensors networks. Synchronous distributed coordination rules for swarming groups in one- or two-dimensional spaces were studied in [58], where convergence and stability analysis were given. In [44, 45], stability properties of a continuous-time model for swarm aggregation in the -dimensional space was discussed, and an asymptotic bound for the spatial size of the swarm was computed using the parameters of the swarm model.

In [101], three heuristic rules were suggested by Reynolds to animate flocking behavior: (1) velocity consensus, (2) center cohesion, and (3) collision avoidance. In order to embody the three Reynolds' rules, Tanner et al. designed flocking algorithms in [110, 111], where a collective potential function and a velocity consensus term were introduced. Later, in [82], Olfati-Saber proposed a general framework to investigate distributed flocking algorithms where, in particular, three algorithms were developed for free and constrained flocking. In [110, 111], it was pointed out that due to the time-varying network topology, the set of differential equations...