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

HAL
open science

# A Connectivity Aware Path Planning for a fleet of UAVs in an Urban Environment: Supplementary Material

Nouman Bashir, Saadi Boudjit, Gabriel Dauphin

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

## To cite this version:

Nouman Bashir, Saadi Boudjit, Gabriel Dauphin. A Connectivity Aware Path Planning for a fleet of UAVs in an Urban Environment: Supplementary Material. 2023. [https://hal.science/hal-04081656](https://hal.science/hal-04081656)

HAL Id: hal-04081656

https://hal.science/hal-04081656

Submitted on 25 Apr 2023

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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Connectivity Aware Path Planning for a fleet of UAVs in an Urban Environment

## Supplementary Material

Nouman Bashir, Saadi Boudjit, and Gabriel Dauphin

### I. INTRODUCTION

In this 7-pages document, we give some supplementary material for the preprint of a paper, titled, A Connectivity Aware Path Planning for a fleet of UAVs in an Urban Environment. Section II shows two illustrations. Section III shows a few complimentary figures. And section IV gives an extensive demonstrations of different theorems formulated and used in the paper.

### II. ILLUSTRATION

Figure 1 are two subfigures illustrating the two application scenarios described in section III-A (p. 4).

### III. SIMULATIONS

We present here three figures accounting for simulations whose implementation is described in the beginning of section V (p. 11). These simulations use parameters listed in table II (p. 12).

Figure 2 shows reaction time between two neighboring UAVs, when there is a total of 4 UAVs.

Figure 3 shows UAVs' minimum distance variation from any other UAV for a fixed fleet speed of 2, 5, and 10 m/s. Similarly for the same experiments.

Figure 4 represents, among all UAVs and obstacle, the minimum UAV-obstacle distance during entire simulation time with fixed fleet speed of 2, 5, and 10 m/s.

Figure 5 demonstrates the delay faced by data packets (i.e., $T_{BS}$) for UAV fleet speed of 2, 5, and 10 m/s. This figure demonstrates that the average delay remains the same for all these speed variations.

Figure 6 plots data packet delays (i.e., $T_{BS}$) for the ground users to reach BS and for different

N. Bashir, S. Boudjit, and G. Dauphin are with L2TI, Institut Galilée, Université Sorbonne Paris Nord, Villetaneuse 93430, France.

E-mail: nouman.bashir@edu.univ-paris13.fr, saadi.boudjit@univ-paris13.fr, gabriel.dauphin@univ-paris13.fr

leaders' locations within the fleet. It shows that leaders' position plays only a slight role in determining the delay incurred by the data packets.

Fig. 7 plots the delay incurred (i.e., $T_{BS}$) by the data packets for ground users to reach BS under 2, 5, and 10 m/s fleet speed. It can be observed from the figure that the delay faced by the data packets under these conditions is not affected by the variation in the fleet speed.

### IV. SET OF PROOFS

#### A. Proof of theorem 1 (p. 8)

The proof is organized in three parts. First we use analytical formulas of $v(t)$, $S(t)$ and $\Phi[s]$, the latter uses a given value of $s \ge 0$. Then we derive the desired properties. And thirdly we prove that $v(\tau)$, $S(\tau)$ and $\Phi[s'']$ are known to all UAVs at time $t$ if $\tau \le t$ and $\Phi[s''] \le t$.

1) We first compute analytic formulas.

* Based on assumption 2, we denote $v(t)$ as a finite linear combination of indicator functions also denoted with 1.

$$v(t) = \sum_{l=0}^{L-1} v_l 1_{[t_l, t_{l+1})}(t) \quad (1)$$

where $[t_l, t_{l+1})$ are the left-closed and right-open intervals of the different indicator functions. Because a speed is non-negative and based on assumption 2, we also have

$$\begin{aligned} \forall l, v_l \in [0, v_{\max}] \\ t_L = +\infty \text{ and } v_{L-1} > 0 \end{aligned} \quad (2)$$

* Using equation (26) defining the ramp function and integrating equation (1), we get

$$S(t) = \sum_{l=0}^{L-1} v_l R_{t_l}^{t_{l+1}}(t) \quad (3)$$

* Because $S(t)$ can be constant on some intervals, there are different ways of defining its inverse. We have chosen to define $\Phi[s]$ as

$$\Phi[s] = \max\{t | S(t) \le s\} \quad (4)$$
<figure><img src="image_4.png" /><figcaption>Fig. 1. Application scenarios described in section III-A (p. 4). (a) Natural disaster scenario. (b) Continuous tracking and monitoring of a rally.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 2. UAV's reaction time to speed change requests (4 transmitting UAVs)</figcaption></figure>

An equivalent definition is

$$ \Phi[s] = t_{l_s} + \frac{s - S(t_{l_s})}{v_{l_s}} \quad (5) $$

where

$$ l_s = \max\{0 \le l < L | S(t_{l_s}) \le s\} \quad (6) $$

This definition of $l_s$ ensures that $v_{l_s} \neq 0$, note that it says nothing as to whether $v_{l_{s-1}} = 0$.

We also have

$$ \Phi[s] \in [t_{l_s}, t_{l_s+1}) \quad (7) $$

## 2) We now derive the expected properties.

* Equation (5) and the linearity of $S(t)$ within each intervals $[t_l, t_{l+1})$ show that

$$ S(\Phi[s]) = S(t_{l_s}) + \mathcal{R}_{S(t_{l_s})}^{S(t_{l_s+1})}(s) = s \quad (8) $$

* We first assume that we do not have both, $s = S(t_{l_s})$ and $v_{l_{s-1}} = 0$.

Equation (5) and (7) prove that

$$ \frac{d}{ds}\Phi(s) = \frac{1}{v_{l_s}} = \frac{1}{v(\Phi(s))} $$

* We then assume that we do have both $s = S(t_{l_s})$ and $v_{l_{s-1}} = 0$. Because $s = S(t_{l_{s-1}}) > S(t_{l_{s-2}})$, we consider

$$ s' \in [S(t_{l_{s-2}}), S(t_{l_{s-1}})) $$

and see that

$$ \Phi(s') = t_{l_{s-2}} + \frac{s' - S(t_{l_{s-2}})}{v_{l_s}} \rightarrow t_{l_{s-1}} < t_{l_s} $$

when $s' \rightarrow s^{-}$.

## 3) Finally we study the availability of these quantities at time $t$. Let us assume that $\tau \le t$ and $s''$ such that $\Phi(s'') \le t$.

* By defining $l_\tau = \max\{l|t_l \le \tau\}$, we get $v(\tau) = v_{l_\tau}$ which is known to all UAVs at time $t$.

* Equation (3) shows that

$$ S(\tau) = \sum_{l=0}^{l_\tau-1} v_l(t_{l+1} - t_l) + v_{l_\tau}(\tau - t_{l_\tau}) $$

which is also known to all UAVs at time $t$.

* Applying equation (5) to $s''$, we have

$$ \Phi[s''] = t_{l_{s''}} + \frac{s'' - S(t_{l_{s''}})}{v_{l_{s''}}} $$

$t_{l_{s''}}$, $v_{l_{s''}}$ and $S(t_{l_{s''}})$ are known to all UAVs at time $t$ since:

- $t_{l_{s''}} \le \Phi[s''] \le t$

- $v_{l_{s''}} = v(t_{l_{s''}})$

- $S(t_{l_{s''}}) = \int_{0}^{t_{l_{s''}}} v(\tau) d\tau$

Therefore $\Phi[s'']$ is also known to all UAVs at time $t$.
<figure><img src="image_6.png" /><figcaption>Fig. 3. Minimum UAV-UAV distance with simulation time (a) Fleet speed 2 m/s (b) Fleet speed 5 m/s (c) Fleet speed 10 m/s</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 4. Minimum UAV-Obstacle distance with simulation time (a) Fleet speed 2 m/s (b) Fleet speed 5 m/s (c) Fleet speed 10 m/s</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 5. Data packets delay to reach BS</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 6. Data packets delay to reach BS</figcaption></figure>

B. Proof of theorem 2 (p. 9)

Equation (27) can be recast into five equations describing each of the five phases listed below

equation (24).

$$ V_n(t) = \begin{cases} A - (n-1)\Delta S_c \underset{e_0}{\stackrel{\longrightarrow}{\rightleftharpoons}} & \text{if } S(t) \in [0, L_{0,n}] \\ A + (S(t) - L_{1,n}) \underset{e_0}{\stackrel{\longrightarrow}{\rightleftharpoons}} & \text{if } S(t) \in [L_{0,n}, L_{1,n}] \\ P_k + (S(t) - L_{k,n}) \underset{e_k}{\stackrel{\longrightarrow}{\rightleftharpoons}} & \text{if } S(t) \in [L_{k,n}, L_{k+1,n}] \\ B + (S(t) - L_{K,n}) \underset{e_K}{\stackrel{\longrightarrow}{\rightleftharpoons}} & \text{if } S(t) \in [L_{K,n}, L_{K+1,n}] \\ B - (N-n)\Delta S_c \underset{e_K}{\stackrel{\longrightarrow}{\rightleftharpoons}} & \text{if } S(t) \in [L_{K+1,n}, L_{K+2,n}] \end{cases} \tag{9} $$
<figure><img src="image_10.png" /><figcaption>Fig. 7. Data packets delay to reach BS from ground users</figcaption></figure>

Equations (29) and (30) are then easily derived.

### C. Proof of theorem 3 (p. 9)

The proposed proof of theorem 3 uses the following lemma.

**Lemma 1.** Let $\overline{P_k}$ and $\overline{P_{k+1}}$ be two points defining a line segment $\overline{P_kP_{k+1}}$ sufficiently far from any obstacle in that

$$ \forall i, \mathcal{D}(\overline{P_k P_{k+1}}, \overline{C_i D_i}) \ge \rho_c \quad (10) $$

Let M be a point of this line segment.

$$ M \in \overline{P_k P_{k+1}} $$

Then for any point $M'$, we have

$$ MM' < \rho_c \Rightarrow M' \notin \overline{C_i D_i} $$

*Proof.* We are actually proving here the contrapositive of this lemma.

Let M be a point in $\overline{P_kP_{k+1}}$ and $M'$ another point in $\overline{C_iD_i}$, for some value of $i$ and $k$.

Equation (10) implies that $MM' \ge \rho_c$. □

This lemma is used in the following proof of theorem 3.

*Proof.* Let $t \in [0, T]$. Let $\mathbf{P} = [P_1...P_K]$ be a complete path with $\Delta_A$ and $\Delta_B$ its departure and arrival areas all of them being sufficiently far from any obstacles (i.e. left of equation (31) holds). Equation (27) proves that there exists $k \in \{0...K\}$ such that

$$ V_n(t) \in \overline{P_{k,n} P_{k+1,n}} \quad (11) $$

Equations (13), (16), and (17) prove that

$$ \overline{P_{0,n}P_1} \subset \Delta_A \text{ and } \overline{P_K P_{K+1,n}} \subset \Delta_B $$

Therefore $\mathcal{D}(\overline{P_{k,n}P_{k+1,n}}, \overline{C_i D_i}) \ge \rho_c$ holds also for $k \in \{0, K\}$.

Left of equation (5) in assumption 1 tells us that $R_nV_n(t) < \rho_c$. Lemma 1 ends the proof. □

### D. Proof of theorem 4 (p. 9)

Based on equations (9) and (23), we have

$$ \Delta S_r \ge \Delta S_c \quad (12) $$

**Lemma 2.** Let $\alpha$ and $\beta$ be two non-negative real numbers.

$$ \sqrt{\alpha^2 + \beta^2} \ge \frac{\alpha + \beta}{\sqrt{2}} \quad (13) $$

*Proof.*

$$ \sqrt{\alpha^2 + \beta^2} \ge \frac{\alpha + \beta}{\sqrt{2}} \Leftrightarrow \alpha^2 + \beta^2 \ge \frac{(\alpha + \beta)^2}{2} \\ \Leftrightarrow \frac{\alpha^2}{2} + \frac{\beta^2}{2} \ge \alpha\beta \Leftrightarrow \frac{1}{2}(\alpha - \beta)^2 \ge 0 $$

**Lemma 3.** Let E, F, G be three points such that

$$ |\angle(\overrightarrow{EF}, \overrightarrow{FG})| \le \frac{\pi}{2} $$

Let $M_e \in \overline{EF}$ and $M_g \in \overline{FG}$

$$ M_e M_g \ge \frac{FM_e + FM_g}{\sqrt{2}} \quad (14) $$

This proof uses the scalar product denoted $\cdot$ and its corresponding norm $|| ||$ derived from the Euclidean distance.

*Proof.* We first prove that $\overrightarrow{FM_e} \cdot \overrightarrow{FM_g} \le 0$ then use this result and that of lemma 2 to end the proof.

1) Because $M_e \in \overline{EF}$ and $M_g \in \overline{FG}$, there exist $\lambda, \mu \in [0, 1]$ such that

$$ \overrightarrow{FM_e} = \lambda \overrightarrow{FE} $$

$$ \overrightarrow{FM_g} = \mu \overrightarrow{FG} $$

We can now conclude on the sign of $FM_e \cdot FM_g$

$$ \overrightarrow{FM_e} \cdot \overrightarrow{FM_g} = \lambda \mu \text{FE} \times \text{FG} \cos \angle(\overrightarrow{FE}, \overrightarrow{FG}) \le 0 $$

2) Thanks to some scalar product operations and to lemma 2, we get

$$ M_e M_g = \left\| \overrightarrow{FM_g} - \overrightarrow{FM_e} \right\| = \sqrt{FM_g^2 - 2FM_e \cdot FM_g + FM_e^2} \ge \sqrt{FM_g^2 + FM_e^2} \ge \frac{FM_e + FM_g}{\sqrt{2}} $$
<figure><img src="image_11.png" /></figure>

Before handling the proof itself, we recast equation (9) describing the position of each virtual UAV into two equations, first a description of where each virtual UAV is inside a global path and then a description of this global path.

$$S_n(s) = \mathcal{R}_{L_{0,n}}^{L_{K+1,n}}(s) - (n-1)\Delta S_c \quad (15)$$

$$V(s) = A - (N - 1)\Delta S_c \xrightarrow{e_0} + \mathcal{R}_{-(N-1)\Delta S_c}^0(s) + \sum_{k=0}^{K} \mathcal{R}_{L_{k,1}}^{L_{k+1,1}}(s) \xrightarrow{e_k} \quad (16)$$

Simple computations show that

$$V_n(t) = V(S_n(S(t))) \quad (17)$$

**Lemma 4.** Let $n_1$ and $n_2$ denote two different UAV and let $S_{n_1}(s)$ and $S_{n_2}(s)$ be their relative positions on the global path. We have

$$|S_{n_1}(s) - S_{n_2}(s)| \ge \Delta S_c \quad (18)$$

*Proof.* There is no loss of generality in assuming that $n_2 > n_1$. The proof depends on $s$ and we consider three possibilities.

1) When $s \le L_{0,n_2}$, we have

$$S_{n_2}(s) = -(n_2 - 1)\Delta S_c \text{ and } S_{n_1}(s) \ge -(n_1 - 1)\Delta S_c$$

By subtracting the two equations, we prove equation (18).

$$S_{n_2}(s) - S_{n_1}(s) \le (n_1 - n_2)\Delta S_c \le -S_c$$

2) When $s \ge L_{K+1,n_1}$, we have

$$S_{n_2}(s) \le \mathcal{L}(\mathbf{P}) - (N - n_2)\Delta S_c$$

$$S_{n_1}(s) = \mathcal{L}(\mathbf{P}) - (N - n_1)\Delta S_c$$

By subtracting the two equations, we prove again equation (18).

$$S_{n_2}(s) - S_{n_1}(s) \le (n_1 - n_2)\Delta S_c \le -S_c$$

3) When $s \in [L_{0,n_2}, L_{K+1,n_1}]$, we note that this implies $s \in [L_{0,n_1}, L_{K+1,n_2}]$ and therefore that

$$S_{n_2}(s) - S_{n_1}(s) = (n_1 - n_2)\Delta S_r \le -\Delta S_r \le -\Delta S_c$$

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

Below is the proof of theorem 4.

*Proof.* Let $t \in [0, T]$ and $n_1, n_2$ denote two different UAVs. We again assume that $n_2 > n_1$, meaning that the $n_2^{th}$-UAV is following the $n_1^{th}$-UAV. Let $\mathbf{P} = [\mathbf{P}_1...\mathbf{P}_K]$ be a complete path with $\Delta_A$ and $\Delta_B$ its departure and arrival areas, all of which fulfill left of equation (32). First we note that we only need to prove that $V_{n_1}(t)V_{n_2}(t) \ge 2\rho_c$, as left of equation (5) in assumption 1 transforms this statement into $R_{n_1}(t) \ne R_{n_2}(t)$.

Lemma 4 and equation (23) show that

$$|S_n(S(t)) - S_{n_1}(S(t))| \ge 2\rho_c\sqrt{2} \quad (19)$$

And to prove that $V_{n_1}(t)V_{n_2}(t) \ge 2\rho_c$ we consider three possibilities, namely both UAVs are at time $t$: in the same line segment, in two consecutive line segments or in two distant line segments.

1) When both UAVs are in the same line segment, equations (17) and (16) show that

$$V_{n_1}(t)V_{n_2}(t) = S_{n_2}(S(t)) - S_{n_1}(S(t))$$

$$\ge 2\rho_c\sqrt{2} \ge 2\rho_c$$

2) When both UAVs are in consecutive line segments, let $J$ denote their intersecting point. Equations (17) and (16) prove that

$$V_{n_1}(t)J + JV_{n_2}(t) = S_{n_2}(S(t)) - S_{n_1}(S(t))$$

$$\ge 2\rho_c\sqrt{2}$$

Thanks to left of equation (32), consecutive line segments have acute bending

$$\left| \angle \left( \overrightarrow{V_{n_1}(t)J}, \overrightarrow{V_{n_1}(t)J} \right) \right| \le \frac{\pi}{2}$$

Lemma 3 shows that $V_{n_1}(t)V_{n_2}(t) \ge 2\rho_c$

3) When both UAVs are in non-consecutive line segments, then their mutual distance is greater than the distance between these line segments. This distance is lower bounded by $2\rho_c$, thanks to left of equation (32).

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

E. Proof of theorem 5 (p. 9)

The definition below gives a more formal definitions of $\bowtie$ and $\boxtimes$.

**Definition 1.** Let $D_1$ and $D_2$ be two points with wireless communication capabilities. The symbol $\bowtie$ denotes here the ability to communicate directly.

$$D_1 \bowtie D_2 \Leftrightarrow D_1 D_2 \le \rho_R \quad (20)$$

Let $D'_j$ a set of points. The symbol $\boxtimes$ denotes here the ability to communicate using a routing communication path.

$$D_1 \boxtimes D_2, \Leftrightarrow \exists D'_{j_1} \dots D'_{j_r}, \text{ such that}$$

$$D_1 \bowtie D'_{j_1} \ D'_{j_1} \bowtie D'_{j_2}, \dots, D'_{j_{r-1}} \bowtie D'_{j_r}, \text{ and } D'_{j_r} \bowtie D_2 \quad (21)$$

$\boxtimes$ is regarded as a reflexive and symmetric relation. $\bowtie$ is transitive and also reflexive and symmetric, it is therefore regarded as an *equivalence relation*.

Similarly to lemma 4, we prove that consecutive UAVs are not too far apart.
**Lemma 5.** Let $n$ and $n+1$ denote two consecutive drones.

$$0 \le S_n(s) - S_{n+1}(s) \le \Delta S_r \quad (22)$$

*Proof.* Left of equation (22) is only claiming that the $(n+1)^{th}$ is following the $n^{th}$, which is true. Right of equation (22) depends on the value of $s$, and three possibilities are considered.

1) When $s \le n(\Delta S_r - \Delta S_c)$ that is smaller than $L_{0,n+1}$, then either both UAVs are on their parking slots or the first one is leaving the parking slot.

In the first outcome, $S_n(s) - S_{n+1}(s)$ is smaller than $\Delta S_c$ which is smaller than $\Delta S_r$.

In the second outcome,

$$\begin{aligned} S_n(s) - S_{n+1}(s) &= \{-(n-1)\Delta S_c\} - \{s - n(\Delta S_r - \Delta S_c)\} \\ &\le \Delta S_r \end{aligned}$$

2) When $s \ge \mathcal{L}(\mathbf{P})+(n-1)\Delta S_r+(N-n)\Delta S_c$ that is greater than $L_{K+1,n+1}$ then either both UAVs are on their parking slots or the last one is reaching the parking slot.

In the first outcome, $S_n(s) - S_{n+1}(s)$ is smaller than $\Delta S_c$ which is smaller than $\Delta S_r$.

In the second outcome,

$$\begin{aligned} S_n(s) - S_{n+1}(s) &= \{\mathcal{L}(\mathbf{P}) + (N-n)\Delta S_c\} - \{s - n\Delta S_r\} \\ &\le \Delta S_r \end{aligned}$$

3) When $s \in [L_{0,n+1}, L_{K+1,n}]$, then both UAVs are moving and

$$S_n(s) - S_{n+1}(s) = \Delta S_r$$

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

**Lemma 6.** Let $a_i$ be an increasing sequence of $I$ numbers and $\overrightarrow{e_i}$ be unitary vectors. Let $\overrightarrow{f}(x)$ be a function defined as

$$\overrightarrow{f}(x) = \sum_{i=1}^{I-1} \mathcal{R}_{a_i}^{a_{i+1}}(x) \overrightarrow{e_i}$$

Then $\overrightarrow{f}(x)$ is a contraction mapping.

$$\left\| \overrightarrow{f}(x_1) - \overrightarrow{f}(x_2) \right\| \le |x_1 - x_2| \quad (23)$$

where $\| \|$ is the norm.

*Proof.* With no less of generality, we assume that $x_1 < x_2$.

• First we consider that both $x_1$ and $x_2$ are in $[a_1, a_I]$. Let $i, j$ such that $x_1 \in [a_i, a_{i+1})$ and $x_2 \in [a_j, a_{j+1})$, we get

$$\begin{aligned} \overrightarrow{f}(x_2) - \overrightarrow{f}(x_1) = (x_2 - a_j) \overrightarrow{e_j} \\ + \sum_{k=i+1}^{j-1} (a_{k+1} - a_k) \overrightarrow{e_k} + (a_i - x_1) \overrightarrow{e_i} \end{aligned}$$

Because the vectors $\overrightarrow{e_k}$ are unitary and because of the triangle inequality, we have

$$\begin{aligned} \left\| \overrightarrow{f}(x_2) - \overrightarrow{f}(x_1) \right\| &\le (x_2 - a_j) + \sum_{k=i+1}^{j-1} (a_{k+1} - a_k) + (a_i - x_1) \\ &= x_2 - x_1 \end{aligned}$$

• If $x_1 \le a_1$, $f(x_1) = f(a_1)$ and by applying equation (23) to $(a_1, x_2)$, we have

$$\left\| \overrightarrow{f}(x_2) - \overrightarrow{f}(x_1) \right\| \le x_2 - a_1 \le x_2 - x_1$$

• If $x_2 \ge a_I$, $f(x_2) = f(a_I)$ and by applying equation (23) to $(x_1, a_I)$, we have

$$\left\| \overrightarrow{f}(x_2) - \overrightarrow{f}(x_1) \right\| \le a_I - x_1 \le x_2 - x_1$$

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

Below is the proof of theorem 5.

*Proof.* Let $\mathbf{P}$ be a complete path and $N > \frac{\mathcal{L}(\mathbf{P})}{\Delta S_r} - 1$. The proof is in four parts, dealing first with connectivity among UAVs, then with connectivity first to A, then to B, and finally with A or B.

1) To prove that all UAVs are connected to each other, it is sufficient to prove that each UAV is connected to its follower when it has one, that is

$$\forall n \in \{1...N-1\}, R_n(t) \doteqdot R_{n+1}(t)$$

Let $n \in \{1...N-1\}$ refer to a UAV. Equation (17), lemmas 5 and 6 yield an upper bound on $V_n(t)V_{n+1}(t)$.

$$\begin{aligned} V_n(t)V_{n+1}(t) &= \left\| \overrightarrow{AV} (S_{n+1}(S(t)) - \overrightarrow{AV} (S_n(S(t))) \right\| \\ &\le |S_{n+1}(S(t)) - S_n(S(t))| \\ &\le \Delta S_r \end{aligned}$$

The triangle inequality, equation (23) and assumptions 1 and 3 prove that this UAV is directly connected with its follower.

$$\begin{aligned} R_n(t)R_{n+1}(t) &\le R_n(t)V_n(t) + V_n(t)V_{n+1}(t) + R_{n+1}(t)V_{n+1}(t) \\ &\le 2\rho_c + \Delta S_r = \rho_r \end{aligned}$$

2) We prove here that connectivity to A is ensured when

$$S(t) \in [0, N\Delta S_r] \quad (24)$$
This interval comes from the following calculation.

$$[0, N\Delta S_r] \subset \bigcup_{n=1}^{N} [L_{1,n} - \Delta S_r, L_{1,n} + \Delta S_r]$$

Hence to prove the statement, it suffices to show for all $n$ that

$$S(t) \in [L_{1,n} - \Delta S_r, L_{1,n} + \Delta S_r] \Rightarrow R_n(t) \not\sqcap A$$

Let $n \in \{1...N\}$ and $t$ such that $S(t)$ belongs to $[L_{1,n} - \Delta S_r, L_{1,n} + \Delta S_r]$.

Because $A = V(0) = V(S_n(L_{1,n}))$, equation (17), lemmas 5 and 6 show that

$$ \begin{aligned} V_n(t)A &= \|V(S_n(S(t)) - V(S_n(L_{1,n})))\| \\ &\le |S_n(S(t)) - S_n(L_{1,n})| \\ &\le |S(t) - L_{1,n}| \le \Delta S_r \end{aligned} $$

The triangle inequality, equation (23) and assumptions 1 and 3 prove that $R_n(t) \not\sqcap A$.

3) We prove here that connectivity to $B$ is ensured when

$$S(t) \in [\mathcal{L}(\mathbf{P}) - \Delta S_r, \mathcal{L}(\mathbf{P}) + N\Delta S_r] \quad (25)$$

This interval comes from the following calculation.

$$[\mathcal{L}(\mathbf{P}) - \Delta S_r, \mathcal{L}(\mathbf{P}) + N\Delta S_r] \subset \bigcup_{n=1}^{N} [L_{K,n} - \Delta S_r, L_{K,n} + \Delta S_r]$$

Hence to prove the statement, it suffices to show for all $n$ that

$$S(t) \in [L_{K,n} - \Delta S_r, L_{K,n} + \Delta S_r] \Rightarrow R_n(t) \not\sqcap B$$

Let $n \in \{1...N\}$ and $t$ such that $S(t)$ belongs to $[\mathcal{L}(\mathbf{P}) - \Delta S_r, \mathcal{L}(\mathbf{P}) + N\Delta S_r]$.

Because $B = V(\mathcal{L}(\mathbf{P})) = V(S_n(L_{K,n}))$, equation (17), lemmas 5 and 6 again show:

$$V_n(t)B = \|V(S_n(S(t)) - V(S_n(L_{K,n})))\| \le \Delta S_r$$

The triangle inequality, equation (23) and assumptions 1 and 3 prove that $R_n(t) \not\sqcap B$.

4) All-time connectivity (i.e. $\forall n, t$, $R_n(t) \not\sqcap A$ or $R_n(t) \not\sqcap B$) is directly derived from equations (24) and (25) when

$$ \begin{aligned} & [0, N\Delta S_r] \cup [\mathcal{L}(\mathbf{P}) - \Delta S_r, \mathcal{L}(\mathbf{P}) + N\Delta S_r] \\ & \supset [0, \mathcal{L}(\mathbf{P}) + (N-1)\Delta S_r] \end{aligned} $$

that is when

$$N\Delta S_r \ge \mathcal{L}(\mathbf{P}) - \Delta S_r$$

which is equivalent to $N \ge \frac{\mathcal{L}(\mathbf{P})}{\Delta S_r} - 1$.

□