Flocking Control of Multiple Mobile Agents with the Rules of Avoiding Collision

This paper investigates the flocking and the coordinative control problems of multiple mobile agents with the rules of avoiding collision. We propose a set of control laws using hysteresis in adding new links and applying new potential function to guarantee that the fragmentation of the network can be avoided, under which all agents approach a common velocity vector, and asymptotically converge to a fixed value of interagent distances and collisions between agents can be avoided throughout the motion. Furthermore, we extend the flocking algorithm to solve the flocking situation of the group with a virtual leader agent. The laws can make all agents asymptotically approach the virtual leader and collisions can be avoided between agents in the motion evolution. Finally, some numerical simulations are showed to illustrate the theoretical results.

Related papers:

title: Robust connectivity of networked vehicles
abstract: We present a simple geometric analysis of wireless connectivity in vehicle networks. We introduce a localized notion of connectedness, and construct a function that measures the robustness of this local connectedness to variations in position. Under a mild feasibility hypothesis, this function provides a sufficient condition for global connectedness of the network. Further, it is distributed, in the sense that both the function and its gradients can be calculated using only neighbor-to-neighbor communications. It can thus form the basis for distributed motion-control algorithms which respect connectivity constraints. We conclude with two simple examples of target applications.

title: Flocks, herds and schools: A distributed behavioral model
abstract: The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar part of the natural world. But this type of complex motion is rarely seen in computer animation. This paper explores an approach based on simulation as an alternative to scripting the paths of each bird individually. The simulated flock is an elaboration of a particle systems, with the simulated birds being the particles. The aggregate motion of the simulated flock is created by a distributed behavioral model much like that at work in a natural flock; the birds choose their own course. Each simulated bird is implemented as an independent actor that navigates according to its local perception of the dynamic environment, the laws of simulated physics that rule its motion, and a set of behaviors programmed into it by the "animator." The aggregate motion of the simulated flock is the result of the dense interaction of the relatively simple behaviors of the individual simulated birds.

title: Flocking for multi-agent dynamic systems: algorithms and theory
abstract: In this paper, we present a theoretical framework for design and analysis of distributed flocking algorithms. Two cases of flocking in free-space and presence of multiple obstacles are considered. We present three flocking algorithms: two for free-flocking and one for constrained flocking. A comprehensive analysis of the first two algorithms is provided. We demonstrate the first algorithm embodies all three rules of Reynolds. This is a formal approach to extraction of interaction rules that lead to the emergence of collective behavior. We show that the first algorithm generically leads to regular fragmentation, whereas the second and third algorithms both lead to flocking. A systematic method is provided for construction of cost functions (or collective potentials) for flocking. These collective potentials penalize deviation from a class of lattice-shape objects called /spl alpha/-lattices. We use a multi-species framework for construction of collective potentials that consist of flock-members, or /spl alpha/-agents, and virtual agents associated with /spl alpha/-agents called /spl beta/- and /spl gamma/-agents. We show that migration of flocks can be performed using a peer-to-peer network of agents, i.e., "flocks need no leaders." A "universal" definition of flocking for particle systems with similarities to Lyapunov stability is given. Several simulation results are provided that demonstrate performing 2-D and 3-D flocking, split/rejoin maneuver, and squeezing maneuver for hundreds of agents using the proposed algorithms.

title: Second-order consensus of multiple agents with coupling delay
abstract: In this paper, we investigate two kinds of second-order consensus algorithms for multiple agents with coupling delay under general fixed directed information topology. Stability analysis is performed based on Lyapunov-Krasovskii functional method. Delay-dependent asymptotical stability condition in terms of linear matrix inequalities (LMIs) is derived for the second-order consensus algorithm of delayed dynamical networks. Both delay-independent and delay-dependent asymptotical stabilities conditions in terms of LMIs are derived for the second-order consensus algorithm with information feedback.

title: Adaptive second-order consensus of networked mobile agents with nonlinear dynamics
abstract: We investigate second-order consensus of multiple nonlinear dynamical mobile agents with a virtual leader in a dynamic proximity network. We assume that only a small fraction of agents in the group have access to the information about the position and velocity of the virtual leader through, for example, certain pre-designed communication mechanism such as wireless broadcasting or sensing. To avoid fragmentation, we propose a connectivity-preserving second-order consensus algorithm. Under the assumption that the initial network is connected, we introduce local adaptation strategies for both the weights on the velocity navigational feedback and the velocity coupling strengths that enable all agents to synchronize with the virtual leader even when only one agent is informed, without requiring any knowledge of the agent dynamics. We finally provide some convincing simulation results to illustrate the theoretical results.

title: Neural-Network-Based Adaptive Leader-Following Control for Multiagent Systems With Uncertainties
abstract: A neural-network-based adaptive approach is proposed for the leader-following control of multiagent systems. The neural network is used to approximate the agent's uncertain dynamics, and the approximation error and external disturbances are counteracted by employing the robust signal. When there is no control input constraint, it can be proved that all the following agents can track the leader's time-varying state with the tracking error as small as desired. Compared with the related work in the literature, the uncertainty in the agent's dynamics is taken into account; the leader's state could be time-varying; and the proposed algorithm for each following agent is only dependent on the information of its neighbor agents. Finally, the satisfactory performance of the proposed method is illustrated by simulation examples.

title: Path tracking control of Lagrange systems with obstacle avoidance
abstract: This paper addresses a path tracking problem with obstacle avoidance for Lagrange systems. The proposed method is based on field potential methods in combination with navigation functions for obstacle avoidance. First, it is shown that a simple combination of the navigation function with the conventional path tracking controller does not work. Therefore, in order to cope with this problem, a new feedback law is proposed for a path parameter which characterizes the reference path. It is proved that the proposed controller achieves both path following and collision avoidance. Moreover, since the method adopts bounded navigation functions, the proposed controllers generate bounded input signals even when target systems approach obstacles. Finally, an experimental evaluation is performed with a two-link manipulator to illustrate the effectiveness of the proposed method.

title: Adaptive flocking with a virtual leader of multiple agents governed by locally Lipschitz nonlinearity
abstract: This paper investigates adaptive flocking of multi-agent systems (MASs) with a virtual leader. All agents and the virtual leader share the same intrinsic nonlinear dynamics, which satisfies a locally Lipschitz condition and depends on both position and velocity information for the agent itself. Under the assumption that the initial network is connected, an approach to preserving the connectivity of the network is proposed. On the basis of the Lyapunov stability theory, an adaptive flocking control law is derived, for making the MASs track the virtual leader without collision. Finally, a numerical example is presented to illustrate the effectiveness of the theoretical results.

title: On consensus algorithms for double-integrator dynamics
abstract: This paper extends some existing results in consensus algorithms for double-integrator dynamics. We propose consensus algorithms for double-integrator dynamics in four cases: (i) with a bounded control input, (ii) without relative velocity measurement, (iii) without relative velocity measurement in the presence of a group reference velocity, and (iv) with a bounded control input and with partial access to a group reference state. We show that consensus is reached asymptotically for the first two cases if the undirected interaction graph is connected. We further show that consensus is reached asymptotically for the third case if the directed interaction graph has a directed spanning tree and the gain for velocity matching with the group reference velocity is above a certain bound. We also show that consensus is reached asymptotically for the fourth case if and only if the group reference state flows directly or indirectly to all of the vehicles in the team.

title: On the use of correlation as a measure of network connectivity
abstract: Numerous studies have demonstrated that brain networks derived from neuroimaging data have nontrivial topological features, such as small-world organization, modular structure and highly connected hubs. In these studies, the extent of connectivity between pairs of brain regions has often been measured using some form of statistical correlation. This article demonstrates that correlation as a measure of connectivity in and of itself gives rise to networks with non-random topological features. In particular, networks in which connectivity is measured using correlation are inherently more clustered than random networks, and as such are more likely to be small-world networks. Partial correlation as a measure of connectivity also gives rise to networks with non-random topological features. Partial correlation networks are inherently less clustered than random networks. Network measures in correlation networks should be benchmarked against null networks that respect the topological structure induced by correlation measurements. Prevalently used random rewiring algorithms do not yield appropriate null networks for some network measures. Null networks are proposed to explicitly normalize for the inherent topological structure found in correlation networks, resulting in more conservative estimates of small-world organization. A number of steps may be needed to normalize each network measure individually and control for distinct features (e.g. degree distribution). The main conclusion of this article is that correlation can and should be used to measure connectivity, however appropriate null networks should be used to benchmark network measures in correlation networks.

title: Distributed Coordinated Tracking With Reduced Interaction via a Variable Structure Approach
abstract: A distributed coordinated tracking problem is solved via a variable structure approach when there exists a dynamic virtual leader who is a neighbor of only a subset of a group of followers, all followers have only local interaction, and only partial measurements of the states of the virtual leader and the followers are available. In the context of coordinated tracking, we focus on both consensus tracking and swarm tracking algorithms. In the case of first-order kinematics, we propose a distributed consensus tracking algorithm without velocity measurements under both fixed and switching network topologies. In particular, we show that distributed consensus tracking can be achieved in finite time. The algorithm is then extended to achieve distributed swarm tracking without velocity measurements. In the case of second-order dynamics, we first propose two distributed consensus tracking algorithms without acceleration measurements when the velocity of the virtual leader is varying under, respectively, a fixed and switching network topology. In particular, we show that the proposed algorithms guarantee at least global exponential tracking. We then propose a distributed consensus tracking algorithm and a distributed swarm tracking algorithm when the velocity of the virtual leader is constant. When the velocity of the virtual leader is varying, distributed swarm tracking is solved by using a distributed estimator. For distributed consensus tracking, a mild connectivity requirement is proposed by adopting an adaptive connectivity maintenance mechanism in which the adjacency matrix is defined in a proper way. Similarly, a mild connectivity requirement is proposed for distributed swarm tracking by adopting a connectivity maintenance mechanism in which the potential function is defined in a proper way. Several simulation examples are presented as a proof of concept.

title: Flocking while preserving network connectivity
abstract: Coordinated motion of multiple agents raises fundamental and novel problems in control theory and robotics. In particular, in applications such as consensus seeking or flocking by a group of mobile agents, a great new challenge is the development of robust distributed motion algorithms that can always achieve the desired coordination. In this paper, we address this challenge by embedding the requirement for connectivity of the underlying communication network in the controller specifications. We employ double integrator models for the agents and design nearest neighbor control laws, based on potential fields, that serve a twofold objective. First, they contribute to velocity alignment in the system and second, they regulate switching among different network topologies so that the connectivity requirement is always met. Collision avoidance among neighboring agents is also ensured and under the assumption that the initial network is connected, the overall system is shown to asymptotically flock for all initial conditions. In particular, it is shown that flocking is achieved even in sparse communication networks where connectivity is more prone to failure. We conclude by illustrating a class of interesting problems that can be achieved while preserving connectivity.

title: Rendezvous of multiple mobile agents with preserved network connectivity
abstract: In coordinative control of a network of multi-agent systems, to guarantee the stability of the coordinated motion, a basic assumption typically is that the underlying topology of the network can maintain its connectivity frequently enough during the motion evolution. However, for a given set of initial conditions, this assumption is very difficult to satisfy and verify. In particular, the connectivity of the initial network generally cannot guarantee the connectivity of the network throughout the evolution. In this paper, we propose a rendezvous protocol with double-integrator dynamics, which combines the functions of motion control and connectivity preservation. This protocol can enable the group of mobile agents to converge to the same position and move with the same velocity while preserving the connectivity of the whole network during the evolution if the initial network is connected. We find that there is a trade-off between the maximum overshoot and the settling time of the velocity convergence. Furthermore, we investigate the rendezvous protocol with a virtual leader and show that all agents can asymptotically attain a desired velocity even if only one agent in the team has information about the virtual leader. We finally show some numerical simulations to verify and illustrate the theoretical results.

title: Distributed Coordination Control of Multiagent Systems While Preserving Connectedness
abstract: This paper addresses the connectedness issue in multiagent coordination, i.e., the problem of ensuring that a group of mobile agents stays connected while achieving some performance objective. In particular, we study the rendezvous and the formation control problems over dynamic interaction graphs, and by adding appropriate weights to the edges in the graphs, we guarantee that the graphs stay connected.

title: Flocking of multiple autonomous agents with preserved network connectivity and heterogeneous nonlinear dynamics
abstract: This paper investigates a flocking problem of multiple agents with heterogeneous nonlinear dynamics. In order to avoid fragmentation, we construct a potential function and a connectivity-preserving flocking algorithm to enable the multiple agents to move with the same velocity while preserving the connectivity of underlying networks with a mild assumption that the initial network is connected and the coupling strength of the initial network of the nonlinear velocity consensus term is larger than a threshold value. Furthermore the proposed flocking algorithm is extended to solve the problem of multi-agent systems with a nonlinear dynamical virtual leader. The result is that all agents' velocities asymptotically approach to the velocity of the virtual leader, and the distance between any two agents is asymptotically stabilized to avoid collisions among agents. Finally, some numerical simulations are presented to illustrate the effectiveness of the theoretical results.

title: Decentralized Control of Connectivity for Multi-Agent Systems
abstract: In this paper we propose a decentralized algorithm to increase the connectivity of a multi-agent system. The connectivity property of the multi-agent system is quantified through the second smallest eigenvalue of the state dependent Laplacian of the proximity graph of agents. An exponential decay model is used to characterize the connection between agents. A supergradient algorithm is then used in conjunction with a recently developed decentralized algorithm for eigenvector computation to maximize the second smallest eigenvalue of the Laplacian of the proximity graph. A potential based control law is utilized to achieve the distances dictated by the supergradient algorithm. The algorithm is completely decentralized, where each agent receives information only from its neighbors, and uses this information to update its control law at each step of the iteration. Simulations demonstrate the effectiveness of the algorithm

title: Coordination of groups of mobile autonomous agents using nearest neighbor rules
abstract: Vicsek et al. proposed (1995) a simple but compelling discrete-time model of n autonomous agents {i.e., points or particles} all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors". In their paper, Vicsek et al. provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function.

title: Consensus problems in networks of agents with switching topology and time-delays
abstract: In this paper, we discuss consensus problems for networks of dynamic agents with fixed and switching topologies. We analyze three cases: 1) directed networks with fixed topology; 2) directed networks with switching topology; and 3) undirected networks with communication time-delays and fixed topology. We introduce two consensus protocols for networks with and without time-delays and provide a convergence analysis in all three cases. We establish a direct connection between the algebraic connectivity (or Fiedler eigenvalue) of the network and the performance (or negotiation speed) of a linear consensus protocol. This required the generalization of the notion of algebraic connectivity of undirected graphs to digraphs. It turns out that balanced digraphs play a key role in addressing average-consensus problems. We introduce disagreement functions for convergence analysis of consensus protocols. A disagreement function is a Lyapunov function for the disagreement network dynamics. We proposed a simple disagreement function that is a common Lyapunov function for the disagreement dynamics of a directed network with switching topology. A distinctive feature of this work is to address consensus problems for networks with directed information flow. We provide analytical tools that rely on algebraic graph theory, matrix theory, and control theory. Simulations are provided that demonstrate the effectiveness of our theoretical results.

title: Flocking of Multi-Agents With a Virtual Leader
abstract: All agents being informed and the virtual leader traveling at a constant velocity are the two critical assumptions seen in the recent literature on flocking in multi-agent systems. Under these assumptions, Olfati-Saber in a recent  This paper revisits the problem of multi-agent flocking in the absence of the above two assumptions. We first show that, even when only a fraction of agents are informed, the Olfati-Saber flocking algorithm still enables all the informed agents to move with the desired constant velocity, and an uninformed agent to also move with the same desired velocity if it can be influenced by the informed agents from time to time during the evolution. Numerical simulation demonstrates that a very small group of the informed agents can cause most of the agents to move with the desired velocity and the larger the informed group is the bigger portion of agents will move with the desired velocity. In the situation where the virtual leader travels with a varying velocity, we propose modification to the Olfati-Saber algorithm and show that the resulting algorithm enables the asymptotic tracking of the virtual leader. That is, the position and velocity of the center of mass of all agents will converge exponentially to those of the virtual leader. The convergent rate is also given.

title: Semi-Global Leader-Following Consensus of Linear Multi-Agent Systems With Input Saturation via Low Gain Feedback
abstract: This paper investigates the problem of leader-following consensus of a linear multi-agent system on a switching network. The input of each agent is subject to saturation. Low gain feedback based distributed consensus protocols are developed. It is established that, under the assumptions that each agent is asymptotically null controllable with bounded controls and that the network is connected or jointly connected, semi-global leader-following consensus of the multi-agent system can be achieved. Numerical examples are presented to illustrate this result.

title: Flocking Control of Groups of Mobile Autonomous Agents Via Local Feedback
abstract: This paper considers a group of mobile autonomous agents moving in Euclidean space with point mass dynamics. We introduce a set of coordination control laws that enable the group to generate the desired stable flocking motion. The control laws are a combination of attractive/repulsive and alignment forces. By using the control laws, all agent velocities asymptotically approach the desired velocity, collisions can be avoided between agents, and the final tight formation minimizes all agent potentials. Moreover, we prove that the velocity of the center of mass (CoM) either is equal to the desired velocity or exponentially converges to it. Finally, for the case that not all agents know the desired final velocity, we show that the desired flocking motion can still be guaranteed