Open access peer-reviewed chapter

Motion Coordination Problems with Collision Avoidance for Multi-Agent Systems

By Jesús Santiaguillo-Salinas and Eduardo Aranda-Bricaire

Submitted: December 17th 2016Reviewed: May 19th 2017Published: September 13th 2017

DOI: 10.5772/intechopen.69845

Downloaded: 636

Abstract

This chapter studies the collision avoidance problem in the motion coordination control strategies for multi-agent systems. The proposed control strategies are decentralised, since agents have no global knowledge of the goal to achieve, knowing only the position and velocity of some agents. These control strategies allow a set of mobile agents achieve formations, formation tracking and containment. For the collision avoidance, we add a repulsive vector field of the unstable focus type to the motion coordination control strategies. We use formation graphs to represent interactions between agents. The results are presented for the front points of differential-drive mobile robots. The theoretical results are verified by numerical simulation.

Keywords

  • motion coordination
  • formation control
  • formation tracking control
  • containment control
  • time-varying formations
  • collision avoidance
  • repulsive vector fields
  • multi-agent systems
  • differential-drive mobile robots

1. Introduction

Multi-agent systems are defined as bundles of multiple autonomous robots coordinated to accomplish cooperative tasks. In recent years, the study of multi-agent systems has gained special interest, because these systems can achieve tasks that would be hard or impossible to achieve by agents working individually. Multiple agents can solve tasks working cooperatively, making them more reliable, faster and cheaper than it is possible with a single agent [1].

The main applications of multi-agent systems include the transport and manipulation of objects, localization, exploration and motion coordination [1, 2]. The main idea of motion coordination is the strategic navigation of a group of agents. Some of the main areas of research in the motion coordination are the formation control, where the goal is to achieve a desired pattern defined by relative position vectors, the time-varying formation tracking control, where the goal is to track a pre-established trajectory while the agents maintain a time-varying desired formation and the time-varying containment control, which consists in a group of mobile agents (called leaders) that track a predetermined trajectory, while another group of agents (called followers) remain within the region determined by the leaders [3].

The time-varying formation problem has been scarcely studied and some examples can be found in [47]. The time-varying formation control can be applied as the solution to complex motion coordination problems. In our case, the time-varying formation allows trajectory tracking with formations oriented to the heading angle of a leader robot, as well as changes in the physical dimensions of the formations. More specifically, the time-varying formation is composed of a predefined static formation which is transformed by a rotation matrix, which depends on the orientation of a specific leader robot and a scaling matrix, which depends on a factor that varies with respect to time. This time-varying formation allows the group of agents to behave as a rigid body which can be translated, rotated and scaled in the plane.

Another ubiquitous problem in all areas of motion coordination is the possible collision between agents when they try to achieve a desired position into a formation or during the trajectory tracking. In the literature, we can find different methods to predict/avoid collisions. In Ref. [8], a mechanism for collision avoidance under central control mode (traffic control type) is presented. In Refs. [911], navigation functions and artificial potential functions are used to avoid collisions between agents. These non-collision strategies are developed based on a combination of attractive potential functions (APFs) and repulsive potential functions (RPFs). Works [1215] address the formation control problem without collisions using discontinuous vector fields.

The interaction topology between agents is modelled by formation graphs, where each agent is represented by a vertex, and the sharing of information between agents is represented by an edge. The control strategies designed in this work are presented for differential-drive mobile robots. This kind of mobile robots is commonly chosen as test bed because of simplicity and commercial availability. Differential-drive mobile robots present interesting challenges because they possess non-holonomic restrictions and even though have a simple kinematic model, it presents singularities. For this reason, the stabilization of such kind of mobile robots has been studied for several years by researches from diverse viewpoints.

The goal of this chapter is to design decentralised control strategies that allow motion coordination for multi-agent systems avoiding collisions between agents. The non-collision strategy is based on previous works [16, 17]. We use bounded control strategies based on sigmoid functions adding a repulsive vector field.

2. Preliminaries

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

Figure 1.

Kinematic model of the differential-drive mobile robot.

[x˙iy˙iθ˙i]=[cosθi0sinθi001][viwi],i=1,,nE1

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

αi=[αxiαyi]=[xi+cosθiyi+sinθi]E2

The kinematics of point α i is given by

[α˙xiα˙yi]=[cosθisinθisinθicosθi][viwi]=Ai(θi)[viwi]E3

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|jNi}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, cjiR2, 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

L(G)=ΔAdE4

Withthe degree matrix defined by

Δ=diag{g1,,gn}E5

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

aij={1, if (Rj,Ri)E0, otherwise.E6

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 ij. 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. [1921].

2.3. Mathematical miscellaneous

Definition 3. [22, 23] Let A=(aij)Rn×nthat satisfies aij0whenever ij 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=ηIMfor 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 −1 exists and the elements of A −1 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

co(Z)={j=1pμjzj | μjR,μj0,j=ipμj=1}.E7

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)), zZ.

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

tanh(z)=[tanh(z1),,tanh(zp)]T.E8

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

Definition 8. Let HRn×nbe a block triangular matrix

H=[AB0C]E9

With ARk×kand CR(nk)×(nk). 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 ARn×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,jN, ij. Then, the agents R j that are in risk of collision with agent R i belong to the set

Mi={RjN|ξiξjd},i=1,2,,nE10

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

βi=ϵjMiδij[(xixj)(yiyj)(xixj)+(yiyj)]E11

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

δij={1,if ξiξjd0,if ξiξj>dE12

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.

Figure 2.

Phase plane of the repulsive vector field β ij .

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,jN, 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

αi*=1gikNi(αk+cki)E13

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

  • Collision avoidance among agents is achieved. In addition, for all time t, the agents remain at a distance greater than or equal to a predefined minimum distance d between them, i.e.

    αi(t)αj(t)d,t0,ijE15

  • A control law to achieve a desired formation is given by

    γi=kei,i=1,,nE16

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

    [viwi]=Ai1(θi)γi,i=1,,nE17

    where Ai1(θ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

    γi={μeiei,ei00,ei=0i=1,,nE18

    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

    [viwi]=Ai1(θi)(γi+βi),i=1,,nE19

    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 .

    Figure 3.

    Formation graph for the simulation (formation with collision avoidance problem).

    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.

    Figure 4.

    Trajectories of the agents in the plane (formation with collision avoidance problem).

    Figure 5.

    Distances between agents (formation with collision avoidance problem).

    Figure 6.

    Position errors of the agents (formation with collision avoidance problem).

    3. Motion coordination control strategies

    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

    Cji(t)=δ(t)R(θn)cjiE20

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

    R(θn)=[cosθnsinθnsinθncosθn]E21

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

    C˙ji(t)=δ˙(t)R(θn)cji+δ(t)R˙(θn)cjiE22

    where

    R˙(θn)=[sinθncosθncosθnsinθn]wnE23

    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,t0.

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

    αi*(t)=1gijNi(αj(t)+Cji(t)),i=1,,n1,E24

    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,t0.

    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

  • Asymptotic time-varying formation by the follower agents, i.e. for  i=1,,n1

    limt(αi(t)αi*(t))=0.E26

  • Collision avoidance between agents, that is, all agents in the system remain at some distance greater than or equal to a predefined minimum distance d from each other, i.e.

    αi(t)αj(t)d,i,j=1,,n,ij,t0.E27

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

    [vnwn]=An1(θn)(kmtanh(αnm(t))+m˙(t))[viwi]=Ai1(θi)(kftanh(αiαi*)+α˙i*),i=1,,n1E28

    where Ai1(θ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

    α˙=(AI2)1[(KI2)tanh((AI2)αC)+M]E29

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

    C=[1g1jN1Cji(t),,1gn1jNn1Cji(t),m(t)]TE30
    M=[1g1jN1C˙ji(t),,1gn1jNn1C˙ji(t),m˙(t)]T

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

    Γ=[0001].E31

    At this point, we have to show that (AI2)is invertible. From the properties of the Kronecker product, we have (AI2)1=A1I21. Since I 2 is the identity matrix, then I21exits 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

    en=αnm(t)ei=αiαi*,i=1,,n1E32

    The system errors in matrix form are given by

    e=(AI2)αCE33

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

    e˙=(KI2)tanh(e)E34

    We propose a Lyapunov function candidate given by

    V=12eT(KI2)1eE35

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

    V˙=eT(KI2)1(KI2)tanh(e)=eTtanh(e)<0,e with e0E36

    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

    [vnwn]=An1(θn)(kmtanh(αnm(t))+m˙(t)+βn)[viwi]=Ai1(θi)(kftanh(αiαi*)+α˙i*+βi),i=1,,n1E37

    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, ji 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 η^=ρ(A1)(k*2n+η*n).

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

    α˙(AI2)1[(KI2)tanh((AI2)αC)+M]α˙(AI2)1(KI2)tanh((AI2)αC)+ME38

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

    α˙ρ(A1)(k*2n+η*n)=η^.E39

    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, t0.

    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

    σrs=prs2+qrs2d2=0E40

    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

    σ˙rs=2[prsqrs][p˙rsq˙rs]=4ϵ(prs2+qrs2)2[prsqrs]((α˙s*kstanh(αsαs*))(α˙r*krtanh(αrαr*)))E41

    Therefore, V˙0is achieved if σrsσ˙rs0. When there exists risk of collision, (prs,qrs)lies in the inner region of σrs=0, that is σrs0, then the analysis reduces to show that σ˙rs0. 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

    σ˙rs=4ϵ(prs2+qrs2)+4prs2+qrs2η^cosθrs4ϵ(prs2+qrs2)4prs2+qrs2η^>0.E42

    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, t0.

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

    σ=[σrs1σrs2]=[prs12+qrs12d2prs22+qrs22d2]=0.E43

    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,

    σ˙rs1+σ˙rs2=4ϵ(prs12+qrs12)+2[prs1qrs1]((ks1tanh(αs1αs1*)+α˙s1*)(krtanh(αrαr*)+α˙r*))+4ϵ(prs22+qrs22)+2[prs2qrs2]((ks2tanh(αs2αs2*)+α˙s2*)(krtanh(αrαr*)+α˙r*))+4ϵ[prs1qrs1][prs2qrs2]4ϵ(prs12+qrs12)4prs12+qrs12η^+4ϵ(prs22+qrs22)4prs22+qrs22η^+4ϵprs12+qrs12prs22+qrs22cosθrs1,rs2>0.E44

    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, t0.

    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(n1)>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 .

    Figure 7.

    Formation graph for the simulation (formation tracking with collision avoidance problem).

    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.

    Figure 8.

    Trajectories of the agents in the plane (formation tracking with collision avoidance problem).

    Figure 9.

    Distances among agents (formation tracking with collision avoidance problem).

    Figure 10.

    Position Errors of the agents (formation tracking with collision avoidance problem).

    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=NFNL, 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 RjNF, there are edges (Ri,Rm1),(Rm1,Rm2),,(Rmr,Rj)Ewith RiNL.

    Assumption 5. For each secondary leader, there is a path to the main leader, i.e. for all RiNL,i=nF+1,,n1, 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,t0. The desired relative position of the ith secondary leader within the desired time-varying formation is given by

    αi*(t)=1gikNi(αk(t)+Cki(t)),i=nF+1,,n1,E45

    where Cji(t)is a time-varying position vector between the agents R i and R j where C˙ji(t)ηc,t0. The desired relative position of the jth follower is given by

    αj*=1gjkNjαk,j=1,,nF.E46

    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

  • Asymptotic time-varying formation by the secondary leader agents, i.e.

    limt(αi(t)αi*(t))=0,i=nF+1,,n1.E48

  • Convergence of the follower agents to the convex hull formed by the leaders, i.e.

    limtdist(αi(t),co(αL(t)))=0,i=1,,nF.E49

  • Collision avoidance among all agents, that is, all agents in the system remain at a distance greater than or equal to a predefined minimum distance d from each other, i.e.

    αr(t)αs(t)d,r,s=1,,n,rs,t0.E50

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

    [vnwn]=An1(θn)(kmtanh(αnm(t))+m˙(t))[viwi]=Ai1(θi)(kftanh(αiαi*)+α˙i*),i=nF+1,,n1[vjwj]=Aj1(θj)(kctanh(αjαj*)+α˙j*),j=1,,nFE51

    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,,n1.

    2. The followers converge to the convex hull formed by the leaders, i.e. limtdist(α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

    [eFeL]=([PFFPFL0PLL]I2)[αFαL][0C˜L]E52

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

    C˜L=[1gnF+1kNnF+1Ck(nF+1)T(t),,1gn1kNn1Ck(n1)T(t),mT(t)]T,E53
    PFF=[1g1LFF1T,,1gnFLFFnFT]T,PFL=[1g1LFL1T,,1gnFLFLnFT]T,
    PLL=[1gnF+1LLL1T,,1gn1LLLnL1T,([001]1×nL)T]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

    αF(t)=PFF1eF(t)PFF1PFLαL(t).E54

    Since eF(t)0as t → ∞, then αF(t)PFF1PFLαL(t). To verify that PFF1exist, we have to analyse the submatrix P FF . Making a similar analysis to [25], we can rewrite P FF as

    PFF=ηIFFnF×nFMFFnF×nF,E55

    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 PFF1exists, and the elements of PFF1are non-negative. Since the elements of P FL are negative or zero, then the elements of PFF1PFLare non-negative. Since the sum of the elements of each row of [PFFPFL]is 0, we have that the sum of the elements of each row of PFF1PFLis 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

    [vnwn]=An1(θn)(kmtanh(αnm(t))+m˙(t)+βn)[viwi]=Ai1(θi)(kftanh(αiαi*)+α˙i*+βi),i=nF+1,,n1[vjwj]=Aj1(θj)(kctanh(αjαj*)+α˙j*+βj),j=1,,nFE56

    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 .

    Figure 11.

    Formation graph (time-varying containment with collision avoidance problem).

    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).

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

    Figure 12 shows the motion of the agents in the plane. The initial positions of leader and follower agents are indicated with an ‘x’ ‘*’ and positions in times t=0.38,12,22,32,42,52,62and 72 s are represented with a circle ‘o’ □. It is observed how the main leader follows the desired trajectory while the secondary leaders achieve a time-varying formation and the followers converge to the convex hull formed by the leaders. Furthermore, there is no collision between agents as shown in Figure 13 , 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.2. Figure 14 shows the position errors of the follower and the leaders. Such errors converge to zero.

    Figure 12.

    Trajectories of the agents (time-varying containment with collision avoidance problem).

    Figure 13.

    Distances among agents (time-varying containment with collision avoidance problem).

    Figure 14.

    Position errors of the agents (time-varying containment with collision avoidance problem).

    4. Conclusions and outlooks

    This chapter presents motion coordination problems with collision avoidance for multi-agent systems, where the agents are differential-drive mobile robots. We propose decentralised control strategies which ensure formation, time-varying formation tracking and time-varying containment. Furthermore, collision avoidance between agents is achieved. We use formation graphs to represent interactions between agents. As shown in numerical simulations, the goals are achieved and system errors converge to zero.

    As future work, it is proposed to control the mid-point of wheel axis of the differential-drive mobile robots and include a strategy for obstacle avoidance. It is also intended to validate the theoretical results obtained through real-time experiments.

    How to cite and reference

    Link to this chapter Copy to clipboard

    Cite this chapter Copy to clipboard

    Jesús Santiaguillo-Salinas and Eduardo Aranda-Bricaire (September 13th 2017). Motion Coordination Problems with Collision Avoidance for Multi-Agent Systems, Multi-agent Systems, Jorge Rocha, IntechOpen, DOI: 10.5772/intechopen.69845. Available from:

    chapter statistics

    636total chapter downloads

    1Crossref citations

    More statistics for editors and authors

    Login to your personal dashboard for more detailed statistics on your publications.

    Access personal reporting

    Related Content

    This Book

    Next chapter

    Multiagent Systems in Automotive Applications

    By Raul Campos‐Rodriguez, Luis Gonzalez‐Jimenez, Francisco Cervantes‐Alvarez, Francisco Amezcua‐Garcia and Miguel Fernandez‐Garcia

    Related Book

    First chapter

    Introductory Chapter: Geographic Information Systems and Science

    By Cláudia M. Viana, Patrícia Abrantes and Jorge Rocha

    We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

    More About Us