A Virtual Point-Oriented Control for Distance-Based Directed Formation and Its Application to Small Fixed-Wing UAVs

Abstract

This paper proposes a new algorithm to solve the control problem for a special class of distance-based directed formations, namely directed-triangulated Laman graphs. The central idea of the algorithm is to construct a virtual point for the agents who have more than two neighbors by employing the information of the desired formation. Compared with the existing methods, the proposed algorithm can make the distance error between the agents converge faster and the path consumption is less. Furthermore, the proposed algorithm is modified to be operable for the small fixed-wing UAV model with nonholonomic and input constraints. Finally, the effectiveness of the proposed method is verified by a series of simulation experiments.

1. Introduction

In recent years, multi-agent systems (MAS) have been widely used in military and civilian fields, such as search and rescue, surveillance, and coverage control [1,2,3]. Formation control of MAS has received a significant amount of research efforts and is one of the most extensively studied areas of collaborative control problems.

The objective of formation control is to drive a group of agents to form and maintain desired geometric characteristics (shapes, distances, angles, etc.). In the review literature [4], the methods of formation control can be classified as position-based [5,6], displacement-based [7,8], and distance-based [9,10]. Compared with the other two methods, the distance-based formation control requires fewer individual perception capabilities. More specifically, it can help to design the formation control laws that only use local relative position measurements, where global position measurements or alignment of the agent’s local coordinate frame are not required [11]. The characteristics of the distance-based formation control mentioned above are helpful especially when MAS are deployed in GPS-denied environments. Thus, distance-based formation control has become a research hotspot [12,13,14,15].

In general, distance-based formation control can be classed into two categories: the undirected graph-based [16,17,18,19,20] and the directed graph-based [21,22,23,24,25]. The difference between the two methods lies in whether any two connected agents in the formation are constrained by the same distance constraint. Rigidity is an important concept for undirected graph-based formations. The gradient control method derived from the rigidity of the graph is frequently used in related studies [9,10,16,17,18,19,20] and proved to be effective. However, the rigidity does not suffice to characterize the formations with directed distance constraints [21]. In the directed formations, the control laws are designed based on the conception of so-called persistence [22,23]. Reference [22] investigated the distance-based control of the cycle-free persistent formations and proved the local asymptotic stability of the cycle-free persistent formations under the gradient law. Reference [23] provided a theoretical framework for the distance-based formation based on the directed graphs, and the conception of the persistent graph was defined. Then the work [23] extended the theoretical results to the cycle-free graphs. By deriving the gradient-based control law from a class of potential functions, reference [24] achieved the distance-based directed formation in three-dimensional space, whose interaction graph is acyclic minimally persistent. Reference [25] further analyzed the asymptotical stability of the gradient descent control law for minimally persistent formation graphs, using the stability of the interconnected systems. A finite-time controller based on the sliding-mode method was proposed in reference [26] to solve the formation and tracking problems. Reference [27] developed a unified distributed control strategy for the global and finite-time convergence of affine, rigid, and translational formation. Reference [12] incorporated the distance-based directed formation control into an optimal control framework for the first time and solved it by the state-dependent Riccati equation (SDRE) method. Moreover, numerous efforts have been made in the literature [13,14,28,29] to prevent agents from converging to a reflected formation, where the positions of the agents are just symmetric to the desired ones.

It should be noted that, compared with the formation control based on the undirected graph, the formation control based on the directed graph is more robust to the measurements of the neighbor agents as the communication and control complexities in the directed formations are halved [30]. Although a great number of well-established control methods have been proposed for distance-based directed formations, it has been found in reality that the behavior of the agent with two neighbors needs to be improved when from a directed acyclic triangle formation. More specifically, the existing control methods cannot guarantee that the controlled agents converge to the desired equilibrium position with the shortest paths. Therefore, the aim of this paper is to control the agents to converge to the equilibrium point with a shorter path by fully employing the information of the desired formation. It benefits MAS (not only in the aspect of the convergence rate but also the energy consumption).

This paper (different from previous work) proposes a new algorithm to solve the control problem for a special class of distance-based directed formations, namely directed-triangulated Laman graphs, which are constructed from the leader first–follower (LFF) structure [12]. The central idea of the algorithm is to introduce a virtual target point for each agent with two neighbors and make the formation converge to the desired formation quickly by controlling the agents to the virtual points. The purpose of introducing virtual points is to integrate distance information between neighbors rather than just distance information to neighbors. The construction of virtual points is obtained by a rotation and translation transformation between the actual formation of the desired formation. The transformation is obtained by the singular value decomposition, which exploits the rotational invariance of the two desired formations. It is worth mentioning that the method proposed in this paper can naturally address the distance-based formation problem for the reflected and colinear initial conditions, although many recent references externally introduced the signed area [13,28,29] or an orthogonal basis approach [14] instead. Further, the proposed method is applied to small fixed-wing UAVs, whose control law design is challenging due to the nonholonomic and input constraints [31,32]. Finally, extensive simulation experiments are performed to verify the effectiveness of our algorithm.

The main contributions of this article are summarized as follows.

(1)

A new algorithm is proposed for a class of directed graph formations. By constructing a virtual point for an agent who has two (or three) neighbors in a 2D (or 3D, respectively) formation, it is possible to achieve a shorter path to the desired formation than the existing methods, which brings more benefits, such as faster convergence and less energy consumption for MAS performing real-world missions. In the real world, the path cost of agents usually corresponds to the energy consumption.

(2)

The proposed algorithm is applied to the formation control of the small fixed-wing UAVs. By means of the vector projection as well as double-layer saturation functions, the proposed algorithm is modified to be operable for the fixed-wing UAV with nonholonomic and input constraints.

(3)

Sufficient simulation experiments have been conducted over the proposed algorithm, including the comparison experiments with the existing algorithms, the 3D formation simulations, and the simulations for the distance-based formation of the fixed-wing UAVs. The simulation results verify the effectiveness of the proposed algorithm.

The rest of the paper is organized as follows. In Section 2, some preliminary results on the directed graphs and the stability of the interconnected systems are introduced, and then the problem of the distance-based directed formation control is formulated. Section 3 proposes the control law of the distance-based directed formation in both 2D and 3D. The proposed formation control law is applied to the small fixed-wing UAVs in Section 4. Section 5 shows the simulation results, followed by a conclusion of the paper in Section 6.

2. Preliminaries

2.1. Directed Graphs

The desired formation of n agents can be represented by a directed graph $\mathcal{G}\stackrel{\Delta }{=}(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\{v_1,\dots ,v_n\}$ is the set of n vertices and $\mathcal{E}\subset \mathcal{V}\times \mathcal{V}$ is the set of m edges. Each vertex represents an agent and the neighbor set of agent i is defined as ${\mathcal{N}}_i\left(\mathcal{E}\right)=\{j\in \mathcal{V}|(i,j)\in \mathcal{E}\}$. The edge $(i,j)\in \mathcal{E}$ indicates that agent i can sense the relative position of agent j. The two-dimensional (2D) and three-dimensional (3D) directed graphs are shown in Figure 1, respectively, where the edge $(i,j)$ is represented by an arrow with the head in vertex j and the tail in vertex i.

Let $p_i\in {\mathbb{R}}^d(d=2or3)$ be the position of agent i. Then the framework is represented by $\left(\mathcal{G},p\right)$, where $p=[p_1,p_2,\dots ,p_n]\in {\mathbb{R}}^{dn}$. The rigidity of the framework is defined as follows.

Definition 1

([12]). A framework $\left(\mathcal{G},p\right)$ is said to be rigid if it cannot be continuously deformed to an equivalent framework $\left(\mathcal{G},q\right)$, where the frameworks $\left(\mathcal{G},p\right)$ and $\left(\mathcal{G},q\right)$ are said to be equivalent if $\parallel p_i-p_j\parallel =\parallel q_i-q_j\parallel$ for all $(i,j)\in \mathcal{E}$.

A formation is minimally rigid if it is rigid and if no single edge can be removed without losing rigidity [33]. It is noted that, for the directed formations, the rigidity of the underlying undirected graph (obtained by replacing all directed edges with undirected ones) is not sufficient for the feasibility of the formation [4]. That is, for the directed graphs, one of the important conceptions is persistence [22], which is defined as follows.

Definition 2

([24]). Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a directed graph. A framework $\left(\mathcal{G},p\right)$ is persistent if there exists $ϵ>0$, such that every realization $p^{\prime }$ fitting for the distance set induced by p and satisfying $d(p,p^{\prime })=ma{x}_{i\in \mathcal{V}}\parallel p_i-p_i^{\prime }\parallel <ϵ$, is congruent to p.

Definition 3

([34]). A persistent graph is minimally persistent if it is persistent and if no edge can be removed without losing persistence.

A graph is constraint consistent if every agent is able to satisfy all its distance constraints provided [22]. A directed graph is said to be persistent if it is constraint consistent and the underlying undirected graph is rigid [34]. Figure 2 shows an illustration for the persistence of the directed graphs in 2D space. More details on persistence and constraint-consistence can be found in the literature [22,34].

Henneberg construction is a systematic and iterative way to construct minimally rigid graphs [33]. Henneberg construction consists of two possible operations: (1) vertex addition and (2) edge splitting. Define the Henneberg-directed vertex addition as follows.

Definition 4

([12]). A Henneberg-directed vertex addition in a 2D (3D) space involves adding a vertex with two (respectively, three) directed outgoing edges to an existing directed graph.

The following lemma states the persistence of the constructed graphs.

Lemma 1

([35]). A directed graph $\overline{\mathcal{G}}\stackrel{\Delta }{=}(\overline{\mathcal{V}},\overline{\mathcal{E}})$, obtained by the Henneberg-directed vertex addition to a directed graph $\mathcal{G}\stackrel{\Delta }{=}(\mathcal{V},\mathcal{E})$, is (minimally) persistent if and only if $\mathcal{G}$ is (respectively, minimally) persistent.

Definition 5

([12]). A minimally persistent directed graph that is obtained by a Henneberg-directed vertex addition starting from a leader first–follower (LFF) structure, is a directed-triangulated Laman graph.

Figure 3 illustrates the process of constructing a directed-triangulated Laman graph in 2D. The triangulated Laman graph starts from a leader first–follower (LFF) structure as shown in Figure 3a. Then a new vertex is added with two directed outgoing edges to the existing Laman graph as illustrated in Figure 3b.

2.2. Stability of Interconnected Systems

Lemma 2

([36]). Consider the system $\dot{x}=f(x,u)$, where x is the state, u is the control input, and $f(x,u)$ is locally Lipschitz w.r.t. the variables x and u in the neighborhood of the origin. Then, the system is locally input-to-state stable (ISS) if and only if the unforced system $\dot{x}=f(x,0)$ has a locally asymptotically stable equilibrium point at the origin.

Lemma 3

([36]). Consider the interconnected system

$$\begin{array}{c}\Xi :\dot{x}=f(x,y)\hfill \\ \Sigma :\dot{y}=g(y,u)\hfill \end{array},$$

(1)

if the system Ξ is ISS w.r.t. the input y and the origin of unforced system Σ (the control input $u=0$) is locally asymptotically stable, then the origin of the interconnected system is locally asymptotically stable.

2.3. Problem Formulation

Consider a group of n agents with the single integrator dynamics

$${\dot{p}}_i=u_i,i=1,\dots ,n,$$

(2)

where $p_i,u_i\in {\mathbb{R}}^d(d=2or3)$ are the position and the velocity-level control input of agent i, respectively.

For a set, the notation $\dim (·)$ denotes the number of elements in the set. The desired formation is represented as the directed framework ${\mathcal{F}}^{*}=\left({\mathcal{G}}^{*},p^{*}\right)$ where ${\mathcal{G}}^{*}\stackrel{\Delta }{=}({\mathcal{V}}^{*},{\mathcal{E}}^{*})$, dim$\left({\mathcal{V}}^{*}\right)=n$, dim$\left({\mathcal{E}}^{*}\right)=m$, and $p^{*}=[p_1^{*},\dots ,p_n^{*}]$. The fixed desired distance between agent i and agent j is

$$d_{ij}^{*}=\parallel p_i^{*}-p_j^{*}\parallel >0,i,j\in {\mathcal{V}}^{*}.$$

(3)

Assumption 1.

The desired formation ${\mathcal{F}}^{*}$ is a directed-triangulated Laman graph.

Let $\mathcal{F}=\left({\mathcal{G}}^{*},p\right)$ represent the actual formation of agents, where $p=[p_1,\dots ,p_n]$. Note that $\mathcal{F}$ shares the same directed graph as ${\mathcal{F}}^{*}$, which means that the graph is fixed and known a priori. The physical meaning of $(i,j)\in {\mathcal{E}}^{*}$ in the actual formation is that agent i can measure its relative position to agent j, but not vice versa.

This paper focuses on the formation shape problem. Under Assumption 1, the control objective for this problem is to ensure

$$\parallel p_i\left(t\right)-p_j\left(t\right)\parallel \to d_{ij}^{*}\mathrm{as}t\to \infty ,i,j\in {\mathcal{V}}^{*},$$

(4)

and become convergent at a faster rate.

Remark 1.

It should be noted that the control objective is for all $i,j\in {\mathcal{V}}^{*}$ rather than $(i,j)\in \mathcal{E}$. Thus, the reflected formation is not the desired formation. There is an example of the reflection in 2D as shown in Figure 4, where agent 3 is located at the symmetric position with respect to the line connecting agents 1 and 2. That is, the reflection occurs on agent 3 in Figure 4b despite the fact that agent 3 maintains the desired distance from agents 1 and 2. More details on the reflected formation can be found in reference [33].

3. Main Results

3.1. Formations in 2D Space

For a directed-triangulated Laman graph in the two-dimensional plane, agents have at most two neighbors except for the leader who has no neighbors. In the following, the movements of agents with one and two neighbors are discussed separately. For convenience and to avoid ambiguity, it is specified that agent 1 is the leader, agent 2 is the first follower, and agent 3 is the agent following both the leader and agent 2, as shown in Figure 5. Agents $4,5,\cdots ,n$ are added to the graph according to the method of the node addition mentioned in Section 2.1.

3.1.1. Movement of the Agent Having One Neighbor

Let the distance error of agent 2 be given by

$$e_{21}=\parallel p_{21}\parallel -d_{21}^{*},$$

(5)

where $p_{21}=\parallel p_2-p_1\parallel$. Then the derivative of the error $e_{21}$ is

$$\begin{array}{cc}\hfill {\dot{e}}_{21}& =\frac{d}{dt}\sqrt{p_{21}^T{p}_{21}}\hfill \\ \hfill & =\frac{p_{21}^T\left(u_2-u_1\right)}{e_{21}+d_{21}^{*}}.\hfill \end{array}$$

(6)

Agent 1, i.e., the Leader, is stationary since it is not responsible for any edge, i.e., $u_1=0$. Define the function $\eta \left(x\right)=\frac{x^T}{\parallel x\parallel }$, where $x\in {\mathbb{R}}^2$ is a vector. Then, the error dynamics (6) can be formulated as ${\dot{e}}_{21}=\eta \left(p_{21}\right)u_2$.

The following theorem provides the control law for agent 2, which guarantees that the distance error $e_{21}$ asymptotically converges to zero.

Theorem 1.

For agent 2, the local asymptotic stability of the closed-loop system (6) can be achieved by the control law

$$u_2=-k_2{\eta }^T\left(p_{21}\right)e_{21},$$

(7)

where $k_2>0$.

Proof. 

Substituting the input (7) into Equation (6) yields the following closed-loop dynamics

$${\dot{e}}_{21}=-k_2\eta \left(p_{21}\right){\eta }^T\left(p_{21}\right)e_{21}.$$

(8)

Note that the term $\eta \left(p_{21}\right){\eta }^T\left(p_{21}\right)>0$ for any $p_{21}$ not equal to zero. Then Equation (8) is negative definite so that the closed-loop system is locally asymptotically stable.    □

3.1.2. Movement of Agent Having Two Neighbors

Except for the leader agent 1 and the first follower agent 2, each of the remaining agents only has two neighbors. Thus, as the representative of the remaining agents, agent 3 is discussed below firstly.

For agent 3, there are two distance errors

$$\begin{array}{c}{e}_{31}=\parallel p_{31}\parallel -d_{31}^{*},\hfill \\ e_{32}=\parallel p_{32}\parallel -d_{32}^{*}.\hfill \end{array}$$

(9)

Then, the distance error dynamics of agent 3 can be written as

$$\left[\begin{array}{c}{\dot{e}}_{31}\hfill \\ {\dot{e}}_{32}\hfill \end{array}\right]=\left[\begin{array}{cc}{\mathbf{0}}_{1\times 2}& \frac{p_{31}^T}{e_{31}+d_{31}^{*}}\\ \frac{p_{23}^T}{e_{32}+d_{32}^{*}}& \frac{p_{32}^T}{e_{32}+d_{32}^{*}}\end{array}\right]\left[\begin{array}{c}{u}_2\\ u_3\end{array}\right],$$

(10)

which can be simplified as

$$\left[\begin{array}{c}{\dot{e}}_{31}\hfill \\ {\dot{e}}_{32}\hfill \end{array}\right]=\left[\begin{array}{cc}{\mathbf{0}}_{1\times 2}& \eta \left(p_{31}\right)\\ \eta \left(p_{23}\right)& \eta \left(p_{32}\right)\end{array}\right]\left[\begin{array}{c}{u}_2\\ u_3\end{array}\right].$$

(11)

Let the nominal system (neglecting the effect of the neighbor agent 2) be

$$\left[\begin{array}{c}{\dot{e}}_{31}\hfill \\ {\dot{e}}_{32}\hfill \end{array}\right]=\left[\begin{array}{c}\eta \left(p_{31}\right)\\ \eta \left(p_{32}\right)\end{array}\right]u_3.$$

(12)

Remark 2.

The nominal system (12) is reasonable due to the fact that the input $u_2$ of agent 2 will converge to zero.

Remark 3.

From the error dynamics (12), it can be observed that agent 3 is required to converge the two distance errors to zero by a single input. This means that the information from both errors must be fully utilized to obtain a better control policy, which is the main objective of this paper.

It is not difficult to find a control law for agent 3 to make the nominal system (12) converge. For example, let

$$u_3=-k_3(e_{31}{p}_{31}^T+e_{32}{p}_{32}^T),$$

(13)

which is a directed graph version of the gradient control law. The corresponding proof of stability is given in reference [37].

However, this control law (13) is unsatisfactory, which can be illustrated by a simple example shown in Figure 6, where agents 1 and 2 remain stationary at the desired distance and agent 3 is controlled to achieve the desired formation. However, controlled by the control policy (13), agent 3 does not move along the “shortest” path, which inevitably leads to problems, such as long detours, slower convergence, unnecessary energy consumption, etc.

Therefore, a better solution for this problem is proposed in this paper, concretely, as shown in Theorem 2. Before presenting Theorem 2, the following assumption is set.

Assumption 2.

There exist fixed points ${\overline{p}}_1$, ${\overline{p}}_2$, ${\overline{p}}_3$, and time T, such that

• $p_1\left(t\right)={\overline{p}}_1$, $p_2\left(t\right)={\overline{p}}_2$ for all $t>T$.
• ${\overline{p}}_1$, ${\overline{p}}_2$, ${\overline{p}}_3$ are the three vertices of a triangle where $\parallel {\overline{p}}_3-{\overline{p}}_1\parallel =d_{31}^{*}$, $\parallel {\overline{p}}_3-{\overline{p}}_2\parallel =d_{32}^{*}$.

Remark 4.

Since the motions of agents 1 and 2 are not influenced by agent 3, Assumption 2 holds, implying that the system consisting of agents 1 and 2 is stable, which can be guaranteed by Theorem 1.

Theorem 2.

For agent 3 in 2D space, the proposed control law is

$$u_3=-k_3{\eta }^T\left({\tilde{p}}_3\right)\parallel {\tilde{p}}_3\parallel ,$$

(14)

where ${\tilde{p}}_3$ is solved by Algorithm 1 and $k_3>0$. Under the control law (7) and (14) with Assumption 2, the LFF formation consisting of three agents 1, 2, 3 converges to the desired formation asymptotically.

Proof. 

The proof is obtained by equivalently transforming the original problem. That is, under Assumption 2, control objective (4) for an LFF formation of three agents is equivalent to the agents forming a formation by ${\overline{p}}_1$, ${\overline{p}}_2$, and the virtual point $p_3^{\prime }$.

Algorithm 1 Solve the vector ${\tilde{p}}_3$ in (14) for agent 3 in 2D

Input:$p_1^{*}$, $p_2^{*}$, and $p_3^{*}$ of the desired formation ${\mathcal{F}}^{*}$, and actual position $p_1$, $p_2$, $p_3$

Output:${\tilde{p}}_3$

1: Calculate the centroids: $p_{centroid}^{*}=(p_1^{*}+p_2^{*})/2$, $p_{centroid}=(p_1+p_2)/2$.   2: Let $H=(p_1^{*}-p_{centroid}^{*}){(p_1-p_{centroid})}^T+(p_2^{*}-p_{centroid}^{*}){(p_2-p_{centroid})}^T$.   3: Calculate SVD of $H=US{V}^T$.   4: Let $R=V{U}^T$.   5: if$det\left(R\right)<0$then   6:     $V(:,2)=-V(:,2)$, $R=V{U}^T$;   7: Let $T=-R{p}_{centroid}^{*}+p_{centroid}$.   8: Let virtual point $p_3^{\prime }=R{p}_3+T$.   9: Calculate ${\tilde{p}}_3=p_3-p_3^{\prime }$ 10: return${\tilde{p}}_3$.

Firstly, the virtual point is solved by Algorithm 1 for agent 3, and then the control law (14) is used to ensure the tracking of the virtual point. Consider the Lyapunov function candidate

$$V=\frac{1}{2}{\tilde{p}}_3^T{\tilde{p}}_3.$$

(15)

Then take the differential of Equation (15) yields

$$\begin{array}{cc}\hfill \dot{V}& ={\tilde{p}}_3^T{\dot{\tilde{p}}}_3\hfill \\ \hfill & ={\tilde{p}}_3^T(-k_3{\eta }^T\left({\tilde{p}}_3\right)\parallel {\tilde{p}}_3\parallel )\hfill \\ \hfill & =-k_3{\parallel {\tilde{p}}_3\parallel }^2\le 0,\hfill \end{array}$$

(16)

which means the tracking of the virtual point is achieved exponentially with the control law (14). Eventually, agents form a formation consisting of three points ${\overline{p}}_1$, ${\overline{p}}_2$, and $p_3^{\prime }$. As a result, agents converge to the desired formation.   □

A graphical interpretation of Algorithm 1 is depicted in Figure 7. The first step of Algorithm 1 is to find the rotation and translation transforms between the actual formation and the desired formation. The second step is to obtain the virtual points $p_3^{\prime }$ from the obtained rotation and translation transforms. The third step is to obtain the error vector ${\tilde{p}}_3$.

Further, for a formation of n agents $(n>3)$ as shown in Figure 5, the following theorem guarantees that the agents form the desired formation.

Theorem 3.

Then the asymptotic stability of the closed-loop directed distance-based formation will be achieved if the agents i $(i\ge 3)$ in 2D are controlled by the law, described as

$$u_i=-k_i{\eta }^T\left({\tilde{p}}_i\right)\parallel {\tilde{p}}_i\parallel ,$$

(17)

where ${\tilde{p}}_i$ is solved by Algorithm 1 and $k_i>0$.

Proof. 

Let the error dynamics of the preceding $i-1$ agents be denoted as ${\Sigma }_{i-1}$, and the error dynamics of the i-th agent be denoted ${\Xi }_i$. Then the error dynamics of the preceding i agents can be denoted by

$${\Sigma }_i:\left\{\begin{array}{c}{\Sigma }_{i-1}\hfill \\ {\Xi }_i\hfill \end{array}\right..$$

(18)

The following proof is performed by the recursion method.

From Theorem 2, it is clear that the interconnected system ${\Sigma }_3$ is asymptotically stable. Then, as shown in Figure 8, suppose the interconnected system ${\Sigma }_{i-1}(i>3)$ is asymptotically stable. Then according to Lemma 3, the interconnected system ${\Sigma }_i$ is asymptotically stable because the system ${\Xi }_i$ is locally input-to-state stable with $u_i$.

In summary, the closed-loop directed distance-based formation is asymptotically stable and the proof is complete.    □

In the practical implementation of the Algorithm 1, since the desired formation is described by the distance constraints, Algorithm 1 does not perform well due to its input requiring the coordinates of the agents in the desired formation. By the following method, the desired distances between the agents can be converted to the desired coordinates required in Algorithm 1.

Taking the i-th agent as an example, the coordinate system is established as shown in Figure 9, where the agents j and k lie on the x-axis while agent i lies on a positive y-axis, which is an orthogonal projection on the x axis. Then the corresponding desired position for the i-th agent can be obtained by solving the following equations

$$\begin{array}{cc}\hfill a+b& =d_{jk},\hfill \\ \hfill a^2+c^2& =d_{ik}^2,\hfill \\ \hfill b^2+c^2& =d_{ij}^2,\hfill \end{array}$$

(19)

where a, b, and $c>0$.

Remark 5.

Note that for any given triangle, one can always find a vertex to build a coordinate system that guarantees that a, b, and c are greater than zero.

In summary, the overall distributed control framework for $n>3$ is shown in Figure 10.

3.2. Extension to 3D Formations

In this part, we will extend the proposed algorithm to the multi-agent formations in a 3D space.

Similar to the 2D case, considering the first two follower agents 2 and 3 using the gradient control law, the proposed control law for the i-th agent $(i\ge 4)$ is described as follows

$$u_i=-k_i{\eta }^T\left({\tilde{p}}_i\right)\parallel {\tilde{p}}_i\parallel ,$$

(20)

where the vector ${\tilde{p}}_i$ can be obtained through Algorithm 2.

Algorithm 2 Solve the vector ${\tilde{p}}_i$ in (20) for the ith agent in 3D

Input:$p_j^{*}$, $p_k^{*}$, $p_l^{*}$ and $p_i^{*}$ of desired formation ${\mathcal{F}}^{*}$, where $j,k,l\in {\mathcal{N}}_i$ and actual positions $p_j$, $p_k$, $p_l$, $p_i$

Output:${\tilde{p}}_i$

1: Calculate the centroids: $p_{centroid}^{*}=(p_j^{*}+p_k^{*}+p_l^{*})/3$, $p_{centroid}=(p_j+p_k+p_l)/3$.   2: Let $H=(p_j^{*}-p_{centroid}^{*}){(p_j-p_{centroid})}^T+(p_k^{*}-p_{centroid}^{*}){(p_k-p_{centroid})}^T+(p_l^{*}-p_{centroid}^{*}){(p_l-p_{centroid})}^T$.   3: Calculate SVD of $H=US{V}^T$.   4: Let $R=V{U}^T$.   5: if$det\left(R\right)<0$then   6:     $V(:,3)=-V(:,3)$, $R=V{U}^T$;   7: Let $T=-R{p}_{centroid}^{*}+p_{centroid}$.   8: Let virtual point $p_i^{\prime }=R{p}_i+T$.   9: Calculate ${\tilde{p}}_i=p_i-p_i^{\prime }$ 10: return${\tilde{p}}_i$.

Remark 6.

Note that the relevant theorems and proofs are the same as in the two-dimensional case in Section 3.1 and are omitted here. It should be particularly noticed that Algorithm 2 is referenced from reference [38], which presents an algorithm for solving the least-squares solution of the rotation and translation matrices between two point sets in a three-dimensional space.

Remark 7.

The algorithms in 2D and 3D are similar in terms of steps. Both of the algorithms in 2D and 3D use the singular value decomposition to obtain a rotation and translation transformation between the desired set of points and the actual set of points to construct the virtual points. The difference is that three points are needed to construct the virtual point in 3D space, while only two points are needed in 2D plane.

4. Application to Small Fixed-Wing UAVs

In this section, the proposed algorithm is applied to the formation of the small fixed-wing UAVs. Considering the nonholonomic dynamics of the small fixed-wing UAVs with the constrained inputs, the control law will be modified accordingly to accommodate the inputs of the fixed-wing UAV model.

Suppose that the UAVs fly at a constant height, where each UAV may be at a different height to avoid collisions. The small fixed-wing UAVs in the formation can be modeled as follows.

$$\begin{array}{c}{\dot{x}}_i=v_{i}cos{\theta }_i,\hfill \\ {\dot{y}}_i=v_{i}sin{\theta }_i,\hfill \\ {\dot{\theta }}_i={\omega }_i,\hfill \end{array}$$

(21)

where ${[x_i,y_i]}^T\in {\mathbb{R}}^2$ and ${\theta }_i\in (-\pi ,\pi ]$ are the position and heading angle of the i-th UAV in the global coordinate frame, respectively. The variables $v_i\in \mathbb{R}$ and ${\omega }_i\in \mathbb{R}$ are the linear and angular velocities of the UAV i, respectively, as well as the inputs to system (21).

Remark 8.

It is worth noting that the models of UAVs are described in 2D instead of 3D. It is based on the fact that when performing the formations, the fixed-wing UAVs usually fly at the constant altitudes [15,30,39,40]. For example, in the practical implementations, the UAVs are usually controlled to fly at different altitudes to avoid collisions. In this sense, by setting a given altitude, each UAV performs a fixed altitude flight.

Due to the limits of the physical capabilities of the UAV, the UAV also has to satisfy the forward minimum velocity constraints as well as the angular velocity constraints to prevent stalling. Specifically, the UAV i should satisfy the following constraints:

$$\begin{array}{c}0<v_{min}\le v_i\le v_{max},\\ |{\omega }_i|\le {\omega }_{max},\end{array}$$

(22)

where $v_{min}$, $v_{max}$, and ${\omega }_{max}$ are the minimum, maximum linear velocities, and the maximum angular velocities of the UAVs, respectively.

For the sake of the subsequent formula representation, let

$$h_i=\left[\begin{array}{c}cos{\theta }_i\\ sin{\theta }_i\end{array}\right],h_i^{\perp }=\left[\begin{array}{c}-sin{\theta }_i\\ cos{\theta }_i\end{array}\right].$$

(23)

Remark 9.

$h_i$ and $h_i^{\perp }$ are used as well in reference [41,42,43], where $h_i$ denotes the unit vector in the head direction of the UAV i while $h_i^{\perp }$ points to the vertical head direction. The graphical explanation of $h_i$ and $h_i^{\perp }$ is in Figure 11.

Thus, the modified control inputs for the small fixed-wing model are described as follows

$$\begin{array}{cc}\hfill v_i& =sa{t}_v\left\{sa{t}_{\overline{v}}\left(h_i^T{u}_i\right)+h_i^T{\overrightarrow{v}}_0)\right\},\hfill \\ \hfill {\omega }_i& =sa{t}_{\omega }\left\{sa{t}_{\overline{\omega }}\left(h_i^{\perp T}{u}_i\right)+h_i^{\perp T}{\overrightarrow{v}}_0\right\},\hfill \end{array}$$

(24)

where the vector ${\overrightarrow{v}}_0\in {\mathbb{R}}^2$ is the desired common velocity,

$$\begin{array}{c}sa{t}_v\left(x\right)=\left\{\begin{array}{cc}{v}_{min},\hfill & x\in (-\infty ,v_{min})\hfill \\ x,\hfill & x\in [v_{min},v_{max}]\hfill \\ v_{max},\hfill & x\in (v_{max},+\infty )\hfill \end{array}\right.,\hfill \\ sa{t}_{\overline{v}}\left(x\right)=\left\{\begin{array}{cc}-{\overline{v}}_{max},\hfill & x\in (-\infty ,-{\overline{v}}_{max})\hfill \\ x,\hfill & x\in [-{\overline{v}}_{max},{\overline{v}}_{max}]\hfill \\ {\overline{v}}_{max},\hfill & x\in ({\overline{v}}_{max},+\infty )\hfill \end{array}\right.,\hfill \\ sa{t}_{\omega }\left(x\right)=\left\{\begin{array}{cc}-{\omega }_{max},\hfill & x\in (-\infty ,-{\omega }_{max})\hfill \\ x,\hfill & x\in [-{\omega }_{max},{\omega }_{max}]\hfill \\ {\omega }_{max},\hfill & x\in ({\omega }_{max},+\infty )\hfill \end{array}\right.,\hfill \\ sa{t}_{\overline{\omega }}\left(x\right)=\left\{\begin{array}{cc}-{\overline{\omega }}_{max},\hfill & x\in (-\infty ,-{\overline{\omega }}_{max})\hfill \\ x,\hfill & x\in [-{\overline{\omega }}_{max},{\overline{\omega }}_{max}]\hfill \\ {\overline{\omega }}_{max},\hfill & x\in ({\overline{\omega }}_{max},+\infty )\hfill \end{array}\right..\hfill \end{array}$$

(25)

and the controller parameters ${\overline{v}}_{max}$ and ${\overline{\omega }}_{max}$ satisfy

$$\begin{array}{cc}\hfill 0<{\overline{v}}_{max}& \le \frac{v_{max}-v_{min}}{2},\hfill \\ \hfill 0<{\overline{\omega }}_{max}& \le {\omega }_{max}.\hfill \end{array}$$

(26)

Remark 10.

Here, the projection vectors are used to modify the proposed control law $u_i$ in Equation (17) to the control inputs $v_i$ and ${\omega }_i$ as shown in Figure 12, while the bilayer saturation functions are used to fit the input constraints. The stability analysis of the modified control law (24) can refer to the proof of Theorem 1 in our previous work [44]. In Section 5, the effectiveness of the modified control law (24) will be verified.

5. Simulation Results

In this section, a series of simulation experiments are used to verify the effectiveness of the proposed controller. Firstly, we compare the proposed method with several existing methods, including the gradient control law, the sliding mode method, and the SDRE method. The comparison experiments are also performed in some special initial conditions, such as the colinear and reflected cases. Then, the simulation of 3D formations is performed. Moreover, to further illustrate the practicality of the proposed controller, the proposed controller is applied to the formation control of the small fixed-wing UAVs, which are subject to the nonholonomic dynamics and the asymmetric input constraints.

5.1. Comparison Experiments

In the comparison experiments, the three control laws used for comparison take the following form:

$$\begin{array}{c}\begin{array}{cc}\hfill \mathrm{Gradient}\mathrm{control}& :u_i=-k{\displaystyle \sum _{j\in {\mathcal{N}}_i}}\eta \left(p_{ij}\right)e_{ij},\hfill \\ \hfill \mathrm{Sliding}\mathrm{mode}& :u_i=-k_s{sgn}^{\alpha }\left({\displaystyle \sum _{j\in {\mathcal{N}}_i}}{p}_{ij}{e}_{ij}\right),\hfill \\ \hfill \mathrm{SDRE}\mathrm{method}& :u_i=-R^{-1}{B}_i^T{S}_i{e}_i,\hfill \end{array}\hfill \end{array}$$

(27)

where $i=1,\dots n$ and the remainder of the relevant notation definitions can be found in [12,24,26]. The parameters of those controllers are listed in

Table 1. The parameters of three controllers.

k	${\mathit{k}}_{\mathit{s}}$	$\mathit{\alpha }$	Q	R
1	1	0.5	$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$	$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$

. Next, three sets of comparison experiments are conducted in two-dimensional space.

Remark 11.

The controller parameters in Table 1 are the result of careful selection and optimization. The parameters k, $k_s$, and α are consistent with references [24,26]. The parameters Q and R have been tested to be in a reasonable range and we found that the two parameters only have a small influence on the performance of the controller.

5.1.1. Comparison Experiment 1

To make the experiments clearer for the comparison, a formation experiment consisting of three agents is first conducted. Consider a LFF structure for the three agents and the underlying graph is shown in Figure 3a. The edge set ${\mathcal{E}}^{*}=\{(2,1),(3,1),(3,2)\}$ and the desired distance $d_{ij}^{*}=5$ where $(i,j)\in \mathcal{E}$. The initial positions of the three agents are set as $p_1\left(0\right)={[0,0]}^T$, $p_2\left(0\right)={[0,5]}^T$, and $p_3\left(0\right)={[10,20]}^T$. Note that agents 1 and 2 remain stationary because the distance between them is just the desired distance.

The trajectories of the agents controlled by the four control laws are shown in Figure 13. As can be seen, the proposed controller directly drives agent 3 to its final location. This is due to the fact that the proposed controller utilizes the information of the desired distances between the neighbors compared to the other three controllers. The distance errors $e_{31}$ and $e_{32}$ are shown in Figure 14. The results show that the agents converge to the desired formation with a faster rate when being controlled by the proposed method.

5.1.2. Comparison Experiment 2

On the basis of the comparison experiment 1, the initial position of agent 2 is reset to be $p_2\left(0\right)={[4,24]}^T$, which means that agent 2 does not stay at the desired distance from agent 1 in the initial moment. The trajectories and the distance errors are shown in Figure 15 and Figure 16, respectively.

From the results, the proposed method still achieves similar results as in comparison experiment 1, i.e., faster convergence and less path cost as compared to the other three methods.

5.1.3. Comparison Experiment 3

Comparison experiment 3 considers two cases of initial conditions: (i) the agents are placed collinearly, and (ii) the agents are reflected with respect to the edges $(3,1)$ and $(5,3)$ in Figure 17. The desired formation ${\mathcal{F}}^{*}$ consisting of six agents is illustrated in Figure 17.

The trajectories of agents initiating with the colinear conditions are shown in Figure 18, where only the agents controlled by the proposed method converge correctly to the desired formation. The reason for the complete failure of the gradient controller and the sliding mode controller under the colinear conditions is that the closed-loop system controlled by these two controllers has an undesired equilibrium point, i.e., the formation where all the agents are colinear. Note that the reflected formation occurs when the agents are controlled by the SDRE method as shown in Figure 18c. It can be observed in Figure 19 that the convergence rate of the formation controlled by our method is obviously faster than the counterpart controlled by the SDRE method.

Figure 20 shows the case when the initial positions of the agents are just the reflected ones of the desired formation. It can be seen in Figure 20 that the desired formation is formed by the proposed method, while the other three methods perform unsatisfactorily. Notice that in Figure 21, the distance errors are zero at $t=0$ because at the initial moment the formation of the agents is a reflection of the desired formation although the agents keep the desired distance from each other.

5.2. Three-Dimensional Formation Situations

In this subsection, we consider a formation of the agents in the three-dimensional space. The desired formation shape is a cube in the three dimensions as shown in Figure 22.

Figure 23 shows the results for the 3D formation, where the graph consists of the eighteen directed edges and the initial conditions are obtained randomly. It can be seen in Figure 23 that the desired cube formation is formed in 3D, while the distance errors of all the edges converge to zero.

5.3. Distance-Based Directed Formation of the Small Fixed-Wing UAVs

In this simulation, a formation of five small fixed-wing UAVs will be realized. Let the underlying graph of the UAVs be as shown in Figure 24. The desired common velocity ${\overrightarrow{v}}_0$ is set as ${\overrightarrow{v}}_0={[15\sqrt{3}/2,15/2]}^T$. The corresponding parameters of the velocity constraints are set as

$$\begin{array}{c}{v}_{min}=10(\mathrm{m}/\mathrm{s}),\hfill \\ v_{max}=18(\mathrm{m}/\mathrm{s}),\hfill \\ {\omega }_{max}=\pi /4(\mathrm{rad}/\mathrm{s}).\hfill \end{array}$$

(28)

The simulation results are illustrated in Figure 25, where the desired UAV formation is achieved by the proposed method. Moreover, it can be seen from Figure 25c,d that the linear and angular velocities constraints are both satisfied.

6. Conclusions

In this paper, we propose a new method to solve a class of distance-based formation problems for the directed graphs. Our method can achieve a shorter convergence path of the formation as our method introduces the information of the desired distances between the neighbors compared to other methods. Nevertheless, some issues remain to be considered, such as the distance-based formation using network communication where the formation system is subject to uncertainties and communication delays. In the future, we will try to address these issues using robust adaptive dynamic programming and the event-triggered mechanism [45,46].