Decentralization of Virtual Linkage in Formation Control of Multi-Agents via Consensus Strategies

Featured Application

The method proposed in this paper can be used for formation control autonomous robots, such as nonholonomic mobile robots, unmanned aerial vehicles and has potential applications in search and rescue missions, area coverage and reconnaissance, etc.

Abstract

Featured Application: This paper addresses the formation control of a team of agents based on the decentralized control and the recently introduced reconfigurable virtual linkage approach. Following a decentralized control architecture, a decentralized virtual linkage approach is introduced. As compared to the original virtual linkage approach, the proposed approach uses decentralized architecture rather than hierarchical architecture, which does not require role assignments in each virtual link. In addition, each agent can completely decide its movement with only exchanging states with part of the team members, which makes this approach more suitable for situations when a large number of agents and/or limited communication are involved. Furthermore, the reconfiguration ability is enhanced in this approach by introducing the scale factor of each virtual link. Finally, the effectiveness of the proposed method is demonstrated through simulation results.

1. Introduction

Formation control is one of the most leading research areas in robotics. It has been extensively studied by researchers around the world on different platforms: mobile robots, aerial robots, spacecraft, and autonomous surface and underwater vehicles [1,2,3,4,5,6,7,8].

In the literature, formation control approaches can be classified into three basic strategies: leader-following, behavior-based, and virtual structure. In the leader–follower approach [9,10,11], some agents are considered as leaders, while others act as followers which track the leaders with predefined offset. However, the leader’s motion is independent of the followers. When a follower fails, the leader will keep on moving as predefined and results in the break of the formation shape. In the behavior approach [12,13,14], several reactive behaviors are prescribed (e.g., move-to-goal, avoid-robot, avoid-static-obstacles, and maintain-formation). The action of each agent is derived by a weighted sum of all the behaviors. The main problem with this approach is that it is difficult to formalize the group mathematically and the team of agents is not guaranteed to converge to the desired formation configuration. The virtual linkage approach considers the entire formation as a single rigid body and is able to maintain the formation shape in high precision during manoeuvers [15,16,17]. Perhaps the main criticism of the virtual structure approach is that it has poor reconfiguration ability and needs to refresh the relative positions of all the team members when a different formation pattern changes.

Although these three approaches have been used in many applications, they focus more on maintaining a specified formation pattern throughout a task and few studies address the effects of formation reconfiguration. However, situations also exist where different formation patterns are needed, for example, a group of agents might need to reconfigure into different patterns to go through a gallery. A reconfigurable formation control method named virtual linkage is proposed by the authors in Reference [18]. Instead of treating the whole formation as a single rigid body, as in the virtual structure, the virtual linkage approach considers the formation as a mechanical linkage which is a collection of rigid bodies connected by joints. A virtual linkage is defined as an assembly of virtual structures (named “virtual link”) connected by virtual joints. By coordinating the value of each virtual joint, the virtual linkage approach is able to reconfigure a group of agents into different formation shapes.

Currently, the virtual linkage approach uses hierarchical architecture. In detail, the states of the virtual linkage are implemented in a virtual linkage server and broadcast to all the virtual link servers. Each virtual link’s state is in turn calculated in the corresponding virtual link server and transmits to all its virtual link members. The principal limitation of this hierarchical architecture is that it does not scale well with the number of agents in the team. In addition, due to the communication range limitations, the virtual linkage server might lose communication with some virtual link servers when the agent group covers a large area. A possible way to solve these drawbacks is to use decentralized architecture in which each agent runs a consensus strategy and totally decides its moving action with communication with parts of the members.

The concept of consensus is an important idea in control and information theory, and it has been applied to the formation control of multiple agents [2,16,19,20,21]. The basic idea of a consensus algorithm is that each agent updates its state’s information only based on its neighbors’ state’s information and finally enable the convergence of all the agent’s state’s information.

The main contribution of this paper is the decentralization of the virtual linkage approach via consensus strategies. Motivated by the pros and cons of the virtual linkage approach and consensus algorithm, a decentralized virtual linkage approach is presented in this paper. Instead of using hierarchical architecture, the proposed method instantiates a local copy of the virtual linkage’s state implements the same consensus algorithm on each agent to facilitate the reconfigurable formation control of a team of agents. The decentralized virtual linkage approach has several advantages as compared to the original virtual linkage approach. First, the decentralized architecture overcomes the limitations of the hierarchical architecture. In details, this approach scales well with the number of agents in the group and only requires each agent to communicate with its local neighbors. Second, with the introduction of expansion/contraction rates for each virtual link, this approach has a stronger reconfiguration ability than the traditional virtual linkage approach.

The paper is organized as follows. In Section 2, the preliminary knowledge is presented. Section 3 illustrates the control strategy for the formation movement. Simulation results are in Section 4. Finally, in Section 5, some concluding remarks of this paper are given.

2. Problem Statement

2.1. Virtual Linkage

The virtual linkage is a reconfigurable formation control method proposed by the authors in Reference [18]. The main idea of virtual linkage is to consider the entire formation as a mechanical linkage which is a collection of rigid bodies connected by joints. It can be defined as a collection of virtual structures connected by virtual joints. Instead of specifying each agent’s desired position relative to a single reference frame, as in the virtual structure, the virtual linkage approach tells each agent the virtual link it belongs to and the relative position in the corresponding virtual link. In this way, the designed virtual linkage can be reconfigured into different formation patterns by coordinating the value of each virtual joint.

Definition 1

(Virtual Joints [18]).A virtual joint is a connection between two virtual structures and imposes constraints on their relative movement.

Definition 2

(Virtual Linkage (VL) [18]).A virtual linkage is an assembly of virtual structures (named “virtual link”) connected by virtual joints.

Figure 1 shows the comparison of an intuitive example of a virtual linkage. Three agents are designed into a virtual linkage composed of two virtual links. They are able to be configured into line formation and arrow formation by only changing the virtual joint angle.

2.2. Architecture of the Previous Virtual Linkage

Figure 2 shows the hierarchical architecture of the original virtual linkage approach proposed in Reference [18]. The states of the virtual linkage are implemented in a virtual linkage server and broadcast to all the virtual link servers. Each virtual link’s state is in turn calculated in the corresponding virtual link server and transmits to all the virtual link members. As can be seen in Figure 2, there is a demand for the virtual link server $F_{vli}$ to exchange message with all the agents which belong to the corresponding virtual link. Meanwhile, the virtual linkage server $F$ also has to communicate with all the virtual link servers. The disadvantages of this hierarchical architecture lie in two aspects. First, it does not scale well with the number of agents in the team with limited communication bandwidth. Second, the virtual linkage server might lose communication with some virtual link servers when the agent group covers a large area.

2.3. Preliminaries of Digraphs and Consensus

To implement the decentralized formation control, the communication topology among a group of agents is represented as a diagraph $G=\left(R,\epsilon \right)$. In detail, $R=\left\{R_i|i=\{1,2,\dots n\right\}\}$ is a set of agents and are called as nodes. $\epsilon \in R\times R=\{(R_i,R_j)\}$ is a set of unordered pair of nodes and called as edge. If $(R_i,R_j)$ is an edge of the diagraph, then information flow from $R_i$ to $R_j$ is allowed and $R_i$, $R_j$ are neighbors. Especially, self-loop edges in the form $(R_i,R_i)$ are not allowed. Another way to represent $G$ is called the adjacency matrix $A=\left[a_{i,j}\right]\in R^{n\times n}$. The elements $a_{ij}$ equals 1 if there exists an edge $(R_i,R_j)\in \epsilon$, otherwise $a_{ij}=0$.

Theorem 1

(Consensus algorithm [22]).Let$A=\left[a_{i,j}\right]\in R^{n+1\times n+1}$be the adjacency matrix, where$a_{ij}=1,\forall i,j\in \{1,\dots ,n\}$once the agent j’s formation state estimate is available to agent$i$and 0 otherwise.$a_{i(n+1)}=$1 if agent$i$has knowledge of reference value${\xi }_{contr}$and 0 otherwise, and$a_{(n+1)k}=0,\forall k\in \{1\dots n+1\}$ 0. Then the consensus algorithm

$${\dot{\xi }}_i=\frac{1}{{\eta }_i}{\displaystyle \sum _{j=1}^n{a}_{ij}\left[{\dot{\xi }}_j-\kappa \left({\xi }_i-{\xi }_j\right)\right]}+\frac{1}{{\eta }_i}{a}_{i(n+1)}\left[{\dot{\xi }}_{contr}^r-\kappa \left({\xi }_i-{\xi }_{contr}\right)\right]$$

(1)

guarantees that ${\xi }_i\to {\xi }_d,\forall i$, asymptotically if and only if the graph of $A$ has a directed spanning tree.

2.4. Agent Model

In this paper, a group of n fully actuated agents is considered. The agents are assumed to know their position in a global coordinate frame and can move in any direction with any specified velocity. The model of the agent is considered as follows:

$$\begin{array}{l}{\dot{x}}_k=u_{xk}\\ {\dot{y}}_k=u_{yk}\end{array}$$

(2)

where $p_k=\left[x_k,y_k\right]$ and $u_k=\left(u_{xk},u_{yk}\right)$ are the position coordinate and control input of the kth agent respectively.

3. Decentralization of Virtual Linkage Approach

This section illustrates the decentralization of virtual linkage approach. First, the decentralized architecture is introduced to illustrate the advantages as compared to the hierarchical architecture. Then the consensus formation control is presented to enable each agent to decide its movement independently with only exchanging state information with its local neighbors.

3.1. Decentralized Coordination Architecture

In this paper, instead of using hierarchical architecture in which the desired destination of each agent is informed by the corresponding virtual link server, a decentralized architecture is adopted in the proposed approach. As compared to the hierarchical architecture, there does not exist virtual linkage and virtual link servers, each agent only needs to exchange information with its local neighbors.

Figure 3 shows the architecture diagram of the proposed decentralized virtual linkage approach. Each agent instantiates a local copy of consensus module, denoted as $F_i$. The consensus module $F_i$ is responsible for calculating the instantiation of virtual linkage states ${\xi }_i=(r_i,q_i,{\mathsf{\Theta }}_i,{\lambda }_i)$ for the ith agent, with the inputs of instantiations of virtual linkage states ${\xi }_j=(r_j,q_j,{\mathsf{\Theta }}_j,{\lambda }_j)$ produced by its local neighbors. The main aim of consensus module is to drive each instantiation of virtual linkage state to converge into the desired states ${\xi }^d=(r^d,q^d,{\mathsf{\Theta }}^d,{\lambda }^d)$.

The states of the virtual linkage are defined as a coordination variable $\xi =(r,q,\mathsf{\Theta },\lambda )$, where $r$ and $q$ are the desired position and attitude of the virtual linkage’s reference frame, respectively, $\mathsf{\Theta }=\left({\theta }_1^{},{\theta }_2^{},\dots ,{\theta }_{k-1}^{},{\theta }_k^{}\right)$ is the desired virtual joint angles, where $k$ is the number of virtual links in the virtual linkage. In addition, $\lambda =\left({\lambda }_{1x},{\lambda }_{1y},{\lambda }_{1z},\dots ,{\lambda }_{kx},{\lambda }_{ky},{\lambda }_{kz}\right)$ is a vector which represents the expansion rates of all virtual links. The benefit of introducing $\lambda$ lies that a group of agents is able to reconfigure into more formation shapes since the length and width of each virtual link can be specified now.

3.2. Consensus Control

3.2.1. Implication of Consensus of Virtual Linkage’s State ${\xi }_i$

As mentioned above, each agent has an instantiation of virtual linkage states ${\xi }_i=(r_i,q_i,{\theta }_i,{\lambda }_i)$ and the consensus module implement consensus strategies to ensure each instantiation converge into the desired value. In this part, the implication of ${\xi }_i$ is illustrated.

In the virtual linkage approach, each agent is specified with a vector $\chi =\left(l_i,{}^{vj}{p}_i^{Ini}\right)$ before task. The $l_i$ is the ID number of virtual link which the ith agent belongs to, and ${}^{vj}{p}_i^{Ini}$ is the ith agent’s relative position in the $j$th unit virtual link. Meanwhile, each agent is randomly initialized with a ${\xi }_i=(r_i,q_i,{\mathsf{\Theta }}_i,{\lambda }_i)$. With knowing the $\chi$ and ${\xi }_i$, each agent now is able to calculate its global position in the world.

Note that each ${\xi }_i$ corresponds to a state of the virtual linkage (See Figure 4). The consensus module will ensure all the ${\xi }_i$ converge into a common value

$${\xi }_1={\xi }_2=\dots ={\xi }_n={}^r{\xi }_{contr}.$$

(3)

The team of agents forms virtual linkages and moves in desired formation shapes along a specified path. Note that the formation pattern can be easily reconfigured by reconfiguring the coordinate variable ${}^r{\xi }_{contr}=({}^r{r}_{contr},{}^r{q}_{contr},{}^r{\mathsf{\Theta }}_{contr},{}^r{\lambda }_{contr})$.

3.2.2. Consensus Module

With the previous section, each agent now is initialized with a ${\xi }_i=(r_i,q_i,{\theta }_i,{\lambda }_i)$. This part aims to design a consensus law and drive ${\xi }_i$ to the desired value ${}^r{\xi }_{contr}$. Here, the consensus tracking algorithm in Reference [22]

$${\dot{\xi }}_i=\frac{1}{{\eta }_i}{\displaystyle \sum _{j=1}^n{a}_{ij}\left[{\dot{\xi }}_j-\kappa \left({\xi }_i-{\xi }_j\right)\right]}+\frac{1}{{\eta }_i}{a}_{i(n+1)}\left[{\dot{\xi }}_{contr}^r-\kappa \left({\xi }_i-{\xi }_{contr}\right)\right]$$

(4)

is directly used, where $a_{ij}$ are the elements of the adjacency matrix $A^c=\left[a_{ij}^c\right]\in R^{n+1\times n+1}$ and ${\eta }_i={\displaystyle \sum _{j=1}^{n+1}{a}_{ij}^c}$. The consensus law consists of two parts. The first term uses the information of its neighbors to make all the ${\xi }_i$ converge into a common value which leads to the desired formation shape. The existence of the second term is to make formation move along the desired path ${\xi }_{contr}$. For a connected graph, consensus to the reference value is guaranteed [22].

3.3. Local Control of Each Agent

After each agent has calculated the ${\dot{\xi }}_i$, then each agent is able to update the value of ${\xi }_i$ using Equation (5). Note that $\lambda =[{\lambda }_{1x},{\lambda }_{1y},\dots {\lambda }_{kx},{\lambda }_{ky}]$ represents the expansion/contraction rates of each virtual link along their coordinate frame’s axis (See Equation (6)). Figure 5 shows the geometry definition of the virtual linkage. The position of a specified agent can be calculated using manipulation kinematics in Equation (7). Here, ${}^{vj}{p}_i$ is the relative position of Agent i in the corresponding virtual link j which it belongs to

$${\xi }_i\left(r_i,q_i,{\mathsf{\Theta }}_i,{\lambda }_i\right)={\xi }_i+{\dot{\xi }}_i\cdot dt$$

(5)

$${}^{vj}{p}_i=\left[\begin{array}{c}{\lambda }_{iy}\cdot {}^{vj}{p}_{ix}^{Ini}\\ {\lambda }_{iy}\cdot {}^{vj}{p}_{iy}^{Ini}\\ 1\end{array}\right]$$

(6)

$${}^w{p}_i^d={}^w{T}_R(r_i,q_i)\cdot {}^R{T}_{vj}^d\left({\mathsf{\Theta }}_i,{\lambda }_i\right)\cdot {}^{vj}{p}_i$$

(7)

Finally, the desired absolute position is passed onto the local controller to position the vehicle. Each agent is supposed to know its own position ${}^w{p}_i$, and the consensus control algorithm in Reference [22]

$$u_i={}^w{\dot{p}}_i^d-k_p\cdot \left({}^w{p}_i-{}^w{p}_i^d\right)-{\displaystyle \sum _{j=1}^n{a}_{ij}^v[({}^w{p}_i-{}^w{p}_i^d)-({}^w{p}_j-{}^w{p}_j^d)]}$$

(8)

is used, where $a_{ij}^v$ are the elements of the adjacency matrix $A^v=\left[a_{ij}^v\right]\in R^{n\times n}$. For a connected graph, consensus to the reference value is guaranteed.

4. Simulation and Results

In this section, the proposed decentralized virtual linkage approach is applied to a multi-agents’ formation control scenario using MATLAB. In the scenarios, nine agents are required to move around a circle while maintaining line formation shapes with a uniform distance of 0.1 m or performing formation reconfigurations by coordinating the desired virtual joint angles ${\mathsf{\Theta }}_d$ and the virtual linkage extract/expansion rates ${\lambda }_d$.

4.1. Simulation Setup

In the scenarios, nine agents are designed as a virtual linkage which consists of two virtual links (See Figure 6) and move around a circle with a radius of 1 m in 10 s. The states of $\chi =\left(l_i,{}^{vj}{p}_i^{Ini}\right)$ for each agent is predefined with Equations (9) and (10).

$$Virtua{l}^{}linkage=\{\begin{array}{l}virtua{l}_{}link1=\{agent1,agent2,agent3,agent4,agent5\}\\ virtua{l}_{}link2=\{agent5,agent6,agent7,agent8,agent9\}\end{array}$$

(9)

Recall that ${}^{vj}{p}_i$ is the representation of the $i$th point in the $j$th virtual link coordinate frame. The nine agents are initialized with:

$$\begin{array}{l}{}^{v1}{p}_1^{Ini}=[0,0],{}^{v1}{p}_2^{Ini}=[0.2,0],{}^{v1}{p}_3^{Ini}=[0.4,0],{}^{v1}{p}_4^{Ini}=[0.6,0],{}^{v1}{p}_5^{Ini}=[1,0]\\ {}^{v2}{p}_5^{Ini}=[0,0],{}^{v2}{p}_6^{Ini}=[0.2,0],{}^{v2}{p}_7^{Ini}=[0.4,0],{}^{v2}{p}_8^{Ini}=[0.6,0],{}^{v2}{p}_9^{Ini}=[1,0]\end{array}$$

(10)

Meanwhile, each agent has an instantiation of virtual linkage states ${\xi }_i=(r_i,q_i,{\mathsf{\Theta }}_i,{\lambda }_i)$ and is initialized as:

$${\xi }_i=randn(6,1)$$

(11)

Moreover, there does not exist leader selection for each virtual link. Figure 7 shows the communication topologies used for these two simulations. Notice that apart from agent 2, each agent only needs to exchange ${\xi }_i$ and its own position ${}^w{p}_i$ with its two neighbors.

Initially, the nine agents are required to align in a line formation with a uniform distance of 0.1 m. Then different formation shapes are reconfigured by coordinating the virtual joint angles ${\mathsf{\Theta }}_d$ and the virtual linkage extract expansion rates ${\lambda }_d$. It is worth mentioning that instead of refreshing the relative positions of all the agents, the virtual linkage approach can be reconfigured into different shapes by only changing ${\mathsf{\Theta }}_d$ and ${\lambda }_d$.

In the following simulations, the required trajectory and formation shapes are specified by:

$${\xi }_{contr}=(r_d,q_d,{\mathsf{\Theta }}_d,{\lambda }_d)$$

(12)

4.2. Formation Moving Using Decentralized Virtual Linkage

In this section, the nine agents are required to align in a line formation with a uniform distance of 0.1 m and move around a circle with a radius of 1 m in 100 s. To perform such tasks, the trajectory of the virtual linkage is specified:

$$r_d=\left(-\frac{9\pi }{500}\cos (\frac{\pi }{50}t),\frac{9\pi }{500}\sin (\frac{\pi }{50}t)\right)$$

(13)

Meanwhile, the attitude of the virtual linkage can be expressed as the angle from the $x$ direction of the virtual link1 to the world coordination frame $x$ direction and is also specified as a function of time

$$q_d=\frac{\pi }{50}t+\frac{\pi }{2}$$

(14)

Using the virtual linkage approach, the nine agents are able to maintain a line formation with a uniform distance of 0.1 m by specifying:

$${\mathsf{\Theta }}_d={\theta }_1=0^{\circ }$$

(15)

$${\lambda }_d=[{\lambda }_{1x},{\lambda }_{1y},{\lambda }_{2x},{\lambda }_{2y}]=[0.4,1,0.4,1]$$

(16)

Figure 8 shows the snapshots during the simulation for 100 s.

Figure 9a,b show the reference state and desired trajectory of the virtual linkage defined in Equations (13)–(16). The individual elements of each ${\xi }_i$ are plotted in Figure 9c–h respectively. As can be seen from the figures, the nine random initialized ${\xi }_i(i=1,2,\dots ,9)$ finally converge into reference state defined in Equations (13)–(16). Recall the implication of virtual linkage states ${\xi }_i$ illustrated in Section 3.2.1 in which the convergence of ${\xi }_i$ indicates that the nine agents finally forms a specified virtual linkage and moves in desired formation shapes along the specified path. Therefore, the simulation results indicate the effectiveness of moving in formation using the virtual linkage approach.

4.3. Formation Reconfiguration Using Decentralized Virtual Linkage Approach

In this part, formation reconfiguration simulation is performed to show the virtual linkage approach’s reconfiguration ability by coordinating the desired virtual joint angle ${\mathsf{\Theta }}_d$ and expansion/contraction vector ${\lambda }_d$.

In the original virtual linkage approach [18], the designed virtual linkage is able to present different formation shapes by coordinating the desired virtual joint angle ${\mathsf{\Theta }}_d$. Moreover, an expansion/contraction vector ${\lambda }_d$ is introduced in this decentralized virtual linkage approach to enable the designed virtual linkage to be reconfigured into more formation patterns, as compared to the hierarchical virtual linkage approach. In this simulation, the group of agents is designed as the virtual linkage defined in Equations (9) and (10) and move along the trajectory in Equations (13) and (14). The ${\mathsf{\Theta }}_d$ and ${\lambda }_d$ are specified as Equations (17) and (18) to illustrate the formation reconfiguration ability.

$${\mathsf{\Theta }}_d={\theta }_1=\{\begin{array}{c}\frac{\pi }{100}t\\ -\frac{\pi }{100}t+\frac{\pi }{2}\end{array}\begin{array}{c}\begin{array}{cc}& t\le 50\end{array}\\ \begin{array}{cc}& 50<t<100\end{array}\end{array}$$

(17)

$${\lambda }_d=[{\lambda }_{1x},{\lambda }_{1y},{\lambda }_{2x},{\lambda }_{2y}]=\left[0.4-0.002t,1,0.4-0.002t,1\right]$$

(18)

Figure 10 shows the snapshots during the simulation for 100 s. As can be seen, the team of agents move around a circle with varying formation patterns. It is worth noting that the two virtual links have different lengths at each moment during the simulation, which indicates that the introduction of ${\lambda }_d$ has provided a stronger reconfiguration ability to the virtual linkage approach.

Figure 11a,b report the reference state and desired trajectory of the virtual linkage defined in Equations (13), (14), (17) and (18). The individual elements of each ${\xi }_i$ are plotted in Figure 11c–h, respectively. As can be seen from the figures, the nine random initialized ${\xi }_i$ finally converge into the same value, which indicates that the nine agents finally form a specified virtual linkage and move in desired formation shapes along the specified path. Notice that ${\lambda }_{1x},{\lambda }_{2x}$ and $\mathsf{\Theta }$ of each ${\xi }_i$ track well with the varying function. Recall that a virtual linkage can reconfigure into different formation patterns by changing the joint anglesand extracting/expanding each link with the scale factor ${\lambda }_d$. Thus, the simulation results indicate the effectiveness of formation reconfiguration using the proposed decentralized virtual linkage approach. What is important for us to recognize here, is the coordinate variable ${\xi }_r=(r_d,q_d,{\mathsf{\Theta }}_d,{\lambda }_d)$ in the proposed approach can be arbitrarily set, which provides great potential to perform complicated tasks. For example, when a group of agents is required to go through a gallery, the desired trajectory and varying formation shapes (${\xi }_r=(r_d,q_d,{\mathsf{\Theta }}_d,{\lambda }_d)$) can be solved by plan method.

5. Comparison with Hierarchical Virtual Linkage Approach

In this section, the advantages of the proposed decentralized virtual linkage approach are illustrated through the comparison with the hierarchical virtual linkage approach and the performance is discussed.

5.1. Role Assignments

The detailed architecture of the hierarchical virtual linkage approach when performing the same simulation in Section 4.2 are presented in Figure 12. In the hierarchical virtual linkage approach, there exist virtual link/linkage servers which handle part of the formation control and communicate with part of agents. In reality, the virtual link/linkage server can be implemented in a specified agent, which implies there exist some agents (virtual link/linkage server) which need to perform the formation control computations. However, other agents only need to communicate with their corresponding virtual link server and move according to the states of the corresponding virtual link. In conclusion, there exist different kinds of agents which play different roles and need extra role assignments in the previous approach.

In the decentralized virtual linkage approach, there does not need to be extra role assignment in Figure 3 since all the agents run the same formation control algorithm in Equations (4) and (8).

5.2. Scalability

As described in Section 3.1, each agent can completely decide its movement and only exchange states with its local neighbors. To verify the scalability of the proposed approach, five agents are required to align in a line formation with a uniform distance of 0.1 m and perform the same simulation task in Section 4.2 using the proposed decentralized virtual linkage approach.

To perform such a task, a virtual linkage which also consists of two virtual links is designed as follows:

$$Virtua{l}_{}linkage\_B=\{\begin{array}{c}virtua{l}_{}link1=\left\{agent1,agent2,agent3\right\}\\ virtua{l}_{}link2=\left\{agent3,agent4,agent5\right\}\end{array}$$

(19)

$$\begin{array}{l}{}^{v1}{p}_1^{Ini}=[0,0],{}^{v1}{p}_2^{Ini}=[0.1,0],{}^{v1}{p}_3^{Ini}=[0.2,0],\\ {}^{v2}{p}_3^{Ini}=[0,0],{}^{v2}{p}_4^{Ini}=[0.1,0],{}^{v2}{p}_5^{Ini}=[0.2,0]\end{array}$$

(20)

The extract/expansion rate is set as ${\lambda }_d=[{\lambda }_{1x},{\lambda }_{1y},{\lambda }_{2x},{\lambda }_{2y}]=[1,1,1,1]$. Figure 13 shows the designed virtual linkage and communication topologies used for this simulation. Figure 14 shows the snapshot during the simulation.

Recall that in Figure 3, each agent exchanges its own understanding of virtual linkage states ${\xi }_i=(r_i,q_i,{\mathsf{\Theta }}_i,{\lambda }_i)$ and the individual tracking error ${}^w{p}_i-{}^w{p}_i^d$ with its neighbors. Supposing 6K bits are required to encode each instantiation of virtual linkage ${\xi }_i$, 2K bits for individual tracking error ${}^w{p}_i-{}^w{p}_i^d$, then each agent only needs exchange these 8K bits message with its neighbors. If an agent has M neighbors and communicates with them for every period of time T and then the required bandwidth in units of bits per second is:

$$BW=8K\cdot M/T$$

(21)

The maximum communication bandwidth $B{W}_1$ in this five agents involved simulation occurs in agent 2, since it has three neighbors (See Figure 13b):

$$B{W}_1=8K\cdot 3/T=24K/T$$

(22)

Meanwhile, nine agents are involved in the simulation in Section 4.2, the maximum communication bandwidth also occurs in agent 2:

$$B{W}_2=8K\cdot 3/T=24K/T=B{W}_1$$

(23)

It is worth noting that, the maximum communication bandwidth in the team is determined by the maximum number of agents’ neighbors and does not increase with the number of agents in the group.

In contrast to the decentralized virtual linkage approach, the hierarchical virtual linkage approach does not scale well with the number of agents. As illustrated in Reference [18], the maximum communication bandwidth increases with the number of agents in the team. The results indicate that the proposed decentralized virtual linkage approach is more suitable for situations when a large number of agents and/or limited communication are involved.

5.3. Reconfiguration Ability

As compared to the virtual structure approach, an important property of the hierarchical virtual linkage approach is that it can reconfigure the group of agents into different formation patterns by coordinating the value of virtual joint angles. To evaluate the reconfiguration ability of the virtual linkage approach, the definition of reconfiguration space is proposed:

Definition 3

(Reconfiguration Space).In virtual linkage approach, the reconfiguration space is defined as the set of formation configuration that can be realized by the designed virtual linkage model. In other words, it corresponds to the formation patterns to which the designed virtual linkage can be reconfigured.

To compare the reconfiguration ability between the original and proposed approach, the reconfiguration spaces of these two approaches are evaluated. In the proposed approach, instead of using ${\xi }^d=(r^d,q^d,{\mathsf{\Theta }}^d)$ to control the designed behavior of the team like the hierarchical virtual linkage approach (See Figure 12), ${\xi }^d=(r^d,q^d,{\mathsf{\Theta }}^d,{\lambda }^d)$ is used as the coordinate variable. Meanwhile, each agent i record its relative percentage position ${}^{vj}{p}_i^{Ini}$ in the corresponding virtual link j rather than the relative position ${}^{vj}{p}_i^{}$. The benefit of this is that the virtual linkage is now able to extract/expansion the virtual link using Equation (6), which facilitates the reconfiguration ability of the proposed virtual linkage.

In detail, the reconfiguration spaces of the hierarchical and decentralized approaches are denoted as $R{S}_{hier}$ and $R{S}_{dec}$ respectively. Recall that ${}^{d}r,{}^{d}q$ are the predefined trajectory and attitude of the virtual linkage, the formation pattern is only determined by the vectors ${}^d\mathsf{\Theta }=\left({\theta }_1,\dots ,{\theta }_n\right)$ and ${\lambda }_d=[{\lambda }_{1x},{\lambda }_{1y},\dots ,{\lambda }_{nx},{\lambda }_{ny}]$. Then the $R{S}_{hier}$ and $R{S}_{dec}$ can be expressed as vector spaces:

$$R{S}_{hier}=\left({}^d\mathsf{\Theta },{}^d{\lambda }_{const}\right)=\left({\theta }_1,\dots {\theta }_n,1,1,\dots 1,1\right)$$

(24)

$$R{S}_{dec}=\left({}^d\mathsf{\Theta },{}^d\lambda \right)=\left({\theta }_1,\dots {\theta }_n,{\lambda }_{1x},{\lambda }_{1y},\dots ,{\lambda }_{nx},{\lambda }_{ny}\right)$$

(25)

It is worth noting that $R{S}_{hier}$ can be seen a special case of $R{S}_{dec}$ when

$${\lambda }_d=[{\lambda }_{1x},{\lambda }_{1y},\dots ,{\lambda }_{nx},{\lambda }_{ny}]=[1,1,\dots ,1,1]$$

(26)

and the decentralized approach has stronger reconfiguration ability than the hierarchical approach since

$$R{S}_{hier}\subset R{S}_{dec}$$

(27)

Figure 15 shows an intuitive way of illustrating the stronger reconfiguration ability by introducing the scale factor ${\lambda }_d$. In the original approach, the designed virtual linkage corresponds to a mechanical linkage which has fixed length and width and is only able to reconfigure into different shapes by coordinating the joint angles. However, proposed approach enables each virtual link to extract/expansion its length and width by introducing the scale factor ${\lambda }_d$, which allows the mechanical linkage to reconfigure into more shapes by extracting/expanding each link and changing the joint angles simultaneously.

6. Conclusions

In this paper, the decentralized virtual linkage approach is presented. Instead of using a hierarchical architecture, as with the original virtual linkage approach, the proposed approach uses decentralized architecture in which each agent can independently determine its movement with only the exchange of state information with its local neighbors. The simulation results show the effectiveness of the decentralized virtual linkage approach. There are several advantages as compared with the original virtual linkage approach. First, the proposed approach uses decentralized architecture rather than hierarchical architecture, which does not require role assignments in each virtual link. In detail, there does not exist an agent which needs to exchange with all the agent members in the same virtual link. Meanwhile, each agent can completely decide its movement with only the exchange of states with its local neighbors, which makes this approach more suitable for situations when a large number of agents and/or limited communication are involved. Last but not least, the reconfiguration ability is enhanced in this approach by introducing the scale factor ${\lambda }_d$.

In future work, more attention will be paid to the formation feedback of the virtual linkage approach. Furthermore, the dynamical formation pattern generation and route planning for unknown environments is also an attractive direction and is worth researching.