Open access peer-reviewed chapter

Motion Coordination Problems with Collision Avoidance for Multi-Agent Systems

Written By

Jesús Santiaguillo-Salinas and Eduardo Aranda-Bricaire

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

DOI: 10.5772/intechopen.69845

Chapter metrics overview

1,423 Chapter Downloads

View Full Metrics

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.

Advertisement

2. Preliminaries

2.1. Differential-drive mobile robots

Let N = { R 1 , , R n } be a set of differential-drive mobile robots moving on the plane with positions ξ i = [ x i , y i ] 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 ˙ i y ˙ i θ ˙ i ] = [ cos θ i 0 sin θ i 0 0 1 ] [ v i w i ] , i = 1 , , n E1

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 = [ α x i α y i ] = [ x i + cos θ i y i + sin θ i ] E2

The kinematics of point α i is given by

[ α ˙ x i α ˙ y i ] = [ cos θ i sin θ i sin θ i cos θ i ] [ v i w i ] = A i ( θ i ) [ v i w i ] E3

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

2.2. Algebraic graph theory

Definition 1. (Formation Graph). Let N = { R 1 , , R n } 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 = { R 1 , , R n } corresponding to the n agents of the system.

  • A set of edges E = { ( R j , R i ) V × V | j N i } where each edge represents a flow of information that goes from agent R j towards agent R i .

  • A set of labels C = { c j i   =   R i     R j } with (R j R i ) ∈ E, c j i R 2 , 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 ) = Δ A d E4

Withthe degree matrix defined by

Δ = diag { g 1 , , g n } E5

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

a i j = { 1 ,  if  ( R j , R i ) E 0 ,  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 ( R i , R m 1 ) , ( R m 1 , R m 2 ) , , ( R m r , R j ) 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 = ( a i j ) R n × n that satisfies a i j 0 whenever 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 = η I M for 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 = { z 1 , , z p } R n , denoted by co(Z), is defined by

co ( Z ) = { j = 1 p μ j z j   |   μ j R , μ j 0 , j = i p μ j = 1 } . E7

Definition 5. Given a point z q = [ x , y ] T and a set Z = { z 1 , , z p } , the distance between z q and co(Z) is defined by dist ( z q , co ( Z ) ) = inf ( dist ( z q , z ) ) , zZ.

Definition 6. Given a vector z = [ z 1 , , z p ] T , we define

tanh ( z ) = [ tanh ( z 1 ) , , tanh ( z p ) ] T . E8

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

Definition 8. Let H R n × n be a block triangular matrix

H = [ A B 0 C ] E9

With A R k × k and 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 ˙ = A x with x = [ x 1 , , x n ] T and A R n × n Hurwitz. Then, the normalised system x ˙ = A D ( x ) x with D ( x ) = diag { 1 / x 1 , , 1 / x n } is stable with finite time convergence.

2.4. Repulsive vector fields

Let N = { R 1 , , R n } be a set of first order agents moving on the plane. The distance between two agents is given by ξ i ξ j , i , j N , ij. Then, the agents R j that are in risk of collision with agent R i belong to the set

M i = { R j N | ξ i ξ j d } , i = 1 , 2 , , n E10

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

β i = ϵ j M i δ i j [ ( x i x j ) ( y i y j ) ( x i x j ) + ( y i y j ) ] E11

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

δ i j = { 1 , if  ξ i ξ j d 0 , if  ξ i ξ j > d E12

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 , 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 { | c i j | } .

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 * = 1 g i k N i ( α k + c k i ) E13

where c ki is the position vector between agents R i and R k . The goal is to design a decentralised control law [ v i , w i ] T = f i ( α i , N i ) , i = 1,…,n such that

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

    lim t ( α i ( t ) α i * ( t ) ) = 0 E14

  • 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 , t 0 , i j E15

A control law to achieve a desired formation is given by

γ i = k e i , i = 1 , , n E16

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

[ v i w i ] = A i 1 ( θ i ) γ i , i = 1 , , n E17

where A i 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

γ i = { μ e i e i , e i 0 0 , e i = 0 i = 1 , , n E18

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

[ v i w i ] = A i 1 ( θ i ) ( γ i + β i ) , i = 1 , , n E19

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 c 32 = [ 0.3 , 0 ] T , c 21 = [ 0.3 cos ( π / 3 ) , 0.3 sin ( π / 3 ) ] T and c 13 = [ 0.3 sin ( π / 6 ) , 0.3 cos ( π / 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).

Advertisement

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

C j i ( t ) = δ ( t ) R ( θ n ) c j i E20

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

R ( θ n ) = [ cos θ n sin θ n sin θ n cos θ n ] E21

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

C ˙ j i ( t ) = δ ˙ ( t ) R ( θ n ) c j i + δ ( t ) R ˙ ( θ n ) c j i E22

where

R ˙ ( θ n ) = [ sin θ n cos θ n cos θ n sin θ n ] w n E23

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 ) = [ m p ( t ) , m q ( t ) ] T be 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

α i * ( t ) = 1 g i j N i ( α j ( t ) + C j i ( t ) ) , i = 1 , , n 1 , 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 ˙ j i ( t ) η c , t 0 .

The goal is to design a decentralised control law [ v i , w i ] T = f i ( α i , N i ) , i = 1 , , n that achieves

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

    lim t ( α n ( t ) m ( t ) ) = 0. E25

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

    lim t ( α 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 , i j , t 0. E27

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

[ v n w n ] = A n 1 ( θ n ) ( k m tanh ( α n m ( t ) ) + m ˙ ( t ) ) [ v i w i ] = A i 1 ( θ i ) ( k f tanh ( α i α i * ) + α ˙ i * ) , i = 1 , , n 1 E28

where A i 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

α ˙ = ( A I 2 ) 1 [ ( K I 2 ) tanh ( ( A I 2 ) α C ) + M ] E29

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

C = [ 1 g 1 j N 1 C j i ( t ) , , 1 g n 1 j N n 1 C j i ( t ) , m ( t ) ] T E30
M = [ 1 g 1 j N 1 C ˙ j i ( t ) , , 1 g n 1 j N n 1 C ˙ j i ( t ) , m ˙ ( t ) ] T

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

Γ = [ 0 0 0 1 ] . E31

At this point, we have to show that ( A I 2 ) is invertible. From the properties of the Kronecker product, we have ( A I 2 ) 1 = A 1 I 2 1 . Since I 2 is the identity matrix, then I 2 1 exits 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 ] T is 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 = 0 has the unique solution X = [ 0 , , 0 ] T .

Now define the errors of the system as

e n = α n m ( t ) e i = α i α i * , i = 1 , , n 1 E32

The system errors in matrix form are given by

e = ( A I 2 ) α C E33

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

e ˙ = ( K I 2 ) tanh ( e ) E34

We propose a Lyapunov function candidate given by

V = 1 2 e T ( K I 2 ) 1 e E35

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

V ˙ = e T ( K I 2 ) 1 ( K I 2 ) tanh ( e ) = e T tanh ( e ) < 0 , e  with  e 0 E36

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

[ v n w n ] = A n 1 ( θ n ) ( k m tanh ( α n m ( t ) ) + m ˙ ( t ) + β n ) [ v i w i ] = A i 1 ( θ i ) ( k f tanh ( α i α i * ) + α ˙ i * + β i ) , i = 1 , , n 1 E37

To analyse the relative distance among the jth and ith agents, we define the variables p j i = α x i α x j and q j i = α y i α y j , 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 ( k f , k m ) and η * = max ( η m , η c ) . Then in the closed-loop system Eqs. (3)(28), the velocities of the agents are bounded by η ^ = ρ ( A 1 ) ( k * 2 n + η * n ) .

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

α ˙ ( A I 2 ) 1 [ ( K I 2 ) tanh ( ( A I 2 ) α C ) + M ] α ˙ ( A I 2 ) 1 ( K I 2 ) tanh ( ( A I 2 ) α C ) + M E38

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

α ˙ ρ ( A 1 ) ( k * 2 n + η * 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, 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

σ r s = p r s 2 + q r s 2 d 2 = 0 E40

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

σ ˙ r s = 2 [ p r s q r s ] [ p ˙ r s q ˙ r s ] = 4 ϵ ( p r s 2 + q r s 2 ) 2 [ p r s q r s ] ( ( α ˙ s * k s tanh ( α s α s * ) ) ( α ˙ r * k r tanh ( α r α r * ) ) ) E41

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

σ ˙ r s = 4 ϵ ( p r s 2 + q r s 2 ) + 4 p r s 2 + q r s 2 η ^ cos θ r s 4 ϵ ( p r s 2 + q r s 2 ) 4 p r s 2 + q r s 2 η ^ > 0. E42

Solving for ϵ, we have that, if ϵ > η ^ / d , then σ ˙ r s > 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 ) d for 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

σ = [ σ r s 1 σ r s 2 ] = [ p r s 1 2 + q r s 1 2 d 2 p r s 2 2 + q r s 2 2 d 2 ] = 0. E43

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

σ ˙ r s 1 + σ ˙ r s 2 = 4 ϵ ( p r s 1 2 + q r s 1 2 ) + 2 [ p r s 1 q r s 1 ] ( ( k s 1 tanh ( α s 1 α s 1 * ) + α ˙ s 1 * ) ( k r tanh ( α r α r * ) + α ˙ r * ) ) + 4 ϵ ( p r s 2 2 + q r s 2 2 ) + 2 [ p r s 2 q r s 2 ] ( ( k s 2 tanh ( α s 2 α s 2 * ) + α ˙ s 2 * ) ( k r tanh ( α r α r * ) + α ˙ r * ) ) + 4 ϵ [ p r s 1 q r s 1 ] [ p r s 2 q r s 2 ] 4 ϵ ( p r s 1 2 + q r s 1 2 ) 4 p r s 1 2 + q r s 1 2 η ^ + 4 ϵ ( p r s 2 2 + q r s 2 2 ) 4 p r s 2 2 + q r s 2 2 η ^ + 4 ϵ p r s 1 2 + q r s 1 2 p r s 2 2 + q r s 2 2 cos θ r s 1 , r s 2 > 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 θ r s 1 , r s 2 = 1 and solving for ϵ, we have that, if ϵ > 2 ( η ^ / d ) , then σ ˙ r s 1 + σ ˙ r s 2 > 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 σ r s 1 + + σ ˙ 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 .

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 ) = [ 4 sin ( 2 ω t ) cos ( ω t ) , 4 sin ( 2 ω t ) sin ( ω t ) ] T where ω = 2 π / T with a period of T = 80s. The static position vectors are given by c 12 = [ 0 , 0.6 ] T , c 21 = [ 0 , 0.6 ] T , c 32 = [ 0.6 cos ( π / 10 ) , 0.6 sin ( π / 10 ) ] T , c 34 = [ 0 , 0.97 ] T , c 43 = [ 0 , 0.97 ] T , and c 54 = [ 0.6 cos ( 3 π / 10 ) , 0.6 sin ( 3 π / 10 ) ] T . The scaling factor is given by δ ( t ) = 1 + 0.2 sin ( ω 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 = { R 1 , , R n } be a set of mobile robots. The set N is composed of two disjoint subsets, so that N = N F N L , where N F = { R 1 , , R n F } , with n F agents, is the subset of followers, and N L = { R n F + 1 , , R n } , 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 R j N F , there are edges ( R i , R m 1 ) , ( R m 1 , R m 2 ) , , ( R m r , R j ) E with R i N L .

Assumption 5. For each secondary leader, there is a path to the main leader, i.e. for all R i N L , i = n F + 1 , , n 1 , there are edges ( R n , R m 1 ) , ( R m 1 , R m 2 ) , , ( R m r , R i ) E .

In order to define the problem statement, let us introduce some notation. Let m ( t ) = [ m p ( t ) , m q ( t ) ] T be 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

α i * ( t ) = 1 g i k N i ( α k ( t ) + C k i ( t ) ) , i = n F + 1 , , n 1 , E45

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

α j * = 1 g j k N j α k , j = 1 , , n F . E46

The goal of this work is to design a decentralised control law [ v i , w i ] T = ( α i , N i ) , i = 1 , , n that ensures

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

    lim t ( α n ( t ) m ( t ) ) = 0. E47

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

    lim t ( α i ( t ) α i * ( t ) ) = 0 , i = n F + 1 , , n 1. E48

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

    lim t dist ( α i ( t ) , co ( α L ( t ) ) ) = 0 , i = 1 , , n F . 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 , r s , t 0. E50

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

[ v n w n ] = A n 1 ( θ n ) ( k m tanh ( α n m ( t ) ) + m ˙ ( t ) ) [ v i w i ] = A i 1 ( θ i ) ( k f tanh ( α i α i * ) + α ˙ i * ) , i = n F + 1 , , n 1 [ v j w j ] = A j 1 ( θ j ) ( k c tanh ( α j α j * ) + α ˙ j * ) , j = 1 , , n F E51

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 k m , k f , k c > 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. lim t ( α n ( t ) m ( t ) ) = 0 , whereas the secondary leaders converge to the desired formation, i.e. lim t ( α i ( t ) α i * ( t ) ) = 0 , for i = n F + 1 , , n 1 .

  2. The followers converge to the convex hull formed by the leaders, i.e. lim t dist ( α j ( t ) , co ( α L ( t ) ) ) = 0 , for j = n 1 , , n F .

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

[ e F e L ] = ( [ P F F P F L 0 P L L ] I 2 ) [ α F α L ] [ 0 C ˜ L ] E52

where e F = [ e 1 T , , e n F T ] T , e L = [ e n F + 1 T , , e n T ] T , α F = [ α 1 T , , α n F T ] T , α L = [ α n F + 1 T , , α n T ] T ,

C ˜ L = [ 1 g n F + 1 k N n F + 1 C k ( n F + 1 ) T ( t ) , , 1 g n 1 k N n 1 C k ( n 1 ) T ( t ) , m T ( t ) ] T , E53
P F F = [ 1 g 1 L F F 1 T , , 1 g n F L F F n F T ] T , P F L = [ 1 g 1 L F L 1 T , , 1 g n F L F L n F T ] T ,
P L L = [ 1 g n F + 1 L L L 1 T , , 1 g n 1 L L L n L 1 T , ( [ 0 0 1 ] 1 × n L ) T ] T ,

where L F F i , L F L i , and L L L i are the ith row of the submatrices L F F , L F L , and L L L , respectively.

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

α F ( t ) = P F F 1 e F ( t ) P F F 1 P F L α L ( t ) . E54

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

P F F = η I F F n F × n F M F F n F × n F , E55

where η = 1, M F F n F × n F is a non-negative matrix and according to Assumption 4, it holds that ρ ( M F F n F × n F ) < η . Therefore, P FF is an M-matrix, which is non-singular, thus P F F 1 exists, and the elements of P F F 1 are non-negative. Since the elements of P FL are negative or zero, then the elements of P F F 1 P F L are non-negative. Since the sum of the elements of each row of [ P F F P F L ] is 0, we have that the sum of the elements of each row of P F F 1 P F L is 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

[ v n w n ] = A n 1 ( θ n ) ( k m tanh ( α n m ( t ) ) + m ˙ ( t ) + β n ) [ v i w i ] = A i 1 ( θ i ) ( k f tanh ( α i α i * ) + α ˙ i * + β i ) , i = n F + 1 , , n 1 [ v j w j ] = A j 1 ( θ j ) ( k c tanh ( α j α j * ) + α ˙ j * + β j ) , j = 1 , , n F E56

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 k m = 1 ,   k f = k c = 2 . The desired marching trajectory is a Lissajous curve given by m ( t ) = [ 4.5 sin ( ω x t + ( π / 2 ) ) , 1.5 sin ( ω y t ) ] T where ω x = 2 π / T and ω y = 6 π / T with a period of T = 80s. The static position vectors are c 87 = [ 1.2 , 0.6 ] T , c 76 = [ 0 , 1.2 ] T , c 67 = [ 0 , 1.2 ] T and c 65 = [ 0.6 , 0.6 ] T . The scaling factor is given by δ ( t ) = 1 + 0.2 sin ( ω x t ) .

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 , 62 and 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).

Advertisement

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.

References

  1. 1. Cao YU, Fukunaga AS, Kahng AB. Cooperative mobile robotics: Antecedents and directions. Autonomous Robots. 1997;4:226–234
  2. 2. Arai T, Pagello E, Parker LE. Guest editorial advances in multirobot systems. IEEE Transactions on Robotics and Automation. 2002;18:655–661
  3. 3. Ji M, Ferrari-Trecate G, Egerstedt M, Buffa A. Containment control in mobile networks. IEEE Transactions on Automatic Control. 2008;53(8):1972–1975
  4. 4. Briñon-Arranz L, Seuret A, Canudas-de-Wit C. Cooperative control design for time-varying formations of multi-agent systems. IEEE Transactions on Automatic Control. 2014;59(8):2283–2288
  5. 5. González-Sierra J, Aranda-Bricaire E. Design of a virtual mechanism for trajectory tracking of convoys of mobile robots. In: Proceedings of the 10th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE ’13); 2013. 30 September–4, October 2013, Mexico City, Mexico: IEEE. pp. 364–368
  6. 6. Peñaloza-Mendoza GR, Hernández-Mendoza DE, Aranda-Bricaire E. Time-varying formation control for multi-agent systems applied to n-trailer configuration. In: Proceedings of the 8th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE '11); 26–28 October 2011, Mérida City, México, IEEE. 2011. pp. 1–6
  7. 7. Rendón-Benitez F, Santiaguillo-Salinas J, González-Sierra J, Aranda-Bricaire E. Marching control of multi-agent systems with orientation to the marching angle of the leader (in Spanish). In: Proceedings of the XV Congreso Latinoamericano de Control Automático (CLCA '12); 23–26 October 2012, Lima, Perú. 2012
  8. 8. Qianwei H, Hongxu M, Hui Z. Collision-avoidance mechanism of multi agent system. In: Proceedings of the 2003 IEEE International Conference on Robotics, Intelligent Systems and Signal Processing; 8–13 October 2, Changsha, China: IEEE. 2003. pp. 1036–1040
  9. 9. De Gennaro MC, Jadbabaie A. Formation control for a cooperative multi-agent system using decentralized navigation functions. In: Proceedings of the American Control Conference (ACC '06); 14–16 June, Minneapolis, Minnesota, USA: IEEE. 2006. pp. 1346–1351
  10. 10. Dimarogonas DV, Kyriakopoulos KJ. Distributed cooperative control and collision avoidance for multiple kinematic agents. In: Proceedings of the 45th IEEE Conference on Decision and Control (CDC '06); 13–15 December, San Diego, CA, USA: IEEE. 2006. pp. 721–726
  11. 11. Dimarogonas DV, Loizou SG, Kyriakopoulos KJ, Zavlanos MM. A feedback stabilization and collision avoidance scheme for multiple independent non-point agents. Automatica. 2006;42:229–243
  12. 12. Hernández-Martínez E, Aranda-Bricaire E. Multi-agent formation control with collision avoidance based on discontinuous vector fields. In: Proceedings of the 35th Annual Conference of IEEE Industrial Electronics (IECON ’09); 3–5 November, Porto, Portugal, IEEE. 2009. pp. 2283–2288
  13. 13. Hernández-Martínez E, Aranda-Bricaire E. Collision avoidance in formation control using discontinuous vector fields. In: Proceeding of the 9th IFAC Symposium on Nonlinear Control Systems (NOLCOS '13); 4–6 September, Toulouse, France: IFAC. 2013. pp. 797–802
  14. 14. Loizou SG, Tannert HG, Kumar V, kyriakopoulos KJ. Closed loop navigation for mobile agents in dynamic environments. In: Procedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '03); 27–31 October, 4, Las Vegas, Nevada: IEEE. 2003. pp. 3769–3774
  15. 15. Yao J, Ordoez R, Gazi V. Swarm tracking using artificial potentials and sliding mode control. In: Proceedings of the 45th IEEE Conference on Decision and Control (CDC '06); 13–15 December, San Diego, CA, USA: IEEE. 2006. pp. 4670–4675
  16. 16. Flores-Resendiz JF, Aranda-Bricaire E. Cyclic pursuit formation control without collisions in multi-agent systems using discontinuous vector fields. In: Proceedings of the XVI Congreso Latinoamericano de Control Automático (CLCA ’14); 14–17 October, Cancún Quintana Roo, México. 2014. pp. 941–946
  17. 17. Flores-Resendiz JF, Aranda-Bricaire E, González-Sierra J, Santiaguillo-Salinas J. Finite-time formation control without collisions for multiagent systems with communication graphs composed of cyclic paths. Mathematical Problems in Engineering. 2015;1:17
  18. 18. Brockett RW. Asymptotic stability and feedback stabilization. In: Millman RS, Brockett RW, Sussmann HJ, editors. Differential Geometric Control Theory. Boston, Birkhauser; 1983. pp. 181–191
  19. 19. Fax JA, Murray RM. Graph laplacians and stabilization of vehicle formations. In: Proceedings of the 15th IFAC World Congress; 2002: 21–26 July, Barcelona, Spain: Elsevier Science. 2002. p. 15
  20. 20. Desai JP. A graph theoretic approach for modeling mobile robot team formations. Journal of Robotic Systems. 2002;19(11):511–525
  21. 21. Lafferriere G, Caughman J, Williams A. Graph theoretic methods in the stability of vehicle formations. In: Proceedings of the American Control Conference (ACC ’04); 2004. 30 June–2 July, Boston, Massachusetts: IEEE. 2004. pp. 3729–3734
  22. 22. Horn RA, Johnson CR. Topics in Matrix Analysis (Online publication). Cambridge University Press; United Kingdom. 2011
  23. 23. Poole GD. Generalized M-matrices and applications. Mathematics of Computation. 1975;29(131):903–910
  24. 24. Rockafellar RT. Convex Analysis. Princeton University Press; New Jersey. 1997
  25. 25. Cai Y, Liu H, Xie G. Finite-time containment control for multi-agent systems with single-integrator dynamics. In: Proceedings of the 31st Chinese Control Conference (CCC ’12); 2012. 25–27 July, Hefei, China: IEEE. 2012. pp. 6433–6438

Written By

Jesús Santiaguillo-Salinas and Eduardo Aranda-Bricaire

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