# Multi-vehicle consensus with target capturing and collision avoidance

Mohamed Anouar El Kamel, Lotfi Beji, Azgal Abichou

► To cite this version:

Mohamed Anouar El Kamel, Lotfi Beji, Azgal Abichou. Multi-vehicle consensus with target capturing and collision avoidance. Twelfth International Conference on Climbing and Walking Robots and the Support Technologies for Mobile Machines (CLAWAR'09), Sep 2009, Istanbul, Turkey. pp.827-834, 10.1142/9789814291279_0101 . hal-00653665

HAL Id: hal-00653665

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

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
MULTI-VEHICLE CONSENSUS WITH
TARGET CAPTURING AND OBSTACLE AVOIDANCE

M. A. El Kamel, L. Beji and A. Abichou

Informatics, Integrative Biology and Complex Systems
university of Evry, France

E-mail: Anouar.Elkamel, Lotfi.Beji@iup.univ-euvry.fr

Mathematical Engineering Laboratory
Polytechnic School of Tunisia

E-mail: azgal.abichou@ept.rnu.tn

In this paper we give an analytic study to construct a command for a group of vehicles to reach a target in an hostile environment. A consensus between different agents is established. This work is an extension to a previous oneEl Kamel et al.(2009) to the case of multi-vehicle. The vector which contains all the velocity fields is considered as a feedback control law. We developed a new technique which decompose the vector of velocities to a sum of two parts; an attractive part that guarantees the convergence toward the target and a responsive part that ensures obstacle avoiding. Our approach is based on LaSalle's theorem. The feedback control law ensures also that each vehicle/agent choose the optimal trajectory in front of the obstacle without neither switching control nor tracking trajectory. We introduce the consensus algorithm with a constant reference state using graph theoretical tools to create an hierarchical formation. The stability of the formation is realized when all agents converge to the desired configuration in neighborhood of the target.

**Keywords:** Formation control, Multi-vehicle coordination, Hierarchical navigation, Target capturing, Collision avoidance, LaSalle's theorem, Graph theory

1. Introduction

After according an interest to a single vehicle evolving in the space,
recently a new issue to the formation control is intensively investi-
gated by control community. This interest come from the several ap-
plications in different domain, inter alia in the medical field (behavior
of a drug in the body), the study of movement of the cells, the road
traffics, the migration of a group of animals (bird, fish) and military
goals. Several works treated the formation navigation of unmanned vehi-
cles, El Kamel et al.(2008), Ren et al.(2008), Chen et al.(2005) but few works have considered the hostile environment. Indeed we are interested in this paper on the formation motion control with obstacle avoidance. Two important difficulties can arise:

How each vehicle of the formation can avoid an obstacle in the plane? and at the same time how does it converge to its predefined target?

Dimos et al.(2008), Chang et al.(2003), Kowalczyk et al.(2005) solve these problems, but the methods used are costly and very painful for execution. In this work a feedback control law with double function was conceived. Indeed, the control law is the sum of an attractive term $u_a$ responsible to bring the robot towards the objective and of a repulsive term $u_r$ which enables it to avoid the obstacle. This is based on an approach which one conceived and which can be summarized as follows:

If $u_a$ is a control law which makes converge the system towards the desired position, then control law $u_a + u_r$, where $u_r$ is a function depending on the Lyapunov function and is not changing with respect to the zone where is the vehicle, make converge also the system towards the same desired position. Using this function $u_r$, one could modify the trajectory behavior in order to avoid a set of points around the obstacle. Also the control law that we propose ensures a fluid behavior of the robots in front of the obstacle. It is to be said by considering the line $L$ which joins the center of the target to the obstacle, the two sets which are in left and right of $L$ are invariant. The behavior of robots in formation depends strongly on the communication between the various agents to carry out a common task and to avoid inter-agents collisions. In this context, we can cite the works of, Ren et al.(2008), Olfati et al.(2007), Olfati et al.(2004) which utilizes the graph tools to define the link between two agents. In our work we will not be interested to the communications tools but only on the existence of links. Our contribution was to adapt all these theories carried out on graph theory amalgamated, with our work in matter of formation stabilization.

Finally, simulations are carried out for a scenario of navigation for target capturing.

## 2. System and problem description

Consider $N$ vehicles moving in the plane where the kinematic behavior of the $i^{th}$ vehicle is described by:

$$ \dot{q}_i = u_i, i \in \mathcal{N} = \{1, ..., n\} \quad (1) $$
with $q_i = (x_i, y_i) \in \mathbb{R}^2$ denotes the position and $u_i = (u_{x_i}, u_{y_i}) \in \mathbb{R}^2$ denotes the velocity which also are the control inputs of the agent $i$. For the formation, we have this written

$$ \dot{q} = u \qquad (2) $$

with $q = [q_1, q_2, \dots, q_n] \in \mathbb{R}^{2n}$ and $u = [u_1, u_2, \dots, u_n] \in \mathbb{R}^{2n}$.

### 3. Regulation Equation and Stabilization

Our main result is to extend the stabilizing control problem such that it incorporates a regulation function. This is necessary for navigation in presence of perturbations. Consequently, we introduce in the following theorem the regulation function.

**Theorem 3.1.** We consider the differential system (2). Assume that for $u = u_a$, $\Omega = \{q \in \mathbb{R}^{2n}/0 \le V(q) \le p\}$ is an invariant set with respect to $\dot{q} = u_a$, where $V: \mathbb{R}^{2n} \to \mathbb{R}_+$ is such that $\frac{\partial V}{\partial q}u_a \le 0$

Then for any function $v_i$ from $\mathbb{R}^{2n}$ to $\mathbb{R}$ the following control law:

$$ u = u_a - \begin{pmatrix} \nu_1(q) & 0 & \dots \\ 0 & \ddots & \\ \vdots & 0 & v_n(q) \end{pmatrix} \otimes I_2 \begin{pmatrix} (F_1)^\perp \\ \vdots \\ (F_n)^\perp \end{pmatrix} \quad \text{where} \quad F_i = \begin{pmatrix} \frac{\partial V}{\partial x_i} \\ \frac{\partial V}{\partial y_i} \end{pmatrix} \quad (3) $$

makes the states of (2) and equation $\dot{q} = u_a$, starting in $\Omega$, approaches the same set

where $\otimes$ is the Kronecker product, $I_2$ is the identity matrix $\in M_{2 \times 2}(\mathbb{R})$

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

**Proof One have** $\Omega = \{q \in \mathbb{R}^{2n}/0 \le V(q) \le p\}$ is invariant for $\dot{q} = u_a$ and $\dot{V} = \frac{\partial V}{\partial q}u_a \le 0$, then According to LaSalle's theorem the solutions of the equation cited above converge to the greatest invariant set of

$$ E = \{q \in \mathbb{R}^{2n} / \dot{V} = 0\} $$

we use the same function $V$ for the system (2, 3), Its differential with respect to $t$ becomes:

$$ \begin{aligned} \dot{V} &= \frac{\partial V}{\partial q} \dot{q} = \dots = \frac{\partial V}{\partial q} u_a - \sum_{i=1}^{n} F_i^t \mathfrak{A}_i F_i^\perp \quad \text{where} \quad \mathfrak{A}_i = \begin{pmatrix} \nu_i & 0 \\ 0 & \nu_i \end{pmatrix} \\ &= \frac{\partial V}{\partial q} u_a - \sum_{i=1}^{n} \nu_i F_i^t F_i^\perp = \frac{\partial V}{\partial q} u_a \le 0 \end{aligned} \quad (4) $$
then $\dot{V} = \frac{\partial V}{\partial q} u_a \le 0$, hence $\Omega = \{q \in \mathbb{R}^{2n}/0 \le V(q) \le V(q_0)\}$ is invariant for the solution of (2,3) which implies that the state of system (2,3) converges to the greatest invariant set of E.

**Remark 3.1.** This theorem enables us to break up the control law on sum of two parts. The first is called attractive and the second represents new entries for our system. $v = [v_1(q), v_2(q), \dots, v_n(q)]$ is the vector of the regulation functions. Changing $v$ will modify the trajectory behavior while conserving the convergence.

# 4. Control Strategy And Obstacle Avoidance

In this section, we suppose that the environment of the formation is not free of obstacles. After having fixed the target, which is the objective to reach, our goal is to move the formation from an initial configuration toward another configuration form with respect to the target. For that we introduce some tools of Algebraic Graph Theory

## 4.1. Tools from Algebraic Graph Theory

Our main issue is to define a graph based configuration of links which we note by $G(\kappa, \varepsilon)$. The graph $G(\kappa, \varepsilon)$ is defined by two sets; $\kappa = \{1, \dots, n\}$ is the indexes set of $N$ nodes, the second is denoted by $\varepsilon$, the set of ages which connects two nodes in communication, such that $\varepsilon = \{(i, j) \in \kappa \times \kappa, j \in N_i\}$ with $N_i$ is the set of node's indexes in connection with the $i^{th}$ node or neighbor. Let $A = (a_{ij})$ the matrix of connection called the *adjacent matrix*, this matrix contains different connection between the vehicles, more precisely two cases was presented: in *directed graph* if the $i^{th}$ vehicle is in relation with the $j^{th}$ vehicle then $a_{ij} = 1$ else 0, in *undirected graph* if the $i^{th}$ vehicle is in relation with the $j^{th}$ vehicle then automatically the $j^{th}$ vehicle is in relation with the $i^{th}$ i.e $a_{ij} = a_{ji} = 1$ else 0. We note by $\Delta$ the diagonal matrix such as his $i^{th}$ member on the diagonal corresponds to the number of connections which the $i^{th}$ agent can establish with the others. We define the *Laplacian matrix L* as follows

$$L = \Delta - A$$

The Laplacian matrix is the key matrix in the stabilization of agents in formation. When we multiply it by $q$ which contains all states of vehicles, that becomes a combination vector of vehicle positions.
## 4.2. Obstacle localization

In this work, we suppose that any obstacle in the plane can be circumscribed by a circle centered in a certain $O$ and of radius $r$. When a vehicle approaches an obstacle, this means that its position $q$ approaches $O_q$; the intersection point between the circle and the line joining $O$ to $q$.

$$O_q = O + r \frac{q - O}{\|q - O\|} \quad (5)$$

$O_q$ moves while $q$ is moving and depends on the vehicle coordinates over time.

In the next section we suppose that the origin of the frame is the position $C$ of the target and $D$ denote the function of the line joining $O$ to $C$.

## 4.3. Stability Analysis

The formation regulation control consists to find a distributed control $u$ which stabilizes each agent while reaching the target with obstacle avoiding. Moreover, when arriving to the target, the formation should respect a predefined configuration around the objective. The final configuration depends on the application. Theoretically, each mobile robot controller should be subdivided into parts such that the formation avoids an existing obstacle in the environment and captures the target. We can summarize this work in the next theorem.

**Theorem 4.1.** Let $G(\eta, \epsilon)$ a directed graph, where $\eta = \{1, ..., n, n + 1\}$. Assume that $L = (l_{ij})_{ij}$ is the Laplacian matrix associated to $G$, which has a directed spanning tree such that $l_{(n+1)r} = 0 \forall r \in \eta$, and $\mathcal{L}$ the quantity $L \otimes I_2$. Let $k = (k_1, k_2, ..., k_n, 0)$ such as $k_{ij} = k_i - k_j$ is the desired configuration of $q_i - q_j$. The following control law:

$$u_i = - \sum_{j=1}^{n} l_{ij}(q_i - q_j - k_{ij}) - l_{i(n+1)}(q_i - C - k_i) - h_i(q_i - k_i)^\perp \quad (6)$$

$$\text{where } h_i = \frac{\text{sign}([y_{i0} - D(x_{i0})][C_x - O_x])}{\|q_i - O_{q_i}\|} \quad \text{and} \quad h_{n+1} = 0 \quad (7)$$

makes converge the states os (2) toward equilibrium configuration in a neighborhood of target $C$ while avoiding $O_{q_i}$.
**Proof** We consider $\tilde{q} = [q_1, q_2, ..., q_n, q_{n+1} = C] = [q, C] \in \mathbb{R}^{2(n+1)}$ the vector with components the positions of all the vehicles and the target C. we assume the following system

$$ \dot{\tilde{q}} = \tilde{u} \qquad (8) $$

For $\tilde{u} = -\mathcal{L}(\tilde{q} - k)$ let the he function $V = \frac{1}{2}\|\tilde{q} - k\|^2$, its differential with respect to $t$ is

$$ \dot{V} = -(\tilde{q} - k)^t \mathcal{L}(\tilde{q} - k) = -(\tilde{q} - k)^t \frac{(\mathcal{L}^t + \mathcal{L})}{2} (\tilde{q} - k) \le -\|\tilde{q} - k\|^2 \min_{i \in \eta} \lambda_i $$

where $\lambda_i$ is an eigenvalue of $\frac{L+L^t}{2}$ according to Courant - Fisher theorem. $\frac{L+L^t}{2}$ and $L$ have the same eigenvalues which verify the following known property

$|\lambda_i - l_{ii}| \le \sum_{j=1, j \ne i}^{n+1} |l_{ij}|$ then $0 \le \lambda_i \le 2l_{ii}$ since $l_{ii} = \sum_{j=1, j \ne i}^{n+1} |l_{ij}|$.

Consequently $\dot{V} \le 0$.

Moreover if we injecte the control law (6) in the system above we obtain

$$ \tilde{u} = -\mathcal{L}(\tilde{q} - k) - \begin{pmatrix} h_1 & 0 & \dots \\ 0 & \ddots & \\ \vdots & 0 & h_{n+1} \end{pmatrix} \otimes I_2(\tilde{q} - k)^\perp \quad (9) $$

where $\frac{\partial V}{\partial \tilde{q}} = \tilde{q} - k$ hence the theorem 3.1 affirm that the solutions of the systems (8) and (2,6,7) converge to M the same largest invariance set of

$$ E = \{\tilde{q} \in \mathbb{R}^{2(n+1)} / \dot{V} = 0\} = \{\tilde{q} \in \mathbb{R}^{2(n+1)} / \mathcal{L}(\tilde{q} - k) = 0\} \quad (10) $$

When $\mathcal{L}(\tilde{q} - k) = 0$ then $L(\tilde{q}_x - k_x) = 0$ and $L(\tilde{q}_y - k_y) = 0$. we have $L$ has a directed spanning tree then according to lemma in Ren et al. (2007) the matrix $L$ has a simple zero eigenvalue with an associated eigenvector $l_{n+1}$ and all of the other eigenvalues have positive real parts. This guarantees that both $(\tilde{q}_x - k_x)$ and $(\tilde{q}_y - k_y)$ are the eigenvector of $L$ belonging to $\text{span}\{l_n\}$. Hence

$$ \tilde{q}_i - k = C \text{st } \forall i \text{ then } q_i - q_j = k_{ij} \quad \forall j \in \mathcal{N}_i \quad (11) $$

that implies $\tilde{q} = [q_1, ..., q_n, q_{n+1} = C]$ converge to the desired configuration. In the other hand, injecting the control law (6,7) in our system (2), we obtain

$$ \dot{q}_{n+1} = 0 \quad \text{then} \quad q_{n+1} = C $$
then the formation converge to the neighborhood of the known target C.

## 5. Simulation

In this section one present the simulation result of formation navigation containing four agents. In following figure we can note the change of the trajectory in front of the obstacle, and the fluid behavior with respect to the line D which join target and obstacle, to ensure that each agent avoid obstacle. In finally all the agent converge to the desired configuration in neighborhood of the target.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Navigation of 4 agents with obstacle and without obstacle</figcaption></figure>

## 6. Conclusion

For a formation, composed by multiple mobile robots moving toward a target, a hierarchical communications between the vehicles are established and a new design methodology of the convergence and the regulation in presence of obstacles is developed. One notes that the controller was subdivided
into two parts where the first one ensures the stabilizing toward the target and the second part modifies the nature trajectory of the robot such that the circle circumscribed obstacles is avoided. Within the framework of the formation, using the graph theory, the particularity of the controller is its distribution preserving interconnection between agents.

## References

* El Kamel et al.(2008). M. A. El Kamel, L.Beji, A. Abichou. Nonholonomic Mobile Robots Cooperative Control for Target Capturing. India Conference, 2008. INDICON 2008. Annual IEEE, Kanpur, India, Vol.2, pp548-552, 11-13 Dec. 2008.

* El Kamel et al.(2009). M. A. El Kamel, L.Beji, A. Abichou. A Novel Obstacle Avoidance Approach For Multi-Mobile Robot Systems Including Target Capturing. 2nd Mediterranean Conference on Intelligent Systems and Automation, cisa'09, Zarzis, Tunisia, 23-25 March 2009. AIP Conference Proceedings Vol. 1107 pp. 249-253

* Chang et al.(2003). Dong Eui Chang, Shawn C. Shadden, Jerrold E. Marsden and Reza Olfati-Saber. Collision Avoidance for Multiple Agent Systems. Proceedings of the 42nd IEEE Conference on Decision and Control. Maui, Hawaii USA, December 2003.

* Dimos et al.(2008). Dimos V. Dimarogonas and Karl H. Johansson. Analysis of Robot Navigation Schemes using Rantzers Dual Lyapunov Theorem. American Control Conference. Seattle, WA, USA, pp. 201-206, 2008.

* Ren et al.(2008). Wei Ren, Nathan Sorensen. Distributed coordination architecture for multi-robot formation control. Robotics and Autonomous Systems. Vol. 56, Issue 4, pp. 324-333, 2008.

* Olfati et al.(2007). R. Olfati-Saber, J.A. Fax, R.M. Murray. Consensus and Cooperation in Networked Multi-Agent Systems. Proceedings of the IEEE. Vol. 95, Issue 1, pp. 215-233, 2007.

* Ren et al.(2007). Wei Ren. Multi-vehicle consensus with a time-varying reference state. Systems & Control letters. Vol. 56, pp. 474-483, 2007.

* Olfati et al.(2004). Reza Olfati-Saber and Richard M. Murray. Consensus Problems in Networks of Agents With Switching Topology and Time-Delays. IEEE Transactions On Automatic Control. VOL. 49, NO. 9, 2004.

* Chen et al.(2005). Y.-Q. Chen and Z. Wang. Formation control: a review and a new consideration. IROS Conference. Alberta, Canada, pp.3664-3669, 2005.

* Kowalczyk et al.(2005). W. Kowalczyk and K. Kozlowski. Artificial Potential Based Control for a Large Scale Formation of Mobile Robots. Climbing and Walking Robots, Springer Berlin Heidelberg. pp.191-199, 2005.