# Design of Connectivity Preserving Flocking Using Control Lyapunov Function

Authors: Bayu Erfianto; Riyanto T. Bambang; Hilwadi Hindersah; Intan Muchtadi-Alamsyah
Journal: Journal of Robotics
 (2016)

---

## Abstract

This paper investigates cooperative flocking control design with connectivity preserving mechanism. During flocking, interagent distance is measured to determine communication topology of the flocks. Then, cooperative flocking motion is built based on cooperative artificial potential field with connectivity preserving mechanism to achieve the common flocking objective. The flocking control input is then obtained by deriving cooperative artificial potential field using control Lyapunov function. As a result, we prove that our flocking protocol establishes group stabilization and the communication topology of multiagent flocking is always connected.


---

## Body

## 1. Introduction

Flocking in nature is a coordinated movement of group of living entities. Recently, flocking behavior has been adopted in a multiagent system to resemble collective movement of living system, for example, collective movement of group of multirobot system and autonomous vehicles. Those multiple agents together form a cooperative system to solve complex problems in distributed manner that is impossible to be carried out by a single agent.With respect to the literature of multiagent system, many theories denote that flocking model is built using three basic heuristic rules, that is, cohesion, separation, and velocity alignment, which is initiated for the first time by [1]. These three rules describe how an individual agent moves according to position and velocity of the nearest agents in flocks. Flocks always move together with velocity converging to the same value and guaranteeing no collision among agents.In multiagent robot, common flocking rule can further be described technically as centroid attraction, collision avoidance, and velocity alignment, respectively. Centroid attraction rule tries to pull the agent to stay close to the nearby agents in the flocks if the agents are moving away. Meanwhile, collision avoidance rule forces the agent to avoid collision with nearby agents in the flock, while velocity synchronization rule will drive the agents to synchronize their velocities while moving in the flock. The most notable flocking controllers are based on the works of Tanner et al. [2, 3] and Olfati-Saber [4]. Olfati-Saber [4] does not use flock centering rule to build flocking formation; instead of that he defines lattice formation to keep interagent distance.The synchronization of movement in flocking can be carried out through local or global communication, with explicit communication and without communication (stigmergic) as summarized in [5]. Erfianto et al. [6] have extended Reynold flocking protocol with explicit communication using broadcast gossip protocol, where the explicit communication of flocking is simulated in Netlogo multiagent simulator. By equipping mobile robot agent with communication capability, it means that flocking protocol is then restricted by communication capability. Previous research works on flocking algorithm are mostly based on the assumption that the network topology is always connected without any mechanism to achieve this circumstance.Network communication is mainly used to exchange information state between an agent and the nearby agents. Regarding this matter, the problem is that the initially connected network can not guarantee connectivity over the time during flock movement. Once disconnected, flock movement can be separated and that causes collective flocking goal not being achieved. Thus, it is important to prevent separation of the flock into multiple separate groups when the network is being disconnected. Regarding this issue, many kinds of research have been conducted to design flocking control input (flocking protocol) to ensure that the flocks achieve the collective goal while preserving connectedness during the movement. Connectivity preserving flocking of multiagent mobile robot then becomes a new trending area, and various flocking protocols have been proposed including both centralized and decentralized approaches, for example, presented in [7–9].Since connectivity of agents in flocking formation depends on its communication range, then the communication topology among agents can be connected or disconnected affected by the movement of an agent in flocks. The changes of signal power may also affect to the actual interagent distance since the distance is correspondingly perceived from measured signal power. Regarding this issue, a connectivity preserving mechanism is required to maintain connectivity during the flock movement. Fang et al. in [10] further divide connectivity preservation into two main categories, that is, conservative connectivity preservation and flexible connectivity preservation. In conservative connectivity preservation, the approach is to preserve all existing links; thus the network topology is strictly fixed, as presented in [7, 11, 12]. In flexible connectivity preservation approaches, the underlying communication topology is allowed to switch into different topologies, which means that edges are allowed to be added or removed from a node as long as the global graph topology is always connected. It is done by maintaining the spanning tree of the underlying network. Regarding these two approaches, therefore, the challenge is to design cooperative control law where it depends on the assumption that the underlying communication topology is connected over the time during the whole flocking evolution.Formation of flocking is commonly used in the various practical implementation of flocking protocol, such as in coverage control using multiagent mobile robot, a formation of multiple UAV, and cooperative mobile sensor networks, as well as cooperative mobile robot, for a surveillance system. Therefore, the design of formation flocking needs to consider navigation capability along with separation, cohesion, velocity alignment, and connectivity of a multiagent network.In this paper, our work is to preserve network connectivity by using an artificial potential function, where flocking protocol can also perform collision avoidance and obstacle avoidance function. The artificial potential function is then considered as control Lyapunov function candidate to be derived as continuous flocking control input. We also define the algebraic connectivity gradient controller and blend this gradient controller into flocking control input. This is the major difference of our work from [7, 9, 13, 14]. As a result, we conclude that, given the initially connected network, our flocking protocol can make all agents converge to a common velocity, collisions between agents, as well as between agent and obstacle, can be avoided, and the connectivity of underlying network can be preserved; thus the desired stable flocking behavior can be achieved.This paper is organized as follows. Section1 is the introduction of this paper. Section 2 of this paper is about problem definition to design connectivity preserving flocking. Section 3 discusses the design of artificial potential function that will be involved in control Lyapunov function. Flocking controller design is presented in Section 4, while the simulation to verify the controller is presented in Section 5.


## 2. Problem Formulation and Assumption

Let us consider a group of points of mobile robots that consists ofN robot agents moving in 2D space. The dynamic of mobile robot agent is modeled as(1)q˙i=pi,p˙i=ui,where q=q1T,q2T,…,qnTT∈R2 denotes position vector, where qij=qi-qj is the Euclidean distance between two agents, which is clearly qij≥0. Let pi∈R2 be the velocity vector and ui∈R2 be the control input of agent i, respectively.Assumption 1.
We assume that each agent obtains its position from sensors. Each agent is also equipped with a wireless communication network; therefore information state can be exchanged within the neighboring agents via a communication network.Regarding Assumption1, interaction among agents can further be modeled by bidirectional communication network, that is, undirected graph topology.Definition 2 (flocking topology).
Topology of a flock of robots is a dynamic undirected topology, denoted asG=V,E, that consists of(i)
node or verticesV=1,…,n;(ii)
set of edges or time varying communication linksE=i,j∈V×V∣qij≤R in which each undirected edge represents the communication between a pair of agents limited by communication range R;(iii)
set of neighborsNi=j∈V∣i,j∈E with symmetric property i∈Nj↔j∈Ni.Without loss of generality, each agent is strictly not self-communicating agenti,j∉E. Regarding Definition 2, interagent communication can then be constructed by adjacency matrix A∈RN×N, with element(2)aij=1ifqij≤R0otherwise,where qij is the Euclidean distance between two agents, and each agent is supposed to have the same communication radius R. Some fundamentals of graph theory used in the paper, including algebraic graph theory, can be found in the main reference [15].From the adjacency matrixA, the degree matrix is defined as D=diag⁡aij=∑j=1Naij. Laplacian matrix of G can be further obtained by subtracting adjacency matrix from degree matrix, such that L=D-A, where Laplacian matrix L is positive semidefinite. Let the eigenvalues of L be 0=λ1≤λ2≤⋯≤λN which is nondecreasing order with corresponding eigenvectors v1,v2,…,vn. We denote that the remarkable properties of Laplacian matrix are as follows.Lemma 3 (see [15]).
Given the undirected graphG(i)
LG is always symmetric and positive semidefinite and satisfies sum of square property (3)xTLx=12∑i=1Naijxi-xj2,where xi∈RN;(ii)
λ1=0; thus λ2>0 if graph Gt is connected; then λ2 is referred to algebraic connectivity of Gt;(iii)
LG has a single zero eigenvalue and the corresponding eigenvector is 1N.This paper will focus on the design of flocking protocol that can preserve connectivity in terms of algebraic graph representation.We define the stable flocking protocol as the necessary condition to preserve connectivity of the network all the time.Definition 4 (stable flocking protocol).
Group of robot agents is said to flock when all agents approach the same velocity, with no collisions among them, such that(4)qi-qj≤R,pi=pj,λ2>0,where λ2 is the second smallest eigenvalue of Laplacian matrix L.The connectivity maintenance of flocking topology is approximately determined by the distance between agents in the flock. The movement of agents that might cause the connectivity can be unavailable during flocking motion. Therefore, our problem is dealing with designing a cooperative flocking protocol using only local information to drive all robot agents to achieve the same velocity, avoiding collision with other agents in flock, avoiding static obstacle, driving the agents to the goal position, and guaranteeing that the network is always connected during the flocking, indicated byλ2L>0.


## 3. Potential Function Design

This section introduces the design of artificial potential functions for the purpose of target attraction, obstacle avoidance, and interagent attraction and repulsion. Since first used in [16], the artificial potential function has been commonly used to solve the problems of motion planning in mobile robotic applications. Theoretically, the artificial potential function generates repulsive fields close to obstacles and attractive fields close target. In artificial potential fields, a noncollided motion is determined by how much the robot is attracted by other agents and repelled by either the obstacle or other agents. We add centroid function and attract-repel function to avoid local minima caused by goal attraction and obstacle function. The potential function method has several advantages, and the most important one is being easy to implement.


### 3.1. Environmental Potential Field

Consider the multiagent robots move in configuration workspace, which is defined as follows.Definition 5 (workspace).
Suppose a point of robot moves in the workspaceW≜q∈R2∣qij≤s2; that is, the Euclidean distance between two points does not exceed the area of s2.We define the free space, where there is no obstacle within the area.Definition 6 (free space).
Free spaceF is defined as F≜W⋃k=1mOk, where a robot agent could move safely without colliding with any obstacles.Given the position of robot agents in stack vectorq=q1T,…,qNTT∈R2, we assume all information of the environment in the W is known by each robot agent. A target or goal position of agent i is defined as qt∈F, which is in the free area of configuration workspace. To attract the robot agent to reach the desired goal position, the attraction-to-target potential function T is defined as follows.Definition 7 (target attraction function).
T i : F → 0 , ∞ is a metric that measures how close a robot agent is to the desired goal position. Target or goal attraction function is defined as(5)Ti=12qi-qt2.LetOk∈R2 be kth obstacle in the workspace and Oi,k∈R2 be the kth obstacle that has to be avoided by agent i.Definition 8 (obstacle).
O k is a kth disc obstacle that exists in workspace W with center qo∈R2 and radius rk: (6)Ok=q∈R2∣q-qo≤rksuch that the distance of any point to the center of obstacle does not exceed rk.Using the definitions above, all robot agents have to avoid obstacles that block the robot route toward the desired position. Therefore, each robot has to execute an obstacle avoidance function that is constructed by measuring the distance between the robot agent and the obstacle centerqo∈W. The obstacle avoidance function computed byith agent is defined as follows.Definition 9 (obstacle avoidance function).
Robot agenti could avoid kth obstacle with the following potential function:(7)Oi,k=exp⁡-1/2qi-qo2rkrk,where qo∈R2 is the center of obstacle and rk is radius of obstacle k, such that robot agent i could avoid obstacle Ok if none of them intersect each other within qi-qo>rk.Using the definitions above, the environmental potential field is composed of goal attractiveness and obstacle repulsiveness, and the result is depicted in Figure1. This figure illustrates two different sizes of obstacles indicated by two hills with high potential value, while the lowest potential, the darkest valley at the center of the basin, illustrates the desired position.Figure 1
Example of environment model used in this paper. Goal position is represented by the lowest potential value; two hills represent different size of obstacles.


### 3.2. Interagent Potential Function

We assume that the sensing capability of an agent equals its communication radius. Suppose there exists pair interaction between robot agentsi and j via wireless communication network. The interaction between paired agents is limited by communication range, where the coverage of robot agent i resembles a disk with a certain radius R.Definition 10 (agent disc radius).
LetBqi,R be a disk with coverage radius R, and qi=xi,yi∈R2 is position of agent i a x,y plane:(i)
Open disk radius is an area covered byBqi,R if qj∈R2∣qi-qj<R.(ii)
Close disk radius is an area covered byBqi,R if qj∈R2∣qi-qj≤R.


### 3.3. Attraction to Centroid

The idea of flock centroid is initiated in [1]. Action to attract flock member to the center of a flock, or flock centering, makes the agents move in a direction toward the centroid. By means of flock centering, the flocking algorithm provides a mechanism to make sure that agents are attracted to each other and not moving away. This concept is further known as a part of the well-known one of three heuristic flocking rules initiated by Reynolds [1]. Illustration of agent’s disk radius and the center of the flock can be seen in Figure 2. This figure also explains how the interaction among agents in the flock occurs.Figure 2
Illustration of an agent disk radius and centroid attraction among the flockmates.The long-range attraction occurs between agents in the flocks. To make sure that robot agents in the flocks are attracted to each other, as well as attracted by the center of the flock, an attractive function is constructed by measuring the distance between individual agents and the center of the flocks. The flock centering attraction function is simply given by(8)Ciqi=∑i=1Nqi-1N∑i=1Nqi2.


### 3.4. Interagent Attraction Repulsion

This paper uses the definition of closed disk coverage, where two interagent distances may occur withinqi-qj≤R. This condition is further coded into communication edge i,j∈E. Based on this interaction, the neighborhood of an agent i is determined by Ni=j∈V∣i,j∈E. Using the definition of Ni, the interagent collision avoidance function is further defined.Definition 11 (interagent collision avoidance).
Collision avoidance function is used to keepqi-qj≤R such that communication can be preserved and no agents collided during the flock movement.Interagent collision avoidance is implemented by attract-repel function. The long-range attraction occurs between two agents in the flocks. It is to make sure that the agents in the flock are attracted by the following function:(9)Ψijqij=∑j∈Nica2qi-qj2,where ca is attraction constant. Properties of attraction function can be characterized as follows:(i)
Attractive potential function can be viewed as potential energy between agents in the flock.(ii)
LetΨijqij be the attraction function; then
(a)
Ψijqij→0, as agent qi-qj→∞; that is, j moves away from agent i.(b)
Ψijqij is differentiable along qij>0 such that ∇qiΨijqij>0.Interagent collision avoidance is implemented by short range repulsive function, which is formulated from the distance between agents. The objective of this function is to repel neighboring agents if they are too close; therefore collision can be avoided. The short range repulsive potential function is defined as(10)Φqij=∑j∈Nicrexp⁡-1/2qi-qj2RR,where cr is repulsion constant. The properties of repulsive function can be characterized as follows:(i)
Repulsive potential function can be viewed as potential energy between agents in the flock within the range0,R such that no collision occurs between agents j∈Ni.(ii)
LetΦijqij be the repulsive function, such that
(a)
Φijqij→∞, as qi-qj→0;(b)
Φijqij is differentiable along qij>0, such that ∇iΦijqij>0.We combine attraction and repulsion potential function to generate attract-repel function as(11)Rijqij=Φijqij+Ψijqij=∑j∈Nica2qi-qj2+∑j∈Nicrexp⁡-1/2qi-qj2RR.The attractive-repulsive potential function may guarantee that agentj never moves away from Ni. The plot of attract-repel function is depicted in Figure 3.Figure 3
Interagent attract-repel potential function with various repulsive constantcr, where ca=1 and R=3.


## 3.1. Environmental Potential Field

Consider the multiagent robots move in configuration workspace, which is defined as follows.Definition 5 (workspace).
Suppose a point of robot moves in the workspaceW≜q∈R2∣qij≤s2; that is, the Euclidean distance between two points does not exceed the area of s2.We define the free space, where there is no obstacle within the area.Definition 6 (free space).
Free spaceF is defined as F≜W⋃k=1mOk, where a robot agent could move safely without colliding with any obstacles.Given the position of robot agents in stack vectorq=q1T,…,qNTT∈R2, we assume all information of the environment in the W is known by each robot agent. A target or goal position of agent i is defined as qt∈F, which is in the free area of configuration workspace. To attract the robot agent to reach the desired goal position, the attraction-to-target potential function T is defined as follows.Definition 7 (target attraction function).
T i : F → 0 , ∞ is a metric that measures how close a robot agent is to the desired goal position. Target or goal attraction function is defined as(5)Ti=12qi-qt2.LetOk∈R2 be kth obstacle in the workspace and Oi,k∈R2 be the kth obstacle that has to be avoided by agent i.Definition 8 (obstacle).
O k is a kth disc obstacle that exists in workspace W with center qo∈R2 and radius rk: (6)Ok=q∈R2∣q-qo≤rksuch that the distance of any point to the center of obstacle does not exceed rk.Using the definitions above, all robot agents have to avoid obstacles that block the robot route toward the desired position. Therefore, each robot has to execute an obstacle avoidance function that is constructed by measuring the distance between the robot agent and the obstacle centerqo∈W. The obstacle avoidance function computed byith agent is defined as follows.Definition 9 (obstacle avoidance function).
Robot agenti could avoid kth obstacle with the following potential function:(7)Oi,k=exp⁡-1/2qi-qo2rkrk,where qo∈R2 is the center of obstacle and rk is radius of obstacle k, such that robot agent i could avoid obstacle Ok if none of them intersect each other within qi-qo>rk.Using the definitions above, the environmental potential field is composed of goal attractiveness and obstacle repulsiveness, and the result is depicted in Figure1. This figure illustrates two different sizes of obstacles indicated by two hills with high potential value, while the lowest potential, the darkest valley at the center of the basin, illustrates the desired position.Figure 1
Example of environment model used in this paper. Goal position is represented by the lowest potential value; two hills represent different size of obstacles.


## 3.2. Interagent Potential Function

We assume that the sensing capability of an agent equals its communication radius. Suppose there exists pair interaction between robot agentsi and j via wireless communication network. The interaction between paired agents is limited by communication range, where the coverage of robot agent i resembles a disk with a certain radius R.Definition 10 (agent disc radius).
LetBqi,R be a disk with coverage radius R, and qi=xi,yi∈R2 is position of agent i a x,y plane:(i)
Open disk radius is an area covered byBqi,R if qj∈R2∣qi-qj<R.(ii)
Close disk radius is an area covered byBqi,R if qj∈R2∣qi-qj≤R.


## 3.3. Attraction to Centroid

The idea of flock centroid is initiated in [1]. Action to attract flock member to the center of a flock, or flock centering, makes the agents move in a direction toward the centroid. By means of flock centering, the flocking algorithm provides a mechanism to make sure that agents are attracted to each other and not moving away. This concept is further known as a part of the well-known one of three heuristic flocking rules initiated by Reynolds [1]. Illustration of agent’s disk radius and the center of the flock can be seen in Figure 2. This figure also explains how the interaction among agents in the flock occurs.Figure 2
Illustration of an agent disk radius and centroid attraction among the flockmates.The long-range attraction occurs between agents in the flocks. To make sure that robot agents in the flocks are attracted to each other, as well as attracted by the center of the flock, an attractive function is constructed by measuring the distance between individual agents and the center of the flocks. The flock centering attraction function is simply given by(8)Ciqi=∑i=1Nqi-1N∑i=1Nqi2.


## 3.4. Interagent Attraction Repulsion

This paper uses the definition of closed disk coverage, where two interagent distances may occur withinqi-qj≤R. This condition is further coded into communication edge i,j∈E. Based on this interaction, the neighborhood of an agent i is determined by Ni=j∈V∣i,j∈E. Using the definition of Ni, the interagent collision avoidance function is further defined.Definition 11 (interagent collision avoidance).
Collision avoidance function is used to keepqi-qj≤R such that communication can be preserved and no agents collided during the flock movement.Interagent collision avoidance is implemented by attract-repel function. The long-range attraction occurs between two agents in the flocks. It is to make sure that the agents in the flock are attracted by the following function:(9)Ψijqij=∑j∈Nica2qi-qj2,where ca is attraction constant. Properties of attraction function can be characterized as follows:(i)
Attractive potential function can be viewed as potential energy between agents in the flock.(ii)
LetΨijqij be the attraction function; then
(a)
Ψijqij→0, as agent qi-qj→∞; that is, j moves away from agent i.(b)
Ψijqij is differentiable along qij>0 such that ∇qiΨijqij>0.Interagent collision avoidance is implemented by short range repulsive function, which is formulated from the distance between agents. The objective of this function is to repel neighboring agents if they are too close; therefore collision can be avoided. The short range repulsive potential function is defined as(10)Φqij=∑j∈Nicrexp⁡-1/2qi-qj2RR,where cr is repulsion constant. The properties of repulsive function can be characterized as follows:(i)
Repulsive potential function can be viewed as potential energy between agents in the flock within the range0,R such that no collision occurs between agents j∈Ni.(ii)
LetΦijqij be the repulsive function, such that
(a)
Φijqij→∞, as qi-qj→0;(b)
Φijqij is differentiable along qij>0, such that ∇iΦijqij>0.We combine attraction and repulsion potential function to generate attract-repel function as(11)Rijqij=Φijqij+Ψijqij=∑j∈Nica2qi-qj2+∑j∈Nicrexp⁡-1/2qi-qj2RR.The attractive-repulsive potential function may guarantee that agentj never moves away from Ni. The plot of attract-repel function is depicted in Figure 3.Figure 3
Interagent attract-repel potential function with various repulsive constantcr, where ca=1 and R=3.


## 4. Flocking Controller Design

This section describes the design of flocking controller by utilizing control Lyapunov function. We use the direct method of Lyapunov to obtain the flocking control input which is derived from overall artificial potential function that has been defined in the previous section. The reader may refer to [17–19] for the detail of control Lyapunov function for multiagent system.


### 4.1. Control Lyapunov Function

Regarding [1, 4, 7], flocking control law, which is also known as flocking protocol, is composed of negative gradient of potential force and consensus velocity of flock members. The force is obtained from the gradient of potential fields. Generally, the objective of flocking control is to steer the flock such that velocity between agents i and j is approximately the same.We extend the control law of formation control problem in [14] into flocking problem. First of all, consider a multiagent system dynamics(12)q˙i=pi,p˙i=ui,where qi∈R2 is position of agent in two-dimensional space, pi is agent velocity, and ui in control input to be designed. Our intention is to use control Lyapunov function to obtain control input ui, which is derived from the potential function. We recall the sum of potential functions from (5), (7), (8), and (11),(13)Piqi=∑i=1NCiqi+∑j∈NiRijqij+Tiqi+Oi,kqi.Definition 12.
A control Lyapunov function is continuously positive-definite function; that is,Vx is positive except for x=0, such that (14)V˙x,u=∇Vxfx,u<0.Regarding Definition12, the candidate of Lyapunov function is then defined by combining all potential energy obtained from potential function, with kinetic energy as the difference between velocity of agent i and agent j,(15)Vi=Piqi+12∑j∈Nipi-pj2.Candidate of Lyapunov function for all agents can then be written as(16)V=∑i=1NVi=∑i=1NCiqi+∑j∈NiRiqi+Tiqi+Oi,kqi+12∑j∈Nipi-pj2.To extract the control input from candidate of Lyapunov function, we differentiate all potential function components inV, such that flocking control input for system (12) is obtained from V˙qi. We consider the assumption described in previous section to generate the following theorem.Theorem 13.
TheN holonomic agents use dynamics in system (12). The stable flocking control input ui can be obtained from the gradient of (16). The flocking protocol is stable such that each agent moves in the flock, the obstacle can be avoided, and there is no interagent collision, and finally agents stop at a defined goal position.To prove the above theorem, we consider (16). It is obvious that Vi0=0, and Vi is positive-definite function and continuous when(17)∑i=1NCiq>0,∑i=1N∑j∈NiRijq>0,qi∈R2.Since the force is negative gradient along the trajectories of qi, then we can write(18)V˙=∑i=1N∂Vi∂qi∂qi∂t=∑i=1N∂Vi∂qi·q˙i=∑i=1N∂Vi∂qipi.The velocity is the form of negative force that equals (19)pi=-∑i=1N∂Vi∂qi.We then check the definiteness of Lyapunov function, such that(20)V˙=-∑i=1N∂Vi∂qi·∂V∂qi=-∑i=1NpiTpi≤0.It is clear that since (20) is negative semidefinite, then control input ui is Lyapunov stable. Therefore, the flocking control input ui can then be obtained from the gradient of Lyapunov function V˙qi,pi as follows:(21)ui=-∇qCiq-∑j∈Ni∇qRijq-∇qTiq-∇qOi,kq+∑j∈Nipi-pj=-qi-∑i=1Nq¯i+exp-qi-qo/rs⁡qi-qo-qi-qt+ca-crexp-qi-qj/Rqi-qj+∑j∈Nipi-pj.The notation q¯=1/N∑i=1N‍qi is the center of the flock. Thus, we can substitute flocking control input in system (12) with (21). It can be observed that the last term of control input is velocity consensus.


### 4.2. Convergence of Velocity

In this subsection, we present the analysis of velocity convergence which is the necessary condition of stable flocking controller as in Definition4. We begin with the stationary of the center of the flocks, which is to attract all flock members during the movement. Now let us consider the following lemma.Lemma 14.
Using system (12) and control input in (21), the centroid of the flocks is stationary ∀t>0.Proof.
Letq¯=1/N∑i=1N‍qi be the center of the flocks. The time derivative of q¯ can further be defined as(22)q-˙=1N∑i=1Nq˙i.
Let us consider the systemui=q˙i and let q˙i=∇qiRiq=-ca-crexp⁡-qi-qj/Rqi-qj be the attract-repel force. Let f-a=-crexp⁡-qi-qj/Rqi-qj; then f-a is odd function such that f-a=-fa. Due to the symmetry of odd function, (22) can be written as(23)q-˙=1N∑i=1N∑j∈Nif-a+fa=0.Let the invariant set of equilibrium (or stationary) points be Ωe=q∣q-˙=0. It implies q˙i=q-˙, which means that all individual agents’ velocity equals the velocity of center of the flocks.We begin with following theorem.Theorem 15.
Robot agent that uses control input (21) eventually can reach the same velocity during flocking and collision can be avoided and achieve the desired goal.Proof.
To prove this theorem, we rewrite the sum of potential functionPi defined in (13):(24)Piqi=∑i=1NCiqi+∑j∈NiRiqi+Tiqi+Okqi.The candidate of Lyapunov function is then defined, which consists of artificial potential function and velocity of each agent.(25)Vi=12∑i=1NPiqi2+pi2.
The derivative of Lyapunov function alongqi is(26)V˙i=∑i=1Nq˙i∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qiRijq+∑i=1NpiTp˙i.
By replacingp˙ in (26) with ui in (21), we obtain(27)V˙i=∑i=1Nq˙i∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq+∑i=1NpiTui=∑i=1NpiT∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq+∑i=1Nui=∑i=1NpiT∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq-∑i=1N∇qiCiq-∇qiTiq-∇qiOiq-∑j∈Ni∇qRijq-∑j∈Nipi-pj=-piT∑j∈Nipi-pj.The neighborhood j∈Ni is represented by adjacency element aij; then (27) can be written as(28)V˙=-∑i=1NpiT∑j∈Niaijpi-pj=-pTL⊗Ip≤0,where L is the Laplacian matrix and I is the identity matrix. Therefore it means that when -pTL⊗Ip=0, the agent velocity p1=p2=⋯=pN, i=1,2,…,N.


### 4.3. Algebraic Connectivity Gradient Controller

In this section, we add the term of gradient of algebraic connectivity alongqi into ui in (21). We redefine the adjacency matrix A as follows:(29)aij=exp-1/2qi-qj2/R⁡R,qi-qj≤R0,otherwise.We can also write the second smallest eigenvalue of Laplacian matrix λ2=v2TLv2, where v2 is corresponding eigenvector of λ2. Due to the properties of Laplacian matrix, the connectivity is guaranteed if λ2L>0. Suppose we define 0,1∈ϵ to be the lower bound of λ2. It is clear that when λ2 goes to ϵ, it means that the graph connectivity is weak. Regarding this condition, we consider adding the value of algebraic connectivity as the additional term in flocking protocol, which is to make sure that λ2≥ϵ.Let us define the following theorem.Theorem 16.
Supposeφqi=coth2⁡(λ2(qi)-ϵ) is the short range function of λ2 along qi. Then φqi is differentiable along qij. Therefore, its gradient exists along qij, and φλ2-ϵ approaches a constant value as λ2 increases.Proof.
To proof this theorem, we follow [20]. We can also write(30)infv∈1⊥⁡λ2=vTLv=infv∈1⊥⁡∑i=1n∑j∈Niaijvi-vj2,where vi is corresponding eigenvector of λ2. Suppose we want to define the gradient controller with algebraic connectivity function. The control input can be defined by taking the derivative of λ2 along qi as follows:(31)uiλ=∂φλ2qi-ϵ∂qi=∂φλ2qi-ϵ∂λ2∂λ2∂qi.The solution of first term is partial derivative of φλ2qi on λ2,(32)∂φp∂λ2=csch2⁡λ2-ϵ.The next step is to find the solution of second term of partial derivative of ∂λ2/∂qi in (31). We use [20] to find ∂λ2/∂qi.
Lemma6 (see [20]).Given any positively weighted graphG, λ2is a nondecreasing function of each weightaij.
Second smallest eigenvalue can be written in the form of(33)λ2=minx⊥1⁡xTLxxTx=minv⊥1⁡∑i,j∈Eaijvi-vj2vTv.As a consequence, therefore, the partial derivative of λ2 can also be written as follows:(34)∂λ2∂qi=vT∂L∂qiv.By replacing xTLx with ∑i,j∈E‍aijvi-vj2 we obtain (35)vT∂L∂qiv=∑i,j∈E∂aij∂qivi-vj2.Therefore, the gradient of φλ2-ϵ exists along qi, and this value asymptotically approaches a constant value as λ2 increases.We further define the gradient of algebraic connectivity as control input as follows:(36)uiλ=-csch2⁡λ2-ϵ∑j∈Niaijvi-vj2qi-qj.We define the following nonnegative energy function as the candidate of Lyapunov function:(37)V=coth⁡λ2-ϵ.With respect to [20], ∇qiV=q˙i=ui. Thus, the derivative of candidate of Lyapunov function is(38)V˙q=∇qiVqq˙=q˙Tq˙=-∑i=1NpiTpi.Equation (36) can then be added into the previous flocking protocol as a new term in (21),(39)ui=-∇qiCiq-∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq-∑j∈Nipi-pj-csch2⁡λ2-ϵ∑j∈Niexp-1/2qi-qj2/R⁡Rvi-vj2qi-qj.To analyze the stability of flocking controller afteruiλ addition, we take the derivative in (28) with respect to qi and add it with the derivative of Lyapunov function in (38) with respect to qi, such that(40)V˙q=-∑i=1NpiT∑j∈Niaijpi-pj-∑i=1NpiTpi=-2∑i=1NpTL⊗Ip=-2pTL⊗Ip≤0.It means that adding gradient of algebraic connectivity to the previous flocking control input remains guarantees the stability in the sense of Lyapunov, connectivity can be maintained, collision between agents as well as with obstacle can be avoided, and the agent can reach the common desired position.


## 4.1. Control Lyapunov Function

Regarding [1, 4, 7], flocking control law, which is also known as flocking protocol, is composed of negative gradient of potential force and consensus velocity of flock members. The force is obtained from the gradient of potential fields. Generally, the objective of flocking control is to steer the flock such that velocity between agents i and j is approximately the same.We extend the control law of formation control problem in [14] into flocking problem. First of all, consider a multiagent system dynamics(12)q˙i=pi,p˙i=ui,where qi∈R2 is position of agent in two-dimensional space, pi is agent velocity, and ui in control input to be designed. Our intention is to use control Lyapunov function to obtain control input ui, which is derived from the potential function. We recall the sum of potential functions from (5), (7), (8), and (11),(13)Piqi=∑i=1NCiqi+∑j∈NiRijqij+Tiqi+Oi,kqi.Definition 12.
A control Lyapunov function is continuously positive-definite function; that is,Vx is positive except for x=0, such that (14)V˙x,u=∇Vxfx,u<0.Regarding Definition12, the candidate of Lyapunov function is then defined by combining all potential energy obtained from potential function, with kinetic energy as the difference between velocity of agent i and agent j,(15)Vi=Piqi+12∑j∈Nipi-pj2.Candidate of Lyapunov function for all agents can then be written as(16)V=∑i=1NVi=∑i=1NCiqi+∑j∈NiRiqi+Tiqi+Oi,kqi+12∑j∈Nipi-pj2.To extract the control input from candidate of Lyapunov function, we differentiate all potential function components inV, such that flocking control input for system (12) is obtained from V˙qi. We consider the assumption described in previous section to generate the following theorem.Theorem 13.
TheN holonomic agents use dynamics in system (12). The stable flocking control input ui can be obtained from the gradient of (16). The flocking protocol is stable such that each agent moves in the flock, the obstacle can be avoided, and there is no interagent collision, and finally agents stop at a defined goal position.To prove the above theorem, we consider (16). It is obvious that Vi0=0, and Vi is positive-definite function and continuous when(17)∑i=1NCiq>0,∑i=1N∑j∈NiRijq>0,qi∈R2.Since the force is negative gradient along the trajectories of qi, then we can write(18)V˙=∑i=1N∂Vi∂qi∂qi∂t=∑i=1N∂Vi∂qi·q˙i=∑i=1N∂Vi∂qipi.The velocity is the form of negative force that equals (19)pi=-∑i=1N∂Vi∂qi.We then check the definiteness of Lyapunov function, such that(20)V˙=-∑i=1N∂Vi∂qi·∂V∂qi=-∑i=1NpiTpi≤0.It is clear that since (20) is negative semidefinite, then control input ui is Lyapunov stable. Therefore, the flocking control input ui can then be obtained from the gradient of Lyapunov function V˙qi,pi as follows:(21)ui=-∇qCiq-∑j∈Ni∇qRijq-∇qTiq-∇qOi,kq+∑j∈Nipi-pj=-qi-∑i=1Nq¯i+exp-qi-qo/rs⁡qi-qo-qi-qt+ca-crexp-qi-qj/Rqi-qj+∑j∈Nipi-pj.The notation q¯=1/N∑i=1N‍qi is the center of the flock. Thus, we can substitute flocking control input in system (12) with (21). It can be observed that the last term of control input is velocity consensus.


## 4.2. Convergence of Velocity

In this subsection, we present the analysis of velocity convergence which is the necessary condition of stable flocking controller as in Definition4. We begin with the stationary of the center of the flocks, which is to attract all flock members during the movement. Now let us consider the following lemma.Lemma 14.
Using system (12) and control input in (21), the centroid of the flocks is stationary ∀t>0.Proof.
Letq¯=1/N∑i=1N‍qi be the center of the flocks. The time derivative of q¯ can further be defined as(22)q-˙=1N∑i=1Nq˙i.
Let us consider the systemui=q˙i and let q˙i=∇qiRiq=-ca-crexp⁡-qi-qj/Rqi-qj be the attract-repel force. Let f-a=-crexp⁡-qi-qj/Rqi-qj; then f-a is odd function such that f-a=-fa. Due to the symmetry of odd function, (22) can be written as(23)q-˙=1N∑i=1N∑j∈Nif-a+fa=0.Let the invariant set of equilibrium (or stationary) points be Ωe=q∣q-˙=0. It implies q˙i=q-˙, which means that all individual agents’ velocity equals the velocity of center of the flocks.We begin with following theorem.Theorem 15.
Robot agent that uses control input (21) eventually can reach the same velocity during flocking and collision can be avoided and achieve the desired goal.Proof.
To prove this theorem, we rewrite the sum of potential functionPi defined in (13):(24)Piqi=∑i=1NCiqi+∑j∈NiRiqi+Tiqi+Okqi.The candidate of Lyapunov function is then defined, which consists of artificial potential function and velocity of each agent.(25)Vi=12∑i=1NPiqi2+pi2.
The derivative of Lyapunov function alongqi is(26)V˙i=∑i=1Nq˙i∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qiRijq+∑i=1NpiTp˙i.
By replacingp˙ in (26) with ui in (21), we obtain(27)V˙i=∑i=1Nq˙i∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq+∑i=1NpiTui=∑i=1NpiT∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq+∑i=1Nui=∑i=1NpiT∇qiCiq+∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq-∑i=1N∇qiCiq-∇qiTiq-∇qiOiq-∑j∈Ni∇qRijq-∑j∈Nipi-pj=-piT∑j∈Nipi-pj.The neighborhood j∈Ni is represented by adjacency element aij; then (27) can be written as(28)V˙=-∑i=1NpiT∑j∈Niaijpi-pj=-pTL⊗Ip≤0,where L is the Laplacian matrix and I is the identity matrix. Therefore it means that when -pTL⊗Ip=0, the agent velocity p1=p2=⋯=pN, i=1,2,…,N.


## 4.3. Algebraic Connectivity Gradient Controller

In this section, we add the term of gradient of algebraic connectivity alongqi into ui in (21). We redefine the adjacency matrix A as follows:(29)aij=exp-1/2qi-qj2/R⁡R,qi-qj≤R0,otherwise.We can also write the second smallest eigenvalue of Laplacian matrix λ2=v2TLv2, where v2 is corresponding eigenvector of λ2. Due to the properties of Laplacian matrix, the connectivity is guaranteed if λ2L>0. Suppose we define 0,1∈ϵ to be the lower bound of λ2. It is clear that when λ2 goes to ϵ, it means that the graph connectivity is weak. Regarding this condition, we consider adding the value of algebraic connectivity as the additional term in flocking protocol, which is to make sure that λ2≥ϵ.Let us define the following theorem.Theorem 16.
Supposeφqi=coth2⁡(λ2(qi)-ϵ) is the short range function of λ2 along qi. Then φqi is differentiable along qij. Therefore, its gradient exists along qij, and φλ2-ϵ approaches a constant value as λ2 increases.Proof.
To proof this theorem, we follow [20]. We can also write(30)infv∈1⊥⁡λ2=vTLv=infv∈1⊥⁡∑i=1n∑j∈Niaijvi-vj2,where vi is corresponding eigenvector of λ2. Suppose we want to define the gradient controller with algebraic connectivity function. The control input can be defined by taking the derivative of λ2 along qi as follows:(31)uiλ=∂φλ2qi-ϵ∂qi=∂φλ2qi-ϵ∂λ2∂λ2∂qi.The solution of first term is partial derivative of φλ2qi on λ2,(32)∂φp∂λ2=csch2⁡λ2-ϵ.The next step is to find the solution of second term of partial derivative of ∂λ2/∂qi in (31). We use [20] to find ∂λ2/∂qi.
Lemma6 (see [20]).Given any positively weighted graphG, λ2is a nondecreasing function of each weightaij.
Second smallest eigenvalue can be written in the form of(33)λ2=minx⊥1⁡xTLxxTx=minv⊥1⁡∑i,j∈Eaijvi-vj2vTv.As a consequence, therefore, the partial derivative of λ2 can also be written as follows:(34)∂λ2∂qi=vT∂L∂qiv.By replacing xTLx with ∑i,j∈E‍aijvi-vj2 we obtain (35)vT∂L∂qiv=∑i,j∈E∂aij∂qivi-vj2.Therefore, the gradient of φλ2-ϵ exists along qi, and this value asymptotically approaches a constant value as λ2 increases.We further define the gradient of algebraic connectivity as control input as follows:(36)uiλ=-csch2⁡λ2-ϵ∑j∈Niaijvi-vj2qi-qj.We define the following nonnegative energy function as the candidate of Lyapunov function:(37)V=coth⁡λ2-ϵ.With respect to [20], ∇qiV=q˙i=ui. Thus, the derivative of candidate of Lyapunov function is(38)V˙q=∇qiVqq˙=q˙Tq˙=-∑i=1NpiTpi.Equation (36) can then be added into the previous flocking protocol as a new term in (21),(39)ui=-∇qiCiq-∇qiTiq+∇qiOiq+∑j∈Ni∇qRijq-∑j∈Nipi-pj-csch2⁡λ2-ϵ∑j∈Niexp-1/2qi-qj2/R⁡Rvi-vj2qi-qj.To analyze the stability of flocking controller afteruiλ addition, we take the derivative in (28) with respect to qi and add it with the derivative of Lyapunov function in (38) with respect to qi, such that(40)V˙q=-∑i=1NpiT∑j∈Niaijpi-pj-∑i=1NpiTpi=-2∑i=1NpTL⊗Ip=-2pTL⊗Ip≤0.It means that adding gradient of algebraic connectivity to the previous flocking control input remains guarantees the stability in the sense of Lyapunov, connectivity can be maintained, collision between agents as well as with obstacle can be avoided, and the agent can reach the common desired position.


## 5. Simulation of Multiagent Connectivity Preserving Flocking

This section demonstrates the simulation results of connectivity preserving flocking in multiagent system using the stable control input obtained from the previous section. The simulation verifies flocking protocol, which is derived using control Lyapunov function. The common algorithm to simulate multiagent robot with connectivity preserving flocking is depicted in Algorithm1. For simulation purpose, the different flocking scenarios are also presented: workspace without obstacle, with single obstacle, and with multiple obstacles. In all scenarios, the point mass mobile robot agents move from the initial position to the goal position while avoiding each other.Algorithm 1:Main algorithm.
initialization all variables and constants while  t<tend  do capture positionq; for  i=1 to N  do compute∇qiTi, ∇qiOi,k; if  qij≤R  then build[aij]; compute∑i=1N(∇qiRi+∇qiCi); end end computeL, λ2, pi; computeui updateqi; updateui; endAll scenarios in simulation are conducted in Matlab. The initial position of each robot agent is generated randomly with initial connected topology atX=1 to 5, Y=1 to 5. The size of obstacles is varied from rk=1 to rk=3. For the purpose of simulation, we use the same communication radius R=5. The simulation scenarios are determined as follows:(1)
multiagent flocking without obstacle,(2)
multiagent flocking with single obstacle,(3)
multiagent flocking with multiple obstacles,(4)
multiagent flocking with algebraic connectivity controller.( 1 ) Multiagent Flocking without Obstacle. In the first scenario, we present the result of simulation of connectivity preserving flocking without obstacle in the configuration workspace. We simulate five points of robots that represent robot agent, randomly starting from initial condition around XY=0,0 up to (5,5) in coordinate plane, and target position is XY=35,35. We plot the trajectory of robot during simulation and the result is depicted in Figure 4.Figure 4
Multiagent flocking trajectories without obstacle.From simulation, it can be seen that the multiagent graph is always connected during flocking evolution. The convergence of agent’s velocity is determined by consensus term as described in control input in (21). In Figure 5 it can be seen that the velocity of agents converges to the same value when consensus is used in the connectivity preserving flocking protocol.Figure 5
Multiagent velocity trajectory in no obstacle scenario.( 2 ) Multiagent Flocking with Single Obstacle. We plot the trajectory of a robot during simulation as depicted in Figure 6. The multiagent graph is always connected during flocking evolution. In this simulation, we can also see that velocity of agents still converges to the same value, as depicted in Figure 7. A slightly different result is obtained when obstacle is present in the workspace. Agents can reach velocity convergence in the beginning. However, when detecting the obstacles, the velocity is a bit varying before it finally converges.Figure 6
Multiagent robot trajectories with single obstacle.Figure 7
Multiagent velocity trajectory in the scenario with obstacle.( 3 ) Multiagent Flocking with Multiple Obstacles. In this scenario, multiple sizes of multiple obstacles are present in the workspace. We assume that three multiple sizes of obstacles represent a small, medium, and large size of obstacle. For this purpose, we use two different subscenarios: first is simulation with five robot agents, and the second one is with ten robot agents.The robot trajectories during simulation of multiagent with multiple size obstacles can be seen in Figure8. We also plot the velocity convergence of flock during simulation and the results are depicted in Figure 9. In Figure 10, ten robot agents are simulated to perform flocking and reach the goal position. This is to see how the flocking control input works with large number of agents. Ten agents can still move in the flock while avoiding three different sizes of obstacle and finally reach the desired position.Figure 8
Multiagent robot trajectories with multiple size multiple obstacles.Figure 9
Multiagent velocity convergence in multiple size multiple obstacles.Figure 10
Multiagent robot trajectories of 10 agents with multiple obstacles.( 4 ) Multiagent Flocking with Algebraic Connectivity Controller. In this scenario, we use (39) to preserve connectivity by using gradient of algebraic connectivity. During simulation, the values of algebraic connectivity, which indicates the measure of connectedness of multiagent network, are plotted and depicted in Figure 13. From the beginning of simulation, it can be seen that the value of algebraic connectivity remains >0, meaning that the flocking controller still guarantees connectivity while avoiding obstacle as illustrated by robot trajectories shown in Figure 11.Figure 11
Multiagent robot trajectories with single and multiple obstacles with algebraic connectivity controller.We also compare the velocity convergence where the gradient ofλ2 is added into the flocking control input, and the plot is depicted in Figure 12. By adding λ2 gradient controller, velocity alignment in flocking protocol is smooth and faster compared to flocking controller without λ2 gradient controller.Figure 12
Multiagent velocity with multiple obstacles scenario. (a) Withoutλ2 gradient. (b) With λ2 gradient.
(a) (b)Figure 13
Algebraic connectivity value during simulation of multiagent velocity convergence in multiple size multiple obstacles.


## 6. Conclusion

In this paper, the control Lyapunov function is successfully used to construct flocking control input with connectivity preservation in a group of networks of mobile robot agents. We model the agents as a dynamic point mass, and the proposed control strategy involves potential force and velocity consensus. Several potential forces are designed to steer the neighbor agents to predetermined distance while avoiding collision among them such that connectedness of network topologies can be guaranteed. Under the assumption that the initial flocking topology is connected, the overall flocking topology is preserved to be connected while obstacle and collision avoidance are also guaranteed.Simulation results verify the new proposed control input with gradient of algebraic connectivity. From the multiagent flocking point of view, it implies that the overall controller could maintain connectivity of agents, forming cohesive multiple agents, and matching velocities. In order to guarantee goal achievement of multiagent flocking, connectivity is still preserved by keeping the second smallest eigenvalue of flocking topologyλ2>0.



---

*Source: 8540761-2016-10-16.xml*