Containment problem with time-varying formation and collision avoidance for multiagent systems

Abstract

This article studies a time-varying version of the so-called containment problem with collision avoidance for multiagent systems. The proposed control strategy is decentralized, since agents have no global knowledge of the goal to achieve, knowing only the position and velocity of a subset of agents. This control strategy allows a subset of mobile agents (called leaders) to track a prescribed trajectory while they achieve a time-varying formation. Simultaneously, another subset of mobile agents (called followers) converge exponentially to the region bounded by the leaders. For the collision avoidance, we added a repulsive vector field of the unstable focus type to the time-varying containment control law. Formation graphs are used 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. Additionally, an experimental case study is presented.

Introduction

Multiagent systems are defined as bundles of autonomous robots coordinated to accomplish cooperative tasks. In recent years, the study of multiagent 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. ¹

Applications of multiagent systems include the transport and manipulation of large objects, localization, exploration, and motion coordination. ^1,2 Two 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, and the marching control, where the goal is to track a preestablished trajectory while the agents maintain a desired formation.

Within motion coordination, the so-called containment problem has attracted the attention of researchers over recent years. The problem is that a group of mobile agents (called leaders) track a predetermined trajectory while another group of agents (called followers) remain within the region determined by the leaders. ³ The containment problem has several practical applications. For instance, when a group of robots secure a zone to remove hazardous material, they should not leave the area, as they can contaminate the surroundings. Also for navigation of a group of robots, when only a subgroup of them (leaders) has the ability to detect obstacles, while the rest (followers) has no such ability. For the followers, a way to navigate safely is moving within the region delimited by the leaders. ⁴

In the literature, there is a number of works related to the containment problem. The papers ^5,6 consider stationary leaders, so that their initial positions form a desired geometric pattern static all the time. In the study by Dimarogonas et al., ⁷ the formation control problem for the leaders is considered. Elsewhere, ^3,4,8 dynamic leaders are considered. A trajectory is assigned to each leader, but they are placed in such a manner so as to form a geometric pattern to which the followers must converge. In studies by Chen et al. and Dong et al., ^9,10 the containment problem is presented, considering a swarm-type behavior of the agents, using a potential function approach. Paper ¹¹ presents the containment problem both in discrete and in continuous cases. Finally, in the work by Cao et al., ¹² a distributed containment control is studied for both stationary and dynamic leaders.

Another ubiquitous problem in all areas of motion coordination that is scarcely considered in the literature is the posible collision between agents when they attempt to reach a desired position. In the study by Qianwei et al., ¹³ a mechanism for collision avoidance under central control mode (traffic control type) is presented. Elsewhere, ^{14 –16} navigation functions and artificial potential functions are used to avoid collisions between agents. Works ^{17 –20} address the formation control problem without collisions using discontinuous vector fields.

The time-varying formation problem has been studied elsewhere. ^{21 –24} 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. The time-varying formation is composed of a predefined static formation which is transformed by a rotation matrix and a scaling matrix.

The interaction topology between agents is modeled 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 its simplicity and commercial availability. Differential-drive mobile robots present interesting challenges because they possess nonholonomic restrictions; and in spite of having 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 researchers from diverse viewpoints.

The goal of this article is to design a decentralized control strategy that allows trajectory tracking with a time-varying formation of a subset of agents called leaders, while another subset of agents called followers remain inside the region formed by the leaders (a time-varying version of the containment problem). In the subset of leaders, the main leader is responsible of the trajectory tracking, while the secondary leaders reach a time-varying formation with respect to the main leader.

The main contribution of this article is the implementation of the containment problem with dynamic leaders under marching, with time-varying formation control avoiding collisions between agents. The collision avoidance strategy is based on previous works. ^25,26 The main difference is that in this work we consider the formation tracking problem. Moreover, in this work we use bounded control strategies based on sigmoid functions instead of normalizing them, adding a repulsive vector field.

In a previous work, ²⁷ we studied the particular case of leader-centered formation graphs. In this work, the general case is presented, where the interaction between secondary leaders is represented by arbitrary formation graphs. Additionally, we present an experimental case study.

Preliminaries

Kinematic model of differential-drive mobile robots

Let $N=\{R_1,\dots ,R_n\}$ be a set of differential-drive mobile robots moving on the plane with positions ${\xi }_i={\left[x_i,y_i\right]}^T$ , $i=1,\dots ,n$ . According to Figure 1, each robot has a kinematic model given by

$\left[\begin{array}{c}{\dot{x}}_i\\ {\dot{y}}_i\\ {\dot{\theta }}_i\end{array}\right]=\left[\begin{array}{cc}\cos {\theta }_i& 0\\ \text{sin}\hspace{0.17em}{\theta }_i& 0\\ 0& 1\end{array}\right]\left[\begin{array}{c}{v}_i\\ w_i\end{array}\right]i=1,\mathrm{...},n$

1

where v_i is the longitudinal velocity of the middle point of wheel axis of the ith robot, w_i its angular velocity, and θ_i the heading angle with respect to the X-axis. If the position ξ_i is taken as output of the system 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 of the wheels axis. According to Figure 1, the coordinates of point α_i are given by

${\alpha }_i=\left[\begin{array}{c}{\alpha }_{xi}\\ {\alpha }_{yi}\end{array}\right]=\left[\begin{array}{c}{x}_i+\mathcal{l}\hspace{0.17em}\cos \hspace{0.17em}{\theta }_i\\ y_i+\mathcal{l}\hspace{0.17em}\text{sin}\hspace{0.17em}{\theta }_i\end{array}\right]$

2

where $\mathcal{l}$ is the distance from ξ_i to point α_i . The kinematics of point α_i is given by

$\left[\begin{array}{c}{\dot{\alpha }}_{xi}\\ {\dot{\alpha }}_{yi}\end{array}\right]=\left[\begin{array}{cc}\cos \hspace{0.17em}{\theta }_i& -\mathcal{l}\hspace{0.17em}\text{sin}\hspace{0.17em}{\theta }_i\\ \text{sin}\hspace{0.17em}{\theta }_i& \mathcal{l}\hspace{0.17em}\cos \hspace{0.17em}{\theta }_i\end{array}\right]\left[\begin{array}{c}{v}_i\\ w_i\end{array}\right]=A_i({\theta }_i)\left[\begin{array}{c}{v}_i\\ w_i\end{array}\right]$

3

where $A_i({\theta }_i)$ is the decoupling matrix for each robot R_i . The decoupling matrix is nonsingular since $\det \left(A_i({\theta }_i)\right)=\mathcal{l}\ne 0$ .

Figure 1.

Kinematic model of the differential-drive mobile robot.

Defining auxiliary control variables $u_i={\left[u_{ix},u_{iy}\right]}^T$ , it is possible to establish a strategy for controlling the position of the point α_i by

$\left[\begin{array}{c}{v}_i\\ w_i\end{array}\right]=\left[\begin{array}{cc}\cos \hspace{0.17em}{\theta }_i& \text{sin}\hspace{0.17em}{\theta }_i\\ -\frac{\text{sin}\hspace{0.17em}{\theta }_i}{\mathcal{l}}& \frac{\cos \hspace{0.17em}{\theta }_i}{\mathcal{l}}\end{array}\right]\left[\begin{array}{c}{u}_{ix}\\ u_{iy}\end{array}\right]=A_i^{-1}({\theta }_i)\left[\begin{array}{c}{u}_{ix}\\ u_{iy}\end{array}\right]$

4

where $A_i^{-1}({\theta }_i)$ is the inverse of the decoupling matrix. The closed-loop system (3) and (4) produces

${\dot{\alpha }}_i=u_i$

5

The auxiliary control variables $u_i={\left[u_{ix},u_{iy}\right]}^T$ correspond to the control strategy designed in this article.

Basic graph theory

• Definition 1: (formation graph) Let $N=\{R_1,\dots ,R_n\}$ be a set of mobile agents and N_i be the set of agents which have a flow of information toward the ith agent. A formation graph $G=\{V,E,C\}$ consists of

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

  $\mathcal{L}(G)=\Delta -{\mathcal{A}}_d$

  6

where Δ is the degree matrix defined by

$\Delta ={\displaystyle \text{diag}}\left\{g_1,\dots ,g_n\right\}$

7

where $g_i=card\left\{N_i\right\}$ , $i=1,\dots ,n$ and ${\mathcal{A}}_d$ is the adjacency matrix of G defined by

$a_{ij}=\{\begin{array}{ll}1,\hfill & \text{if}(R_j,R_i)\in E\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$

8

The set $N=\{R_1,\dots ,R_n\}$ is composed of two disjoint subsets, so that $N=N_F\cup N_L$ , where $N_F=\{R_1,\dots ,R_{n_F}\}$ , with n_F agents, is the subset of followers and $N_L=\{R_{n_F+1},\dots ,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.

Let $\mathcal{L}(G)$ be the Laplacian of a formation graph $G=\{V,E,C\}$ . The matrix $\mathcal{L}(G)$ is partitioned into blocks corresponding to subsets of followers and leaders as follows:

$\mathcal{L}(G)=\left[\begin{array}{cc}{\mathcal{L}}_{FF}& {\mathcal{L}}_{FL}\\ 0_{n_L\times n_F}& {\mathcal{L}}_{LL}\end{array}\right]$

where ${\mathcal{L}}_{FF}\in {ℝ}^{n_F\times n_F}$ , ${\mathcal{L}}_{FL}\in {ℝ}^{n_F\times n_L}$ , and ${\mathcal{L}}_{LL}\in {ℝ}^{n_L\times n_L}$ represent, respectively, the Laplacian of a subgraph of G containing the interactions between followers only, the interactions between followers and leaders, and the Laplacian of a subgraph of G containing the interactions between leaders only.

In the rest of this article, we make the following standings assumptions:

Assumption 1: For each follower agent, there is a communication, either direct or indirect, with at least one leader agent, that is, for all $R_j\in N_F$ there are edges $(R_i,R_{m_1}),(R_{m_1},R_{m_2}),\dots ,(R_{m_r},R_j)\in E$ with $R_i\in N_L$ .

Assumption 2: For each secondary leader agent, there is a communication, either direct or indirect, with the main leader agent, that is, for all $R_i\in N_L,i=n_F+1,\dots ,n-1$ there are edges $(R_n,R_{m_1}),(R_{m_1},R_{m_2}),\dots ,(R_{m_r},R_i)\in E$ .

For further details about formation graphs, Laplacian, and its properties, the reader is referred to Fax and colleagues. ^{28 –30}

Mathematical miscellaneous

• Definition 3: Let $A=(a_{ij})\in {ℝ}^{n\times n}$ that satisfies $a_{ij}\le 0$ whenever i ≠ j and a_ii > 0 for each i. ^31,32 The matrix A is called an M matrix if it satisfies any one of the following equivalent conditions:

• Definition 4: ³³ The convex hull of a set of vectors $Z=\{z_1,\dots ,z_p\}\subset {ℝ}^n$ , denoted by co(Z), is defined by

• $co(Z)=\left\{{\displaystyle \sum _{j=i}^p{\mu }_j{z}_j|{\mu }_j\in ℝ},{\mu }_j\ge 0,\hspace{0.17em}{\displaystyle \sum _{j=i}^p{\mu }_j=1}\right\}.$

• Definition 5: Given a point $z_q={\left[x,y\right]}^T$ and a set $Z=\{z_1,\dots ,z_p\}$ , the distance between z_q and co(Z) is defined by $dist(z_q,co(Z))=\inf (dist(z_q,z)),z\in Z$ .

• Definition 6: Given a vector $z={\left[z_1,\dots ,z_p\right]}^T$ , we define $\text{tanh}(z)={\left[\text{tanh}(z_1),\dots ,\text{tanh}(z_p)\right]}^T$ .

Problem statement

In order to define the problem statement, let us introduce some notation:

Let $m(t)={\left[m_p(t),m_q(t)\right]}^T$ be a continuously differentiable preestablished trajectory, where $\left|\right|\dot{m}(t)\left|\right|\le {\eta }_m$ , ∀t ≥ 0.

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

${\alpha }_i^{*}(t)=\frac{1}{g_i}{\displaystyle \sum _{k\in N_i}}\left({\alpha }_k(t)+C_{ki}(t)\right),i=n_F+1,\mathrm{...},n-1$

where C_ji (t) is a time-varying position vector between the agents i and j and will be specifically defined in the next section. The time derivative of C_ji (t) satisfies $\left|\right|{\dot{C}}_{ji}(t)\left|\right|\le {\eta }_c$ , ∀t ≥ 0.

The goal of this work is to design a decentralized control law $u_i=\left({\alpha }_i,N_i\right)$ , $i=1,\dots ,n$ that ensures

Asymptotic tracking of a prescribed trajectory by the main leader agent (marching control), that is

$\underset{t\to \infty }{{\displaystyle \lim }}\left({\alpha }_n(t)-m(t)\right)=0$

Asymptotic time-varying formation by the secondary leader agents (time-varying formation control), that is

$\underset{t\to \infty }{{\displaystyle \lim }}\left({\alpha }_i(t)-{\alpha }_i^{*}(t)\right)=0,i=n_F+1,\mathrm{...},n-1$

Convergence of the follower agents to the convex hull formed by the leaders (containment control), that is

$\underset{t\to \infty }{\lim }dist\left({\alpha }_i(t),co({\alpha }_L(t))\right)=0,i=1,\dots ,n_F$

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, that is

$\left|\right|{\alpha }_r(t)-{\alpha }_s(t)\left|\right|\ge d,r,s=1,\dots ,n,\forall t\ge 0$

Control strategy for containment with time-varying formation

Time-varying position vector

To maintain a formation (by the secondary leader agents) oriented to the direction of the main leader agent and rescale the formation, we use a time-varying position vector given by

$C_{ji}(t)=S(t)R({\theta }_n)c_{ji}$

9

where c_ji is a static position vector corresponding to the desired formation, $R({\theta }_n)$ is a rotation matrix, and S(t) is a scaling matrix given by

$R({\theta }_n)=\left[\begin{array}{cc}\cos \hspace{0.17em}{\theta }_n& -\text{sin}\hspace{0.17em}{\theta }_n\\ \text{sin}\hspace{0.17em}{\theta }_n& \cos \hspace{0.17em}{\theta }_n\end{array}\right]\hspace{1em}\text{and}\hspace{1em}S(t)=\left[\begin{array}{cc}\mu (t)& 0\\ 0& \mu (t)\end{array}\right]$

10

respectively. The time-derivative of (9) is given by

${\dot{C}}_{ji}(t)=\dot{S}(t)R({\theta }_n)c_{ji}+S(t)\dot{R}({\theta }_n)c_{ji}$

11

where

$\dot{R}({\theta }_n)=\left[\begin{array}{cc}-\text{sin}\hspace{0.17em}{\theta }_n& -\cos \hspace{0.17em}{\theta }_n\\ \cos \hspace{0.17em}{\theta }_n& -\text{sin}\hspace{0.17em}{\theta }_n\end{array}\right]w_n\hspace{1em}\text{and}\hspace{1em}\dot{S}(t)=\left[\begin{array}{cc}\dot{\mu }(t)& 0\\ 0& \dot{\mu }(t)\end{array}\right]$

12

Control strategy and convergence analysis

For containment under marching with time-varying formation, we propose a control law for the leaders and followers, based on the fundamental consensus algorithm, ³⁴ given by

$u_n=-k_m\text{tanh}\left({\alpha }_n-m(t)\right)+\dot{m}(t)$

13

$u_i=-k_f\text{tanh}\left({\alpha }_i-{\alpha }_i^{*}\right)+{\dot{\alpha }}_i^{*},i=n_F+1,\dots ,n-1$

14

$u_j=-k_c\text{tanh}\left({\alpha }_j-{\alpha }_j^{*}\right)+{\dot{\alpha }}_j^{*},j=1,\dots ,n_F$

15

where m(t) is the desired trajectory, $\dot{m}(t)$ is the marching velocity, k_m , k_f , and k_c are control gains and ${\alpha }_j^{*}=(1/g_j){\displaystyle {\sum }_{k\in N_j}}{\alpha }_k$ , $j=1,\dots ,n_F$ . Note that for each secondary leader and each follower, the control input depends on the position and velocity of the agents with which they have communication. In practical implementations, these velocities can be calculated by numerical differentiation.

The first main result of this article is the following:

Theorem 1: Consider the system (5) and the control laws (13) to (15). Suppose that k_m , k_f , k_c > 0. Then in the closed-loop system defined by (5), (13) to (15), it follows that:

1. The main leader R_n converges to the desired marching trajectory, that is, ${{\displaystyle \lim }}_{t\to \infty }\left({\alpha }_n(t)-m(t)\right)=0$ , whereas the secondary leaders converge to the desired formation, that is, ${{\displaystyle \lim }}_{t\to \infty }\left({\alpha }_i(t)-{\alpha }_i^{*}(t)\right)=0$ , for $i=n_F+1,\dots ,n-1$ .

2. The followers converge to the convex hull formed by the leaders, that is, ${{\displaystyle \lim }}_{t\to \infty }dist\left({\alpha }_j(t),co({\alpha }_L(t))\right)=0$ , for $j=n_1,\dots ,n_F$ .

Proof: Part 1. The closed-loop system (5), (13) to (15) is given by

$\dot{\alpha }={(A\otimes I_2)}^{-1}\left[-(K\otimes I_2)\text{tanh}((A\otimes I_2)\alpha -C)+M\right]$

16

where $\alpha ={\left[{\alpha }_1^T,\dots ,{\alpha }_n^T\right]}^T$ , $K={\displaystyle diag}\left\{k_c,\dots ,k_c,k_f,\dots ,k_f,k_m\right\}$ , ⊗ denotes the Kronecker product, I ₂ is the 2 × 2 identity matrix,

$\begin{array}{l}C={\left[0^T,\dots ,0^T,\frac{1}{g_{n_F+1}}{\displaystyle \sum _{k\in N_{n_F+1}}}{C}_{ki}^T(t),\dots ,\frac{1}{g_{n-1}}{\displaystyle \sum _{k\in N_{n-1}}}{C}_{ki}^T(t),m^T(t)\right]}^T\hfill \\ M={\left[0^T,\dots ,0^T,\frac{1}{g_{n_F+1}}{\displaystyle \sum _{k\in N_{n_F+1}}}{\dot{C}}_{ki}^T(t),\dots ,\frac{1}{g_{n-1}}{\displaystyle \sum _{k\in N_{n-1}}}{\dot{C}}_{ki}^T(t),{\dot{m}}^T(t)\right]}^T,\hspace{1em}A=\left(\Lambda \mathcal{L}(G)\right)+\Gamma \hfill \end{array}$

where $\mathcal{L}(G)$ is the Laplacian of the formation graph G, $\Lambda ={\displaystyle diag}\left\{\frac{1}{g_1},\dots ,0\right\}$ and $\Gamma =\left[\begin{array}{ccc}0& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & 1\end{array}\right]$ .

To begin with, we have to show that $(A\otimes I_2)$ is invertible. From the properties of the Kronecker product, we have ${(A\otimes I_2)}^{-1}=A^{-1}\otimes I_2^{-1}$ . Since I ₂ is the identity matrix, then $I_2^{-1}$ exits and we address in the matrix $A=(\Lambda \mathcal{L}(G))+\Gamma$ . The matrix $\Lambda \mathcal{L}(G)$ is positive semidefinite. Hence, the matrix $(\Lambda \mathcal{L}(G))+\Gamma$ is positive definite. In addition, $(\Lambda \mathcal{L}(G))+\Gamma =(a_{ij})$ satisfies a_ij ≤ 0 for i ≠ j and a_ii > 0, ∀i, so that from definition 3 and assumptions 1 and 2, $(\Lambda \mathcal{L}(G))+\Gamma$ has a inverse and therefore $A^{-1}$ exist.

Define the errors of the system as

$e_n={\alpha }_n-m(t)$

17

$e_i={\alpha }_i-{\alpha }_i^{*},\hspace{1em}i=n_F+1,\dots ,n-1$

18

$e_j={\alpha }_j-{\alpha }_j^{*},\hspace{1em}j=1,\dots ,n_F$

19

In matrix form, the system errors are given by

$e=\left(A\otimes I_2\right)\alpha -C$

20

where $e={\left[e_1^T,\dots ,e_n^T\right]}^T$ . The dynamics of the error coordinates are given by

$\dot{e}=-\left(K\otimes I_2\right)\text{tanh}(e)$

21

We propose a Lyapunov function candidate given by

$V=\frac{1}{2}{e}^T{(K\otimes I_2)}^{-1}e$

22

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

$\dot{V}=e^T{(K\otimes I_2)}^{-1}(K\otimes I_2)\text{tanh}(e)=-e^T\text{tanh}(e)<0,\forall e\hspace{0.17em}\text{with}\hspace{0.17em}e\ne 0$

23

so the errors converge asymptotically to 0.

Part 2. Rewrite the system errors (20) in the form

$\left[\begin{array}{c}{e}_F\\ e_L\end{array}\right]=\left(\left[\begin{array}{cc}{P}_{FF}& P_{FL}\\ 0& P_{LL}\end{array}\right]\otimes I_2\right)\left[\begin{array}{c}{\alpha }_F\\ {\alpha }_L\end{array}\right]-\left[\begin{array}{c}0\\ {\tilde{C}}_L\end{array}\right]$

24

where $e_F={\left[e_1^T,\dots ,e_{n_F}^T\right]}^T$ , $e_L={\left[e_{n_F+1}^T,\dots ,e_n^T\right]}^T$ , ${\alpha }_F={\left[{\alpha }_1^T,\dots ,{\alpha }_{n_F}^T\right]}^T$ , ${\alpha }_L={\left[{\alpha }_{n_F+1}^T,\dots ,{\alpha }_n^T\right]}^T$

$\begin{array}{c}{\tilde{C}}_L={\left[\frac{1}{g_{n_F+1}}{\displaystyle \sum _{k\in N_{n_F+1}}}{C}_{ki}^T(t),\dots ,\frac{1}{g_{n-1}}{\displaystyle \sum _{k\in N_{n-1}}}{C}_{ki}^T(t),m^T(t)\right]}^T,\hspace{1em}{P}_{FF}={\left[\frac{1}{g_1}{\mathcal{L}}_{F{F}_1}^T,\dots ,\frac{1}{g_{n_F}}{\mathcal{L}}_{F{F}_{n_F}}^T\right]}^T,\\ P_{FL}={\left[\frac{1}{g_1}{\mathcal{L}}_{F{L}_1}^T,\dots ,\frac{1}{g_{n_F}}{\mathcal{L}}_{F{L}_{n_F}}^T\right]}^T,\hspace{1em}{P}_{LL}={\left[\frac{1}{g_{n_F+1}}{\mathcal{L}}_{L{L}_1}^T,\dots ,\frac{1}{g_{n-1}}{\mathcal{L}}_{L{L}_{n_L-1}}^T,{\left({\left[\begin{array}{cccc}0& \cdots & 0& 1\end{array}\right]}_{1\times n_L}\right)}^T\right]}^T\end{array}$

where ${\mathcal{L}}_{F{F}_i}$ , ${\mathcal{L}}_{F{L}_i}$ , and ${\mathcal{L}}_{L{L}_i}$ are the ith row of the submatrix ${\mathcal{L}}_{FF}$ , ${\mathcal{L}}_{FL}$ , and ${\mathcal{L}}_{LL}$ , respectively.

Solving for the position of follower agents α_F (t) of Equation (24), we have

${\alpha }_F(t)=P_{FF}^{-1}{e}_F(t)-P_{FF}^{-1}{P}_{FL}{\alpha }_L(t).$

Since $e_F(t)\to 0$ as t → ∞, then ${\alpha }_F(t)\to -P_{FF}^{-1}{P}_{FL}{\alpha }_L(t)$ . To verify that $P_{FF}^{-1}$ exist, we have to analyze the submatrix P_FF . Making a similar analysis to, ⁵ we can rewrite P_FF as

$P_{FF}=\eta I_{F{F}_{n_F\times n_F}}-M_{F{F}_{n_F\times n_F}}$

where η = 1, $M_{F{F}_{n_F\times n_F}}$ is a nonnegative matrix and according to assumption 1, it holds that $\rho \left(M_{F{F}_{n_F\times n_F}}\right)<\eta$ . Therefore, P_FF is an M matrix, which is nonsingular, thus $P_{FF}^{-1}$ exists and the elements of $P_{FF}^{-1}$ are nonnegative. Since the elements of P_FL are negative or 0, then the elements of $-P_{FF}^{-1}{P}_{FL}$ are nonnegative. Since the sum of the elements of each row of $[P_{FF}\hspace{1em}{P}_{FL}]$ is 0, we have that the sum of the elements of each row of $-P_{FF}^{-1}{P}_{FL}$ is 1 and according to definition 4, when t → ∞, the follower positions are within the convex hull formed by the leaders.

Collision avoidance strategy

Once the control strategy for containment with time-varying formation has been designed, and having made the corresponding convergence analysis, we now address the problem of collision avoidance between agents by designing a complementary control law based on repulsive vector fields depending on the distance among agents.

The distance between any pair of agents is given by $\parallel {\alpha }_r-{\alpha }_s\parallel$ , $\forall r,s\in N$ , r ≠ s. Then the agents α_s who are at risk of collision with the agent α_r belong to the set

$M_r=\left\{{\alpha }_s\in N\left|\right|{\alpha }_r-{\alpha }_s\left|\right|\le d\right\},\hspace{1em}s=1,\dots ,n$

25

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

${\beta }_r=\{\begin{array}{ll}\epsilon {\displaystyle \sum _{s\in M_r}\left[\begin{array}{c}({\alpha }_{xr}-{\alpha }_{xs})-({\alpha }_{yr}-{\alpha }_{ys})\\ ({\alpha }_{xr}-{\alpha }_{xs})+({\alpha }_{yr}-{\alpha }_{ys})\end{array}\right]},\hfill & \text{if}\left|\right|{\alpha }_r-{\alpha }_s\left|\right|\le d\hfill \\ 0,\hfill & \text{if}\hspace{0.17em}\left|\right|{\alpha }_r-{\alpha }_s\left|\right|>d\hfill \end{array}$

26

where ε > 0 is a design parameter to be defined later. The vector fields are proposed in such a way that, for agent R_r there exists an unstable counterclockwise focus, centered at the position of the other agents.

We consider the following assumption:

Assumption 3. The initial conditions of all agents satisfy $\left|\right|{\alpha }_r(0)-{\alpha }_s(0)\left|\right|>d$ , $\forall r,s\in N$ . Namely, there is no risk of collision between agents at t = 0.

Finally, the control strategy for the agents is given by

$u_n=-k_m\text{tanh}({\alpha }_n-m(t))+\dot{m}(t)+{\beta }_n$

27

$u_i=-k_f\text{tanh}({\alpha }_i-{\alpha }_i^{*})+{\dot{\alpha }}_i^{*}+{\beta }_i,i=n_F+1,\dots ,n-1$

28

$u_j=-k_c\text{tanh}({\alpha }_j-{\alpha }_j^{*})+{\dot{\alpha }}_j^{*}+{\beta }_j,j=1,\dots ,n_F$

29

To analyze the relative distance among any pair of agents, r and s, we define the variables $p_{rs}={\alpha }_{xs}-{\alpha }_{xr}$ and $q_{rs}={\alpha }_{ys}-{\alpha }_{yr}$ , $r,s=1,\dots ,n$ , r ≠ s which correspond to the horizontal and vertical distances between agents. In the plane $p_{rs}-q_{rs}$ , we identify the origin as the point where collision between r th and s th agents occurs and a circle of radius d, centered at the origin, as the influence region between the two agents. Outside the circle, only the containment with time-varying formation 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 (5) and the control laws (13) to (15). Then in the closed-loop system defined by (5), (13) to (15), the velocities of the agents are bounded by $\widehat{\eta }=\sqrt{\rho \left({({(A\otimes I_2)}^{-1})}^T({(A\otimes I_2)}^{-1})\right)}\left(k^{*}\sqrt{2n}+{\eta }^{*}\sqrt{n_L}\right)$ .

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

$\left|\right|\dot{\alpha }\left|\right|\le \left|\right|{(A\otimes I_2)}^{-1}\left[-(K\otimes I_2)\text{tanh}((A\otimes I_2)\alpha -C)+M\right]\left|\right|\le \left|\right|{(A\otimes I_2)}^{-1}\left|\right|\left[\left|\right|-(K\otimes I_2)\left|\right|\left|\right|\text{tanh}((A\otimes I_2)\alpha -C)\left|\right|+\left|\right|M\left|\right|\right]$

where $\left|\right|-(K\otimes I_2)\left|\right|=k^{*}$ , with $k^{*}=\max \left(k_c,k_f,k_m\right)$ , $\left|\right|\text{tanh}((A\otimes I_2)\alpha -C)\left|\right|\le \sqrt{2n}$ , $\left|\right|M\left|\right|\le {\eta }^{*}\sqrt{n_L}$ , with ${\eta }^{*}=\max \left({\eta }_m,{\eta }_c\right)$ and $\left|\right|{(A\otimes I_2)}^{-1}\left|\right|\le \sqrt{\rho \left({({(A\otimes I_2)}^{-1})}^T({(A\otimes I_2)}^{-1})\right)}$ . Finally, we have

$\left|\right|\dot{\alpha }\left|\right|\le \sqrt{\rho \left({({(A\otimes I_2)}^{-1})}^T({(A\otimes I_2)}^{-1})\right)}\left(k^{*}\sqrt{2n}+{\eta }^{*}\sqrt{n_L}\right)=\widehat{\eta }$

30

This concludes the proof.

Now, we can state our second main result. First, we consider the scenario when only two agents are in risk of collision. Based on this, we state the following theorem which is essential, since it considers the simplest case of risk of collision.

Theorem 2. Consider the system (5) and the control laws (27) to (29). Suppose that there exists risk of collision between only two agents and the parameter ε satisfies $\epsilon >\widehat{\eta }/d$ . Then in the closed-loop system (5) and (33) to (35), the agents converge asymptotically to their desired positions and they stay at a distance greater than or equal to d, ∀t ≥ 0.

Proof. We want to show that the agents r and s will avoid collision between them and they stay at some minimum distance from each other. We define a surface given by

${\sigma }_{rs}=p_{rs}^2+q_{rs}^2-d^2=0$

31

The dynamics of p_rs and q_rs is

$\left[\begin{array}{c}{\dot{p}}_{rs}\\ {\dot{q}}_{rs}\end{array}\right]=-k_s\text{tanh}({\alpha }_s-{\alpha }_s^{*})+{\dot{\alpha }}_s^{*}+\epsilon \left[\begin{array}{c}{p}_{rs}-q_{rs}\\ p_{rs}+q_{rs}\end{array}\right]+k_r\text{tanh}({\alpha }_r-{\alpha }_r^{*})-{\dot{\alpha }}_r^{*}-\epsilon \left[\begin{array}{c}{p}_{sr}-q_{sr}\\ p_{sr}+q_{sr}\end{array}\right]$

32

To determine the behavior under the action of the repulsive vector fields, we use the positive definite function

$V=\frac{1}{2}{\sigma }_{rs}^2$

33

whose time derivative is given by

$\dot{V}={\sigma }_{rs}{\dot{\sigma }}_{rs}$

34

The time derivative of (31) is calculated and it is evaluated along the trajectories of the closed-loop system

${\dot{\sigma }}_{rs}=2\left[\begin{array}{cc}{p}_{rs}& q_{rs}\end{array}\right]\left[\begin{array}{c}{\dot{p}}_{rs}\\ {\dot{q}}_{rs}\end{array}\right]=2\left[\begin{array}{cc}{p}_{rs}& q_{rs}\end{array}\right]\left((-k_s\text{tanh}({\alpha }_s-{\alpha }_s^{*})+{\dot{\alpha }}_s^{*})-(-k_r\text{tanh}({\alpha }_r-{\alpha }_r^{*})+{\dot{\alpha }}_r^{*})\right)+4\epsilon (p_{rs}^2+q_{rs}^2)$

35

Note that $p_{rs}=-p_{sr}$ and $q_{rs}=-q_{sr}$ . Therefore, $\dot{V}<0$ is achieved if ${\sigma }_{rs}{\dot{\sigma }}_{rs}<0$ . When there exists risk of collision, the trajectories lie in the inner region of ${\sigma }_{rs}=0$ , that is, ${\sigma }_{rs}<0$ , then the analysis reduces to show that ${\dot{\sigma }}_{rs}>0$ . This means that the resulting vector fields inside the circle points outward, that is, to the region free of collision. Using the definition of the cross product, we have

${\dot{\sigma }}_{rs}=4\sqrt{p_{rs}^2+q_{rs}^2}\widehat{\eta }\hspace{0.17em}\cos \hspace{0.17em}{\theta }_{rs}+4\epsilon \left(p_{rs}^2+q_{rs}^2\right)\ge -4\sqrt{p_{rs}^2+q_{rs}^2}\widehat{\eta }+4\epsilon \left(p_{r1}^2+q_{r1}^2\right)>0$

36

Solving for ε and taking into account that $p_{rs}^2+q_{rs}^2<d$ we have that, if $\epsilon >\widehat{\eta }/d$ then ${\dot{\sigma }}_{rs}>0$ . This implies that agents r and s move away from each other. Since $\left|\right|{\alpha }_s(0)-{\alpha }_r(0)\left|\right|\ge d$ , then the agents satisfy $\left|\right|{\alpha }_s(t)-{\alpha }_r(t)\left|\right|\ge d$ for all times.□

In order to generalize the problem, we now consider the scenario where three agents are at risk of collision, that is, agent r is at risk of collision against agents s1 and s2.

Theorem 3: Consider the system (5) and the control laws (27) to (29). Suppose that there exists a risk of collision between three agents and the parameter ε satisfies $\epsilon >2(\widehat{\eta }/d)$ . Then in the closed-loop system (5) and (27) to (29), 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

$\sigma =\left[\begin{array}{c}{\sigma }_{rs1}\\ {\sigma }_{rs2}\end{array}\right]=\left[\begin{array}{c}{p}_{rs1}^2+q_{rs1}^2-d^2\\ p_{rs2}^2+q_{rs2}^2-d^2\end{array}\right]=0$

37

The dynamics of p _rs1, q _rs1, and p _rs2, q _rs12 are

$\begin{array}{c}\left[\begin{array}{c}{\dot{p}}_{rs1}\\ {\dot{q}}_{rs1}\end{array}\right]=\left(\left(-k_{s1}\text{tanh}\left({\alpha }_{s1}-{\alpha }_{s1}^{*}\right)+{\dot{\alpha }}_{s1}^{*}\right)-\left(-k_r\text{tanh}\left({\alpha }_r-{\alpha }_r^{*}\right)+{\dot{\alpha }}_r^{*}\right)\right)+2\epsilon \left[\begin{array}{c}{p}_{rs1}-q_{rs1}\\ p_{rs1}+q_{rs1}\end{array}\right]+\epsilon \left[\begin{array}{c}{p}_{rs2}-q_{rs2}\\ p_{rs2}+q_{rs2}\end{array}\right]\\ \left[\begin{array}{c}{\dot{p}}_{rs2}\\ {\dot{q}}_{rs2}\end{array}\right]=\left(\left(-k_{s2}\text{tanh}\left({\alpha }_{s2}-{\alpha }_{s2}^{*}\right)+{\dot{\alpha }}_{s2}^{*}\right)-\left(-k_r\text{tanh}\left({\alpha }_r-{\alpha }_r^{*}\right)+{\dot{\alpha }}_r^{*}\right)\right)+2\epsilon \left[\begin{array}{c}{p}_{rs2}-q_{rs2}\\ p_{rs2}+q_{rs2}\end{array}\right]+\epsilon \left[\begin{array}{c}{p}_{rs1}-q_{rs1}\\ p_{rs1}+q_{rs1}\end{array}\right]\end{array}$

38

We use the positive definite function

$V=\frac{1}{2}{\sigma }^T\sigma$

39

whose time derivative is given by

$\dot{V}={\sigma }^T\dot{\sigma }={\sigma }_{rs1}{\dot{\sigma }}_{rs1}+{\sigma }_{rs2}{\dot{\sigma }}_{rs2}\le {\sigma }^{*}({\dot{\sigma }}_{rs1}+{\dot{\sigma }}_{rs2})<0$

40

where ${\sigma }^{*}=\max \{{\sigma }_{rs1},{\sigma }_{rs2}\}$ . Evaluated $\dot{V}$ considering that the trajectories lie in the inner region of σ = 0, that is, ${\sigma }_{rs1},{\sigma }_{rs2}<0$ , then the analysis reduces to show that ${\dot{\sigma }}_{rs1}+{\dot{\sigma }}_{rs2}>0$ . Hence

${\dot{\sigma }}_{rs1}+{\dot{\sigma }}_{rs2}=2\left[p_{rs1}\hspace{0.17em}\hspace{0.17em}{q}_{rs1}\right]\left((-k_{s1}\text{tanh}({\alpha }_{s1}-{\alpha }_{s1}^{*})+{\dot{\alpha }}_{s1}^{*})-(-k_r\text{tanh}({\alpha }_r-{\alpha }_r^{*})+{\dot{\alpha }}_r^{*})\right)+4\epsilon (p_{rs1}^2+q_{rs1}^2)+2\left[p_{rs2}\hspace{0.17em}\hspace{0.17em}{q}_{rs2}\right]\left((-k_{s2}\text{tanh}({\alpha }_{s2}-{\alpha }_{s2}^{*})+{\dot{\alpha }}_{s2}^{*})-(-k_r\text{tanh}({\alpha }_r-{\alpha }_r^{*})+{\dot{\alpha }}_r^{*})\right)+4\epsilon (p_{rs2}^2+q_{rs2}^2)+4\epsilon \left[p_{rs1}\hspace{0.17em}\hspace{0.17em}{q}_{rs1}\right]\left[\begin{array}{c}{p}_{rs2}\\ q_{rs2}\end{array}\right]\ge -4\sqrt{p_{rs1}^2+q_{rs1}^2}\widehat{\eta }+4\epsilon (p_{rs1}^2+q_{rs1}^2)-4\sqrt{p_{rs2}^2+q_{rs2}^2}\widehat{\eta }+4\epsilon (p_{rs2}^2+q_{rs2}^2)+4\epsilon \sqrt{p_{rs1}^2+q_{rs1}^2}\sqrt{p_{rs2}^2+q_{rs2}^2}\cos {\theta }_{rs\mathrm{1,}rs2}>0$

41

In this scenario, agents s1 and s2 can be positioned at any point of the circumference of radio d around the agent r, considering that, from theorem 2, they must remain at a distance greater than or equal to d between them. The worst case occurs when the agents s1 and s2 are uniformly distributed over the circumference of radio d. Thus, $\cos \hspace{0.17em}{\theta }_{rs1,rs2}=-1$ and solving for ε we have that, if $\epsilon >2(\widehat{\eta }/d)$ then ${\dot{\sigma }}_{rs1}+{\dot{\sigma }}_{rs2}>0$ . This implies that agents s1 and s2 and r avoid collision between them.□

Geometrically, the most general scenario occurs when an agent r is surrounded by other six agents. Now, we can state our second main result.

Theorem 4: Consider the system (5) and the control laws (27) to (29). Suppose that there exists risk of collision between n ≥ 3 agents and the parameter ε satisfies $\epsilon >2(\widehat{\eta }/d)$ . Then, in the closed-loop system (5) and (27) to (29), 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 theorem 3, considering a surface with n − 1 components and showing that, if ${\sigma }_{rs1}+\cdots +{\dot{\sigma }}_{r(n-1)}>0$ , then $\dot{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, so the agents avoid collision between them.ð

Numerical simulation

The results of a numerical simulation using the control strategy given by (27) to (29) are shown below. For the simulation, we considered eight unicycle-type mobile robots, where the point α_i to control is located 0.15 m ahead the midpoint of the wheels axis. The formation graph employed in the simulation is shown in Figure 2.

Figure 2.

Formation graph for the simulation.

The parameters used in the simulation are $k_m=1,k_f=k_c=2$ . The desired marching trajectory is the Lissajous curve $m(t)={\left[4.5\text{sin}\left({\omega }_{x}t+(\pi /2)\right),1.5\text{sin}\left({\omega }_y\right)\right]}^T$ , where ${\omega }_x=(2\pi /T)$ and ${\omega }_y=(6\pi /T)$ , with a period of T = 80 s. The static position vectors are $c_{87}={\left[-1.2,-0.6\right]}^T$ , $c_{76}={\left[0,1.2\right]}^T$ , $c_{67}={\left[0,-1.2\right]}^T$ , and $c_{65}={\left[-0.6,-0.6\right]}^T$ . The scaling factor is given by $\mu (t)=1+0.2\hspace{0.17em}\text{sin}({\omega }_{x}t)$ .

The minimum allowed distance between agents is d = 0.2 m and the parameter ε was set to $\epsilon =2.2(\widehat{\eta }/d)$ , $k=1,\dots ,n$ to ensure the minimum distance condition will not be violated.

Figure 3 shows the motion of the agents in the plane. The initial position of the agents is 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.

Figure 3.

Trajectories of the agents in the plane.

Figure 4(a) and (b) shows the errors of the follower and the leaders, respectively. Such errors converge to 0. The required control signals are shown in Figure 5(a) and (b).

Figure 4.

Errors of the agents of the system.

Figure 5.

Controls of the agents of the system.

Figure 6(a) depicts all the posible distances between agents. The distances between any pair of agents is always greater than or equal to the predefined distance d = 0.2. To better appreciate Figure 6(a), a zoom to the distances between the agents that are at risk of collision is presented in Figure 6(b).

Figure 6.

Distances among agents of the system.

Experimental case study

To validate the theoretical results, the control strategy is implemented on the experimental platform shown in Figure 7. The platform is composed of four AmigoBot differential-drive mobile robots manufactured by MobileRobots Inc (www.mobilerobots.com). Each robot has placed on top a set of infrared markers whose centroid coincides with the middle point of the wheel axis. The position and orientation of each robot are obtained by an OptiTrack vision system. The vision system consists of 12 Flex 13 cameras manufactured by Natural Point and the software Motive: Tracker [version 1.0, eference http://optitrack.com/products/motive/tracker/]. The control strategy is computed in Visual C++ using the Aria libraries designed for communication and management of the AmigoBot robots.

Figure 7.

Experimental platform.

The point α_i to be controlled is located 0.15 m ahead the middle point of the wheel axis of each robot. The formation graph employed in the experiment is shown in Figure 8. The parameters used in the experiment are k_m = 1, k_f = 2, and k_c = 3. The desired marching trajectory is a Lemniscate of Gerono given by $m(t)={\left[\cos (2\pi t/T),0.5\text{sin}(4\pi t/T)\right]}^T$ , with a period of T = 60 s. The static position vectors are given by $c_{43}={\left[-1.2\text{sin}(\pi /3),-1.2\cos (\pi /3)\right]}^T$ , $c_{42}={\left[-1.2\text{sin}(\pi /3),1.2\cos (\pi /3)\right]}^T$ , $c_{32}={\left[0,1.2\right]}^T$ , and $c_{23}={\left[0,-1.2\right]}^T$ . The scaling factor was set to μ = 1.

Figure 8.

Formation graph for the experiment.

• Remark 1: The physical dimensions of the work area and the AmigoBot mobile robots are, respectively, 4.4 × 3.7 m and 0.28 × 0.33 m. Since we attempt to control the front points α_i , the minimum distance required between agents is d > 0.66 m. If we activated the repulsive vector fields, the motion of the agents when trying to avoid collision can easily move out of the work area and the experiment cannot continue. Unfortunately, due to this reason, we are forced to disable the repulsive vector fields in order to perform the experiment.

Figure 9 shows a comparison between a numerical simulation and a real-time experiment of the motion of the agents in the plane. Simulation results are dashed lines and experimental results are solid lines. The initial position of the agents are indicated with an x and positions in times $t=0.1,15,29,43$ and 57 s are represented with a circle o. As can be seen, the simulation results and the experimental results are quite similar. The main leader follows the desired trajectory, the secondary leaders achieve a time-varying formation, and the follower converges to the convex hull formed by the leaders. Figure 10 shows the posture of the agents in different times of the trajectories recorded by a camera. Every robot (point α_i ) converge to the desired position.

Figure 9.

Trajectories of the agents in the plane (experiment).

Figure 10.

Trajectories of the agents in different times.

Figure 11(a) and (b) shows the errors of the follower and the leaders, respectively, of both the numerical simulation and real-time experiment. Such errors converge to 0. The required control signals are shown in Figure 12(a) and (b).

Figure 11.

Errors of the agents of the system.

Figure 12.

Controls of the agents of the system.

Conclusions and future work

This article presents a time-varying version of the containment problem with collision avoidance for multiagent systems, where the agents are differential-drive mobile robots. We propose a decentralized control strategy which ensures that the followers converge to the convex hull formed by the leaders, while the latter converge to a desired marching trajectory, moving in a time-varying formation. Furthermore, collision avoidance between agents is achieved. We use formation graphs to represent interactions between agents. As shown in numerical simulations and real-time experiments, the goals are achieved and system errors converge to 0.

As future work, it is proposed to control the midpoint of wheel axis of the differential-drive mobile robots. It is also proposed to include a strategy for obstacle avoidance. It is also intended to conduct further experiments considering a time-varying scaling factor placing the robots so that there is a risk of collision between them.