# A Strategy for Multi-Robot Navigation

Lotfi Beji, Mohamed Anouar El Kamel, Azgal Abichou

► To cite this version:

Lotfi Beji, Mohamed Anouar El Kamel, Azgal Abichou. A Strategy for Multi-Robot Navigation. 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC 2011), Dec 2011, Orlando, United States. pp.4214-4219, 10.1109/CDC.2011.6160369. hal-00653812

HAL Id: hal-00653812

https://hal.science/hal-00653812v1

Submitted on 16 Jan 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A strategy for multi-robot navigation

Lotfi Beji, Mohamed ElKamel and Azgal Abichou

**Abstract**— The paper addresses the problem of trajectory regulation of driftless systems such that a stabilizing control input is assumed exists. The perturbed trajectory depends on a regulation control-input which must be designed such that the system's stability is preserved and some undesirable sets belonging to navigation area must be avoided. For the stability and regulation of a multi-robot system a converging attractive set around the target is constructed and a repulsive set around obstacles is emphasized. Taking into account a communication algorithm agents-agents to agents-target, we prove that the proposed regulation control-input preserves the navigation area invariance property and the system's stability. Simulation results illustrate the effectiveness of the proposed control algorithm.

## I. INTRODUCTION

Research in the field of modelling and control of multi-vehicle formations has made tremendous strides during the past few decades. Interest in multi-vehicle formations and their control has increased because of the many possible applications in military as well as civil fields. The study of robot formation control, inspired from swarm evolution in nature, began from the industry and military worlds with the idea of using multiple small vehicles instead of one big one. Teams of inexpensive robots, performing co-operative tasks, may prove to be more cost and energy-effective than a single one. They are, in addition, capable of achieving a mission more efficiently. Using formations of robots includes other advantages such as increased feasibility, accuracy, robustness, flexibility and probability of success. Many studies have focused on the subject, based on different approaches and using different strategies, such as flexible/rigid virtual structure, behavioral approach, leader-follower approach, consensus algorithms and swarm intelligence. Each approach has its advantages and disadvantages, and is used to achieve a specific goal: the rendezvous problem and alignment for wheeled mobile robot formation [7] [20], the cooperative monitoring/surveillance for multiple UAVs formation [10] [24], the delivery time for vehicles in an industrial environment [22] [23]. Such a consensus is designed so that the vehicles update the value of their information states based on those of their neighbors, and the control law is designed so that the information states of all of the vehicles in the formation converge to common objective [1] [14]. The consensuses of navigation are designed to be distributed, assuming only neighbor-to-neighbor interaction

L. Beji is with the IBISC EA 4526 Laboratory, University of Evry, 91020 Evry, France Lotfi.Beji@ibisc.fr

M.A. ElKamel is with the IBISC & LIM Laboratory, La Marsa, Tunisia elkamel@ibisc.univ-evry.fr

A. Abichou is with the LIM Laboratory, La Marsa, Tunisia Azgal.Abichou@ept.rnu.tn

between vehicles [13]. In this area, a special edition which regroups recent results in the field was proposed by Beji and Abichou [19] under the title Modelling and/or Control of Multi-Robot Formations. We resume these contributions: in sharing modelling approaches and control algorithms, the presented results permit to coordinate industrial Automatic Guided Vehicles (AGVs) [23], formation vector control of groups of non-holonomic mobile robots [20], organize inter-space vehicles in platoons, success pattern transformations in swarm systems, recover Micro Air Vehicles (MAVs) in flight [21], move flexible virtual structure shape based on co-leaders [8], and render automatic the short distance in a platoon of vehicles (see [19] and the papers edited in).

In this paper, the regulation control problem for driftless systems is addressed with the consideration of a motivating example for the unicycle like model given in [17]. Using this control model, the time-varying control law can be augmented by a function which preserves the system stability and used to solve the regulation problem. In order to illustrate our main idea, let us note that the trajectories, as solutions of the system in closed-loop, don't take into account restriction caused by obstacles belonging to the robot navigation area. As we try to preserve the system stability, any additional input could just modify solutions in presence of a perturbation. Hence, this additional term will be called regulation control input.

The contents of the paper is as following: in section II we prove the theoretical results for the regulation control-input of driftless systems. The system's trajectory avoiding a set of undesirable points is shown in section III. The multi-robot navigation avoiding a set of obstacles is the subjective of section IV. Section V shows the communication algorithm between agents and the target and the analysis of results. Finally, some comments will conclude the paper.

## II. REGULATION CONTROL-INPUT FOR DRIFTLESS SYSTEMS

Driftless systems are linear in control and take this general form:

$$ \dot{q} = \sum_{i=1}^{m} f_i(q)u_i \quad (1) $$

where $q \in \mathbb{R}^n$ and $u = (u_1, u_2, u_3, ..., u_m)^T \in \mathbb{R}^m$, denote the state and the control input of the system, respectively. One considers the matrix $P$ such that their columns are formed by the function $f_i$. The system (1) is then written in compact form:

$$ \dot{q} = P(q)u \quad (2) $$
In the literature, the stabilization problem of (2) has been studied extensively, including the results of Pomet [17]. Consequently, if the vectors $f_1(0), f_2(0), f_3(0), \dots, f_m(0)$ are linearly independent, then (2) failed the Brokett's necessary conditions [16]. Hence the system cannot be stabilized by a stationary feedback law depending only on the system's states. As an alternative, a time varying control law may guarantee the stability of the system at the origin (see also [18] for a system with drift). For the unicycle like model starting from the fact that a time-varying stabilization law exists and adding a regulation control input, the main result is given in the following theorem.

**Theorem 2.1:** Let $D \subset \mathbb{R}^n$ a set that contains the equilibrium. One considers $q$ a solution of system (2) and $V: \mathbb{R}^n \times [0, +\infty[ \to \mathbb{R}$ the Lyapunov function associated to $u_a(q,t) \in \mathbb{R}^m$, satisfying the following:

$$ \alpha_1(q) \leq V(q,t) \leq \alpha_2(q) \\ \frac{\partial V}{\partial t} + \frac{\partial V}{\partial q} P(q) u_a(q,t) \leq -\alpha_3(q) \quad (3) $$

Such that for $(q,t) \in D \times [0, +\infty[, \alpha_1, \alpha_2$ and $\alpha_3$ are continuous and positive definite functions in $D$. For all given function $\nu: \mathbb{R}^n \to \mathbb{R}$ continuous in $D$, the control law

$$ u = u_a(q,t) + \nu[[(\frac{\partial V}{\partial q})^t P(q)]^t]^{\perp} \quad (4) $$

led to the uniform asymptotic stability of (2) toward a given target.

<figure><img src="image_2.png" /></figure>

**Proof.** As the Lyapunov function $V$ verifies the conditions (3), hence, the control input $u_a$ for system $\dot{q} = P(q)u_a(q,t)$ implies its uniform asymptotic stability. Using the same function $V$ for (2) with the control law (4), under the hypothesis that the inverse of $P(q)P^T(q)$ exists for $q \in \mathbb{R}^n$, we get:

$$ \begin{aligned} \dot{V} &= \frac{\partial V}{\partial t} + \left(\frac{\partial V}{\partial q}\right)^T P(q)u \\ &= \frac{\partial V}{\partial t} + \left(\frac{\partial V}{\partial q}\right)^T P(q)\left[u_a + \nu\left[\left[\left(\frac{\partial V}{\partial q}\right)^T P(q)\right]^T\right]\right]^{\perp} \quad (5) \\ &= \frac{\partial V}{\partial t} + \frac{\partial V}{\partial q} P(q)u_a \end{aligned} $$

which leads to the inequalities in (3). Consequently, for $q$ solution of (2) under the control input (4), the proposed function $V$ verifies (3). As a result, (2) combined with (4) lead to uniform asymptotic stability results.

<figure><img src="image_3.png" /></figure>

If a stationary feedback law exists for (2), we could propose a result similar to Theorem 2.1. In this case, the stabilizing control input takes this form: $u = u_a + \nu\left[\left(\frac{\partial V}{\partial q}\right)^T P(q)\right]^T$.

In order to avoid some undesirable set $O$ taking the system initial conditions in $\mathbb{R}^n \setminus O$, the function $\nu$ is emphasized in the following closed loop form From the literature, the

stability results consists to give the adequate form of $u_a$, this enures the system's stability around fixed positions or trajectories. Here we assume that $u_a$ exists, hence, the equilibrium stability of the unperturbed system is asserted. However, to ensure that the solutions of the controlled system avoid some undesirable set $O$, some conditions on the regulating control input $\nu$ will be defined taking the system initial conditions in $\mathbb{R}^n \setminus O$. The general form of a system in closed loop is reduced to (Theorem 2.1):

$$ \begin{aligned} \dot{q} &= P(q)[u_a(q) + \nu[\left(\frac{\partial V}{\partial q}\right)^t P(q)]^t]^{\perp} \\ &\triangleq \mathcal{X}(q, \nu) \end{aligned} \quad (6) $$

where $q \in \mathbb{R}^n$ and $\nu$ is the regulation control-input.

Note that for the time-varying case, $\mathcal{X}$ is function of $(q, \nu, t)$. We must achieve the same result to a system with a drift term.

### III. AVOIDING A SET OF POINTS

In order to constrain the system's trajectory in closed loop (6), we evoke conditions on $\mathcal{X}(\cdot)$ in avoiding a set of points.

**Proposition 3.1:** Considering system (6) which evolves in $\mathbb{R}^n$. For a continuous $\varphi: E \in \mathbb{R}^n \to F \in \mathbb{R}$ and $A$ as a compact set, one defines the set of points to be avoided:

$$ \mathcal{O} = \{c(c_1, c_2, \dots, c_n) \subset \mathbb{R}^n / \varphi(c) \subset A\} = \varphi^{-1}(A) $$

Let $N$ a submanifold in $\mathbb{R}^n \setminus O$, surrounding $O$ (i.e. if $U$ is in neighborhood of a point of $\partial O$, then $N \cap U \neq \emptyset$). If there exists a function $\nu(q)$ such that

$$ \varphi(q + \tau \mathcal{X}(q, \nu)) \in C_F A \quad (7) $$

for all $\tau \in [0, 1]$ and $q \in N$, we have the following,

1) the integral curve of $\mathcal{X}(q, \nu)$ from $q_0 = q(t_0) \in N$ is included in $N$ for $t$ small enough.

2) If further $\mathcal{X}$ is locally Lipschitzian for $q \in N$, then the integral curve of $\mathcal{X}(q, \nu)$ from $q_0 = q(t_0) \in \mathbb{R}^n \setminus O$ do not leave $\mathbb{R}^n \setminus O$.

<figure><img src="image_4.png" /></figure>

**Proof.** As $\mathbb{R}^n \setminus O$ is an open of $\mathbb{R}^n$, then $\mathbb{R}^n \setminus O$ is a variety, and $N$ is a subvariety of $\mathbb{R}^n \setminus O$ enveloping $O$. Then there exists a function $\nu$ such that the vector field $\mathcal{X}(q, \nu)$ implies $\forall \tau \in [0, 1]$ and $\forall q \in N$

$$ q - c(q) \neq -\tau \mathcal{X}(q, \nu) $$

then

$$ c(q) \neq (1 - \tau)q + \tau(\mathcal{X}(q, \nu) + q) $$

Hence, $c(q)$ does not belong to the segment connecting $q$ to $(\mathcal{X}(q, \nu) + q)$. The fact that

$$ (\mathcal{X}(q, \nu) + q) - q = \mathcal{X}(q, \nu) $$

it implies that the vector field $\mathcal{X}(q, \nu)$ resulting from $q \in N$ do not interfere the set $O$. If further $\forall q \in N, \mathcal{X}(q, \nu) \in T_q N$ then the integral curve $\mathcal{X}(q, \nu)$ with $q_0 \in N$ is continuous and is included in $N$ for $t$ small enough.
Now, if further the vector field $\mathcal{X}(q, \nu)$ is locally Lipschitzian in $N$, the theorem of Cauchy-Lipschitz guarantees that the solution is unique in $N$. Hence, if an integral curve $\gamma(t)$ of $\mathcal{X}(q, \nu)$, from $q(t_0) \in \mathbb{R}^n \setminus \mathcal{O}$, interfere $N$, then $\gamma(t)$, restricted to $N$, will be confused at one of curves resulting from $N$. Thus $\gamma(t)$, for $t$ small enough, remains in $N$ and return after that in $\mathbb{R}^n \setminus \mathcal{O}$, without crossing $\mathcal{O}$ (as $\mathcal{O}$ is enveloped by $N$).

#### IV. AVOIDING A SET OF OBSTACLES

In this section, we generalize the problem of navigation with an environment nonempty of obstacles. Further, it is assumed that these obstacles are sufficiently spaced so that vehicles can pass through them. Recall that each $i^{th}$ obstacle is surrounded by a circumscribed circle, and let $O_i$ denotes its $i^{th}$ center with $p$ the number of obstacles in the navigation space. $L_i$ will design the line joining the center of the target $C$ and $O_i$ where we assume that a fixed reference is attached to the target.

<figure><img src="image_5.png" /><figcaption>Fig. 1. A robot in front of an obstacle.</figcaption></figure>

We introduce the function $\varphi_i$ as following:

$$ \varphi_i: \begin{array}{rcl} E & \mapsto & F = [0, +\infty[ \\ c & \to & \|c - O_i\| \end{array} $$

Consider the $i^{th}$ set to be avoided

$$ O_i = \varphi_i^{-1}(A = [0; r_i]) $$

$r_i = \|\overrightarrow{O_iO_{q_i}}\|$. In avoiding a set of obstacles, our main results are summarized in the following theorem.

**Theorem 4.1:** For system (6), under the regulation control input:

$$ \nu = \sum_{i=1}^{p} \frac{\psi([y - L_i(x)][O_{ix} - C_x])}{\|q - O_{iq}\|} \quad (8) $$

with $\psi(p) = \frac{p}{|p| + 1}$ for all $p \in \mathbb{R}$, the solution $q$ obeys to two properties:

1) $\|q - O_i\| > r_i, \forall q_0 \in \mathbb{R}^n \setminus \bigcup_i O_i$ with $i \in \{1, .., p\}$.

2) $q$ converges asymptotically to an attractive set centered in $C$.

<figure><img src="image_6.png" /></figure>

In order to achieve the result of Theorem 4.1, we construct the following two lemmas.

**Lemma 4.2:** Referring to system (6) with the associated function $V = \frac{1}{2}\|q\|^2$. Let $\beta$ the angle between $\mathcal{X}(q, \nu)$ and $q^{\perp}$, we get

$$ \frac{\nu}{\sqrt{1 + \nu^2}} = \cos(\beta) \quad (9) $$

<figure><img src="image_7.png" /></figure>

**Proof.** For (6) such that $V = \frac{1}{2}\|q\|^2$, we obtain

$$ \dot{q} = -q + \nu q^{\perp} = \mathcal{X}(q, \nu) \quad (10) $$

$\nu$ is given by (8). From

$$ \|\mathcal{X}(q, \nu)\| = \sqrt{1 + \nu^2} \|q\| \quad (11) $$

and the fact that

$$ \begin{aligned} \frac{\langle \mathcal{X}(q, \nu) / q^{\perp} \rangle}{\|q\|^2} &= \nu \\ \Leftrightarrow \frac{\|\mathcal{X}(q, \nu)\|}{\|q\|} \cos \beta &= \nu \end{aligned} \quad (12) $$

where $\beta$ is the angle defined by $\mathcal{X}(q, \nu)$ and $q^{\perp}$. Consequently, from (11) and (12), the following equality holds:

$$ \frac{\nu}{\sqrt{1 + \nu^2}} = \cos(\beta) \quad (13) $$

<figure><img src="image_8.png" /></figure>

**Lemma 4.3:** For system (6) with $V = \frac{1}{2}\|q\|^2$ and $\beta$ as defined above. There exists a set $N$ surrounding $O_i$ such that $\forall q \in N$,

- if $\langle q/O_i^{\perp} \rangle > 0$ then $\mathcal{X}(q, \nu) \sim \varpi(q)q^{\perp}$

- if $\langle q/O_i^{\perp} \rangle < 0$ then $\mathcal{X}(q, \nu) \sim -\varpi(q)q^{\perp}$

with

$$ \varpi(q) = \sqrt{1 + \nu^2} \quad (14) $$

<figure><img src="image_9.png" /></figure>

**Proof.** Closely to the $i^{th}$ obstacle, we get:

$$ \begin{aligned} \lim_{\|q - O_i\| \to r_i} \nu &= \lim_{\|q - O_i\| \to r_i} \sum_{j=1}^{p} \frac{\psi(\langle q / O_j^{\perp} \rangle)}{\|q - O_{jq}\|} \\ &= \lim_{\|q - O_i\| \to r_i} \sum_{j \neq i}^{p} \frac{\psi(\langle q / O_j^{\perp} \rangle)}{\|q - O_{jq}\|} \\ &\quad + \lim_{\|q - O_i\| \to r_i} \frac{\psi(\langle q / O_i^{\perp} \rangle)}{\|q - O_{iq}\|} \end{aligned} $$

The following investigation emphasizes three study cases which depend on each vehicle's initial position with respect to the line defined by $L_i$. Hence,

- if for $\|q - O_i\| \to r_i$ we have $\langle q/O_i^{\perp} \rangle > 0$ then

$$ \begin{aligned} \lim_{\|q - O_i\| \to r_i} \nu &= \lim_{\|q - O_i\| \to r_i} \psi(\langle q/O_i^{\perp} \rangle) \lim_{\|q - O_i\| \to r_i} \frac{1}{\|q - O_{iq}\|} \end{aligned} $$

As a result,

$$ \lim_{\|q - O_i\| \to r_i} \nu = +\infty \quad (15) $$
From Lemma 4.2, it implies that

$$ \lim_{\|q-O_i\| \to r_i} \cos(\beta) = \lim_{\|q-O_i\| \to r_i} \frac{\nu}{\sqrt{1+\nu^2}} = 1 $$

Consequently,

$$ \lim_{\|q-O_i\| \to r_i} \beta = 2k\pi \quad \forall k \in \mathbb{Z} $$

which permits to write the following:

$$ \forall \varepsilon > 0 \exists \eta_1 > 0 / \|q - O_i\| - r_i < \eta_1 \text{ and } |\beta - 2k\pi| < \varepsilon $$

and the existence of

$$ N_1 = \{p \in \mathbb{R}^2 / r_i < \|q - O_i\| < r_i + \eta_1\} $$

Now, as from the definition of $\beta$, there exists a real positive function $\varpi$ such that

$$ \lim_{\|q-O_i\| \to r_i} \|\mathcal{X}(q, \nu) - \varpi(q)q^{\perp}\| = 0 $$

Determining the function $\varpi$.

$$ \begin{align*} & \lim_{\|q-O_i\| \to r_i} \|\mathcal{X}(q, \nu) - \varpi(q)q^{\perp}\|^2 &&= 0 \\ \Leftrightarrow & \lim_{\|q-O_i\| \to r_i} \|\mathcal{X}(q, \nu)\|^2 + \varpi(q)^2 \|q^{\perp}\|^2 &&= 0 \\ & -2\varpi(q)\|q^{\perp}\| \|\mathcal{X}(q, \nu)\| \cos \beta &&= 0 \\ \Leftrightarrow & \lim_{\|q-O_i\| \to r_i} [(1+\nu^2) + \varpi(q)^2] &&= 0 \\ & -2\varpi(q)\sqrt{1+\nu^2} \|q\|^2 &&= 0 \\ \Leftrightarrow & \lim_{\|q-O_i\| \to r_i} (\varpi(q) - \sqrt{1+\nu^2}) \|q\|^2 &&= 0 \end{align*} $$

As $q \in N_1$, it is obvious that $\varpi(q) = \sqrt{1+\nu^2}$, meaning that $\forall q \in N_1$,

$$ \mathcal{X}(q, \nu) \sim \varpi(q)q^{\perp} $$

• Now, if $\|q - O_i\| \to r_i$, we have $\langle q/O_i^{\perp} \rangle < 0$, in the following same procedure as shown above,

$$ \lim_{\|q-O_i\| \to r_i} \cos(\beta) = \lim_{\|q-O_i\| \to r_i} \frac{\nu}{\sqrt{1+\nu^2}} = -1 $$

hence,

$$ \lim_{\|q-O_i\| \to r_i} \beta = (2k+1)\pi \quad \forall k \in \mathbb{Z} $$

Thus, there exists $\eta_2 > 0$ such that $\forall q \in N_2 = \{p \in \mathbb{R}^2 \setminus \mathcal{O} / r_i < \|q - O_i\| < r_i + \eta_2\}$, we have the following

$$ \mathcal{X}(q, \nu) \sim -\varpi(q)q^{\perp} $$

• If for $\|q - O_i\| \to r_i$ the case $\langle q/O_i^{\perp} \rangle = 0$ holds, then

$$ \begin{align*} \lim_{\|q-O_i\| \to r_i} \nu &= \lim_{\|q-O_i\| \to r_i} \sum_{j \neq i}^{p} \frac{\psi(\langle q/O_j^{\perp} \rangle)}{\|q - O_{jq}\|} \\ &\quad + \lim_{\|q-O_i\| \to r_i} \frac{\psi(\langle q/O_i^{\perp} \rangle)}{\|q - O_{iq}\|} \\ &= \lim_{\|q-O_i\| \to r_i} \sum_{j \neq i}^{p} \frac{\psi(\langle q/O_j^{\perp} \rangle)}{\|q - O_{jq}\|} \end{align*} $$

which implies that the domain that surrounds the obstacle $\mathcal{O}_i$ is such that $N = \{p \in \mathbb{R}^2 \setminus r_i < \|q - O_i\| < r_i + \min(\eta_1, \eta_2)\}$.

<figure><img src="image_10.png" /></figure>

The proof of Theorem 4.1 is achieved in the following step.

**Proof.** Recall the system (16) with the associated Lyapunov function $V = \frac{1}{2} \|q\|^2$,

$$ \dot{q} = u \quad (16) $$

$q \in \mathbb{R}^{2n}$ and $u \in \mathbb{R}^{2n}$. Further we assume that $q \in N$ where $N$ is the set defined in Lemma 4.3.

One distinguishes the following two cases.

• If $\langle q/O_i^{\perp} \rangle > 0$ then from Lemma 4.3

$$ \mathcal{X}(q, \nu) \sim \varpi(q)q^{\perp} $$

As $q \in N$ then instead of $\mathcal{X}$ we consider $\varpi(q)q^{\perp}$. Let $\tau \in [0, 1[$, then

$$ \begin{align*} \varphi(q + \tau\varpi(q)q^{\perp})^2 &= \|q - O_i + \tau\varpi(q)q^{\perp}\|^2 \\ &= \|q - O_i\|^2 + \tau^2\varpi(q)^2\|q\|^2 \\ &\quad + 2\tau\varpi(q)\langle q - O_i/q^{\perp} \rangle \\ &= \|q - O_i\|^2 + \tau^2\varpi(q)^2\|q\|^2 \\ &\quad + 2\tau\varpi(q)\langle O_i^{\perp}/q \rangle \end{align*} $$

which implies that $\varphi(q + \tau\varpi(q)q^{\perp})^2 > r_i^2$ because $\tau\varpi(q)\langle O_i^{\perp}/q \rangle > 0$. As a result

$$ \varphi(q + \tau\varpi(q)q^{\perp}) \in C_F A = [r, +\infty[$

From proposition 3.1, $\forall q \in N$ and $\langle q/O_i^{\perp} \rangle > 0$ $q$ avoid all the $\mathcal{O}_i$.

• If $\langle q/O_i^{\perp} \rangle < 0$, then form Lemma 4.3

$$ \mathcal{X}(q, \nu) \sim -\varpi(q)q^{\perp} $$

As $q \in N$ then instead of $\mathcal{X}$ we consider $-\varpi(q)q^{\perp}$. Let consider $\tau \in [0, 1[$, then

$$ \begin{align*} \varphi(q - \tau\varpi(q)q^{\perp})^2 &= \|q - O_i - \tau\varpi(q)q^{\perp}\|^2 \\ &= \|q - O_i\|^2 + \tau^2\varpi(q)^2\|q\|^2 \\ &\quad - 2\tau\varpi(q)\langle q - O_i/q^{\perp} \rangle \\ &= \|q - O_i\|^2 + \tau^2\varpi(q)^2\|q\|^2 \\ &\quad - 2\tau\varpi(q)\langle O_i^{\perp}/q \rangle \end{align*} $$

which implies that $\varphi(q + \tau\varpi(q)q^{\perp})^2 > r_i^2$ because $-2\tau\varpi(q)\langle O_i^{\perp}/q \rangle > 0$. Consequently

$$ \varphi(q + \tau\varpi(q)q^{\perp}) \in C_F A = [r_i, +\infty[$

for all $q \in N$ and $\langle q/O_i^{\perp} \rangle < 0$.

As a result $\forall q \in N$ and $\langle q/O_i^{\perp} \rangle \in \mathbb{R}^*$, from Proposition 3.1, $q$ avoid all the $\mathcal{O}_i$.

<figure><img src="image_11.png" /></figure>

## V. COMMUNICATION AGENTS-TARGET

In order to reach a shared objective which materializes the target and to avoid collisions, we solve the communication problem between agents through the graph theory. A depth analysis of the algebraic graph theory was studied in [1] [2]. For problems related to multi-agent networked systems with close ties to consensus problems, this includes subjects such as consensus [3][4] [14], collective behavior of flocks and swarms [5] [6] [9], formation control for multi-robot systems [7] [8] [10] [13], optimization-based cooperative control [11] [12], etc. In this paper and from control point of view, the
communication's consensus is considered as a perturbation to the stabilizing decentralized controller. Further, the position of the target is augmented to the multi-robot vector of states with the appropriate strength.

Let $G(\eta, \epsilon)$ a direct graph which admits a unit depth with one sink [2] where $\eta = \{1, ..., n, r\}$ is the set of nodes and $\epsilon = \{(i, j) \in \eta \times \eta / i \in \mathcal{N}_j\}$ denotes the edges. Let $L$ the Laplacian matrix associated to $G$ and $\mathcal{L}$ is the quantity $L \otimes I_2$ with $\otimes$ is the Kronecker product. Further, we consider $P(G)$ denotes the Disagreement matrix and defines the graph Laplacian of the mirror graph $\hat{G}: P(G) = \frac{1}{2}(L(G) - L(\hat{G}))$ where the digraph $\hat{G}$ is the inverse of $G$ (more details are in [2]). Note that the matrix $P(G)$ is positive semidefinite.

The main result is summarized in the following theorem.

**Theorem 5.1:** We consider the following kinematics associated to agents

$$ \dot{\tilde{q}} = \tilde{u} \quad (17) $$

with $\tilde{q} = [q_1, q_2, ..., q_n, q_r] \in \mathbb{R}^{2(n+1)}$ is the agent positions including the target position $q_r$. Let the vector $k = (k_1, k_2, ..., k_n, 0)$ such that $k_{ij} = k_i - k_j$ is related to the $(i, j)$ configuration $q_i - q_j$, and the strength zero is affected to the target.

The control law

$$ \tilde{u}_i = -\mathcal{L}(\tilde{q} - k) - \begin{pmatrix} \nu_1 & 0 & \dots \\ 0 & \ddots \\ \vdots & 0 & \nu_r \end{pmatrix} \otimes I_2 \begin{pmatrix} (P(G) \otimes I_2(\tilde{q} - k))_{x_1} \\ (P(G) \otimes I_2(\tilde{q} - k))_{y_1} \\ \vdots \\ (P(G) \otimes I_2(\tilde{q} - k))_{x_r} \\ (P(G) \otimes I_2(\tilde{q} - k))_{y_r} \end{pmatrix}^\perp \quad (18) $$

with $\nu_i = \frac{\text{sign}([y_{i0} - L_i(x_{i0})][C_{ix} - O_x])}{\|\tilde{q}_i - O_{\tilde{q}_i}\|}$ leads to the convergence of the formation's states toward the target $C$ while avoiding $O_{q_i}$. $I_2$ is the identity matrix $\in \mathcal{M}_{2 \times 2}(\mathbb{R})$. $\square$

<figure><img src="image_12.png" /></figure>

To prove this theorem we introduce the following results. One considers the kinematic system under the conditions of Theorem 5.1 such that

$$ \dot{\tilde{q}} = -\mathcal{L}(G)(\tilde{q} - k) \quad (19) $$

The subdivision into two parts of (19) leads to

$$ \dot{\tilde{q}}_x = L(\tilde{q}_x - k_x); \quad \dot{\tilde{q}}_y = L(\tilde{q}_y - k_y) \quad (20) $$

where $\tilde{q}_x = (x_1, x_2, ..., x_n, x_r)$, $\tilde{q}_y = (y_1, y_2, ..., y_n, y_r)$, $k_x = (k_{x_1}, k_{x_2}, ..., k_{x_n}, 0)$ and $k_y = (k_{y_1}, k_{y_2}, ..., k_{y_n}, 0)$.

**Proposition 5.2:** Let

$$ V = (\tilde{q} - k)^t P(G) \otimes I_2(\tilde{q} - k) \quad (21) $$

The solutions of (19) converge toward the largest invariant set

$$ \begin{aligned} E &= \{\tilde{q} \in \mathbb{R}^{2(n+1)} / \dot{V} = 0\} \\ &= \{\tilde{q} \in \mathbb{R}^{2(n+1)} / \mathcal{L}(G)(\tilde{q} - k) = 0\} \end{aligned} \quad (22) $$

<figure><img src="image_13.png" /></figure>

**Proof.** As the matrix $P(G)$ is positive semidefinite, from the definition of $V$, we can write

$$ \begin{aligned} V &= (\tilde{q}_x - k_x)^t P(G) (\tilde{q}_x - k_x) \\ &\quad + (\tilde{q}_y - k_y)^t P(G) (\tilde{q}_y - k_y) \\ &= V_x + V_y \end{aligned} $$

It is easy to show that the time derivative of $V_x$ leads to

$$ \dot{V}_x = -\|L(G)(\tilde{q}_x - k_x)\|^2 \le 0 \quad (23) $$

taking into account the property [2], $L(G)^t L(\hat{G}) = 0$, then

$$ \dot{V} = -\|L(G)(\tilde{q}_x - k_x)\|^2 - \|L(G)(\tilde{q}_y - k_y)\|^2 \le 0 \quad (24) $$

which implies $0 \le V(\tilde{q}) \le V(\tilde{q}_0)$, meaning that the set

$$ \Omega = \{\tilde{q} \in \mathbb{R}^{2(n+1)} / V(\tilde{q}) \le V(\tilde{q}_0)\} \quad (25) $$

is the largest invariant set for system (19). Following to the LaSalle's theorem [15], the solutions of (19) converge toward the largest invariant set defined by $(\tilde{q} \in \mathbb{R}^{2(n+1)})$

$$ \begin{aligned} E(\tilde{q}) &= \{\dot{V} = 0\} \\ &= \{\|L(\tilde{q}_x - k_x)\|^2 = \|L(\tilde{q}_y - k_y)\|^2 = 0\} \\ &= \{\mathcal{L}(\tilde{q} - k) = 0\} \end{aligned} \quad (26) $$

<figure><img src="image_14.png" /></figure>

Now, suppose that the directed graph $G$ admits a unit depth with one sink, hence the Laplacian matrix $L(G)$ associated to $G$ has a simple zero eigenvalue with an associated eigenvector $1_n$ and all of the other eigenvalues have positive real parts. $1_n$ is a $n \times 1$ column vector of all ones, and its polynomial characteristic is as $R(\lambda) = -\lambda(1 - \lambda)^{n-1}$. Hence, zero is a simple eigenvalue. The eigenvector $X = (X_1, .., X_n)$ associated to 0 verifies $LX = 0$. Meaning that $X_1 = ... = X_n = X_j$, consequently $1_n$ is the eigenvector associated to 0. From the topology of $L$ and as it was shown that the system converge to $E = \{\tilde{q} \in \mathbb{R}^{2(n+1)} / \mathcal{L}(\tilde{q} - k) = 0\}$, consequently $L(\tilde{q}_x - k_x) = 0$ and $L(\tilde{q}_y - k_y) = 0$ with the guarantee that $(\tilde{q}_x - k_x)$ and $(\tilde{q}_y - k_y)$ are the eigenvectors of $L$ associated to 0 which implies that they are generated by $\{1_n\}$. As a result,

$$ \tilde{q}_i = \text{cst } \forall i \quad \text{and} \quad \tilde{q}_i - \tilde{q}_j = k_{ij} \quad \forall j \in N_i \quad (27) $$

and $\tilde{q} = [\tilde{q}_1, ..., \tilde{q}_n, \tilde{q}_r]$ converge toward the desired topology. In other hand, the control law from (18) leads to

$$ \dot{q}_r = 0 \Leftrightarrow q_r = q_{r0} $$

and

$$ \dot{q}_i = - \begin{pmatrix} x_i - x_r - (k_{x_i} - k_{x_r}) \\ y_i - y_r - (k_{y_i} - k_{y_r}) \end{pmatrix} - \nu_i \begin{pmatrix} \left(\frac{\partial V}{\partial q}\right)_{x_i} \\ \left(\frac{\partial V}{\partial q}\right)_{y_i} \end{pmatrix}^\perp $$
where from $V$,

$$ \frac{\partial V}{\partial \tilde{q}} = P(G) \otimes I_2(\tilde{q} - k) \quad (28) $$

Thus, from Proposition 3.1 it is straightforward to show that $q_i$ avoids $O_{q_i}$.

<figure><img src="image_15.png" /></figure>

### A. Analysis of results

The proposed control schema including the proposed regulation control-input and a communication topology are simulated with Matlab. A group of multi-robot with 6 agents, where the target coordinate is considered known and as the 7th agent (figure 2). Further an obstacle is considered fixe with an appropriate repulsive circle to avoid this. So a minimum of distance should be maintained between the center of the obstacle and the agents while an attractive set is constructed around the target. The effectiveness of the regulation control-input $v$ is validated which preserves the system's invariance with respect to this set. Far from the obstacle, the regulation $v$ vanishes and does not affect the formation's stability.

<figure><img src="image_16.png" /><figcaption>Fig. 2. Communication strategy toward a linear configuration.</figcaption></figure>

## VI. CONCLUSION

For a formation composed of multi-mobile agents, a new control methodology has been developed. We proposed an extension of the stabilizing controller that brings together the multi-agent formation toward a desired set. The controller incorporates an additive scalar functions of which there are agents in the group. This regulation control-input allows agents to avoid obstacles and collisions between them. To perform further tasks, other forms of navigation strategies and constraints could be integrated. As application, a decentralized navigation are performed, and where the agents of the group are rendered to an attractive circle surrounding the target. The proposed regulation control scheme can be extended to systems with drift with holonomic and nonholonomic kinematic constraints.

## REFERENCES

[1] R. Olfati-Saber, J.A. Fax, and R.M. Murray, "Consensus and Cooperation in Networked Multi-Agent Systems," Proc. of the IEEE, Vol. 95, Issue 1, 2007, pp. 215-233.

[2] C. Gao, J. Corts, and F. Bullo, "Notes on averaging over acyclic digraphs and discrete coverage control," Automatica, Vol. 44, No. 9, 2008, pp. 2120-2127.

[3] Z. Lin, M. Brouke, and B. Francis, BLocal "control strategies for groups of mobile autonomous agents," IEEE Trans. Autom. Control, vol.49, no.4, 2004, pp. 622-629.

[4] R. Olfati-Saber and R. M. Murray, "Consensus Problems in Networks of Agents With Switching Topology and Time-Delays," IEEE Transactions On Automatic Control, vol.49, no.9, 2004, pp. 1520-1533.

[5] R. Olfati-Saber, "BFlocking for multi-agent dynamic systems: Algorithms and theory," IEEE Trans. Autom. Control, vol.51, no.3, 2006, pp. 401-420.

[6] R. A. Freeman, P. Yang, and K. M. Lynch, "BDistributed estimation and control of swarm formation statistics," in Proc. American Control Conference, Minneapolis, MN, 2006, pp. 749-755.

[7] M.A.El Kamel, L.Beji, and A.Abichou "A Decentralized Formation Control Method Including Self-Organization Around A Target," 9th Int. IFAC Symposium on Robot Control, Gifu, Japan, 2009.

[8] A. Essghaier, L. Beji and M.A. El Kamel, A. Abichou, and J. Lerbet, Co-leaders and a flexible virtual structure based formation motion control, Int. J. Vehicle Autonomous Systems, vol.9, no.1/2, 2011, pp.108-124.

[9] T. Sahin, and E. Zergeroglu "Mobile dynamically reformable formations for efficient flocking behaviour in complex environments," Proc. of the IEEE Int. Conf. on Robotics and Automation, Pasadena, CA, USA, 2008, pp. 1910-1915.

[10] W. Ren and R. W. Beard. "Formation Feedback Control for Multiple Spacecraft via Virtual Structures," IEE Proceedings-Control Theory Application, Vol.151, 2004, pp. 357-368.

[11] Srinivas, Y. Dashora, A. K. Choudhary, J. A. Harding, and M. K. Tiwari, "A cooperative multi colony ant optimization based approach to efficiently allocate customers to multiple distribution centers in a supply chain network," int. conf. on computational science and its applications, Singapore, 2005, pp. 1340-1362.

[12] M. Alghanbari and J. P. How, "BDecentralized task assignment for unmanned aerial vehicles," in 44th IEEE Conf. Decision and Control (CDC-ECC'05), 2005, pp. 5668-5673.

[13] W. Ren and N. Sorensen, "Distributed coordination architecture for multi-robot formation control," Robotics and Autonomous Systems, vol.56, Issue 4, 2008, pp. 324-333.

[14] W. Ren "Multi-vehicle consensus with time-varying reference state," Systems & Control letters, vol.56, 2007, pp. 474-483.

[15] H. K. Khalil, Nonlinear Systems (3rd Edition), Prentice Hall, 2001.

[16] R. W. Brokett, "Asymptotic stability and feedback stabilization," in Differential Geometric Control Theory, vol.27, 1983, pp.181-191.

[17] J. B. Pomet, "Explicit design of time varying stabilizing control laws for a class of controllable systems without drift," Systems & control letters, vol.18, no2, 1992, pp.147-158.

[18] L. Beji, A. Abichou, A. and Y. Bestaoui, "Position and attitude control of an underactuated autonomous airship," Journal of Differential Equations, vol.8, n.3, 2003, pp.231-255.

[19] L. Beji and A. Abichou, "Modelling and/or control of multi-vehicle formations," Int. J. Vehicle Autonomous Systems, vol.9, Nos.1/2, 2011.

[20] H. Yamaguchi, Y. Kanbo and A. Kawakami, "Formation vector control of nonholonomic mobile robot groups and its experimental verification," Int. J. Vehicle Autonomous Systems, vol.9, Nos.1/2, 2011.

[21] M. B. Colton, L. Sun, D. C. Carlson and R. W. Beard, "Multi-vehicle dynamics and control for aerial recovery of micro air vehicles," Int. J. Vehicle Autonomous Systems, vol.9, Nos.1/2, 2011.

[22] D. Herrero-Perez and H. Martinez-Barbera, "Coordination of AGVs in an industrial environment," 7th int. joint conf. on Autonomous agents and multiagent systems, Estoril, Portugal, 2008.

[23] R. Olmi, C. Secchi and C. Fantuzzi, "Coordination of industrial AGVs," Int. J. Vehicle Autonomous Systems, vol.9, Nos.1/2, 2011.

[24] M.L. Cummings, S. Bruni, S. Mercier and P.J. Mitchell, "Automation Architecture for Single Operator, Multiple UAV Command and Control," The International C2 Journal, vol.1, no.2, 2007, pp. 1-24.