Circular Formation Control with Collision Avoidance Based on Probabilistic Position

1  Introduction

Owing to the current technological development/progress in computation and communication, distributed cooperative control of multi-agent systems (MASs) has received enormous attention from research communities in recent years. Its practical applications include search mechanisms, navigation, map manipulation, target interception, and tracking [1–4]. The main objective of cooperative control theory is to develop and design a protocol that guarantees the synchronization of a group of neighboring agents via local information exchange. Literature studies present different phenomena in cooperative control, such as consensus [5,6], formation control [7], and containment control [8].

Formation control is one of the fundamental research problems in distributed cooperative control of MASs that has presented wide application prospects, such as unmanned aerial vehicles (UAVs) [9], unmanned ground vehicles (UGVs) [10], autonomous underwater vehicles (AUVs) [11], coordination control of satellites [12], etc. In general, formation control aims to design a distributed control protocol that leads the state/output of the agent to maintain an expected shape. The formation control problem has been investigated using different control techniques in recent years. Based on [13], the techniques are classified into three strategies, namely, distance-based [14], displacement-based [15], and bearing-based [16] strategies. The consensus-based techniques are used to address the formation control problems in [17,18]. In [19], the adaptive control design is introduced to address the formation tracking problem of multiple mobile robots with unknown skidding and slipping environments. The distributed formation control problems are addressed in [20] by using an event-triggered mechanism. Based on multiple Euler-Lagrange functions, the authors in [21] investigated H∞ formation control design. In [22], a novel fault-tolerant control strategy is developed by utilizing decentralized state observers for multi-quadrotor systems. Based on the leader-follower method, a distributed adaptive-based sliding mode formation control scheme is designed for a class of second-order nonlinear MASs with unknown dynamics [23].

Among the challenging problems proposed in the formation control of MASs, the circular formation becomes a hot subject of interest because of its manifold applications, such as source-seeking exploration [24], surveillance [25], and sensor networks [26]. Circular formation control is to drive a group of agents to converge to or move on a defined circular trajectory with spacing adjustment between the neighboring agents [27]. Up to now, scholars are progressively adopting innovative research strategies and measurements to investigate the circular formation control problem of MASs. Several methodologies have been proposed to deal with the circular formation control problem, including the leader-follower technique [28], the cyclic pursuit technique [29], the behavioral technique [30], and the virtual structure technique [31]. In [32], authors developed a circular motion control law and phase-distributed protocol to achieve a circular formation for any preset relative phase. In [33,34], distributed control protocols are designed to solve the circle-forming problem of a group of anonymous agents. The circular formation stabilization of networked dynamic unicycles is considered in [35], where a distributed dynamic protocol is developed for each unicycle. Interested readers are referred to the survey paper [36] for a comprehensive review of the techniques and methodologies in circular formation control of MASs.

From a practical perspective, collision avoidance is one of the fundamental and challenging problems in formation control. A collision avoidance strategy is developed for multiple UAVs in formation flight to avoid collisions and obstacles [37]. In [38], formation tracking control with collision avoidance problem is addressed for nonlinear MASs by adopting the artificial potential approach with the neural networks technique. A novel control scheme based on adaptive neural networks is designed for a class of second-order nonlinear MASs to solve the formation control problem with multiple tasks, including obstacle avoidance, collision avoidance, and connectivity maintenance [39].

Although considerable research efforts devoted to the circular formation control problem, most of the existing results consider the single-integrator model [28,33,40], and only a few works have considered collision avoidance. Thus, it is of practical significance to study more realistic models, such as models that capture UAV systems. In this work, the circular formation problem has a wide array of practical potential applications in engineering. It has applications in the defense industry to provide surveillance and navigation of a particular area within a defined radius. It has applications in escorting and patrolling tasks of multi-robots, such as UAVs patrolling borders [41]. These facts motivate us to develop a novel distributed control scheme to achieve circular formation and meet practical challenges.

Motivated by the aforegoing observation, the problem of circular formation for the second-order MASs based on a probabilistic position is addressed in this paper. The mobile agents are required to follow a circular trajectory such that the agents in the circular trajectory must have the same direction. Compared to the existing circular formation control techniques [28,42], the leader-follower strategy and probabilistic position are combined to solve the circular formation problem, which significantly enhances the flexibility and stability of the system. The main difficulty in this paper is caused by the fact that the agents may get a tangential path after getting in a circular trajectory. By using the Lyapunov methods, convergence analysis of the designed circular formation control protocol is provided. The main contributions of this work are as follows. First, unlike [33,40], this paper considers the circular formation of second-order MASs, which makes this work more application-oriented. The second-order systems can be used to model many real systems, such as unicycle dynamics (after dynamic feedback linearization) or quadrotor UAV simplified dynamics. Second, by introducing a probabilistic position control law, a novel distributed control protocol is proposed to achieve circular formation, which is different from [43]. The probabilistic position law is proposed to represent the probabilistic position of each agent in the circular trajectory. It is shown that under the proposed control scheme the agents move along the circular trajectory of the desired radius and also avoid the tangential path. Third, the proposed control strategy guarantees inter-agent collision avoidance.

The rest of the paper is organized as follows. Section 2 represents notations and preliminaries. Section 3 formulates the circular formation problem and presents the controller design. Section 4 discusses the main results. Finally, Section 5 presents simulation results and Section 6 summarizes the conclusions of the study.

2  Notations and Preliminaries

2.1 Notations

Throughout this paper, let Rn, Rn×n, and Z represent the sets of nth dimensional space, (n×n) real matrices, and integer numbers, respectively In denotes the identity matrix of dimension . denotes the transpose of a matrix or vector M. diag{A1,…,An} denotes a block diagonal matrix. ∥x∥ is the Euclidean norm of a vector x. The notation ⊗ stands for the Kronecker product. The subscript 𝒪 represents the orbits. 𝒞=1,2 represents the orientation of agents such that 𝒞=1 for the clockwise direction and 𝒞=2 for the counterclockwise direction.

2.2 Graph Theory

In MASs, the interaction topology is represented by a graph [44]. A graph 𝒢 (𝒱,ℰ) is a pair of avertex set 𝒱={v1,v2,…,vn} and an edge set ℰ={eij=(vi,vj)}⊂𝒱×𝒱. The weighted adjacency matrix of graph 𝒢 is given by 𝒜=[aij]∈Rn×n where aij=1 if (vi,vj)∈ℰ and aij=0 otherwise. Neighbors set of the vertex is denoted by a set 𝒩i={j| aij>0}. The graph 𝒢 is undirected if aij=aji. The (weighted) graph Laplacian matrix ℒ∈Rn×n is represented as ℒ=𝒟−𝒜 where 𝒟=diag{di} is the degree matrix with di=∑j∈𝒩i aij. A graph 𝒢 contains a spanning tree if there exists a node from vr such that there is a path vr to any node in the graph. A graph 𝒢 is strongly connected if every pair vi, vj are connected.

Definition 1 (Laplacian). The Laplacian matrix is given as ℒ=[lij𝒪𝒞] where

[lij]𝒪𝒞={∑𝒪,j=1n⁡[aij]𝒪𝒞 if j≠i,𝒞=1,2,0otherwise .

where the adjacency matrix is defined by 𝒜ij=[aij]𝒪𝒞 for i,j=1,…,n,

[aij]𝒪𝒞={1if (i,j)∈𝒪i∪ 𝒪i+1.0otherwise .

3  Control Law Design

3.1 Problem Formulation

We consider a group of n(n≥2) agents initially located in a plane, each agent must maintain circular formation as shown in Fig. 1. The dynamics of each agent i is defined as

p˙(t)=vi(t),v˙(t)=ui(t), i=1,…,n,(1)

where pi∈Rn, vi∈Rn , and ui∈Rn represent the position, velocity, and control input of the agent i to be designed, respectively.

Figure 1: The desired circular formation in a counterclockwise direction, maintaining circular distance and avoiding tangential movement

Definition 2. (Circular path). The agents move in a circular formation if

∥pi−p0∥=r,i=1,…,n.(2)

For a given desired radius vector of different circular trajectories ri,i=1,…,n the agents maintain circular formations with different radii if

∥pi−p0∥=ri, i=1,…,n.(3)

If iri=jrj then the agents are moving in the same circular trajectory otherwise they are in a different circular trajectory.

Definition 3. (Agents direction). The agent must have the same direction of motion θi∈[0,2π], i=1,…,n in the same orbit/circular path such that ∑i θi=2π but for different circular trajectories, the agent direction may be different.

Definition 4. (Collision avoidance condition). For given desired αi∈θ⊂[0,2πn]. The agents in the same circular trajectory have the property of collision avoidance if

∥αi−αi±1∥>0,∀i,(4)

and constant.

Definition 5. (Problem definition). For a given n (n≥2)agents, design a distributed control law uifor i=1,…,n such that each agent maintains the circular formation with collision avoidance.

To achieve this objective, let us assume that:

•   All the agents must move in one direction with the same constant angular velocity in the same orbit.

•   There exist a constant distance between agents to avoid collisions, the distance between agents is rotational in the same circle as well as different circles.

•   Each agent knows its initial velocities ωi(t0).

•   The position of each agent is presumed, because of its circular trajectory.

•   The dynamics of followers (trajectory and uncertainty) are stabilizable which means that the pair (A,B) is stabilizable.

3.2 Probabilistic Position

The probabilistic position law of each dynamic agent along circular trajectories modeled by the system Eq. (1) can be designed as

P(r)=n−∫02πr (1(n−1)t)ndt

4  Main Results

Lemma 1. [44] Let ℒ∈Rn×n be the Laplacian matrix of an undirected graph𝒢, then

1.    ℒis symmetric and positive semi−definite, and has at least one zero eigenvalue with associatedeigenvector 1; that is, ℒ1=0;

2.    If 𝒢 is connected, then 0 is a simple eigenvalue of ℒ, and all the other n−1 eigenvalues are positive.

Lemma 2. (Young’s Inequality, [45]). If a and b are non−negative real numbers and p,q are positivereal numbers such that 1/p + 1/q = 1,then ab≤app+bqq.

Lemma 3. [46] Under a time-invariant information exchange topology, the continuous-time protocol achieves consensus asymptotically if and only if the information exchange topology has a spanning tree.

Lemma 4. Consider the multi-agent system (1). The system uncertainties are supposed as:

i.   Agents not maintaining a circular path, ∥pi−p0∥≠ri,∀i,

ii.   Agents may get a tangential path after getting in a circular trajectory, getting a p˙i slope when∥pi−p0∥∥p˙i−p0∥such that ∥pi−p0∥∈ri and ∥p˙i−p0∥≠ri.

Proof.

i.   Agents not maintaining a circular path is a contradiction to Definition 2, which will affect formation. Let’s consider ri∈Z such that Z=±1,±2,±3,… circles with area A=πr2 . Let’s assume that pi is the position of agent i and pj is the position of agent . If (pi−pj)∈ri (circular path), we have d(pi−pj)dt because the derivative across any point/line/plane is a slope A=π,4π,9π,16π,…. Let’s assume the distance covered by pi is π, then the distance covered by pj≃π, which means: if (pi−pj)≃0 is achieved it means that the consensus is achieved for i and j, pi and pj are following the same trajectory (circular).

ii.   While getting a tangential trajectory is a contradiction to Definition 2. We have d(pi−pj)dt=0, which means that the value for (pi−pj)≃0, implies that agent i is the leader following the circular path, and j follows the same trajectory.

Remark 1. Each dynamic agent must follow the circular trajectory in the same radius and avoid the tangential path.

Theorem 1. Consider the multi-agent system (1). The control law generated by the probabilistic position is designed as

ui=𝒞ij𝒪𝒞+k∑i∈𝒩j aij(vi−vj)(5)

such that 𝒞ij𝒪𝒞=f(P), will make sure that the agents remain in the same radius and avoids the tangential path where 𝒞ij𝒪𝒞 represents the probabilistic position of each agent in each circle,𝒪𝒞 represents the circular orbit, and k control gain.

Proof. For the multi-agent system (1), the controller is designed as follows [6]:

ui=∑i∈𝒩j (pi−pj)+∑i∈𝒩j (vi−vj),

in our paper, ∑i=1i≠jn (pi−pj) converges to a constant value it will make sure that agents are apart from each other while maintaining strong communication links. For general formation control design, we construct the Lyapunov function as

V(e)=eT(p,v)Pe(p,v)

such that e(p,v)=[pT,vT], where e(p,v) is error function e(p,v)→0, as T→∞. Then, the derivative of V(e) is given by

V(e)=eT(p,v)Pe˙(p,v)+e˙T(p,v)Pe(p,v)

The desired trajectory is described as follows

p=cos(θ)+jsin(θ),p˙=cos(θ)−jsin(θ),θ˙=12(x32+xn−1).

The error can be calculated as e(θ)=I3−[p,p˙,θ˙]T. We have e˙T=eTAT. Thus

A=[sin(θ)−jcos(θ)1−(cos(θ)+jsin(θ))000sin(θ)+jcos(θ)1−(cos(θ)−jsin(θ)000−12(32p12+(n−1)pn−2)1−12(p32+pn−1)]

By solving the Lyapunov equation ATP + PA=−Q for any Q>0, the matrix is obtained as

P=−12×A−1=12×[1−(jsin(θ)+cos(θ))jcos(θ)−sin(θ)000−jsin(θ)+cos(θ)−1jcos(θ)+sin(θ)00012(32p12+(n−1)pn−2)1−12(p32+pn−1)]

The matrix P is positive semi-definite if and only if

{P11=1−(cos(θ)+jsin(θ))−sin(θ)+jcos(θ)>0for  θ=0; P22=−jsin(θ)+cos(θ)−1jcos(θ)+sin(θ)>0for  θ=(π6,15π36);P33=(32p12+(n−1)pn−2)1+12(p32+pn−1)>0for  θ=(0,π1.59); 

Remark 2. Theorem 1 leads to the contradiction that ∑i∈𝒩j (pi−pj) converges to 𝒞ij𝒪𝒞 only in the static case. Thus, Lemma 4 is true only for a static case. The results are extended to the dynamic case by applying the virtual leader-follower strategy in the next subsection.

4.1 Virtual Leader-Follower Strategy

In this subsection, the virtual leader-follower strategy is designed to deal with the system uncertainties where each follower agent tracks the virtual leader dynamics. A distributed hybrid control law is designed to ensure the formation control stabilization and consensus in presence of the uncertain trajectory with tracking error converging to zero.

Lemma 5. The dynamic of the virtual leader follows a desired circular trajectory defined as

θ˙0=ω0,ω˙0=u0,(6)

where θ0∈[0,2π],ω0, and u0 are respectively the rotation angle, angular velocity, and control input of the virtual leader given as

u0=k0∑i=1n bi0(vi−v0),(7)

where k0is the control gain, bi0=diag(B1,B2,…,Bn) denotes the connectivity anddirect access of thefollower agent i to the virtual leader.

Proof. The distributed formation stabilization controller can be designed as

uform=ui+u0,(8)

and the consensus controller is proposed as follows

ucons=∑𝒪=1𝒞=1,2n ∑i∈𝒩j aij𝒪𝒞((pi+pip)−(p0+p0p)).(9)

By adding the two controllers Eqs. (8) and (9), a distributed hybrid controller is given by

ui=uform+ucons,

which is equivalent to

ui=𝒞ij𝒪𝒞+k0∑i∈𝒩j bi0(vi−v0)+k∑i∈𝒩j aij𝒪𝒞(vi−vj)+∑𝒪=1𝒞=1,2n ∑i∈𝒩j aij𝒪𝒞((pi+pip)−(p0+p0p)).(10)

For 𝒞=2, we obtain

ui=∑i∈𝒩j [aij𝒪2((pi+pip)−(p0+p0p)+k(vi−vj))+k0∑i∈𝒩j bi0(vi−v0)+Cij𝒪2].(11)

Eq. (11) can be also written in a vector form as

ui=∑i∈𝒩j ℒijpij+kℒijvij+k0bi0ℒi0vi0+𝒞ij02,(12)

where pij=((pi  +  pip)−(p0 + p0p)). Furthermore, for θ∈[0,2π], by substituting p=r(cos(θ)+jsin(θ)) and v=p˙ into Eq. (11), we obtain

ui=∑i∈𝒩jaij𝒪2[ri(cos⁡(θi) + jsin(θi)) + rip(cos⁡(θip) + jsin(θip))−r0(cos⁡(θ0) + jsin(θ0))+ r0p(cos(θ0p) + jsin(θ0p)) + k(ri(−sin(θi) + jcos(θi))−rj(−sin(θj) + jcos(θj)))]+k0∑i∈𝒩jbi0[ri(−sin(θi) + jcos(θi))−r0(−sin(θ0) + jcos(θ0))] + Cij𝒪2.(13)

Remark 3. Under the proposed control scheme, inter-agent collision avoidance is guaranteed under the following assumptions:

a)   All the agents move in a counterclockwise direction, i.e., orientation with constant velocity.

b)   There exist a positive or constant relative distance between the agents, i.e., ‖pi(t)−pj(t)‖>0 and constant,∀i,j∈{1,2,…,n}, i≠j, at all t≥0.

Lemma 6. Consider a graph 𝒢 with a directed spanning tree. The consensus is reached for the multi-agent system Eq. (1) and the control law Eq. (12) with a complex polynomial of the following form

i(s)=s2+(a1+ib1)s+a0+ib0,

where a1,b1,a0,b0∈R. Thus, i(s) is stable if

a1>0

and

a1b1b0+a12a0−b02>0.

Proof. Let A=(−1000.5), B=(0010), and hi=(pi,vi)T for i=1,…,n. We have

h˙i=Ahi+((ℒij⊗B)+k(ℒij⊗B)+k0bi0(ℒi0⊗B)+𝒞ij02B)h,

for h=(h1T,h2T,…,hnT)T. Then, it can be written as

h˙=[(In⊗A)+(ℒij⊗B)+k(ℒij⊗B)+k0bi0(ℒi0⊗B)+d)]h,

for ℒ=PJP−1, we have

h˙=(P−1⊗I2)[(In⊗A)+(ℒij⊗B)+k(ℒij⊗B)+k0bi0(ℒi0⊗B)+d]=[(P−1⊗A)+(JP−1⊗B)+k(JP−1⊗B)+k0bi0(JP−1⊗B)+P−1d]=[(I2⊗A)+(J⊗B)+k(J⊗B)+k0bi0(J⊗B)+P−1d]h,

where J is the Jordan matrix given as

Jl=(ul0001⋱0000⋱0⋱10ul)nl×nl,

such that ul are complex eigenvalues. By using the Leonhard-Mikhailov theorem, the condition of spanning (directed) is true only if 0<bi0(k + 1)<1 and for every i=1,…,n,

f(k,bi0,ul)=(bi0/(k+1))21−bi0(k+1)[sin2(θi)−sin2(ϕi)]2×[cos2(ϕi)−cos2(θi)]2−4sin2(θi)sin2(ϕi)>0,

where

ϕi=(|k+1|(∥ul∥)+|d|−sign(k+1)(Re(ul))2)1/2,

θi=(|k+1|(∥ul∥)+|d|+sign(k+1)(Re(ul))2)1/2,

which completes the case for a directed spanning tree.

Remark 4. In the circular orbit, we have an infinite set of points for the tangential trajectory. Let’s define hi as the tangential path, for each i=1,…,n,hi∈(−1,1). Thus, ri will no longer be the radius as the agent not following the circular path, it will be changed to si, where si is the tangent on any point in the circle. The tangential trajectory si(−sin(hi) + jcos(hi)) will vary in the interval si∈(−1,1).

From Remark 4, for every i=1,…,n, there exists δi which defines the signal of the actual trajectory to be followed as

{δ0(hi)=r0(cos(h0)+jsin(h0))δi(hi)=r0−si(cos(hi)+jsin(hi))+ri,(14)

for i=1,…,n. Then, differentiating Eq. (14) yields

{δ˙0(θ0)=r0(−sin(θ0)+jcos(θ0))δ˙i(θi)=−si(−sin(θi)+jcos(θi))

To show the stability of the system, consider the Lyapunov function

V1(δi)=12∑i=1n(δi−δ0)2.

It is easy to check that V1 is differentiable and positive definite. By taking the derivative of V1 along the trajectories of the system, we obtain

V˙1(δi)=∑i=1n (δi−δ0)(δ˙i−δ˙0),(15)

by using Young’s inequality, for each i=1,…,n and ξ1,ξ2,ξ3,μ1,μ2,μ3,μ4>0, we have

V˙1(δi)=∑i=1n (δiδ˙i−δiδ˙0−δ0δ˙i+δ0δ˙0)

≤∑i=1n ((δi22ξ1+δ˙i22μ1)−(δi22ξ1+δ˙022μ2)−(δ022ξ3+δ˙i22μ3)+(δ022ξ3+δ˙022μ4)),

We take

d=δ˙i22μ1−δ˙022μ2−δ˙i22μ3+δ˙022μ4

Thus, for ξ2≃ξ3, we have V˙1≤d, which implies that V˙1 is a negative definite. Consequently, for every i=1,…,n, δi is asymptotically stable. Further, the system can achieve both formation stabilization with collision avoidance and consensus.

For every i=1,…,n, we define the error ei=(δi−δ0δ˙i−δ˙0). We discuss two cases.

Case 1: when e1=e2=…=ei,… We consider the following Lyapunov function candidate

V2(δ)=12e2,

Differentiating V2 yields

V˙2(δ)=ee˙.

Case 2: when e1≠e2≠…≠ei…, we define the error sets as e={ei, i=1,…,n}. We choose a Lyapunov function as follows

V3(δi)=12∑i=1n⁡ ei2,

Taking the derivative of V3 yields

V˙3(e)=∑i=1n eie˙i

=ei(Aei+Bx)

=ei(Aei+B(ℒijpij+kℒijvij+k0bi0+ℒi0vi0+𝒞ij02))

=eiAei+eiBℒijpij+eiBkℒijvij+eiBk0bi0ℒi0vi0+eiB𝒞ij02⏟d

by using Young’s inequality, we have

V˙3(e)≤ei22ξ1+(Aei)22μ1+ei22ξ2+(Bℒijpij)22μ2+ei22ξ3+(Bℒijvij)22μ3+ei22ξ4+(Bk0bi0ℒi0vi0)22μ4+ei22ξ5+d22μ5,

for ξ1,ξ2,ξ3,ξ4,ξ5,μ1,μ2,μ3,μ4,μ5>0. If ξ1=−ξ2 , ξ3=−ξ4 and ξ5<<<<<; we have

V˙3(ei)≤(Aei)22μ1+(Bℒijpij)22μ2+(Bℒijvij)22μ3+(Bk0bi0ℒi0vi0)22μ4+d22μ5=d¯^≈h˙.

We conclude that the system is stable, and the error will converge to zero. We write the system Eq. (1) in generalized form as

{e˙i=Aei+Buiyi=Cei,(16)

where ei∈Rn, ui∈Rm, and yi∈Rq are the state, control input, and output of agent i, respectively. A,B, and C are constant matrices with appropriate dimensions given as follows

A=[∂δ0∂θ0∂δ0∂θi∂δi∂θ0∂δi∂θi]=[r0(−sin(θ0)+jcos(θ0))00−si(−sin(θi)+jcos(θi))],B=[0010],C=[10]

The feedback control gain k is given by k=μBBTP, such that P is the positive definite solution of the following algebraic Riccati inequality (ARI)

ATP+PA−12BBTP+2I2≤0. (17)

Since, A−Bk is Hurwitz the pair (A, B) is controllable.

Lemma 7. Lyapunov candidate (potential function) is the error in the dynamical system Eq. (14) given as

V=eiTPei,∀i=1,…,n, where ei=(δi−δ0δ˙i−δ˙0).

Proof.

We have e˙i=(δ˙i−δ˙0δ¨i−δ¨0). The derivative of V along the trajectories leads to

V˙=2eiTPe˙i

=2eiTe˙i(k11k)e˙i

=2(k(δi−δ0)(δ˙i−δ˙0)+(δ˙i−δ˙0)2+(δi−δ0)(δ¨i−δ¨0)+k(δ˙i−δ˙0)(δ¨i−δ¨0)).

Applying Young’s inequality, we obtain

V˙≤2((δ˙i−δ˙0)22ξ1+k2(δi−δ0)22μ1+(δ˙i−δ˙0)22ξ2+k2(δi−δ0)22μ2+(δ¨i−δ¨0)22ξ3+(δi−δ0)22μ3+(δ¨i−δ¨0)22ξ4+k2(δ˙i−δ˙0)22μ4).

If ξ1=−ξ2 and ξ3=−ξ4, we have

V˙≤2(k2(δi−δ0)22μ1+k2(δi−δ0)22μ2+(δi−δ0)22μ3+k2(δ˙i−δ˙0)22μ4)≤d~.