Motion Coordination Problems with Collision Avoidance for Multi-Agent Systems

2.1. Differential-drive mobile robots

Let N={R1,…,Rn}be a set of differential-drive mobile robots moving on the plane with positions ξi=[xi,yi]T,i=1,…,n. The kinematic model for each robot according to Figure 1 , is given by

where v _i is the longitudinal velocity of the middle point of wheels axis of the ith robot, w _i its angular velocity and θ _i the orientation with respect to the X axis. It is known that systems like Eq. (1) cannot be stabilised by any continuous and time-invariant control law [18]. Moreover, if the position ξ _i is taken as output of the system Eq. (1), the so-called decoupling matrix becomes singular. For this reason, to avoid singularities in the control law, it is common to study the kinematics of a point α _i off the wheels axis. The coordinates of point α _i are given by

The kinematics of point α _i is given by

where A _i (θ _i ) is the decoupling matrix for each robot R _i . The decoupling matrix is non-singular since det(Ai(θi))=ℓ≠0.

2.2. Algebraic graph theory

Definition 1. (Formation Graph). Let N={R1,…,Rn}be a set of mobile agents and N _i be the subset of agents which have a flow of information towards the ith agent. A formation graph G = {V, E, C} consists of

• A set of vertices V={R1,…,Rn}corresponding to the n agents of the system.

• A set of edges E={(Rj,Ri)∈V×V|j∈Ni}where each edge represents a flow of information that goes from agent R _j towards agent R _i .

• A set of labels C={cji = Ri − Rj}with (R _j R _i ) ∈ E, cji∈R2, with c _ji being a vector specifying a desired relative position between the agents R _j and R _i .

Definition 2. (Laplacian). Let us have a formation graph G, the Laplacian associated with G is given by

With ∆ the degree matrix defined by

where g i = card { N i } , i = 1 , … , n and A d is the adjacency matrix of G defined by

Given a formation graph G, there exist a path in this graph if between the vertices R _i and R _j, there is a sequence of edges (Ri,Rm1),(Rm1,Rm2),…,(Rmr,Rj)with i ≠ j. We call cycle to a path that begins and ends at the same vertex.

For further details about formation graphs, Laplacian and its properties and algebraic graph theory, the reader is referred to Refs. [19–21].

2.3. Mathematical miscellaneous

Definition 3. [22, 23] Let A=(aij)∈Rn×nthat satisfies aij≤0whenever i ≠ j and a _ii > 0 for each i. The matrix A is called an M-matrix if it satisfies any one of the following equivalent conditions

• A=ηI−Mfor some non-negative matrix M and some η>ρ(M), where ρ(M) is the spectral radius of M.

• The real part of each eigenvalue of A is positive.

• All principal minors of A are positive.

• A ⁻¹ exists and the elements of A ⁻¹ are non-negative.

Definition 4. [24] The convex hull of a set of vectors Z={z1,…,zp}⊂Rn, denoted by co(Z), is defined by

Definition 5. Given a point zq=[x,y]Tand a set Z={z1,…,zp}, the distance between z _q and co(Z) is defined by dist(zq,co(Z))=inf(dist(zq,z)), z ∈ Z.

Definition 6. Given a vector z=[z1,…,zp]T, we define

Definition 7. Given a matrix A∈Cn×nwith eigenvalues λ1,…,λn, then its spectral radius ρ(X) is defined as ρ(X)=max{∣λ1∣,…,∣λn∣}.

Definition 8. Let H∈Rn×nbe a block triangular matrix

With A∈Rk×kand C∈R(n−k)×(n−k). Then, the eigenvalues of the matrix H are the eigenvalues of the submatrices A and C.

Definition 9. [17] Consider the dynamical system x˙=Axwith x=[x1,…,xn]Tand A∈Rn×nHurwitz. Then, the normalised system x˙=AD(x)xwith D(x)=diag{1/∥x1∥,…,1/∥xn∥}is stable with finite time convergence.

2.4. Repulsive vector fields

Let N={R1,…,Rn}be a set of first order agents moving on the plane. The distance between two agents is given by ∥ξi−ξj∥,∀i,j∈N, i ≠ j. Then, the agents R _j that are in risk of collision with agent R _i belong to the set

where d is the minimum allowed distance between the agents. To avoid collisions between agents, we propose repulsive vector fields given by

where ϵ > 0 and the parameter δ _ij is given as follows

The repulsive vector fields are proposed in such a way that there is an unstable focus that rotates anticlockwise as shown in Figure 2 , centred on the position of the other agents that are in risk of collision.

For the control strategies designed in this chapter, we will take into account the following assumptions:

Assumption 1. The initial conditions of all agents satisfy ∥αi(0)−αj(0)∥≥d,∀i,j∈N, with i ≠ j. That is, there is no risk of collision between any agents at t = 0.

Assumption 2. The ith agent, besides knowing the position of the agents of the set N _i , it can detect the presence of any other agent that is within the circle of radius d.

Also, consider the following:

Remark 1. It should be clear that the minimum allowed distance between agents d must be less than the minimum distance between agents within a desired formation, i.e. d<min{|cij|}.

2.5. Case of study: Formation with collision avoidance

The desired relative position of the ith agent in a desired formation is given by

where c _ki is the position vector between agents R _i and R _k . The goal is to design a decentralised control law [vi,wi]T=fi(αi,Ni),i = 1,…,n such that

• The agents achieve a desired formation, i.e.

  limt→∞(αi(t)−αi*(t))=0E14

A control law to achieve a desired formation is given by

where ei=αi−αi*is the position error and k > 0 the control gain. For differential-drive mobile robots, we have

where Ai−1(θi)is the inverse of the decoupling matrix. We consider a normalised version of Eq. (10) to deal with a system where all agents move at the same velocity, given by

where μ is the constant velocity of all agents.

Proposition 1. Consider the system Eq. (3) and the control law Eq. (17) with γ _i given by (18) and a connected formation graph composed entirety by the superposition of different cycles. Then, in the closed-loop system Eqs. (3)–(17), we have finite time convergence of the agents to the desired formation.

Proof. The proof of this Proposition is detailed in [17].▪

To achieve formation with collision avoidance between agents, we propose a control law given by

With γ _i given by Eq. (18) and β _i the repulsive vector field given by Eq. (11).

Proposition 2. Consider the system Eq. (3) and the control law Eq. (19) with Eqs. (18) and (11). Also consider a connected formation graph composed entirety by the superposition of different cycles. Suppose that there exist risk of collision between n agents at time instant t and ϵ>6(μ/d). Then, in the closed-loop system Eqs. (3)–(19), the agents reach their desired position in finite time and remain at a distance greater than or equal to a predefined minimum distance d between them for all t ≥ 0.

Proof. For the proof of this Proposition, mathematical induction is performed, first showing the cases of risk of collision between two agents and between three agents, applying induction to arrive at the general solution of n agents. This proof is detailed in Ref. [17]. It is worth mentioning that, geometrically, the worst case occurs when an agent is surrounded by other six agents. Also, the value of ϵ>6(μ/d)is very conservative, so it is possible that with a lower ϵ, collision avoidance is achieved.▪

The results obtained from a numerical simulation using the control strategy given by Eq. (19) are shown below. For the simulation, three differential-drive mobile robots are considered, where the point α _i to be controlled is located at 0.045 m in front of the mid-point of wheels axis. The formation graph using in the simulation is shown in Figure 3 .

The parameters used in the simulation are d=0.2,μ=0.1,ϵ=2(μ/d). The position vectors are given by c32=[−0.3,0]T,c21=[0.3cos(π/3),0.3sin(π/3)]Tand c13=[0.3sin(π/6),−0.3cos(π/6)]T. The desired formation is an equilateral triangle of 0.3 m. The agents were placed in initial positions in such a way that in the trajectories towards their desired positions risk of collision between them exits.

Figure 4 shows the motion of the agents in the plane. It is observed how the agents achieve the desired formation avoiding collisions. The effect of the repulsive vector fields can be seen when modified the trajectories of the agents to avoid collisions. In Figure 5 , the distances between agents are shown, we can see that the minimum distance between agents is always greater than or equal to the predefined distance d = 0.2. Figure 6 shows the position errors of the agents. Such errors converge to zero.

3.1. Time-varying position vector

In order to maintain a formation oriented to the direction of a leader agent R _n and resize the formation, we use a time-varying position vector given by

where c _ji is a position vector corresponding to the static desired formation, R(θ _n ) is a rotation matrix given by

and δ(t) is a scaling factor. The time derivative of Eq. (14) is given by

where

3.2. Time-varying formation tracking with collision avoidance

In the time-varying formation tracking problem presented in this subsection, the agent R _n is the leader, responsible for tracking a desired trajectory. The n–1 remaining agents are follower, responsible for performing a time-varying formation with respect to the leader. The leader agent does not know the position and velocities of the followers agents but only knows the desired trajectory and velocity. The followers do not know the desired trajectory and velocity but only knows the positions and velocities of others agents in the system.

We make the following standing assumption

Assumption 3. For each follower agent, there is a path to the leader agent, i.e., for all R i , i = 1 , … , n − 1 , there are edges ( R n , R m 1 ) , ( R m 1 , R m 2 ) , … , ( R m r , R i ) ∈ E .

Let m(t)=[mp(t),mq(t)]Tbe a continuously differentiable pre-established navigation trajectory, where ∥m˙(t)∥≤ηm,∀t≥0.

The desired relative position of the ith follower within the desired time-varying formation is given by

where C _ji (t) is a time-varying position vector between the agents R _i and R _j . The time derivative of C _ji (t) satisfies ∥C˙ji(t)∥≤ηc,∀t≥0.

The goal is to design a decentralised control law [vi,wi]T=fi(αi,Ni),i=1,…,nthat achieves

• Asymptotic tracking of a prescribed trajectory by the leader agent, i.e.

  limt→∞(αn(t)−m(t))=0.E25

To achieve time-varying formation tracking, we propose a control law defined by

where Ai−1(θi)is the inverse of the decoupling matrix, m(t) is the desired trajectory, m˙(t)is the navigation velocity, k _m and k _f are the control gains.

The first main result of this subsection is the following:

Proposition 3. Consider the system Eq. (3) and the control law Eq. (28). Suppose that k m , k f > 0 . Then, in the closed-loop system defined by Eqs. (3)–(28), it follows that the leader agent R _n converge to the desired trajectory, i.e. lim t → ∞ ( α n ( t ) − m ( t ) ) = 0 , whereas the follower agents converge to the desired formation, i.e. lim t → ∞ ( α i ( t ) − α i * ( t ) ) = 0 , for i = 1 , … , n − 1 .

Proof. The closed-loop system Eqs. (3)–(28) is given by

where α=[α1,…,αn]T,K=diag{kf,…,kf,km}, ⊗ denote the Kronecker product, I ₂ is the 2 × 2 identity matrix,

A=ΛL(G)+Γ, where L(G)is the Laplacian of the formation graph G,Λ=diag{1/g1,…,1/gn−1,0}and

At this point, we have to show that (A⊗I2)is invertible. From the properties of the Kronecker product, we have (A⊗I2)−1=A−1⊗I2−1. Since I ₂ is the identity matrix, then I2−1exits and we address in the matrix A=ΛL(G)+Γ. From the properties of the Laplacian, we know that the matrix ΛL(G)is positive semidefinite and singular, that is, it has no inverse. This since the vector of ones X=[1,…,1]Tis solution of the system ΛL(G)X=0. When matrix Γ is added to ΛL(G), the resulting matrix A is no singular and positive definite, since taking into consideration the Assumption 3, the system ΛL(G)X=0has the unique solution X=[0,…,0]T.

Now define the errors of the system as

The system errors in matrix form are given by

where e=[e1,…,en]T. The dynamics of the error coordinates are given by

We propose a Lyapunov function candidate given by

and evaluating its time derivative along the trajectories of the system, we have

then the errors converge asymptotically to zero.▪

Modifying the previous control law Eq. (28) by adding the repulsive vector field Eq. (11), finally, we have the strategy to achieve time-varying formation tracking with collision avoidance given by

To analyse the relative distance among the jth and ith agents, we define the variables pji=αxi−αxjand qji=αyi−αyj,j,i=1,…,n, j ≠ i which correspond to the horizontal and vertical distances between agents. In the plane p _ji – q _ji , we identify the origin as the point where collision between the jth and ith agents occurs and a circle of radius d, centred at the origin, as the influence region between the two agents. Outside the circle, only the time-varying formation tracking control law acts, while inside the circle, the repulsive vector fields appear.

In order to present our second main result, we need to establish the following Technical Lemma.

Lemma 1. Consider the system Eq. (3) and the control law Eq. (28) along with definitions k*=max(kf,km)and η*=max(ηm,ηc). Then in the closed-loop system Eqs. (3)–(28), the velocities of the agents are bounded by η^=ρ(A−1)(k*2n+η*n).

Proof. Taking the norm of the system Eq. (29), we get

where ∥tanh((A⊗I2)α−C)∥≤2n,∥M∥≤η*n, with ∥−(K⊗I2)∥=ρ(K⊗I2)and ∥(A⊗I2)−1∥=ρ([(A⊗I2)−1]), but since I ₂ is the identity matrix with two eigenvalues 1 and from the spectrum properties of the Kronecker product, we have ∥−(K⊗I2)∥=ρ(K)=max(kf,km)=k*and ∥(A⊗I2)−1∥=ρ([(A)−1]). Finally, we have

This concludes the proof.▪

Now, we can state our second main result. First, we consider the case when only two agents are in risk of collision. From this simplest case, we state a series of theorems leading to the general case.

Proposition 4. Consider the system Eq. (3) and the control law Eq. (37). Suppose that there exists risk of collision between only two agents at time instant t and the parameter ϵ satisfies ϵ > η ^ / d . Then, in the closed-loop system Eqs. (3)–(37), the agents tend asymptotically to their desired positions, and they stay at a distance greater than or equal to d, ∀t≥0.

Proof. We show that the rth and sth agents will avoid collision between them, and they stay at some minimum distance from each other. Define a surface given by

To determine the behaviour under the action of the repulsive vector fields, we use the positive definite function V=12σrs2which time derivative is given by V˙=σrsσ˙rs. The time derivative of Eq. (40) along the trajectories of the closed-loop system is given by

Therefore, V˙≤0is achieved if σrsσ˙rs≤0. When there exists risk of collision, (prs,qrs)lies in the inner region of σrs=0, that is σrs≤0, then the analysis reduces to show that σ˙rs≥0. That means the resulting vector fields inside the circle point outwards, that is, to the region free of collision. Using the definition of the cross product, we have

Solving for ϵ, we have that, if ϵ>η^/d, then σ˙rs>0. This implies that the rth and sth agents move away from each other until they reach a distance d. Since ∥αs(0)−αr(0)∥≥d, then the agents not only avoid collision but also satisfy ∥αs(t)−αr(t)∥≥dfor all time.

Now, we consider the case when three agents are in risk of collision, that is, agent R _r is in risk of collision against agents R _s1 and R _s2.▪

Proposition 5. Consider the system Eq. (3) and the control law Eq. (37). Suppose that there exists risk of collision between three agents and the parameter ϵ satisfies ϵ > 2 ( η ^ / d ) . Then, in the closed-loop system, Eqs. (3)–(37), the agents converge asymptotically to their desired positions, and they stay at a distance greater than or equal to d, ∀t≥0.

Proof. We define a surface composed of two components given by

We use the positive definite function V=12σTσwhich time derivative is given by V˙=σTσ˙=σrs1σ˙rs1+σrs2σ˙rs2≤σ*(σ˙rs1+σ˙rs2)where σ*=max{σrs1,σrs2}. Evaluating V˙and considering that the trajectories lie in the inner region of σ = 0, that is, σrs1,σrs2<0then the analysis reduces to show that σ˙rs1+σ˙rs2>0. Hence,

In this scenario, agents R _s1 and R _s2 can be positioned at any point of the circumference of radius d around the agent R _r , considering that, from Proposition 4, they must remain at a distance greater than or equal to d between them. The worst case occurs when the agents R _s1 and R _s2 are uniformly distributed over the circumference of radius d. Thus, cosθrs1,rs2=−1and solving for ϵ, we have that, if ϵ>2(η^/d), then σ˙rs1+σ˙rs2>0. This implies that agents R _s1, R _s2 and R _r avoid collision between them.

Geometrically, the most general case occurs when the rth agent is surrounded by six agents, i.e. seven agents are in danger of collision.

Proposition 6. Consider the system Eq. (3) and the control law Eq. (37). Suppose that there exists risk of collision between n ≥ 3 agents and the parameter ϵ satisfies ϵ>2(η^/d). Then, in the closed-loop system Eqs. (3)–(37), the agents converge asymptotically to their desired positions, and they stay at a distance greater than or equal to d, ∀t≥0.

Proof. We follow a similar procedure to that presented in the proof of Proposition 5, considering a surface with n – 1 components and showing that, if σrs1+…+σ˙r(n−1)>0, then V˙<0, taking into account that the worst case is presented when the n – 1 agents are uniformly distributed over the circumference of radio d around the agent R _r , so the agents avoid collision between them.▪

The results of a numerical simulation using the control strategy given by Eq. (37) are shown below. For the simulation, we considered five differential-drive mobile robots, where the point α _i to control is located 0.15 m ahead the mid-point of the wheel axis. The formation graph employed in the simulation is shown in Figure 7 .

The control gains used in the simulation are k _m = 2 and k _f = 3. The desired marching trajectory is a quadrifolium curve given by m(t)=[4sin(2ωt)cos(ωt),4sin(2ωt)sin(ωt)]Twhere ω=2π/Twith a period of T = 80s. The static position vectors are given by c12=[0,0.6]T,c21=[0,−0.6]T,c32=[−0.6cos(π/10),−0.6sin(π/10)]T,c34=[0,−0.97]T,c43=[0,0.97]T, and c54=[−0.6cos(3π/10),−0.6sin(3π/10)]T. The scaling factor is given by δ(t)=1+0.2sin(ωt).

The minimum allowed distance between agents is d = 0.3 m and the parameter ϵ was set to ϵ=1.5(2(η^/d))to ensure the minimum distance condition will not be violated.

Figure 8 shows the motion of the agents in the plane. The initial position of the agents is indicated with an ‘x’ and positions in different time instants are represented with a circle ‘o’. Is observed how the leader follows the desired trajectory while the followers achieve a time-varying formation. Furthermore, the minimum distance requirement is satisfied as shown in Figure 9 , which depicts all the possible distances between agents. The distances between any pair of agents are always greater than or equal to the predefined distance d = 0.3. Figure 10 shows the position errors of the agents. Such errors converge to zero.

3.3. Time-varying containment problem with collision avoidance

Let N={R1,…,Rn}be a set of mobile robots. The set N is composed of two disjoint subsets, so that N=NF∪NL, where NF={R1,…,RnF}, with n _F agents, is the subset of followers, and NL={RnF+1,…,Rn}, with n _L agents, is the subset of leaders. The agent R _n is the main leader, responsible for tracking a desired trajectory. The n _L −1 remaining agents are secondary leaders, responsible for performing a time-varying formation with respect to the main leader.

In this subsection, we make the following standings assumptions

Assumption 4. For each follower, there is a path to at least one leader agent, i.e. for all Rj∈NF, there are edges (Ri,Rm1),(Rm1,Rm2),…,(Rmr,Rj)∈Ewith Ri∈NL.

Assumption 5. For each secondary leader, there is a path to the main leader, i.e. for all Ri∈NL,i=nF+1,…,n−1, there are edges (Rn,Rm1),(Rm1,Rm2),…,(Rmr,Ri)∈E.

In order to define the problem statement, let us introduce some notation. Let m(t)=[mp(t),mq(t)]Tbe a continuously differentiable pre-established trajectory, where ∥m˙(t)∥≤ηm,∀t≥0. The desired relative position of the ith secondary leader within the desired time-varying formation is given by

where Cji(t)is a time-varying position vector between the agents R _i and R _j where ∥C˙ji(t)∥≤ηc,∀t≥0. The desired relative position of the jth follower is given by

The goal of this work is to design a decentralised control law [vi,wi]T=(αi,Ni),i=1,…,nthat ensures

• Asymptotic tracking of a prescribed trajectory by the main leader agent, i.e.

  limt→∞(αn(t)−m(t))=0.E47

To achieve time-varying containment, we propose a bounded control law given by

where k _m , k _f and k _c are control gains. Note that for each secondary leader and each follower, the control input depends on the position and velocity of the agents with which has a communication. In practical implementations, these velocities can be calculated by numerical differentiation.

The first main result of this subsection is the following.

Proposition 7. Consider the system Eq. (3) and the control law Eq. (51). Suppose that km,kf,kc>0. Then, in the closed-loop system defined by Eqs. (3)–(51), it follows that:

1. The main leader R _n converges to the desired marching trajectory, i.e. limt→∞(αn(t)−m(t))=0, whereas the secondary leaders converge to the desired formation, i.e. limt→∞(αi(t)−αi*(t))=0, for i=nF+1,…,n−1.

2. The followers converge to the convex hull formed by the leaders, i.e. limt→∞dist(αj(t),co(αL(t)))=0, for j=n1,…,nF.

Proof. For part 1, the proof has a procedure similar to that performed in the Proposition 3.

For part 2, the system errors are given by

where eF=[e1T,…,enFT]T,eL=[enF+1T,…,enT]T,αF=[α1T,…,αnFT]T,αL=[αnF+1T,…,αnT]T,

where LFFi,LFLi, and LLLiare the ith row of the submatrices LFF,LFL, and LLL, respectively.

Solving for the position of follower agents α _F (t) of Eq. (52), we have

Since eF(t)→0as t → ∞, then αF(t)→−PFF−1PFLαL(t). To verify that PFF−1exist, we have to analyse the submatrix P _FF . Making a similar analysis to [25], we can rewrite P _FF as

where η = 1, MFFnF×nFis a non-negative matrix and according to Assumption 4, it holds that ρ(MFFnF×nF)<η. Therefore, P _FF is an M-matrix, which is non-singular, thus PFF−1exists, and the elements of PFF−1are non-negative. Since the elements of P _FL are negative or zero, then the elements of −PFF−1PFLare non-negative. Since the sum of the elements of each row of [PFF PFL]is 0, we have that the sum of the elements of each row of −PFF−1PFLis 1 and according to Definition 4, when t → ∞, the follower positions are within the convex hull formed by the leaders.

Modifying the previous control law Eq. (51) by adding the repulsive vector field Eq. (11), finally, we have the strategy to achieve time-varying containment with collision avoidance given by

The second main result in this subsection is very similar to the second presented in the previous subsection, which consists of a series of three propositions, considering the simplest case, when there is risk of collision between two agents, then the case when there is risk of collision between three agents and, finally, the general case.

The results of a numerical simulation using the control strategy given by (56) are shown below. For the simulation, we considered eight differential-drive mobile robots, where the point α _i to control is located 0.15 m ahead the mid-point of the wheels axis. The formation graph employed in the simulation is shown in Figure 11 .

The parameters used in the simulation are km=1, kf=kc=2. The desired marching trajectory is a Lissajous curve given bym(t)=[4.5sin(ωxt+(π/2)),1.5sin(ωyt)]Twhere ωx=2π/Tand ωy=6π/Twith a period of T = 80s. The static position vectors are c87=[−1.2,−0.6]T, c76=[0,1.2]T,c67=[0,−1.2]Tand c65=[−0.6,−0.6]T. The scaling factor is given by δ(t)=1+0.2sin(ωxt).