Non-Collision Conditions in Multi-Agent Virtual Leader-Based Formation Control

Abstract

Formation control is one of the most important issues of group coordination for multi-agent robots systems. Some schemes are based on the leader-followers approach where some robots are considered as group leaders which influence the group behaviour. In this work, we address a formation strategy using a virtual leader which has communication with the rest of the follower robots, considered as omnidirectional robots. The virtual leader approach presents advantages such as analysis simplification and fewer sensing requirements in the control law implementation. The formation control is based on attractive potential functions only. The control law guarantees the convergence to the desired formation but, in principle, does not avoid inter-agent collisions. A set of necessary and sufficient non-collision conditions based on the explicit solution of the closed-loop system is derived. The conditions allow concluding from the initial conditions whether or not the agents will collide. The results are extended to the case of unicycle-type robots.

Keywords

Formation control Multi-agent robots systems Artificial Potential Functions Non-collision Unicycles

1. Introduction

Multi-agent robots systems (MARS) are understood as groups of autonomous robots (called agents) coordinated to achieve cooperative tasks. The range of applications includes toxic residue cleaning, transportation and manipulation of large objects, exploration, search and rescue, and simulation of biological entities' behaviours [1]. The research areas of MARS encompass motion coordination, task assignment, communications, sensor networks, etc. [2]. Formation control is an important sub-area of motion coordination. It refers both to omnidirectional and mobile wheeled robots. The goal is to guarantee the convergence to a particular formation pattern avoiding inter-agent collision at the same time [3, 11]. The problem is complex because it is assumed that the agents have a limited sensing capacity and no robot possesses global information about the position of all robots. Therefore, the control strategies are decentralized and the main intention is to achieve the desired global behaviours through local interactions [13].

Different schemes of formation control exist [4, 5]. Some schemes consider all agents with the same capacities and achieve formation patterns, without a specific position, following some simple behaviour rules such as neighbours-rules, swarm intelligence, physics-based techniques, etc. [5, 6, 7, 8]. Other formation schemes are based on formation graphs which represent specific inter-agent communication channels to achieve a specific geometric pattern [9, 10, 29]. Some tools of graph theory and linear systems are used to prove the convergence to the desired formation for special formation graphs such as the complete formation graph (i.e., where every agent measures the position of the rest of the group [18]), cyclic pursuit [13], undirected graphs [21], leaders-followers graphs (i.e., where all robots have communication with one or more group leaders [11, 12]), etc. In this paper, we utilize a formation graph where one agent is considered as a virtual leader. Some advantages of the use of virtual leaders are the simplification of the analysis and best performance of the closed-loop system. Some important works about virtual leaders are [14, 15, 16].

The non-collision problem is generally solved using the negative gradient of an artificial potential function [17]. In the standard methodology, this function is the sum of Attractive (APF) and Repulsive Potential Functions (RPF). The APF are designed according to the desired inter-agent distances of a particular formation, whereas RPF serve to create repulsive forces to avoid collisions. In decentralized strategies, these RPF appear only when the minimum allowed distance between agents is violated. A formation control law based on APF only, guarantees the convergence to the desired formation, but inter-robot collisions could occur for some initial conditions. A formation control law based on the sum of APF and RPF guarantees non-collision, but does not ensure convergence to the desired formation for all initial conditions. This occurs because the robots can be trapped in undesired equilibrium points. The analysis to calculate these equilibria and the trajectories which do not converge to the desired formation is very complex [18]. A complete survey of convergence and collision avoidance based on APF and RPF was presented in our previous work [28].

Some research on the analysis of non-collision based on repulsive forces also exists. In [18], it is shown that the undesired equilibria are unstable for a complete graph formation strategy, however, they are not explicitly calculated. In [19, 20], some “navigation functions” are designed with attractive and repulsive behaviour. However, the RPF are centralized and high-order functions, i.e., every agent needs to be fed back with the position of the rest of agents. The main disadvantages are that the system is no longer decentralized and the approach requires a high computational cost in real-time implementations. In [21], a general form of decentralized RPF approach applied to undirected formation graphs is obtained, showing the complexity of the analysis for the general case. However, the analysis of convergence to the desired formation assumes that the basin of attraction of the undesired equilibria and the set of admissible initial conditions are disjointed. Other attempts to achieve global convergence without collisions in formation control include: hybrid architectures where a high-level supervisor switches momentarily to reactive non-collision strategy [30], the use of small disturbances in order to escape from undesired equilibria which exhibit a saddle point behaviour [31] and the use of discontinuous repulsive vector fields [32]. Despite successful implementations, the repulsive forces are heuristically designed and therefore, formal proof about global convergence are rarely found (for example [33]).

Instead of using the mix of APF and some type of repulsive forces, in this paper a simple formation strategy based on APF only is used. Then, our main result is to obtain necessary and sufficient non-collision conditions based on the explicit solution of the closed-loop system. The main idea is to predict, from the initial positions, whether or not the agents will collide. Doing this, the convergence and the non-collision requirements are satisfied in a subset of initial conditions within the workspace. Preliminary results for the case of another formation strategy for three agents only were reported in [22]. In this paper, the non-collision conditions and their geometric interpretation are generalized for the case of any number of agents formed with respect to a virtual leader. A related result reported in the literature is [13], where non-collision conditions are obtained for the case of point robots formed in a cyclic pursuit graph. Roughly speaking, if the arguments of the polar coordinates of the initial conditions of the robots define a strictly increasing sequence, then the robots will not collide for any time instant.

The paper is organized as follows: Section 2 introduces a formal problem statement. Section 3 describes the formation control strategy for agents, considered as points in plane, using APF; also, convergence to the desired formation is demonstrated. In Section 4, non-collision conditions are derived. The result is extended to the case of unicycle formations in Section 4.1. Section 5 presents numerical simulations. Finally, concluding remarks are offered in Section 6.

2. Problem statement

Denote by N = {R₁,…,R_n}, a set of n agents moving in the plane with positions z_i(t) = [x_i(t), y_i(t)] ^T , i = 1,..,n. The kinematic model of each agent or robot R_i is described by

{\dot{z}}_{i} = u_{i}, i = 1, \dots, n,

(1)

where u_i = [u_i1, u_i2] ^T ∈ ℜ² is the velocity along the X and Y axis of i-th robot. Let N_i denote the subset of positions of the robots which are detectable for R_i. In this paper, the subsets N_i are defined by

\begin{array}{l} N_{i} = {z_{n}}, i = 1, \dots, n - 1 \\ N_{n} = {z_{1}, \dots, z_{n - 1}} \end{array}

(2)

The last agent R_n is considered as the group leader and the rest are follower robots. The agent R_n has more sensing capacities because it can sense the position of all followers. We assume that R_n is virtual, i.e., this agent does not exist as a real robot but can be represented or emulated by a computer. Let c_ji =[h_ji, v_ji] ^T denote a vector which represents the desired position of R_i with respect to R_j in a particular formation. Thus, we define z_i* = f(N_i), i = 1,…,n as the desired relative position of every R_i in the formation given by

z_{i}^{*} = z_{n} + c_{n i}, i = 1, \dots, n - 1

(3)

z_{n}^{*} = \frac{1}{n - 1} \sum_{i = 1}^{n - 1} (z_{i} + c_{i n})

(4)

The desired relative position of the group leader can be considered as a combination of the desired positions of z_n with respect to every follower in the group. The formation strategy using R_n as virtual leader is shown in Fig. 1. This formation can be considered as a star formation centred at the virtual leader. In plain words, the goal of each agent R_i, i = 1,…,n – 1 is to be steered to a relative position c_ni with respect to the virtual leader avoiding collisions.

Figure 1.

Formation Control Strategy using a virtual leader

Note that the positions of robots and the vectors c_ni are defined with respect to a global frame. Other works consider either the desired positions of robots using local frames [24, 25] or the relative distances and orientations between robots [11, 26, 27].

Problem Statement The control goal is to design a control law u_i(t) = g_i(N_i(t)) for every robot R_i, such that lim_t→∞(z_i – z_i^*) = 0, i = 1,…,n and ‖ z_i(t) – z_j(t) ‖ > d, ∀t ≥ 0, i ≠ j, i, j ≠ n where d is the diameter of a circle that circumscribes each robot.

Remark 1. It is important to observe that the collisions between the leader and every follower are not analysed because they do not occur in the physical world. Thus, we only analyse the collisions between followers.

Remark 2. The star-shaped topology shown in Fig. 1 has been chosen because it renders symmetric expressions for the distance between any pair of agents. Another topology rendering the same kind of symmetry is the so-called undirected complete graph [18], where every agent detects the position of the rest of the agents. We have chosen the former topology because it requires less communication channels between agents.

For completeness of the paper, let us introduce the following definition.

Definition 1. The desired relative position of n mobile agents given by (3)-(4) is said to be a closed-formation if

c_{i n} = - c_{n i}, \forall i = 1, \dots, n - 1.

(5)

3. Control strategy

In this section, a formation strategy is presented which ensures the convergence to a desired formation only. The collision problem will be analysed in Section 4. For system (1), local potential functions are defined by

\begin{array}{l} V_{i} = ∥ z_{i} - z_{n} - c_{n i} ∥^{2}, i = 1, \dots, n - 1 \\ V_{n} = \sum_{j = 1}^{n - 1} ∥ z_{n} - z_{j} - c_{j n} ∥^{2} \end{array}

(6)

The functions V_i are positive definite and reach their global minimum (V_i =0) when z_i – z_j= c_ji, i = 1,…,n, j ∈ N_i. Using these functions, we define a control law given by

\begin{array}{l} u_{i} = - \frac{1}{2} k {(\frac{\partial V_{i}}{\partial z_{i}})}^{T}, i = 1, \dots n - 1 \\ u_{n} = - \frac{1}{2 (n - 1)} k {(\frac{\partial V_{n}}{\partial z_{n}})}^{T} \end{array}

(7)

where k > 0 is a design parameter.

Theorem 1. Consider the system (1) and the control law (7). Suppose that k > 0 and the desired formation is closed. Then, in the closed-loop system (1)-(7) the agents converge exponentially to the desired formation, i.e., lim_t→∞(z_i – z_i^*) = 0, i = 1,…,n.

Proof: The closed-loop system (1)-(7) has the form

\dot{z} = k ((M \otimes I_{2}) z + c),

(8)

where z = [z₁,…,z_n] ^T , ⊗ denotes the Kronecker product, I₂ is the 2 × 2 identity, $c = {[c_{n 1}, …, c_{n (n - 1)}, \frac{1}{n - 1} \sum_{i = 1}^{n - 1} c_{i n}]}^{T}$ and

M = [\begin{matrix} - 1 & 0 & 0 & \dots & 0 & 1 \\ 0 & - 1 & 0 & \dots & 0 & 1 \\ ⋮ & ​ & ⋱ & ​ & ​ & ​ \\ 0 & 0 & 0 & \dots & - 1 & 1 \\ \frac{1}{n - 1} & \frac{1}{n - 1} & \frac{1}{n - 1} & \dots & \frac{1}{n - 1} & - 1 \end{matrix}] .

A change of coordinates for the closed-system (8) is defined by

[\begin{matrix} e \\ ϑ \end{matrix}] = (Q \otimes I_{2}) z - c_{q},

(9)

where e = [e₁,..,e_n1]^T, c_q = [c_n1,c_n2,…,c_n(n–1),0] ^T and

Q = [\begin{matrix} 1 & 0 & 0 & \dots & 0 & - 1 \\ 0 & 1 & 0 & \dots & 0 & - 1 \\ ⋮ & ​ & ⋱ & ​ & ​ & ​ \\ 0 & 0 & 0 & \dots & 1 & - 1 \\ \frac{1}{n - 1} & \frac{1}{n - 1} & \frac{1}{n - 1} & \dots & \frac{1}{n - 1} & 1 \end{matrix}] .

We observe that e_i = z_i – z_i^*, i = 1,…,n – 1 are the error coordinates of the first n – 1 i agents. The variable ϑ does not have a physical interpretation but serves to complete the change of coordinates.

The dynamics of the coordinates (9) are given by

[\begin{matrix} \dot{e} \\ \dot{ϑ} \end{matrix}] = k {([\begin{matrix} \tilde{M} & 0 \\ 0 & 0 \end{matrix}] \otimes I_{2}) e + {\tilde{c}}_{q}},

(10)

where c˜_q ∈ ℜ^n×1 and M˜ ∈ ℜ^{(n–1)(n–1)} have the form

\begin{array}{l} \tilde{M} = \frac{1}{n - 1} [\begin{matrix} - n & - 1 & - 1 & \dots & - 1 & - 1 \\ - 1 & - n & - 1 & \dots & - 1 & - 1 \\ ⋮ & ​ & ⋱ & ​ & ​ & ⋮ \\ - 1 & - 1 & - 1 & \dots & - n & - 1 \\ - 1 & - 1 & - 1 & \dots & - 1 & - n \end{matrix}], \\ {\tilde{c}}_{q} = \frac{1}{n - 1} {[- \sum_{i = 1}^{n - 1} (c_{i n} + c_{n i}), \dots, \sum_{i = 1}^{n - 1} (c_{i n} + c_{n i})]}^{T} . \end{array}

Due to condition (5), c˜_q = 0. Then, the dynamics of the new coordinates are given by

\begin{array}{l} \dot{e} = k (\tilde{M} \otimes I_{2}) e \\ \dot{ϑ} = 0. \end{array}

(11)

We observe that $\dot{ϑ} = 0$ and the dynamics of the coordinates (10) are reduced to dimension n – 1. The equilibrium point of the system (11) is e = 0. The matrix M˜ is clearly Hurwitz because it has n – 2 eigenvalues equal to −1 and one eigenvalue equal to −2. Therefore, the trajectories of e_i, i = 1,…,n – 1 converge exponentially to zero. This means that the first n – 1 agents converge to the desired relative position in the formation. Now, let us analyse the position of z_n at the equilibrium point. Fig. 2 shows the positions of all agents when e_i, i = 1,…,n – 1 converge to zero. Due to condition (5), we deduce that r_jn=–c_nj= c_jn, j = 1,…,n – 1. Thus, e_i = 0, i = 1,…,n – 1 implies that z_n = z_n*. Then, we conclude that all agents converge to the desired formation.

Figure 2.

Positions of agents at equilibrium point.

Remark 3. Note that M is almost identical to the so-called Laplacian Matrix [21] of the formation given by (3)-(4). The only difference is the n – th row, due to the factor $\frac{1}{2 (n - 1)}$ in the last expression of (7).

4. Non-collision conditions

The control law (7) guarantees that all agents converge exponentially to the desired formation but inter-agent collisions can occur starting from some initial positions. Collision-free trajectories between follower robots are defined by the condition

f_{i j} (t) = {‖ z_{i} (t) - z_{j} (t) ‖}^{2} > d^{2}, \forall t > 0, i \neq j, i, j \neq n

(12)

where d is the diameter of a circle that circumscribes each robot.

In order to characterize collision-free trajectories, the first step is to obtain an analytical expression of the solution of the closed-loop system (8). Such expression is provided by the next proposition.

Proposition 1. Consider the closed-loop system (8). The trajectories of the agents are given by

z (t) = \frac{1}{2 (n - 1)} (B \otimes I_{2}) z_{0} + \bar{c}

(13)

where z₀ = [z₁₀,…,z_n0] ^T with z_i0 = z_i(0) represents the agents' initial conditions,

\begin{array}{l} B = [\begin{matrix} δ (t) & s_{2}^{2} & s_{2}^{2} & \dots & s_{2}^{2} & (n - 1) s_{1} s_{2} \\ s_{2}^{2} & δ (t) & s_{2}^{2} & \dots & s_{2}^{2} & (n - 1) s_{1} s_{2} \\ ⋮ & ​ & ⋱ & ​ & ​ & ⋮ \\ s_{2}^{2} & s_{2}^{2} & s_{2}^{2} & \dots & δ (t) & (n - 1) s_{1} s_{2} \\ s_{1} s_{2} & s_{1} s_{2} & s_{1} s_{2} & \dots & s_{1} s_{2} & (n - 1) (2 - s_{1} s_{2}) \end{matrix}] \\ \bar{c} = [\begin{matrix} (2 (n - 2) s_{2} + s_{1} s_{2}) c_{n 1} + s_{2}^{2} \sum_{\begin{array}{l} j \neq 1 \\ j \neq n \end{array}} c_{j n} \\ (2 (n - 2) s_{2} + s_{1} s_{2}) c_{n 2} + s_{2}^{2} \sum_{\begin{array}{l} j \neq 2 \\ j \neq n \end{array}} c_{j n} \\ ⋮ \\ (2 (n - 2) s_{2} + s_{1} s_{2}) c_{n (n - 1)} + s_{2}^{2} \sum_{\begin{array}{l} j \neq n - 1 \\ j \neq n \end{array}} c_{j n} \\ s_{1} s_{2} \sum_{j \neq n} c_{j n} \end{matrix}] \end{array}

where s₁(t) = 1 + e^−kt, s₂(t) = 1 – e^−kt, δ(t) = 2(n – 3)e^−kt +s²₁.

Proof: A change of coordinates for the closed-loop system (8) is defined by

p = (T \otimes I_{2}) z - c_{q},

(14)

where

T = [\begin{matrix} 1 & 0 & 0 & \dots & 0 & - 1 \\ 0 & 1 & 0 & \dots & 0 & - 1 \\ ⋮ & ​ & ⋱ & ​ & ​ & ⋮ \\ 0 & 0 & 0 & \dots & 1 & - 1 \\ 0 & 0 & 0 & \dots & 0 & 1 \end{matrix}] .

The dynamics in the new coordinates are

\dot{p} = k (({\tilde{A}}_{t} \otimes I_{2}) p + {\hat{c}}_{t}),

(15)

where

{\tilde{A}}_{t} = \frac{1}{n - 1} [\begin{matrix} - n & - 1 & - 1 & \dots & - 1 & 0 \\ - 1 & - n & - 1 & \dots & - 1 & 0 \\ ⋮ & ​ & ⋱ & ​ & ​ & ⋮ \\ - 1 & - 1 & - 1 & \dots & - n & 0 \\ 1 & 1 & 1 & \dots & 1 & 0 \end{matrix}],

{\hat{c}}_{t} = \frac{1}{n - 1} [\begin{matrix} - \sum_{i = 1}^{n - 1} (c_{i n} + c_{n i}) \\ ⋮ \\ \sum_{i = 1}^{n - 1} (c_{i n} + c_{n i}) \end{matrix}] .

Due to condition (5), ĉ_t = 0. Then, the dynamics of the new coordinates are given by

\dot{p} = k ({\tilde{A}}_{t} \otimes I_{2}) p .

(16)

We can diagonalize the matrix Ã_t⊗I₂ through the following similarity transformation

(D \otimes I_{2}) = (P^{- 1} \otimes I_{2}) ({\tilde{A}}_{t} \otimes I_{2}) (P \otimes I_{2}),

(17)

where

\begin{array}{l} D = [\begin{matrix} - 2 k & 0 & 0 & \dots & 0 & 0 \\ 0 & - k & 0 & \dots & 0 & 0 \\ ⋮ & ​ & ⋱ & ​ & ⋮ & ​ \\ 0 & 0 & 0 & \dots & - k & 0 \\ 0 & 0 & 0 & \dots & 0 & 0 \end{matrix}], \\ P = [\begin{matrix} 2 & 1 & 0 & 0 & 0 & \dots & 0 & 0 \\ 2 & - (n - 2) & - 1 & - 1 & - 1 & \dots & - 1 & 0 \\ 2 & 1 & 1 & 0 & 0 & \dots & 0 & 0 \\ 2 & 1 & 0 & 1 & 0 & \dots & 0 & 0 \\ ​ & ​ & ​ & ​ & ⋱ & ​ & ​ & ​ \\ 2 & 1 & 0 & 0 & 0 & \dots & 1 & 0 \\ - 1 & 0 & 0 & 0 & 0 & \dots & 0 & 1 \end{matrix}] . \end{array}

Then, the solution of (15) is given by

p (t) = (P E (t) P^{- 1} \otimes I_{2}) p_{0},

(18)

where p₀= p(0) is the vector of initial conditions of coordinates p and

E (t) = [\begin{matrix} e^{- 2 k t} & 0 & 0 & \dots & 0 & 0 \\ 0 & e^{- k t} & 0 & \dots & 0 & 0 \\ ⋮ & ​ & ⋱ & ​ & ⋮ & ​ \\ 0 & 0 & 0 & \dots & e^{- k t} & 0 \\ 0 & 0 & 0 & \dots & 0 & 1 \end{matrix}] .

After some algebra, the solution in original coordinates can be written as in (13).

Replacing the explicit solution of two follower agents in the condition of collision-free trajectories (12), we obtain

\begin{array}{c} z_{i} (t) - z_{j} (t) = s_{2} (t) (z_{j 0} - z_{i 0}) - (z_{j 0} - z_{i 0}) \\ + s_{2} (t) (c_{j n} + c_{n i}), \forall i, j \neq n, i \neq j \end{array}

(19)

Recalling that s₂ = 1 – e^−kt and defining a_ji = c_jn + c_ni, the function f_ij(t) in condition (12) for the case of two followers can be written as

\begin{array}{l} f_{i j} (t) = s_{2}^{2} (t) {‖ {\hat{z}}_{i 0} - z_{i 0} ‖}^{2} \\ - 2 s_{2} (t) {({\hat{z}}_{i 0} - z_{i 0})}^{T} (z_{j 0} - z_{i 0}) + {‖ z_{j 0} - z_{i 0} ‖}^{2} \end{array}

(20)

where ẑ _i0 = z_j0 + a_ji, ∀i, j = 1,….,n – 1, i ≠ j is th e desired relative positions of R with respect to R_j at t = 0. Using this notation, we establish our main result.

Theorem 2. Consider the dynamics of two agents R_i and R_j, i, j = 1,…,n – 1, i ≠ j of the closed-loop system (1)-(7) and suppose that

k > 0

‖a_ji‖² > d², i ≠ j

‖z_i0 – z_j0‖² > d², i ≠ j

Then, anyone of the following three conditions is sufficient to guarantee non-collision between the i-th and j-th agents, i.e., f_ij(t) > d², ∀t > 0: i)

(ẑ _i0 – z_i0) ^T (z_j0 – z_i0) ≤ 0.

ii)

(ẑ _i0 – z_i0) ^T (z_j0 – z_i0) ≤ ‖ẑ_i0 – z_i0‖².

iii)

‖ẑ_i0 – z_i0‖² > (ẑ_i0 – z_i0) ^T (z_j0 – z_i0) > 0 and

φ_{j i} > d^{2}

(21)

where $φ_{j i} = {‖ z_{j 0} - z_{i 0} ‖}^{2} - \frac{{({({\hat{z}}_{i 0} - z_{i 0})}^{T} (z_{j 0} - z_{i 0}))}^{2}}{{‖ {\hat{z}}_{i 0} - z_{i 0} ‖}^{2}}$ . Moreover, if f_ij(t) > d² then necessarily one of the conditions i)-iii) is satisfied.

Remark 4. Hypothesis 2) means that the desired distance between agent R_i and R_j must be greater than d. Hypothesis 3) means that agents do not collide at t = 0.

Proof of Theorem 2: (sufficiency) Note that the function s₂(t) ∈ [0,1). Therefore, f_i = f_ij(0) = ‖z_j0 – z_i0‖² and f_f = lim_i→∞ f_ij(t) = ‖a_ji‖². By hypothesis 2) and 3) f_i, f_f > d². The derivative of f_ij(t) is given by

\frac{d}{d t} f_{i j} (t) = 2 k e^{- k t} η (t),

(22)

where η(t) = ‖ẑ_i0 – z_i0‖²s(t) –(ẑ_i0 – z_i0) ^T (z_i0 – z_i0). The derivative of f_ij(t) vanishes only when η(t) = 0.

If (ẑ_i0 – z_i0) ^T (z_j0 – z_i0) ≤ 0, then η(t) is positive and f_ij(t) is monotonously increasing, therefore, f_ij(t) > d², ∀t ≥ 0. Fig. 3 shows the initial position of the agents in this case.

ii)

If (ẑ_i0 – z_i0) ^T (z_j0 – z_i0) ≥ ‖ẑ_i0 – z_i0‖², then η(t) never crosses by zero and we conclude that f_ij(t) is monotonously decreasing. Therefore, f_i > f_f and f_f > d² implies that f_ij(t) > d², ∀t ≥ 0. Fig. 4 shows the initial positions of the agents in this case.

iii)

If ‖ẑ_i0 – z_i0‖² > (ẑ_i0 – z_i0] ^T (z_j0 – z_i0) > 0, then η(t) is negative, crosses by zero at time instant t_α and, after that, it is positive. Calculating t_α we obtain

t_{α} = - \frac{1}{k} l n (1 - \frac{{({\hat{z}}_{i 0} - z_{i 0})}^{T} (z_{j 0} - z_{i 0})}{{‖ {\hat{z}}_{i 0} - z_{i 0} ‖}^{2}})

(23)

Evaluating

f_{i j} (t_{α}) = {‖ z_{j 0} - z_{i 0} ‖}^{2} - \frac{{({({\hat{z}}_{i 0} - z_{i 0})}^{T} (z_{j 0} - z_{i 0}))}^{2}}{{‖ {\hat{z}}_{i 0} - z_{i 0} ‖}^{2}} = φ_{j i} .

By condition (21), it is satisfied that f_ij(t) > d² when η(t_α) = 0. The distance between agents R_i and R_j decreases up to time instant t_α. After that, the distance becomes increasing ∀t > t_α. Therefore f_ij(t) > d², ∀t ≥ 0. Fig. 5 shows the initial positions of the agents in this case.

Figure 3.

Agents' positions in space in case (ẑ_i0 – z_i0) ^T (z_j0 – z_i0) ≤ 0

Figure 4.

Agents' positions in space in case (ẑ_i0 – z_i0) ^T (z_j0 – z_i0) ≥ ‖ẑ_i0 – z_i0‖²

Figure 5.

Agents' positions in space in case ‖ẑ_i0 – z_i0‖² > (ẑ_i0 – z_i0) ^T (z_j0 – z_i0) > 0

(Necessity). It is necessary to prove that if f_ij(t) > d² then necessarily i), ii) or iii) hold. Previously, we have shown that f_i, f_f > d² and that $\frac{d}{d t} f_{i j} (t)$ vanishes only when η(t) = 0. Because s₂(t) is monotonously increasing, the behaviour of f_ij(t) falls necessarily within one of the following cases:

f_ij(t) is monotonously increasing because η(t) never crosses by zero and remains on the positive interval. This occurs only when condition i) is satisfied.

f_ij(t) is monotonously decreasing because η(t) never crosses by zero and remains on the negative interval. This occurs only when condition ii) is satisfied.

f_ij(t) is decreasing, crosses by zero at time instant t_α and after that, becomes increasing. This occurs only when condition iii) is satisfied.

Remark 5. The distance between the leader and the i-th follower, i.e., ‖z_i(t) – z_n(t)‖², i = 1,…,n – 1 is given by

\begin{array}{l} f_{i n} (t) = {‖ z_{i} - z_{n} ‖}^{2} = e^{- 4 k t} {‖ b_{2} ‖}^{2} + 2 e^{- 3 k t} b_{1}^{T} b_{2} \\ + e^{- 2 k t} ({‖ b_{1} ‖}^{2} + 2 b_{2}^{T} a_{n i}) + 2 e^{- k t} b_{1}^{T} a_{n i} + {‖ a_{n i} ‖}^{2} \end{array}

(24)

where $b_{1} = \frac{n - 2}{n - 1} (z_{i 0} + a_{i n}) - \frac{1}{n - 1} \sum_{\begin{array}{l} j \neq i \\ j \neq n \end{array}} (z_{j 0} + a_{j n})$ and $b_{2} = \frac{1}{n - 1} (z_{i 0} + a_{i n}) + \frac{1}{n - 1} \sum_{\begin{array}{l} j \neq i \\ j \neq n \end{array}} (z_{j 0} + a_{j n}) - z_{n 0}$ . The analysis of the non-collision conditions for the case of the leader and a follower is more complex, but it is not studied because these collisions do not occur in the physical world. However, it is an issue for further theoretical research.

Remark 6. Another choice of formation graph which allows a simple explicit solution of the closed-loop system is the so-called complete graph, where each agent detects the position of all the others agents. This solution produces symmetric expressions for the distances between agents and hence allows obtaining a result similar to Theorem 2. This result has been reported for the case of three robots only in [22].

4.1 Extension to formation control of unicycles

The analysis of Section 4 can be adapted to the case of unicycles. The kinematic model of each agent R_i, as shown in Fig. 6, is given by

Figure 6.

Kinematic model of unicycles.

[\begin{matrix} {\dot{x}}_{i} \\ {\dot{y}}_{i} \\ {\dot{θ}}_{i} \end{matrix}] = [\begin{matrix} c o s θ_{i} & 0 \\ s i n θ_{i} & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} v_{i} \\ w_{i} \end{matrix}], i = 1, \dots, n

(25)

where v_i is the longitudinal velocity of the midpoint of the wheels axis, w_i the angular velocity of the robot. It is known [23] that the dynamical system (25) cannot be stabilized by any continuous and time-invariant control law. Instead, consider the coordinates α _i = (p_i, q_i) shown in Fig. 6. The coordinates α_i are given by

α_{i} = [\begin{matrix} p_{i} \\ q_{i} \end{matrix}] = [\begin{matrix} x_{i} + ℓ c o s (θ_{i}) \\ y_{i} + ℓ s i n (θ_{i}) \end{matrix}] .

(26)

The idea of controlling coordinates α _i instead of the centre of the wheels axis is frequently found in the mobile robot literature in order to avoid singularities in the control law [11]. The kinematics of (26) is given by

{\dot{α}}_{i} = A_{i} (θ_{i}) [\begin{matrix} v_{i} \\ w_{i} \end{matrix}], i = 1, \dots, n

(27)

where

A_{i} (θ_{i}) = [\begin{matrix} c o s θ_{i} & - ℓ s i n θ_{i} \\ s i n θ_{i} & ℓ c o s θ_{i} \end{matrix}]

(28)

is the so-called decoupling matrix of every R_i. The decoupling matrix is non-singular because det(A(θ _i )) = ℓ ≠ 0. Then, it is possible to impose on α _i any desired dynamics using the control law

[\begin{matrix} v_{i} \\ w_{i} \end{matrix}] = A^{- 1} (θ_{i}) {\dot{α}}_{i d}, i = 1, \dots, n

(29)

where $A^{- 1} (θ_{i}) = [\begin{matrix} c o s θ_{i} & s i n θ_{i} \\ - \frac{s i n θ_{i}}{ℓ} & \frac{c o s θ_{i}}{ℓ} \end{matrix}]$ and ${\dot{α}}_{i d}$ is the desired dynamics of coordinates α _i .

Following the control strategy of Section 3, the desired inter-agent relative positions for the n unicycles are established by

α_{i}^{*} = α_{n} + c_{n i}, i = 1, \dots, n - 1

(30)

α_{n}^{*} = \frac{1}{n - 1} \sum_{i = 1}^{n - 1} (α_{i} + c_{i n})

(31)

Then, the formation control strategy is given by

\begin{array}{l} [\begin{matrix} v_{i} \\ w_{i} \end{matrix}] = - \frac{1}{2} k A^{- 1} (θ_{i}) {(\frac{\partial {\tilde{V}}_{i}}{\partial α_{i}})}^{T}, i = 1, \dots n - 1 \\ [\begin{matrix} v_{n} \\ w_{n} \end{matrix}] = - \frac{1}{2 (n - 1)} k A^{- 1} (θ_{n}) {(\frac{\partial {\tilde{V}}_{n}}{\partial α_{n}})}^{T} \end{array}

(32)

where the functions V˜_i are similar to functions V_i, but dependent on coordinates α _i instead of coordinates z_i.

Corollary 1. Consider the system (25) and the control law (32). Suppose that k > 0. Then, in the closed-loop system (25)-(32), the agents converge to the desired formation, i.e., lim _t→∞ (α_i – α_i^*) = 0.

Remark 7. The control law (32) steers the coordinates α _i to a desired position. However, the angles θ_i remain uncontrolled. These angles do not converge i to any specific value. Thus, the control law (32) is to be considered as a formation control without orientation.

5. Numerical simulations

Figures 7 and 8 show a simulation for the closed-loop system (1)-(7) for n = 4, d = 2 and k = 1. The desired relative distances are given by c₄₁ = [–5,0], c₄₂ = [0,5] and c₄₃ = [5 0]. The initial conditions are given by z₁₀ = [3,4], z₂₀=[4,–2], z₃₀= [–3,0] and z₄₀ = [–3,–5]. In Fig. 8, d_ij is the distance between the follower agents i and j. In order to check the non-collision conditions given by Theorem 2, three couples of robots need to be considered (from the three follower robots); namely [R₁,R₂], [R₁,R₃] and [R₂,R₃]. Following the calculations of Theorem 2 we obtain the results of Table 1 where τ _ij = (ẑ_i0 – z_i0) ^T (z_j0 – z_i0). We observe that all pairs of agents satisfy case iii) of Theorem 2. Finding φ_ij and t_α for every pair of agents we obtain the values of Table 2.

Table 1.

Checking the non-collision conditions on simulation.

Pair (R_i, R_j)	a_ji	τ_ij	‖ẑ_i0 – z_i0‖²
[1,2]	[–5,–5]	62	137
v[1,3]	[–10,0]	112	272
[2,3]	[–5,5]	98	193

Table 2.

Checking the condition iii) on simulation.

Pair (R_i, R_j)	φ_ji	t_α
[1,2]	8.94	0.6025
[1,3]	5.88	0.5306
[2,3]	3.23	0.7088

Figure 7.

Trajectories of the agents in plane.

Figure 8.

Inter-robot distances.

We readily check that φ₁₂, φ₁₃ > d². Therefore, the pairs of agents [R₁,R₂] and [R₁,R₃] do not collide. In Fig. 8, the distances d₁₂ and d₁₃ decrease to some value greater than 4 at their respective time instant t_α and then they increase up to the desired value. We observe that the pair [R₂,R₃] collides because φ₂₃ < d² at time t_α = 0.7088. The distance d₂₃ in Fig. 8 decreases to a value less than 4. Fig. 7a shows the initial positions of the agents. Fig. 7b shows the trajectory of agents at time of maximal proximity between [R₁,R₃]. Fig. 7c shows the time of collision of agents [R₂,R₃]. Finally, Fig. 7d shows the position of agents when they achieve the desired formation.

6. Conclusions

An analysis of non-collision conditions of a simple formation control strategy for multi-agent robots is presented. The formation strategy is based on a virtual leader. This virtual leader can be emulated by a computer or another control device and serves for the communication between followers. The formation control is based on attractive potential functions which only ensure the convergence to the desired formation, however, agents might still collide. To ensure collision-free trajectories, a set of necessary and sufficient conditions, based on the exact solution of the closed-loop system, is presented. The main idea is to predict, from the initial conditions, whether or not the agents will collide. The virtual leader serves to calculate and simplify the non-collision conditions. The main result has an application in experimental work where the analysis of these conditions can be achieved off-line and the robots can be protected from undesired shocks. The results are extended to the case of unicycle-type robots.

Footnotes

7. Acknowledgments

The first author acknowledges financial support from UIA and CONACyT, Mexico.

References

Cao

Y. U.

Fukunaga

A.S.

Kahng

A.B.

, Cooperative mobile robotics: Antecedents and directions, Autonomous Robots, vol. 4, no. 1, pp. 34–46, 1997.

Arai

Pagello

Parker

L.E.

, Guest Editorial Advances in Multirobot systems, IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 655–661, 2002.

Chen

Y. Q.

Wang

, Formation control: A Review and a New Consideration, International Conference on Intelligent Robots and Systems, pp. 3181–3186, 2005.

Yamaguchi

, A distributed motion coordination strategy for multiple nonholonomic mobile robots in cooperative hunting operations, Robotics and Autonomous Systems, vol. 43, no. 1, pp. 257–282, 2003.

Balch

Arkin

R.C.

, Behavior-based formation control for multirobot teams, IEEE Transactions on Robotics and Automation, vol. 14, no. 3, pp. 926–939, 1998.

Reynolds

, Flocks, birds, and schools: A distributed behavioral model, Comput. Graphics, vol. 21, no. 1, pp. 25–34, 1987.

Fredslund

Mataric

M.J.

, General Algorithm for Robot Formations Using Local Sensing and Minimal Communication, IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 837–846, 2002.

Spears

W. M.

Spears

D.F.

Hamann

J.C.

Heil

, Distributed, Physics-Based Control of Swarms of Vehicles, Autonomous Robots, vol. 17, no. 1, pp. 137–162, 2004.

Desai

J.P.

, A Graph Theoretic Approach for Modeling Mobile Robot Team Formations, Journal of Robotic Systems, vol. 19, no. 11, pp. 511–525, 2002.

10.

Fax

J.A.

Murray

R.M.

, Information Flow and Cooperative Control of Vehicle Formations, IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1465–1476, 2004.

11.

Desai

J.P.

Ostrowski

J.P.

Kumar

, Modeling and control of formations of nonholonomic mobile robots, IEEE Transactions on Robotics and Automation, vol. 6, no. 17, pp. 905–908, 2001.

12.

Tanner

H.G.

Pappas

G.J.

and Kumar

, Leader-to-Formation Stability, IEEE Transactions on Robotics and Automation, vol. 20, no. 3, pp. 443–455, 2004.

13.

Lin

Broucke

Francis

, Local Control Strategies for Groups of Mobile Autonomous Agents, IEEE Transactions on Automatic Control, vol. 49, no. 4, pp. 622–629, 2004.

14.

Egerstedt

, and Stotsky

, Control of mobile platforms using a virtual vehicle approach, IEEE Transactions on Automatic Control, vol. 46, no. 1, pp. 1777–1782, 2001.

15.

Smith

T. R.

Mann

H.H.

, and Leonard

N.E.

, Orientation control of multiple underwater vehicles, IEEE Conference on Decision and Control, pp. 4598–4603, 2001.

16.

Leonard

N.E.

Fiorelli

, Virtual Leaders, Artificial Potentials and Coordinated Control of Groups, IEEE Conference on Decision and Control, pp. 2968–2973, 2001.

17.

Rimon

and Koditschek

D.E.

, Exact robot navigation using artificial potential functions, IEEE Transactions on Robotics and Automation, vol. 8, no. 5, pp. 501–518, 1992.

18.

K.D.

, Formation control of mobile agents using local potential functions, American Control Conference, pp. 2148–2153, 2006.

19.

Tanner

H.G.

Kumar

, Towards Decentralization of Multi-robot Navigation Functions, IEEE Conference on Robotics and Automation, pp. 4132–4137, 2005.

20.

Dimarogonas

D.V.

Loizou

S.G.

Kyriakopoulos

K.J.

Zavlanos

M.M.

, A feedback stabilization and collision avoidance scheme for multiple independent non-point agents, Automatica, vol. 42, no. 1, pp. 229–243, 2006.

21.

Dimarogonas

D.V.

Kyriakopoulos

K.J.

, Distributed cooperative control and collision avoidance for multiple kinematic agents, IEEE Conference on Decision and Control, pp. 721–726, 2006.

22.

Hernandez-Martinez

E.G.

Aranda-Bricaire

, Non-Collision Conditions in Multi-agent Robots Formation using Local Potential Functions, IEEE Conference on Robotics and Automation, pp. 3776–3781, 2008.

23.

Brockett

R.W.

, Asymptotic Stability and Feedback Stabilization, In Brockett

R.W.

Millman

R.S.

and Sussmann

H.J.

, Eds., Differential Geometric Control Theory, Birkhauser, 1983.

24.

S.S.

Fua

, Queues and Artificial Potential Trenches for Multirobot Formations, IEEE Transactions on Robotics, vol. 21, no. 4, pp. 646–656, 2005.

25.

K.D.

Pan

, Nonlinear formation control of unicycle-type mobile robots, Robotics and Autonomous Systems, vol. 55, no. 3, pp. 191–204, 2007.

26.

Lin

Francis

Maggiore

, Necessary and Sufficient Graphical Conditions for Formation Control of Unicycles, IEEE Transactions on Automatic Control, vol. 50, no. 1, pp. 121–127, 2005.

27.

Chen

Wang

, Obstacle Avoidance and Role Assignment Algorithms for Robot Formation Control, IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4201–4206, 2007.

28.

Hernandez-Martinez

E.G.

Aranda-Bricaire

, Convergence and Collision Avoidance in Formation Control: A Survey of the Artificial Potential Functions approach, in “Multi-Agent Systems – Modeling, Control, Programming, Simulations and Application”, Alkhateeb

Maghayreh

E. A.

and Doush

I. A.

, Eds., INTECH, pp. 103–126, 2011.

29.

Hernandez-Martinez

E.G.

Aranda-Bricaire

, Decentralized Formation Control of Multi-agent Robot Systems Based on Formation Graphs, Studies in Informatics and Control, vol. 21, no. 1, pp 7–16, 2012.

30.

Xie

Wang

, Leader-following formation control of multiple mobile vehicles, IET Control Theory & Applications, vol. 1 no. 2, pp 545–552, 2007.

31.

Antich

Ortiz

, Extending the potential fields approach to avoid trapping situations, IEEE/RSJ International Conference on Intelligent Robots and Systems, pp 1386–1391, 2005.

32.

Hernandez-Martinez

E.G.

Aranda-Bricaire

, Multi-agent formation control with collision avoidance based on discontinuous vector fields, 35th Annual Conference of the IEEE Industrial Electronics Society, pp 2283–2288, 2009.

33.

Barnes

Fields

Valavanis

, Unmanned ground vehicle swarm formation control using potential fields, IEEE Mediterranean Conference on Control and Automation, 2007.