# Learning-‘N-Flying: A Learning-based, Decentralized Mission Aware UAS
Collision Avoidance Scheme

Alëna Rodionova<EMAIL_ADDRESS>0000-0001-8455-9917 University
of PennsylvaniaDepartment of Electrical and Systems
EngineeringPhiladelphiaPA19104USA ,  Yash Vardhan Pant<EMAIL_ADDRESS>University of California, BerkeleyDepartment of Electrical Engineering and
Computer SciencesBerkeleyCAUSA ,  Connor Kurtz<EMAIL_ADDRESS>Oregon
State UniversitySchool of Electrical Engineering and Computer
ScienceCorvallisORUSA ,  Kuk Jang<EMAIL_ADDRESS>University of
PennsylvaniaDepartment of Electrical and Systems
EngineeringPhiladelphiaPA19104USA ,  Houssam Abbas
<EMAIL_ADDRESS>Oregon State UniversitySchool of Electrical
Engineering and Computer ScienceCorvallisORUSA and  Rahul Mangharam
<EMAIL_ADDRESS>University of PennsylvaniaDepartment of Electrical and
Systems EngineeringPhiladelphiaPA19104USA

(2021)

###### Abstract.

Urban Air Mobility, the scenario where hundreds of manned and UAS (UAS) carry
out a wide variety of missions (e.g. moving humans and goods within the city),
is gaining acceptance as a transportation solution of the future. One of the
key requirements for this to happen is safely managing the air traffic in
these urban airspaces. Due to the expected density of the airspace, this
requires fast autonomous solutions that can be deployed online. We propose
Learning-‘N-Flying (LNF) a multi-UAS Collision Avoidance (CA) framework. It is
decentralized, works on-the-fly and allows autonomous UAS managed by different
operators to safely carry out complex missions, represented using Signal
Temporal Logic, in a shared airspace. We initially formulate the problem of
predictive collision avoidance for two UAS as a mixed-integer linear program,
and show that it is intractable to solve online. Instead, we first develop
Learning-to-Fly (L2F) by combining: a) learning-based decision-making, and b)
decentralized convex optimization-based control. LNF extends L2F to cases
where there are more than two UAS on a collision path. Through extensive
simulations, we show that our method can run online (computation time in the
order of milliseconds), and under certain assumptions has failure rates of
less than $1\%$ in the worst-case, improving to near $0\%$ in more relaxed
operations. We show the applicability of our scheme to a wide variety of
settings through multiple case studies.

Collision avoidance, unmanned aircraft systems, temporal logic, robustness,
neural network, Model Predictive Control

††copyright: acmcopyright††journalyear: 2021††doi:
nn.nnnn/nnnnnnn.nnnnnnn††journal: JACM††journalvolume:
Unassigned††journalnumber: Unassigned††publicationmonth: 1††ccs: Computer
systems organization Robotic control††ccs: Computing methodologies Neural
networks

##  1\. Introduction

With the increasing footprint and density of metropolitan cities, there is a
need for new transportation solutions that can move goods and people around
rapidly and without further stressing road networks. UAM (UAM) (Hackenberg,
2018) is a one such concept quickly gaining acceptance (NASA, 2018) as a means
to improve connectivity in metropolitan cities. In such a scenario, hundreds
of Autonomous manned and UAS (UAS) will carry goods and people around the
city, while also performing a host of other missions. A critical step towards
making this a reality is safe traffic management of the all the UAS in the
airspace. Given the high expected UAS traffic density, as well as the short
timescales of the flights, UTM (UTM) needs to be autonomous, and guarantee a
high degree of safety, and graceful degradation in cases of overload. The
first requirement for automated UTM is that its algorithms be able to
accommodate a wide variety of missions, since the different operators have
different goals and constraints. The second requirement is that as the number
of UAS in the airspace increases, the runtimes of the UTM algorithms does not
blow up - at least up to a point. Thirdly, it must provide guaranteed
collision avoidance in most use cases, and degrade gracefully otherwise; that
is, the determination of whether it will be able to deconflict two UAS or not
must happen sufficiently fast to alert a higher-level algorithm or a human
operator, say, who can impose additional constraints.

In this paper we introduce and demonstrate a new algorithm, LNF, for multi-UAS
planning in urban airspace. LNF starts from multi-UAS missions expressed in
Signal Temporal Logic (STL), a formal behavioral specification language that
can express a wide variety of missions and supports automated reasoning. In
general, a mission will couple various UAS together through mutual separation
constraints, and this coupling can cause an exponential blowup in computation.
To avoid this, LNF lets every UAS plan independently of others, while ignoring
the mutual separation constraints. This independent planning step is performed
using Fly-by-Logic, our previous UAS motion planner. An online collision
avoidance procedure then handles potential collisions on an as-needed basis,
i.e. when two UAS that are within communication range detect a future
collision between their pre-planned trajectories. Even online optimal
collision avoidance between two UAS requires solving a Mixed-Integer Linear
Program (MILP). LNF avoids this by using a recurrent neural network which maps
the current configuration of the two UAS to a sequence of discrete decisions.
The network’s inference step runs much faster (and its runtime is much more
stable) than running a MILP solver. The network is trained offline on
solutions generated by solving the MILP. To generalize from two UAS collision
avoidance to multi-UAS, we introduce another component to LNF: Fly-by-Logic
generates trajectories that satisfy their STL missions, and a robustness tube
around each trajectory. As long as the UAS is within its tube, it satisfies
its mission. To handle a collision between 3 or more UAS, LNF shrinks the
robustness tube for each trajectory in such a way that sequential 2-UAS
collision avoidance succeeds in deconflicting all the UAS.

We show that LNF is capable of successfully resolving collisions between UAS
even within high-density airspaces and the short timescales, which are exactly
the scenarios expected in UAM. LNF creates opportunities for safer UAS
operations and therefore safer UAM.

##### Contributions of this work

In this paper, we present an online, decentralized and mission-aware UAS CA
(CA) scheme that combines machine learning-based decision-making with Model
Predictive Control (MPC). The main contributions of our approach are:

  1. (1)

It systematically combines machine learning-based decision-making111With the
offline training and fast online application of the learned policy, see
Sections 4.2 and 6.2. with an MPC-based CA controller. This allows us to
decouple the usually hard-to-interpret machine learning component and the
safety-critical low-level controller, and also repair potentially unsafe
decisions by the ML components. We also present a sufficient condition for our
scheme to successfully perform CA.

  2. (2)

LNF collision avoidance avoids the live-lock condition where pair-wise CA
continually results in the creation of collisions between other pairs of UAS.

  3. (3)

Our formulation is mission-aware, i.e. CA does not result in violation of the
UAS mission. As shown in (Rodionova et al., 2020), this also enables faster
STL-based mission planning for a certain class of STL specifications.

  4. (4)

Our approach is computationally lightweight with a computation time of the
order of $10ms$ and can be used online.

  5. (5)

Through extensive simulations, we show that the worst-case failure rate of our
method is less than $1\%$, which is a significant improvement over other
approaches including (Rodionova et al., 2020).

Figure 1. Two UAS communicating their planned trajectories, and cooperatively
maneuvering within their robustness tubes to avoid a potential collision in
the future.

##### Related Work.

UTM and Automatic Collision Avoidance approaches Collision avoidance (CA) is a
critical component of UAS Traffic Management (UTM). The NASA/FAA Concept of
Operations (Administration, 2018) and (Li et al., 2018) present airspace
allocation schemes where UAS are allocated airspace in the form of non-
overlapping space-time polygons. Our approach is less restrictive and allows
overlaps in the polygons, but performs online collision avoidance on an as-
needed basis. A tree search-based planning approach for UAS CA is explored in
(Chakrabarty et al., 2019). The next-gen CA system for manned aircrafts,
ACAS-X (Kochenderfer et al., 2012) is a learning-based approach that provides
vertical separation recommendations. ACAS-Xu (Manfredi and Jestin, 2016)
relies on a look-up table to provide high-level recommendations to two UAS. It
restricts desired maneuvers for CA to the vertical axis for cooperative
traffic, and the horizontal axis for uncooperative traffic. While we consider
only the cooperative case in this work, our method does not restrict CA
maneuvers to any single axis of motion. Finally, in its current form, ACAS-Xu
also does not take into account any higher-level mission objectives, unlike
our approach. This excludes its application to low-level flights in urban
settings. The work in (Fabra et al., 2019) presents a decentralized, mission
aware CA scheme, but requires time of the order of seconds for the UAS to
communicate and safely plan around each other, whereas our approach has a
computation times in milliseconds.

Multi-agent planning with temporal logic objectives Multi-agent planning for
systems with temporal logic objectives has been well studied as a way of safe
mission planning. Approaches for this usually rely on grid-based
discretization of the workspace (Saha et al., 2014; DeCastro et al., 2017), or
a simplified abstraction of the dynamics of the agents (Desai et al., 2017;
Aksaray et al., 2016). (Ma et al., 2016) combines a discrete planner with a
continuous trajectory generator. Some methods (Kloetzer and Belta, 2008;
Fainekos et al., 2005; Kloetzer and Belta, 2006) work for subsets of Linear
Temporal Logic (LTL) that do not allow for explicit timing bounds on the
mission requirements. The work in (Saha et al., 2014) allows some explicit
timing constraints. However, it restricts motion to a discrete set of motion
primitives. The predictive control method of (Raman et al., 2014a) uses the
full STL grammar; it handles a continuous workspace and linear dynamics of
robots, however its reliance on mixed-integer encoding (similar to (Saha and
Julius, 2016; Karaman and Frazzoli, 2011)) limit its practical use as seen in
(Pant et al., 2017). The approach of (Pant et al., 2018) instead relies on
optimizing a smooth (non-convex) function for generating trajectories for
fleets of multi-rotor UAS with STL specifications. While these methods can
ensure safe operation of multi-agent systems, these are all centralized
approaches, i.e. require joint planning for all agents and do not scale well
with the number of agents. In our framework, we use the planning method of
(Pant et al., 2018), but we let each UAS plan independently of each other in
order for the planning to scale. We ensure the safe operation of all UAS in
the airspace through the use of our predictive collision avoidance scheme.

##### Organization of the paper

The rest of the paper is organized as follows. Section 2 covers preliminaries
on Signal Temporal Logic and trajectory planning. In Section 3 we formalize
the two-UAS CA problems, state our main assumptions, and develop a baseline
centralized solution via a MILP formulation. Section 4 presents a
decentralized learning-based collision avoidance framework for UAS pairs. In
Section 5 we extend this approach to support cases when CA has to be performed
for three or more UAS. We evaluate our methods through extensive simulations,
including three case studies in Section 6. Section 7 concludes the paper.

##  2\. Preliminaries: Signal Temporal Logic-based UAS planning

##### Notation.

For a vector $x=(x_{1},\ldots,x_{m})\in\mathbb{R}^{m}$,
$\|x\|_{\infty}=\max_{i}|x_{i}|$.

Figure 2. Step-wise explanation and visualization of the framework. Each UAS
generates its own trajectories to satisfy a mission expressed as a Signal
Temporal Logic (STL) specification, e.g. regions in green are regions of
interest for the UAS to visit, and the no-fly zone corresponds to
infrastructure that all the UAS must avoid. When executing these trajectories,
UAS communicate their trajectories to others in range to detect any collisions
that may happen in the near future. If a collision is detected, the two UAS
execute a conflict resolution scheme that generates a set of additional
constraints that the UAS must satisfy to avoid the collision. A co-operative
CA-MPC controls the UAS to best satisfy these constraints while ensuring each
UAS’s STL specification is still satisfied. This results in new trajectories
(in solid pink and blue) that will avoid the conflict and still stay within
the predefined robustness tubes.

###  2.1. Introduction to Signal Temporal Logic and its Robustness

Let $\mathbb{T}=\\{0,dt,2dt,3dt\ldots\\}$ be a discrete time domain with
sampling period $dt$ and let $\mathcal{X}\subset\mathbb{R}^{m}$ be the state
space. A signal is a function $\mathbf{x}:E\rightarrow\mathcal{X}$ where
$E\subseteq\mathbb{T}$; The $k^{\text{th}}$ element of $\mathbf{x}$ is written
$x_{k}$, $k\geq 0$. Let $\mathcal{X}^{\mathbb{T}}$ be the set of all signals.

Signal specifications are expressed in Signal Temporal Logic (STL) (Maler and
Nickovic, 2004), of which we give an informal description here. An STL formula
$\varphi$ is created using the following grammar:

$\varphi:=\top~{}|~{}p~{}|~{}\neg\varphi~{}|~{}\varphi_{1}\vee\varphi_{2}~{}|~{}\Diamond_{[a,b]}\varphi~{}|~{}\square_{[a,b]}\varphi~{}|~{}\varphi_{1}\mathcal{U}_{[a,b]}\varphi_{2}$

Here, $\top$ is logical True, $p$ is an atomic proposition, i.e. a basic
statement about the state of the system, $\neg,\vee$ are the usual Boolean
negation and disjunction, $\Diamond$ is Eventually, $\square$ is Always and
$\mathcal{U}$ is Until. It is possible to define the $\Diamond$ and $\square$
in terms of Until $\mathcal{U}$, but we make them base operations because we
will work extensively with them.

An STL specification $\varphi$ is interpreted over a signal, e.g. over the
trajectories of quad-rotors, and evaluates to either True or False. For
example, operator Eventually ($\Diamond$) augmented with a time interval
$\Diamond_{[a,b]}\varphi$ states that $\varphi$ is True at some point within
$[a,b]$ time units. Operator Always ($\square$) would correspond to $\varphi$
being True everywhere within time $[a,b]$. The following example demonstrates
how STL captures operational requirements for two UAS:

###### Example 1.

(A two UAS timed reach-avoid problem) Two quad-rotor UAS are tasked with a
mission with spatial and temporal requirements in the workspace schematically
shown in Figure 2:

  1. (1)

Each of the two UAS has to reach its corresponding Goal set (shown in green)
within a time of $6$ seconds after starting. UAS $j$ (where $j\in\\{1,2\\}$),
with position denoted by $\mathbf{p}_{j}$, has to satisfy:
$\varphi_{\text{reach},j}=\Diamond_{[0,6]}(\mathbf{p}_{j}\in\text{Goal}_{j})$.
The Eventually operator over the time interval $[0,6]$ requires UAS $j$ to be
inside the set $\text{Goal}_{j}$ at some point within $6$ seconds.

  2. (2)

The two UAS also have an Unsafe (in red) set to avoid, e.g. a no-fly zone. For
each UAS $j$, this is encoded with Always and Negation operators:

$\varphi_{\text{avoid},j}=\square_{[0,6]}\neg(\mathbf{p}_{j}\in\text{Unsafe})$

  3. (3)

Finally, the two UAS should be separated by at least $\delta$ meters along
every axis of motion:

$\varphi_{\text{separation}}=\square_{[0,6]}||\mathbf{p}_{1}-\mathbf{p}_{2}||_{\infty}\geq\delta$

The 2-UAS timed reach-avoid specification is thus:

(1) $\varphi_{\text{reach-
avoid}}=\bigwedge_{j=1}^{2}(\varphi_{\text{reach},j}\wedge\varphi_{\text{avoid},j})\wedge\varphi_{\text{separation}}$

To satisfy $\varphi$ a planning method generates trajectories $\mathbf{p}_{1}$
and $\mathbf{p}_{2}$ of a duration at least $hrz(\varphi)=6$s, where
$hrz(\varphi)$ is the time horizon of $\varphi$. If the trajectories satisfy
the specification, i.e. $(\mathbf{p}_{1},\,\mathbf{p}_{2})\models\varphi$,
then the specification $\varphi$ evaluates to True, otherwise it is False. In
general, an upper bound for the time horizon can be computed as shown in
(Raman et al., 2014a). In this work, we consider specifications such that the
horizon is bounded. More details on STL can be found in (Maler and Nickovic,
2004) or (Raman et al., 2014a). In this paper, we consider discrete-time STL
semantics which are defined over discrete-time trajectories.

The Robustness value (Fainekos and Pappas, 2009) $\rho_{\varphi}(\mathbf{x})$
of an STL formula $\varphi$ with respect to the signal $\mathbf{x}$ is a real-
valued function of $\mathbf{x}$ that has the important following property:

###### Theorem 2.1.

(Fainekos and Pappas, 2009) (i) For any
$\mathbf{x}\in\mathcal{X}^{\mathbb{T}}$ and STL formula $\varphi$, if
$\rho_{\varphi}(\mathbf{x})<0$ then $\mathbf{x}$ violates $\varphi$, and if
$\rho_{\varphi}(\mathbf{x})>0$ then $\mathbf{x}$ satisfies $\varphi$. The case
$\rho_{\varphi}(\mathbf{x})=0$ is inconclusive.

(ii) Given a discrete-time trajectory $\mathbf{x}$ such that
$\mathbf{x}\models\varphi$ with robustness value
$\rho_{\varphi}(\mathbf{x})=r>0$, then any trajectory $\mathbf{x}^{\prime}$
that is within $r$ of $\mathbf{x}$ at each time step, i.e.
$||x_{k}-x^{\prime}_{k}||_{\infty}<r,\,\forall k\in\mathbb{H}$, is such that
$\mathbf{x}^{\prime}\models\varphi$ (also satisfies $\varphi$).

###  2.2. UAS planning with STL specifications

Fly-by-logic (Pant et al., 2017, 2018) generates trajectories by centrally
planning for fleets of UAS with STL specifications, e.g. the specification
$\varphi_{\textit{reach-avoid}}$ of example 1. It maximizes the robustness
function by picking waypoints for all UAS through a centralized, non-convex
optimization.

While successful in planning for multiple multi-rotor UAS, performance
degrades as the number of UAS increases, in particular because for $N$ UAS,
$N\choose 2$ terms are needed for specifying the pair-wise separation
constraint $\varphi_{\textit{separation}}$. For these reasons, the method
cannot be used for real-time planning. In this work, we use the underlying
optimization of (Pant et al., 2018) to generate trajectories, but ignore the
mutual separation requirement, allowing each UAS to independently (and in
parallel) solve for their own STL specification. For the timed reach-avoid
specification (1) in example 1, this is equivalent to each UAS generating its
own trajectory to satisfy
$\varphi_{j}=\varphi_{\textit{reach},j}\wedge\varphi_{\textit{avoid},j}$,
independently of the other UAS. Ignoring the collision avoidance requirement
$\varphi_{\textit{separation}}$ in the planning stage allows for the
specification of (1) to be decoupled across UAS. Therefore, this approach
requires online UAS collision avoidance. This is covered in the following
section.

##  3\. Problem formulation: Mission aware UAS Collision Avoidance

We consider the case where two UAS flying pre-planned trajectories are
required to perform collision avoidance if their trajectories are on path for
a conflict.

###### Definition 1.

2-UAS Conflict: Two UAS, with discrete-time positions $\mathbf{p}_{1}$ and
$\mathbf{p}_{2}$ are said to be in conflict at time step $k$ if
$||p_{1,k}-p_{2,k}||_{\infty}<\delta$, where $\delta$ is a predefined minimum
separation distance222A more general polyhedral constraint of the form
$M(p_{1,k}-p_{2,k})<q$ can be used for defining the conflict.. Here, $p_{j,k}$
represents the position of UAS $j$ at time step $k$.

While flying their independently planned trajectories, two UAS that are within
communication range share an $H$-step look-ahead of their trajectories and
check for a potential conflict in those $H$ steps. We assume the UAS can
communicate with each other in a manner that allows for enough advance notice
for avoiding collisions, e.g. using 5G technology. While the details of this
are beyond the scope of this paper, we formalize this assumption as follows:

###### Assumption 1.

The two UAS in conflict have a communication range that is at least greater
than their $n$-step forward reachable set (Dahleh et al., 2004) ($n\geq 1$)
333This set can be computed offline as we know the dynamics and actuation
limits for each UAS.. That is, the two UAS will not collide immediately in at
least the next $n$-time steps, enabling them to communicate with each other to
avoid a collision. Here $n$ is potentially dependent on the communication
technology being used.

###### Definition 2.

Robustness tube: Given an STL formula $\varphi$ and a discrete-time position
trajectory $\mathbf{p}_{j}$ that satisfies $\varphi$ (with associated
robustness $\rho$), the (discrete) robustness tube around $\mathbf{p}_{j}$ is
given by $\mathbf{P}_{j}=\mathbf{p}_{j}\oplus\mathbb{B}_{\rho}$, where
$\mathbb{B}_{\rho}$ is a 3D cube with sides $2\rho$ and $\oplus$ is the
Minkowski sum operation ($A\oplus B:=\\{a+b\;|\;a\in A,b\in B\\}$). We say the
radius of this tube is $\rho$ (in the inf-norm sense).

Robustness tube defines the space around the UAS trajectory, such that as long
as the UAS stays within its robustness tube, it will satisfy STL specification
for which it was generated. See examples of the robustness tubes in Figures 1
and 2.

The following assumption relates the minimum allowable radius $\rho$ of the
robustness tube to the minimum allowable separation $\delta$ between two UAS.

###### Assumption 2.

For each of the two UAS in conflict, the radius of the robustness tube is
greater than $\delta/2$, i.e. $\min(\rho_{1},\rho_{2})\geq\delta/2$ where
$\rho_{1}$ and $\rho_{2}$ are the robustness of UAS 1 and 2, respectively.

This assumption defines the case where the radius of the robustness tube is
wide enough to have two UAS placed along opposing edges of their respective
tubes and still achieve the minimum separation between them. We assume that
all the trajectories generated by the independent planning have sufficient
robustness to satisfy this assumption (see Sec. 2.2). Now we define the
problem of collision avoidance with satisfaction of STL specifications:

###### Problem 1.

Given two planned $H$-step UAS trajectories $\mathbf{p}_{1}$ and
$\mathbf{p}_{2}$ that have a conflict, the collision avoidance problem is to
find a new sequence of positions $\mathbf{p}_{1}^{\prime}$ and
$\mathbf{p}_{2}^{\prime}$ that meet the following conditions:

(2a) $\displaystyle||p_{1,k}^{\prime}-p_{2,k}^{\prime}||\geq\delta,\,$
$\displaystyle\forall k\in\\{0,\dotsc,H\\}$ (2b) $\displaystyle
p_{j,k}^{\prime}\in P_{j,k},\,$ $\displaystyle\forall
k\in\\{0,\dotsc,H\\},\,\forall j\in\\{1,2\\}.$

That is, we need a new trajectory for each UAS such that they achieve minimum
separation distance and also stay within the robustness tube around their
originally planned trajectories.

##### Convex constraints for collision avoidance

Let $z_{k}=p_{1,k}-p_{2,k}$ be the difference in UAS positions at time step
$k$. For two UAS not to be in conflict, we need

(3) $z_{k}\not\in\mathbb{B}_{\delta/2},\ \forall k\in\\{0,\ldots,H\\},$

This is a non-convex constraint. For a computationally tractable controller
formulation which solves Problem 1, we define convex constraints that when
satisfied imply Equation (3). The $3$D cube $\mathbb{B}_{\delta/2}$ can be
defined by a set of linear inequality constraints of the form
$\widetilde{M}^{i}z\leq\widetilde{q}^{i},\,\forall i\in\\{1,\ldots,6\\}$.
Equation (3) is satisfied when $\exists
i\,|\widetilde{M}^{i}z>\widetilde{q}_{i}$. Let $M=-\widetilde{M}$ and
$q=-\widetilde{q}$, then $\forall i\in\\{1,\ldots,6\\}$,

(4)
$M^{i}(p_{1,k}-p_{2,k})<{q}^{i}\Rightarrow(p_{1,k}-p_{2,k})\not\in\mathbb{B}_{\delta/2}$

Intuitively, picking one $i$ at time step $k$ results in a configuration (in
position space) where the two UAS are separated in one of two ways along one
of three axes of motion444Two ways along one of three axes defines $6$
options, $i\in\\{1,\ldots,6\\}$.. For example, if at time step $k$ we select
$i$ with corresponding $M^{i}=[0,0,1]$ and $q^{i}=-\delta$, it implies that
UAS 2 flies over UAS 1 by $\delta$ meters, and so on.

##### A Centralized solution via a MILP formulation

Here, we formulate a MILP (MILP) to solve the two UAS CA problem of problem 1
in a predictive, receding horizon manner. For the formulation, we consider a
$H$-step look ahead that contains the time steps where the two UAS are in
conflict. Let the dynamics of either UAS555For simplicity we assume both UAS
have identical dynamics associated with multi-rotor robots, however our
approach would work otherwise. be of the form $x_{k+1}=Ax_{k}+Bu_{k}$. At each
time step $k$, the UAS state is defined as
$x_{k}=[p_{k},\,v_{k}]^{T}\in\mathbb{R}^{6}$, where $p$ and $v$ are the UAS
positions and velocities in the 3D space. Let $C$ be the observation matrix
such that $p_{k}=Cx_{k}$. The inputs $u_{k}\in\mathbb{R}^{3}$ are the thrust,
roll and pitch of the UAS. The matrices $A$ and $B$ are obtained through
linearization of the UAS dynamics around hover and discretization in time, see
(Luukkonen, 2011) and (Pant et al., 2015) for more details. Let
$\mathbf{x}_{j}\in\mathbb{R}^{6(H+1)}$ be the pre-planned full state
trajectories, $\mathbf{x}_{j}^{\prime}\in\mathbb{R}^{6(H+1)}$ the new full
state trajectories and $\mathbf{u}_{j}^{\prime}\in\mathbb{R}^{3H}$ the new
controls to be computed for the UAS $j=1,2$. Let
$\mathbf{b}\in\\{0,1\\}^{6(H+1)}$ be binary decision variables, and $\mu$ is a
large positive number, then the MILP problem is defined as:

(5)
$\displaystyle\min_{\mathbf{u}_{1}^{\prime},\,\mathbf{u}_{2}^{\prime},\,\mathbf{b}}J(\mathbf{x}_{1}^{\prime},\,\mathbf{u}_{1}^{\prime},\,\mathbf{x}_{2}^{\prime},\,\mathbf{u}_{2}^{\prime})$
$\displaystyle x_{j,0}^{\prime}$ $\displaystyle=x_{j,0},\,\forall
j\in\\{1,2\\}$ $\displaystyle x_{j,k+1}^{\prime}$
$\displaystyle=Ax_{j,k}^{\prime}+Bu_{j,k}^{\prime},\,\forall
k\in\\{0,\dotsc,H-1\\},\,\forall j\in\\{1,2\\}$ $\displaystyle
Cx^{\prime}_{j,k}$ $\displaystyle\in P_{j,k},\,\forall
k\in\\{0,\dotsc,H\\},\,\forall j\in\\{1,2\\}$ $\displaystyle
M^{i}C\,(x_{1,k}^{\prime}-x_{2,k}^{\prime})$
$\displaystyle\leq{q}_{i}+\mu(1-b^{i}_{k}),\,\forall
k\in\\{0,\dotsc,H\\},\forall i\in\\{1,\dotsc,6\\}$
$\displaystyle\sum_{i=1}^{6}b^{i}_{k}$ $\displaystyle\geq 1,\,\forall
k\in\\{0,\dotsc,H\\}$ $\displaystyle u_{j,k}^{\prime}$ $\displaystyle\in
U,\,\forall k\in\\{0,\dotsc,H\\},\,\forall j\in\\{1,2\\}$ $\displaystyle
x_{j,k}^{\prime}$ $\displaystyle\in X,\,\forall k\in\\{0,\dotsc,H+1\\},\forall
j\in\\{1,2\\}.$

Here $b^{i}_{k}$ encodes action $i=1,\dotsc,6$ taken for avoiding a collision
at time step $k$ which corresponds to a particular side of the cube
$\mathbb{B}_{\delta/2}$. Function $J$ could be any cost function of interest,
we use $J=0$ to turn (5) into a feasibility problem. A solution (when it
exists) to this MILP results in new trajectories
($\mathbf{p}_{1}^{\prime},\,\mathbf{p}_{2}^{\prime}$) that avoid collisions
and stay within their respective robustness tubes of the original
trajectories, and hence are a solution to problem 1.

Such optimization is joint over both UAS. It is impractical as it would either
require one UAS to solve for both or each UAS to solve an identical
optimization that would also give information about the control sequence of
the other UAS. Solving this MILP in an online manner is also intractable, as
we shown in Section 6.2.1.

##  4\. Learning-2-Fly: Decentralized Collision Avoidance for UAS pairs

To solve problem 1 in an online and decentralized manner, we develop our
framework, Learning-to-Fly (L2F). Given a predefined priority among the two
UAS, this combines a learning-based CR (CR) scheme (running aboard each UAS)
that gives us the discrete components of the MILP formulation (5), and a co-
operative collision avoidance MPC for each UAS to control them in a
decentralized manner. We assume that the two UAS can communicate their pre-
planned $N$-step trajectories $\mathbf{p}_{1},\,\mathbf{p}_{2}$ to each other
(refer to Sec. 2.2), and then L2F solves problem 1 by following these steps
(also see Algorithm 1) :

  1. (1)

Conflict resolution: UAS 1 and 2 make a sequence of decisions,
$\mathbf{d}=(d_{0},\ldots,d_{H})$ to avoid collision. Each
$d_{k}\in\\{1,\ldots\,6\\}$ represents a particular choice of $M$ and $q$ at
time step $k$, see eq. (4). Section 4.2 will describe our proposed learning-
based method for picking $d_{k}$.

  2. (2)

UAS 1 CA-MPC: UAS 1 takes the conflict resolution sequence $\mathbf{d}$ from
step 1 and solves a convex optimization to try to deconflict while assuming
UAS 2 maintains its original trajectory. After the optimization the new
trajectory for UAS 1 is sent to UAS 2.

  3. (3)

UAS 2 CA-MPC: (If needed) UAS 2 takes the same conflict resolution sequence
$\mathbf{d}$ from step 1 and solves a convex optimization to try to avoid UAS
1’s new trajectory. Section 4.1 provides more details on CA-MPC steps 2 and 3.

The visualization of the above steps is presented in Figure 2. Such
decentralized approach differs from the centralized MILP approach, where both
the binary decision variables and continuous control variables for each UAS
are decided concurrently.

###  4.1. Distributed and co-operative Collision Avoidance MPC (CA-MPC)

Let $\mathbf{x}_{j}$ be the pre-planned trajectory of UAS $j$,
$\mathbf{x}_{\textit{avoid}}$ be the pre-planned trajectory of the other UAS
to which $j$ must attain a minimum separation, and let
$prty_{j}\in\\{-1,+1\\}$ be the priority of UAS $j$. Assume a decision
sequence $\mathbf{d}$ is given: at each $k$ in the collision avoidance
horizon, the UAS are to avoid each other by respecting (4), namely
$M^{d_{k}}(p_{1,k}-p_{2,k})<{q}^{d_{k}}$. Then each UAS $j=1,2$ solves the
following Collision-Avoidance MPC optimization (CA-MPC): $\text{CA-
MPC}_{j}(\mathbf{x}_{j},\,\mathbf{x}_{avoid},\,\mathbf{P}_{j},\
\mathbf{d},\,prty_{j})$:

(6)
$\displaystyle\min_{\mathbf{u}_{j}^{\prime},\boldsymbol{\lambda}_{j}}\sum_{k=0}^{H}\lambda_{j,k}$
$\displaystyle x_{j,0}^{\prime}$ $\displaystyle=x_{j,0}$ $\displaystyle
x_{j,k+1}^{\prime}$
$\displaystyle=Ax_{j,k}^{\prime}+Bu_{j,k}^{\prime},\,\forall
k\in\\{0,\dotsc,H-1\\}$ $\displaystyle Cx_{j,k}^{\prime}$ $\displaystyle\in
P_{j,k},\,\forall k\in\\{0,\dotsc,H\\}$ $\displaystyle prty_{j}\cdot
M^{d_{k}}C\,(x_{avoid,k}-x_{j,k}^{\prime})$ $\displaystyle\leq
q^{d_{k}}+\lambda_{j,k},\,\forall k\in\\{0,\dotsc,H\\}$
$\displaystyle\lambda_{j,k}$ $\displaystyle\geq 0,\,\forall
k\in\\{0,\dotsc,H\\}$ $\displaystyle u_{j,k}^{\prime}$ $\displaystyle\in
U,\,\forall k\in\\{0,\dotsc,H\\}$ $\displaystyle x_{j,k}^{\prime}$
$\displaystyle\in X,\,\forall k\in\\{0,\dotsc,H+1\\}.$

This MPC optimization tries to find a new trajectory $\mathbf{x}_{j}^{\prime}$
for the UAS $j$ that minimizes the slack variables $\lambda_{j,k}$ that
correspond to violations in the minimum separation constraint
$\eqref{eq:pickaside}$ w.r.t the pre-planned trajectory
$\mathbf{x}_{\textit{avoid}}$ of the UAS in conflict. The constraints in (6)
ensure that UAS $j$ respects its dynamics, input constraints, and state
constraints to stay inside the robustness tube. An objective of $0$ implies
that UAS $j$’s new trajectory satisfies the minimum separation between the two
UAS, see Equation (4)666Enforcing the separation constraint at each time step
can lead to a restrictive formulation, especially in cases where the two UAS
are only briefly close to each other. This does however give us an
optimization with a structure that does not change over time, and can avoid
collisions in cases where the UAS could run across each other more than once
in quick succession (e.g. https://tinyurl.com/arc-case), which is something
ACAS-Xu was not designed for..

CA-MPC optimization for UAS 1: UAS 1, with lower priority, $prty_{1}=-1$,
first attempts to resolve the conflict for the given sequence of decisions
$\mathbf{d}$:

(7)
$\displaystyle(\mathbf{x_{1}^{\prime}},\mathbf{u}_{1}^{\prime},\boldsymbol{\lambda}_{1})$
$\displaystyle=\textbf{CA-
MPC}_{1}(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{d},-1)$

An objective of $0$ implies that UAS 1 alone can satisfy the minimum
separation between the two UAS. Otherwise, UAS 1 alone could not create
separation and UAS 2 now needs to maneuver as well.

CA-MPC optimization for UAS 2: If UAS 1 is unsuccessful at collision
avoidance, UAS 1 communicates its current revised trajectory
$\mathbf{x}_{1}^{\prime}$ to UAS 2, with $prty_{2}=+1$. UAS 2 then creates a
new trajectory $\mathbf{x}_{2}^{\prime}$ (w.r.t the same decision sequence
$\mathbf{d}$):

(8)
$\displaystyle(\mathbf{x}_{2}^{\prime},\mathbf{u}_{2}^{\prime},\boldsymbol{\lambda}_{2})$
$\displaystyle=\textbf{CA-
MPC}_{2}(\mathbf{x}_{2},\mathbf{x}_{1}^{\prime},\mathbf{P}_{2},\mathbf{d},+1)$

Algorithm 1 is designed to be computationally lighter than the MILP approach
(5), but unlike the MILP it is not complete.

Notation :
$(\mathbf{x}^{\prime}_{1},\mathbf{x}^{\prime}_{2},\mathbf{u}_{1}^{\prime},\mathbf{u}_{2}^{\prime})=\textbf{L2F}(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{P}_{2})$

Input: Pre-planned trajectories $\mathbf{x}_{1}$, $\mathbf{x}_{2}$, robustness
tubes $\mathbf{P}_{1}$, $\mathbf{P}_{2}$

Output: Sequence of control signals $\mathbf{u}_{1}^{\prime}$,
$\mathbf{u}_{2}^{\prime}$ for the two UAS, updated trajectories
$\mathbf{x}_{1}^{\prime}$, $\mathbf{x}_{2}^{\prime}$

Get $\mathbf{d}$ from conflict resolution

UAS 1 solves CA-MPC optimization (6):
$(\mathbf{x}_{1}^{\prime},\mathbf{u}_{1}^{\prime},\boldsymbol{\lambda}_{1})=\textbf{CA-
MPC}_{1}(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{d},-1)$

if  _$\sum_{k}\lambda_{1,k}=0$_ then

Done: UAS 1 alone has created separation; Set
$\mathbf{u}_{2}^{\prime}=\mathbf{u}_{2}$

else

UAS 1 transmits solution to UAS 2

UAS 2 solves CA-MPC optimization (6):
$(\mathbf{x}_{2}^{\prime},\mathbf{u}_{2}^{\prime},\boldsymbol{\lambda}_{2})=\textbf{CA-
MPC}_{2}(\mathbf{x}_{2},\mathbf{x}_{1}^{\prime},\mathbf{P}_{2},\mathbf{d},+1)$

if  _$\sum_{k}\lambda_{2,k}=0$_ then

Done: UAS 2 has created separation

else

if  _$||p_{1,k}^{\prime}-p_{2,k}^{\prime}||\geq\delta,\,\forall k=0,\dotsc,H$_
then

Done: UAS 1 and UAS 2 created separation

else

Not done: UAS still violate Equation (2a)

end if

end if

end if

Apply control signals $\mathbf{u}_{1}^{\prime}$, $\mathbf{u}_{2}^{\prime}$ if
Done; else Fail.

Algorithm 1 Learning-to-Fly: Decentralized and cooperative collision avoidance
for two UAS. Also see Figure 2.

The solution of CA-MPC can be defined as follows:

###### Definition 4.0 (Zero-slack solution).

The solution of the CA-MPC optimization (6), is called the zero-slack solution
if for a given decision sequence $\mathbf{d}$ either

1) there exists an optimal solution of (6) such that $\sum_{k}\lambda_{1,k}=0$
or

2) problem (6) is feasible with $\sum_{k}\lambda_{1,k}>0$ and there exists an
optimal solution of (6) such that $\sum_{k}\lambda_{2,k}=0$.

The following Theorem 4.2 defines the sufficient condition for CA and Theorem
4.3 makes important connections between the slack variables in CA-MPC
formulation and binary variables in MILP. Both theorems are direct
consequences of the construction of CA-MPC optimizations. We omit the proofs
for brevity.

###### Theorem 4.2 (Sufficient condition for CA).

Zero-slack solution of (6) implies that the resulting trajectories for two UAS
are non-conflicting and within the robustness tubes of the initial
trajectories777Theorem 4.2 formulates a conservative result as (4) is a convex
under approximation of the originally non-convex collision avoidance
constraint (3). Indeed, non-zero slack $\exists k|\lambda_{2,k}>0$ does not
necessarily imply the violation of the mutual separation requirement (2a). The
control signals $u_{1}^{\prime},u_{2}^{\prime}$ computed by Algorithm 1 can
therefore in some instances still create separation between UAS even when the
conditions of Theorem 4.2 are not satisfied..

###### Theorem 4.3 (Existence of the zero-slack solution).

Feasibility of the MILP problem (5) implies the existence of the zero-slack
solution of CA-MPC optimization (6).

The Theorem 4.3 states that the binary decision variables $b^{i}_{k}$ selected
by the feasible solution of the MILP problem (5), when used to select the
constraints (defined by $M,\,q$) for the CA-MPC formulations for UAS 1 and 2,
imply the existence of a zero-slack solution of (6).

###  4.2. Learning-based conflict resolution

Motivated by Theorem 4.3, we propose to learn offline the conflict resolution
policy from the MILP solutions and then online use already learned policy. To
do so, we use a Long Short-Term Memory (LSTM) (Hochreiter and Schmidhuber,
1997) recurrent neural network augmented with fully-connected layers. LSTMs
perform better than traditional recurrent neural networks on sequential
prediction tasks (Gers et al., 2002).

Figure 3. Proposed LSTM model architecture for CR-S. LSTM layers are shown
unrolled over $H$ time steps. The inputs are $z_{k}$ which are the differences
between the planned UAS positions, and the outputs are decisions $d_{k}$ for
conflict resolution at each time $k$ in the horizon.

The network is trained to map a difference trajectory
$\mathbf{z}=\mathbf{x}_{1}-\mathbf{x}_{2}$ (as in Equation (3)) to a decision
sequence $\mathbf{d}$ that deconflicts pre-planned trajectories
$\mathbf{x}_{1}$ and $\mathbf{x}_{2}$. For creating the training set,
$\mathbf{d}$ is produced by solving the MILP problem (5), i.e. obtaining a
sequence of binary decision variables $\mathbf{b}\in\\{0,1\\}^{6(H+1)}$ and
translating it into the decision sequence
$\mathbf{d}\in\\{1,\ldots,6\\}^{H+1}$.

The proposed architecture is presented in Figure 3. The input layer is
connected to the block of three stacked LSTM layers. The output layer is a
time distributed dense layer with a softmax activation function that produces
the class probability estimate
$\eta_{k}=[\eta_{k}^{1},\ldots,\eta_{k}^{6}]^{\top}$ for each
$k\in\\{0,\ldots,H\\}$, which corresponds to a decision
$d_{k}=\text{argmax}_{i=1,\ldots 6}\eta_{k}^{i}$.

###  4.3. Conflict Resolution Repairing

The total number of possible conflict resolution (CR) decision sequences of
over a time horizon of $H$ steps is $H^{6}$. Learning-based collision
resolution produces only one such CR sequence, and since it is not guaranteed
to be correct, an inadequate CR sequence might lead to the CA-MPC being unable
find a feasible solution of (6), i.e. a failure in resolving a collision. To
make the CA algorithm more resilient to such failures, we propose a heuristic
that instead of generating only one CR sequence, generates a number of
slightly modified sequences, aka backups, with an intention of increasing the
probability of finding an overall solution for CA. We call it a CR repairing
algorithm. We propose the following scheme for CR repairing.

####  4.3.1. Naïve repairing scheme for generating CR decision sequences

The naïve-repairing algorithm is based on the initial supervised-learning CR
architecture, see Section 4.2. The proposed DNN model for CR has the output
layer with a softmax activation function that produces the class probability
estimates $\eta_{k}=[\eta_{k}^{1},\ldots,\eta_{k}^{6}]^{\top}$ for each time
step $k$, see Figure 3. Discrete decisions were chosen as:

(9) $d_{k}=\underset{i=1,\ldots 6}{\text{argmax}}\ \eta_{k}^{i},$

which corresponds to the highest probability class for time step $k$. Denote
such choice of $d_{k}$ as $d_{k}^{1}$.

Analogously to the idea of top-1 and top-$S$ accuracy rates used in image
classification (Russakovsky et al., 2015), where not only the highest
predicted class counts but also the top $S$ most likely labels, we define
higher order decisions $d^{s}_{k}$ as following: instead of choosing the
highest probability class at time step $k$, one could choose the second
highest probability class ($s=2$), third highest ($s=3$), up to the sixth
highest ($s=6$).

Formally, the second highest probability class choice $d_{k}^{2}$ is defined
as:

(10) $d_{k}^{2}=\underset{i=1,\ldots 6,\,i\not=d_{k}^{1}}{\text{argmax}}\
\eta_{k}^{i}$

In the same manner, we define decisions up to $d_{k}^{6}$. General formula for
the $s$-th highest probability class, decision $d_{k}^{s}$ is defined as
following ($s=1,\ldots,6$):

(11) $d_{k}^{s}=\underset{i=1,\ldots 6,\,i\not=d_{k}^{j}\ \forall
j<s}{\text{argmax}}\ \eta_{k}^{i}$

Using equation (11) to generate decisions $d_{k}$ at time step $k$, we define
the naïve scheme for generating new decision sequences $\mathbf{d}^{\prime}$
following Algorithm 2.

Notation :
$(\mathbf{x}_{1}^{\prime},\mathbf{x}_{2}^{\prime},\mathbf{u}_{1}^{\prime},\mathbf{u}_{2}^{\prime})=\textbf{Repairing}(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{P}_{2},\varUpsilon)$

Input: Pre-planned trajectories $\mathbf{x}_{1}$, $\mathbf{x}_{2}$, robustness
tubes $\mathbf{P}_{1}$, $\mathbf{P}_{2}$, original decision sequence
$\mathbf{d}$, class probability estimates $\mathbf{\eta}$, set of collision
indices: $\varUpsilon=\\{k:\ ||p_{1,k}^{\prime}-p_{2,k}^{\prime}||<\delta,\
0\leq k\leq H\\}$.

Output: Sequence of control signals $\mathbf{u}_{1}^{\prime}$,
$\mathbf{u}_{2}^{\prime}$ for the two UAS, updated trajectories
$\mathbf{x}_{1}^{\prime}$, $\mathbf{x}_{2}^{\prime}$

for  _$s=2,\ldots,6$_ do

Define repaired sequence $\mathbf{d}^{\prime}$ using naïve scheme as follows:

  * -

$\forall k\not\in\varUpsilon:\ d^{\prime}_{k}=d_{k}$

  * -

$\forall k\in\varUpsilon:\ d^{\prime}_{k}=d_{k}^{s}=\text{argmax}_{i=1,\ldots
6,\,i\not=d_{k}^{j}\ \forall j<s}\ \eta_{k}^{i}$

$(\mathbf{x}_{1}^{\prime},\mathbf{x}_{2}^{\prime},\mathbf{u}_{1}^{\prime},\mathbf{u}_{2}^{\prime})=\textbf{CA-
MPC}(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{P}_{2},\mathbf{d}^{\prime})$

if  _$||p_{1,k}^{\prime}-p_{2,k}^{\prime}||\geq\delta,\,\forall k=0,\dotsc,N$_
then

Break: Repaired CR sequence $\mathbf{d}^{\prime}$ led to UAS 1 and UAS 2
creating separation

end if

end for

if  _$||p_{1,k}^{\prime}-p_{2,k}^{\prime}||\geq\delta,\,\forall k=0,\dotsc,H$_
then

$\mathbf{d}^{\prime}=\mathbf{d}$: Repairing failed. Return trajectories for
the original decision sequence.

end if

Algorithm 2 Naïve scheme for CR repairing

###### Example 4.4.

Let the horizon of interest be only $H=5$ time steps and the initially
obtained decision sequence be $\mathbf{d}=(1,1,1,1,1)$. Given the collision
was detected at time steps 2 and 3, i.e. $\varUpsilon=(2,3)$, let the second-
highest probability decisions be $d_{2}^{2}=3$ and $d_{3}^{2}=5$. Then the
proposed repaired decision sequence is $\mathbf{d}^{\prime}=(1,1,3,5,1)$. If
such CR sequence $\mathbf{d}^{\prime}$ still violates the mutual separation
requirement, then the naïve repairing scheme will propose another decision
sequence using the third-highest probability decisions $d_{3}$. Let
$d_{2}^{3}=2$ and $d_{3}^{3}=3$ then $\mathbf{d}^{\prime}=(1,1,2,3,1)$. If it
fails again, the next generated sequence will use fourth-highest decisions,
and so on up to the fifth iteration of the algorithm (requires $d_{k}^{6}$
estimates). If none of the sequences managed to create separation, the
original CR sequence $\mathbf{d}=(1,1,1,1,1)$ will be returned.

Other variations of the naïve scheme are possible. For example, one can use
augmented set of collision indices $\varUpsilon$ or another order of decisions
$d_{k}$ across the time indices, e.g. replace decisions $d_{k}$ one-by-one
rather than all $d_{k}$ for collision indices $\varUpsilon$ at once. Moreover,
other CR repairing schemes can be efficient and should be explored. We leave
it for future work.

##  5\. Learning-‘N-Flying: Decentralized Collision Avoidance for Multi-UAS
Fleets

The L2F framework of Section 4 was tailored for CA between two UAS. When more
than two UAS are simultaneously on a collision path, applying L2F pairwise for
all UAS involved might not necessarily result in all future collisions being
resolved. Consider the following example:

###### Example 5.1.

Figure 4 depicts an experimental setup. Scenario consists of 3 UAS which must
reach desired goal states within 4 seconds while avoiding each other, minimum
allowed separation is set to $\delta=0.1m$. Initially pre-planned UAS
trajectories have a simultaneous collision across all UAS located at
$(0,0,0)$. Robustness tubes radii were fixed at $\rho=0.055$ and UAS
priorities were set in the increasing order, e.g. UAS with a lower index had a
lower priority: $1<2<3$. First application of L2F lead to resolving collision
for UAS 1 and UAS 2, see Figure 4(a). Second application resolved collision
for UAS 1 and UAS 3 by UAS 3 deviating vertically downwards, see Figure 4(b).
The third application led to UAS 3 deviate vertically upwards, which resolved
collision for UAS 2 and UAS 3, though created a re-appeared violation of
minimum separation for UAS 1 and UAS 3 in the middle of their trajectories,
see Figure 4(c).

(a) L2F for pair UAS 1, UAS 2. Pairwise separations: $\delta_{12}=0.11$m,
$\delta_{13}=0.06$m, $\delta_{23}=0.05$m.

(b) L2F for pair UAS 1, UAS 3. Pairwise separations: $\delta_{12}=0.11$m,
$\delta_{13}=0.11$m, $\delta_{23}=0.04$m.

(c) L2F for pair UAS 2, UAS 3 results. Pairwise separations:
$\delta_{12}=0.11$m, $\delta_{13}=0.01$m, $\delta_{23}=0.1$m.

Figure 4. Sequential L2F application for the 3 UAS scenario. Pre-planned
colliding trajectories are depicted in dashed lines. Simultaneous collision is
detected at point $(0,0,0)$. The updated trajectories generated by L2F are
depicted in solid color. Initial positions of UAS marked by “O”.

To overcome this live lock like issue, where repeated pair-wise applications
of L2F only result in new conflicts between other pairs of UAS, we propose a
modification of L2F called Learning-N-Flying (LNF). The LNF framework is based
on pairwise application of L2F, but also incorporates a _Robustness Tube
Shrinking_ (RTS) process described in Section 5.1 after every L2F application.
The overall LNF framework is presented in Algorithm 3. Section 6.3 presents
extensive simulations to show the applicability of the LNF scheme to scenarios
where more than two UAS are on collisions paths, including in high-density UAS
operations.

Input: Pre-planned fleet trajectories $\mathbf{x}_{i}$, initial robustness
tubes $\mathbf{P}_{i}$, UAS priorities

Output: New trajectories $\mathbf{x}_{i}^{\prime}$, new robustness tubes
$\mathbf{P}^{\prime}_{i}$, control inputs $u^{\prime}_{i,0}$

Each UAS $i$ detects the set of UAS that it is in conflict with: $S=\\{j\ |\
\exists k\ ||p_{i,k}-p_{j,k}||<\delta,\ 0\leq k\leq H\\}$

Order $S$ by the UAS priorities

for  _$j\in S$_ do

$(\mathbf{x}_{i}^{\prime},\mathbf{x}_{j}^{\prime},\mathbf{u}_{i}^{\prime},\mathbf{u}_{j}^{\prime})=\textbf{L2F}(\mathbf{x}_{i},\mathbf{x}_{j},\mathbf{P}_{i},\mathbf{P}_{j})$,
see Section 4

if  _$\varUpsilon=\\{k:\ ||p_{i,k}^{\prime}-p_{j,k}^{\prime}|| <\delta,\ 0\leq
k\leq H\\}\not=\emptyset$_ then

$(\mathbf{x}_{i}^{\prime},\mathbf{x}_{j}^{\prime},\mathbf{u}_{i}^{\prime},\mathbf{u}_{j}^{\prime})=\textbf{Repairing}(\mathbf{x}_{i},\mathbf{x}_{j},\mathbf{P}_{i},\mathbf{P}_{j},\varUpsilon)$

end if

$(\mathbf{P}^{\prime}_{i},\mathbf{P}^{\prime}_{j})=\textbf{RTS}\,(\mathbf{x}^{\prime}_{i},\mathbf{x}^{\prime}_{j},\mathbf{P}_{i},\mathbf{P}_{j})$

end for

Apply controls $u_{i,0}^{\prime}$ for the initial time step of the receding
horizon

Algorithm 3 Learning-‘N-Flying: Decentralized and cooperative collision
avoidance for multi-UAS fleets. Applied in a receding horizon manner by each
UAS $i$.

###  5.1. Robustness tubes shrinking (RTS)

The high-level of idea of RTS is that, when two trajectories are de-collided
by L2F, we want to constrain their further modifications by L2F so as not to
induce new collisions. In Example 5.1, after collision-free
$\mathbf{x}_{1}^{\prime}$ and $\mathbf{x}_{2}^{\prime}$ are produced by L2F
and before $\mathbf{x}_{2}^{\prime}$ and $\mathbf{x}_{3}$ are de-collided, we
want to constrain any modification to $\mathbf{x}_{2}^{\prime}$ s.t. it does
not collide again with $\mathbf{x}_{1}^{\prime}$. Since trajectories are
constrained to remain within robustness tubes, we simply shrink those tubes to
achieve this. The amount of shrinking is $\delta$, the minimum separation. RTS
is described in Algorithm 4.

Notation :
$(\mathbf{P}^{\prime}_{1},\mathbf{P}^{\prime}_{2})=\textbf{RTS}\,(\mathbf{x}^{\prime}_{1},\mathbf{x}^{\prime}_{2},\mathbf{P}_{1},\mathbf{P}_{2})$

Input: New trajectories $\mathbf{x}^{\prime}_{1}$, $\mathbf{x}^{\prime}_{2}$
generated by L2F, initial robustness tubes $\mathbf{P}_{1}$, $\mathbf{P}_{2}$

Output: New robustness tubes $\mathbf{P}^{\prime}_{1}$,
$\mathbf{P}^{\prime}_{2}$

Set $msep=\min_{0\leq k\leq H}||p_{1,k}^{\prime}-p_{2,k}^{\prime}||$

for  _$k=0,\ldots,H$_ do

if  _$\mathbf{dist}(P_{1,k},P_{2,k})\geq\delta$_ then

No shrinking required: $P^{\prime}_{1,k}=P_{1,k},\ P^{\prime}_{2,k}=P_{2,k}$

else

Determine the axis ($X$, $Y$ or $Z$) of maximum separation between
$p^{\prime}_{1,k}$ and $p^{\prime}_{2,k}$

Define the 3D box $\varPi_{k}$ with edges of size $\min(msep,\delta)$ along
the determined axis and infinite edges along other two axes

Center $\varPi_{k}$ at the midpoint between $p^{\prime}_{1,k}$ and
$p^{\prime}_{2,k}$

Remove $\varPi_{k}$ from both tubes:
$P^{\prime}_{1,k}=P_{1,k}\setminus\varPi_{k},\
P^{\prime}_{2,k}=P_{2,k}\setminus\varPi_{k}$

end if

end for

Algorithm 4 Robustness tubes shrinking. Also see Figure 5. Figure 5.
Visualization of the robustness tubes shrinking process.

###### Example 5.2.

Figure 5(a) presents the initial discrete-time robustness tubes and
trajectories for UAS 1 and UAS 2. Successful application of L2F resolves the
detected collision between initially planned trajectories $\mathbf{p}_{1}$,
$\mathbf{p}_{2}$, depicted in dashed line. New non-colliding trajectories
$\mathbf{p}_{1}^{\prime}$ and $\mathbf{p}_{2}^{\prime}$ produced by L2F are in
solid color. Figure 5(b) shows that for time step $k=0$ no shrinking is
required since the robustness tubes $P_{1,0}$, $P_{2,0}$ are already
$\delta$-separate. For time steps $k=1,2,3$, the axis of maximum separation
between trajectories is $Z$, therefore, boxes $\varPi_{k}$ are defined to be
of height $\delta$ with infinite width and length. Boxes $\varPi_{k}$ are
drawn in gray, midpoints between the trajectories are drawn in yellow. Figure
5(c) depicts the updated $\delta$-separate robustness tubes
$\mathbf{P}^{\prime}_{1}$ and $\mathbf{P}^{\prime}_{2}$.

###### Theorem 5.3 (Sufficient condition for $\delta$-separate tubes).

Zero-slack solution of (6) implies that robustness tubes updated by RTS
procedure are the subsets of the initial robustness tubes and
$\delta$-separate, e.g. for robustness tubes
$(\mathbf{P}^{\prime}_{1},\mathbf{P}^{\prime}_{2})=\textbf{RTS}\,(\mathbf{x}^{\prime}_{1},\mathbf{x}^{\prime}_{2},\mathbf{P}_{1},\mathbf{P}_{2})$,
the following two properties hold:

(12)
$\displaystyle\mathbf{dist}(\mathbf{P}_{1}^{\prime},\mathbf{P}_{2}^{\prime})\geq\delta$
(13) $\displaystyle\mathbf{P}_{j}^{\prime}\subseteq\mathbf{P}_{j},\ \forall
j\in\\{1,2\\}$

See the proof in the appendix Section A.

###  5.2. Combination of L2F with RTS

Three following lemmas define important properties of L2F combined with the
shrinking process. Proofs can be found in the appendix Section A.

###### Lemma 5.0.

Let two trajectories $\mathbf{x}_{1}^{\prime}$, $\mathbf{x}_{2}^{\prime}$ be
generated by L2F and let the robustness tubes $\mathbf{P}_{1}^{\prime}$,
$\mathbf{P}_{2}^{\prime}$ be the updated tubes generated by RTS procedure from
initial tubes $\mathbf{P}_{1}$, $\mathbf{P}_{2}$ using the trajectories
$\mathbf{x}_{1}^{\prime}$, $\mathbf{x}_{2}^{\prime}$. Then

(14) $\mathbf{p}_{j}^{\prime}\in\mathbf{P}_{j}^{\prime},\ \forall
j\in\\{1,2\\}.$

The above Lemma 5.4 states that RTS procedure preserves trajectory belonging
to the corresponding updated robustness tube.

###### Lemma 5.0.

Let two robustness tubes $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ be
$\delta$-separate. Then any pair of trajectories within these robustness tubes
are non-conflicting, i.e.:

(15) $\forall\mathbf{p}_{1}\in\mathbf{P}_{1},\
\forall\mathbf{p}_{2}\in\mathbf{P}_{2},\
||p_{1,k}-p_{2,k}||\geq\delta,\,\forall k\in\\{0,\dotsc,H\\}.$

Using Lemma 5.5 we can now prove that every successful application of L2F
combined with the shrinking process results in new trajectories does not
violate previously achieved minimum separations between UAS, unless the RTS
process results in an empty robustness tube. In other words, it solves the 3
UAS issue raised in Example 5.1. We formalize this result in the context of 3
UAS with the following Lemma:

###### Lemma 5.0.

Let $\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{x}_{3}$ be pre-planned conflicting
UAS trajectories, and let $\mathbf{P}_{1}$, $\mathbf{P}_{2}$ and
$\mathbf{P}_{3}$ be their corresponding robustness tubes. Without loss of
generality assume that the sequential pairwise application of L2F combined
with RTS has been done in the following order:

(16)
$\displaystyle(\mathbf{x}_{1}^{\prime},\mathbf{x}_{2}^{\prime})=\textbf{L2F}\,(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{P}_{2}),$
$\displaystyle\qquad(\mathbf{P}_{1}^{\prime},\mathbf{P}_{2}^{\prime})=\textbf{RTS}\,(\mathbf{x}_{1},\mathbf{x}_{2},\mathbf{P}_{1},\mathbf{P}_{2})$
(17)
$\displaystyle(\mathbf{x}_{1}^{\prime\prime},\mathbf{x}_{3}^{\prime})=\textbf{L2F}\,(\mathbf{x}_{1}^{\prime},\mathbf{x}_{3},\mathbf{P}_{1}^{\prime},\mathbf{P}_{3}),$
$\displaystyle\qquad(\mathbf{P}_{1}^{\prime\prime},\mathbf{P}_{3}^{\prime})=\textbf{RTS}\,(\mathbf{x}_{1}^{\prime\prime},\mathbf{x}_{3}^{\prime},\mathbf{P}_{1}^{\prime},\mathbf{P}_{3})$
(18)
$\displaystyle(\mathbf{x}_{2}^{\prime\prime},\mathbf{x}_{3}^{\prime\prime})=\textbf{L2F}\,(\mathbf{x}_{2}^{\prime},\mathbf{x}_{3}^{\prime},\mathbf{P}_{2}^{\prime},\mathbf{P}_{3}^{\prime}),$
$\displaystyle\qquad(\mathbf{P}_{2}^{\prime\prime},\mathbf{P}_{3}^{\prime\prime})=\textbf{RTS}\,(\mathbf{x}_{2}^{\prime\prime},\mathbf{x}_{3}^{\prime\prime},\mathbf{P}_{2}^{\prime},\mathbf{P}_{3}^{\prime})$

If all three L2F applications gave zero-slack solutions then position
trajectories
$\mathbf{p}_{1}^{\prime\prime},\mathbf{p}_{2}^{\prime\prime},\mathbf{p}_{3}^{\prime\prime}$
pairwise satisfy mutual separation requirement, e.g.:

(19)
$\displaystyle||p^{\prime\prime}_{1,k}-p^{\prime\prime}_{2,k}||\geq\delta,\
\forall k\in\\{0,\ldots,H\\}$ (20)
$\displaystyle||p^{\prime\prime}_{1,k}-p^{\prime\prime}_{3,k}||\geq\delta,\
\forall k\in\\{0,\ldots,H\\}$ (21)
$\displaystyle||p^{\prime\prime}_{2,k}-p^{\prime\prime}_{3,k}||\geq\delta,\
\forall k\in\\{0,\ldots,H\\}$

and are within their corresponding robustness tubes:

(22) $\mathbf{p}^{\prime\prime}_{j}\in\mathbf{P}^{\prime\prime}_{j},\ \forall
j\in\\{1,2,3\\}.$

By induction we can extend Lemma 5.6 to any number of UAS. Therefore, we can
conclude that for any $N$ pre-planned UAS trajectories, zero-slack solution of
LNF is a sufficient condition for CA, e.g. resulting trajectories generated by
LNF are non-conflicting and withing the robustness tubes of the initial
trajectories. Note that this approach can still fail to find a solution,
especially as repeated RTS can result in empty robustness tubes.

###### Theorem 5.7.

For the case of $N$ UAS, when applied at any time step $k$, LNF (algorithm 3)
terminates after no more than $N\choose 2$ applications of pairwise L2F
(algorithm 1).

This result follows directly from the inductive application of Lemma 5.6. In
experimental evaluations (Section 6.3), we see that this worst-case number of
L2F applications is not required often in practice.

##  6\. Experimental evaluation of L2F and LNF

In this section, we show the performance of our proposed methods via extensive
simulations, as well as an implementation for actual quad-rotor robots. We
compare L2F and L2F with repair (L2F+Rep) with the MILP formulation of Section
3 and two other baseline approaches. Through multiple case studies, we show
how LNF extends the L2F framework to work for scenarios with than two UAS.

###  6.1. Experimental setup

Computation platform: All the simulations were performed on a computer with an
AMD Ryzen 7 2700 8-core processor and 16GB RAM, running Python 3.6 on Ubuntu
18.04.

Generating training data: We have generated the data set of 14K trajectories
for training with collisions between UAS using the trajectory generator in
(Mueller et al., 2015). The look-ahead horizon was set to $T=4$s and
$dt=0.1$s. Thus, each trajectory consists of $H+1=41$ time-steps. The initial
and final waypoints were sampled uniformly at random from two 3D cubes close
to the fixed collision point, initial velocities were set to zero.

Implementation details for the learning-based conflict resolution: The MILP to
generate training data for the supervised learning of the CR scheme was
implemented in MATLAB using Yalmip (Lofberg, 2004) with MOSEK v8 as the
solver. The learning-based CR scheme was trained for $\rho=0.055$ and minimum
separation $\delta=0.1$m which is close to the lower bound in Assumption 2.
This was implemented in Python 3.6 with Tensorflow 1.14 and Keras API and
Casadi with qpOASES as the solver. For traning the LSTM models (with different
architectures) for CR, the number of training epochs was set to 2K with a
batch size of 2K. Each network was trained to minimize categorical cross-
entropy loss using Adam optimizer (Kingma and Ba, 2014) with training rate of
$\alpha=0.001$ and moment exponential decay rates of $\beta_{1}=0.9$ and
$\beta_{2}=0.999$. The model with 3 LSTM layers with 128 neurons each, see
Figure 3, was chosen as the default learning-based CR model, and is used for
the pairwise CA approach of both L2F and LNF.

Implementation details for the CA-MPC: For the online implementation of our
scheme, we implement CA-MPC using CVXgen and report the computation times for
this implementation. We then import CA-MPC in Python, interface it with the CR
scheme and run all simulations in Python.

###  6.2. Experimental evaluation of L2F

Figure 6. Trajectories for 2 UAS from different angles. The dashed (planned)
trajectories have a collision at the halfway point. The solid ones, generated
through L2F method, avoid the collision while remaining within the robustness
tube of the original trajectories. Initial UAS positions marked as stars.
Playback of the scenario is at https://tinyurl.com/l2f-exmpl.

Figure 7. Trajectories for 2 Crazyflie quad-rotors before (dotted) and after
(solid) L2F. Videos of this are at
%.␣The␣dotted␣(planned)%trajectories␣have␣a␣collision␣at␣the␣halfway␣point.␣The␣solid␣ones,%generated␣through␣L2F,␣avoid␣the␣collision.␣Vhttps://tinyurl.com/exp-
cf2

We evaluate the performance of L2F with 10K test trajectories (for pairwise
CA) generated using the same distribution of start and end positions as was
used for training. Figure 6 shows an example of two UAS trajectories before
and after L2F. Successful avoidance of the collision at the midway point on
the trajectories can easily be seen on the playback of the scenario available
at https://tinyurl.com/l2f-exmpl. To demonstrate the feasibility of the
deconflicted trajectories, we also ran experiments using two Crazyflie quad-
rotor robots as shown in Figure 7. Videos of the actual flights and additional
simulations can be found at https://tinyurl.com/exp-cf2.

####  6.2.1. Results and comparison to other methods

We analyzed three other methods alongside the proposed learning-based approach
for L2F.

  1. (1)

A random decision approach which outputs a sequence sampled from the discrete
uniform distribution.

  2. (2)

A greedy approach that selects the discrete decisions that correspond to the
direction of the most separation between the two UAS at each time step. For
more details see (Rodionova et al., 2020).

  3. (3)

A L2F with Repairing approach following Section 4.3.

  4. (4)

A centralized MILP solution that picks decisions corresponding to binary
decision variables in (5).

(a) Separation rate defines the fraction of initially conflicting trajectories
for which UAS managed to achieve minimum separation.

(b) Failure rate (1-Separation rate) defines the fraction of initially
conflicting trajectories for which UA could not achieve minimum separation.

Figure 8. Model sensitivity analysis with respect to variations of fraction
$\rho/\delta$ which connects the minimum allowable robustness tube radius
$\rho$ to the minimum allowable separation between two UAS $\delta$, see
Assumption 2. A higher $\rho/\delta$ implies there is more room within the
robustness tubes to maneuver for CA.

For the evaluation, we measured and compared the separation rate and the
computation time for all the methods over the same 10K test trajectories.
Separation rate defines the fraction of the conflicting trajectories for which
UAS managed to achieve minimum separation after a CA approach. Figure 8 shows
the impact of the $\rho/\delta$ ratio on separation rate. Higher $\rho/\delta$
implies wider robustness tubes for the UAS to maneuver within, which should
make the CA task easier as is seen in the figure. The centralized MILP has a
separation rate of $1$ for each case here, however is unsuitable for an online
implementation with its computation time being over a minute ( seetable 1) and
we exclude it from the comparisons in the text that follows. In the case of
$\rho/\delta=0.5$, where the robustness tubes are just wide enough to fit two
UAS (see Assumption 2), we see the L2F with repairing (L2F+Rep) significantly
outperforms the methods. This worst-case performance of L2F with repairing is
$0.999$ which is significantly better than the other approaches including the
original L2F. As the ratio grows, the performance of all methods improve, with
L2F+Rep still outperforming the others and quickly reaching a separation rate
of $1$. For $\rho/\delta\geq 1.15$, L2F no longer requires any repair and also
has a separation rate of $1$.

Table 1 shows the separation rates for three different $\rho/\delta$ value as
well as the computation times (mean and standard deviation) for each CA
algorithm. L2F and L2F+Rep have an average computation time of less than
$10$ms, making them suited for an online implementation even at our chosen
control sampling rate of $10$Hz. For all CA schemes excluding MILP, the
smaller the $\rho/\delta$ ratio, the more UAS 1 alone is unsuccessful at
collision avoidance MPC (7), and UAS 2 must also solve its CA-MPC (8) and
deviate from its pre-planned trajectory. Therefore, computation time is higher
for smaller $\rho/\delta$ ratio and lower for higher $\rho/\delta$ values. A
similar trend is observed for the MILP, even though it jointly solves for both
UAS, showing that it is indeed harder to find a solution when the
$\rho/\delta$ ratio is small.

|  | CA Scheme
---|---|---
| Random | Greedy | L2F | L2F+Rep | MILP
Separation rate | $\boldsymbol{\rho}/\boldsymbol{\delta}=\textbf{0.5}$ | 0.311 | 0.528 | 0.899 | 0.999 | 1
$\boldsymbol{\rho}/\boldsymbol{\delta}=\textbf{0.95}$ | 0.605 | 0.825 | 0.999 | 1 | 1
$\boldsymbol{\rho}/\boldsymbol{\delta}=\textbf{1.15}$ | 0.659 | 0.989 | 1 | 1 | 1
Comput. time (ms) (mean $\pm$ std) | $\boldsymbol{\rho}/\boldsymbol{\delta}=\textbf{0.5}$ | $7.9\pm 0.01$ | $9.7\pm 0.6$ | $9.1\pm 1.3$ | $9.7\pm 3.6$ | $(98.9\pm 44.9)\cdot 10^{3}$
$\boldsymbol{\rho}/\boldsymbol{\delta}=\textbf{0.95}$ | $7.5\pm 0.01$ | $9.3\pm 0.5$ | $8.7\pm 0.5$ | $8.7\pm 0.5$ | $(82.5\pm 36.3)\cdot 10^{3}$
$\boldsymbol{\rho}/\boldsymbol{\delta}=\textbf{1.15}$ | $6.3\pm 1.9$ | $7.1\pm 2.$ | $8.6\pm 0.5$ | $8.7\pm 0.4$ | $(33.1\pm 34.9)\cdot 10^{3}$
Table 1. Separation rates and computation times (mean and standard deviation)
comparison of different CA schemes. Separation rate is the fraction of
conflicting trajectories for which separation requirement (2a) is satisfied
after CA. Computation time estimates the overall time demanded by CA scheme.
MILP reports the time spent on solving (5). Other CA schemes report time
needed for CR and CA-MPC together. L2F with repairing includes repairing time
as well.

###  6.3. Experimental evaluation of LNF

Next, we carry out simulations to evaluate the performance of LNF, especially
in terms of scalability to cases with more than two UAS and analyze its
performance in wide variety of settings.

####  6.3.1. Case study 1: Four UAS position swap

We recreate the following experiment from (Alonso-Mora et al., 2015). Here,
two pairs of UAS must maneuver to swap their positions, i.e. the end point of
each UAS is the same as the starting position for another UAS. See the 3D
representation of the scenario in Figure 9(a). Each UAS start set is assumed
to be a singular point fixed at:

(23) $\textit{Goal}_{1}=(1,0,0),\ \textit{Goal}_{2}=(0,1,0),\
\textit{Goal}_{3}=(-1,0,0),\ \textit{Goal}_{4}=(0,-1,0)$

and goal states are antipodal to the start states:

(24) $\textit{Start}_{j}=-\textit{Goal}_{j},\ \forall j\in\\{1,2,3,4\\}.$

All four UAS must reach desired goal states within 4 seconds while avoiding
each other. With a pairwise separations requirement of at least $\delta=0.1$
meters, the overall mission specification is:

(25)
$\varphi_{\textit{mission}}=\bigwedge_{j=1}^{4}\Diamond_{[0,4]}(\mathbf{p}_{j}\in\textit{Goal}_{j})\
\wedge\
\bigwedge_{j\not=j^{\prime}}\square_{[0,4]}||\mathbf{p}_{j}-\mathbf{p}_{j^{\prime}}||\geq
0.1\vspace{-3pt}$

Following Section 2.2, initial pre-planning is done by ignoring the mutual
separation requirement in (25) and generating the trajectory for each UAS
$j=\\{1,2,3,4\\}$ independently with respect to its individual STL
specification:

(26) $\varphi_{j}=\Diamond_{[0,4]}(\mathbf{p}_{j}\in\textit{Goal}_{j}).$

Obtained pre-planned trajectories contain a joint collision that happens
simultaneously (at $t=2$s, see Figure 10) across all four UAS and located at
point $(0,0,0)$, see Figure 9(b). For LNF experimental evaluation, the
robustness value was fixed at $\rho=0.055$ and the UAS priorities were set in
the increasing order, e.g. UAS with a lower index has the lower priority:
$1<2<3<4$.

Figure 9. Four UAS position swap. (a): 3D representation of the scenario.
(b)-(c): 2D projections of the scenario onto the horizontal plane $XoY$ before
and after collision avoidance. Initial colliding trajectories are depicted in
dashed lines in (a) and (b). Collision is detected at point $(0,0,0)$, it
involves all four UAS and happens simultaneously across the agents. The
updated non-colliding trajectories generated by LNF are depicted in solid
color in (a) and (c). Initial positions of UAS marked by “O” and final
positions by “$\star$”.

Figure 10. Four UAS position swap: Relative distances before (top) and after
(bottom) the collision avoidance algorithm. Initial simultaneous collisions
across all four UAS are successfully resolved by LNF. Note that the symmetry
in the initial positions and trajectories results in multiple UAS pairs with
the same relative distances for the time horizon of interest before collision
avoidance (top).

Simulation results. The non-colliding trajectories generated by LNF are
depicted in Figure 9(c). Playback of the scenario can be found at
https://tinyurl.com/swap-pos.

It is observed that the opposite UAS pairs chose to change attitude and pass
over each other, see Figure 9(a). Within these opposite pairs, UAS chose to
have horizontal deviations to avoid collision, see Figure 9(c). LNF algorithm
performed $4\choose 2$$=6$ pairwise applications of L2F (see Theorem 5.7).
Such high number of applications is expected due to a complicated simultaneous
nature of the detected collision across the initially pre-planned
trajectories. No CR repairing was required to successfully produce non-
colliding trajectories by the LNF algorithm. It took LNF $37.8$ms to perform
CA. Figure 10 represents relative distances between UAS pairs before and after
collision avoidance. Figure 10 shows that none of the UAS cross the safe
minimum separation threshold of $0.1$m after LNF, e.g. joint collision has
been successfully resolved by LNF.

####  6.3.2. Case study 2: Four UAS reach-avoid mission

Figure 11 depicts a multi UAS case-study with a reach-avoid mission. Scenario
consists of four UAS which must reach desired goal states within 4 seconds
while avoiding the wall obstacle and each other. Each UAS
$j\in\\{1,\ldots,4\\}$ specification can be defined as:

(27) $\varphi_{j}=\Diamond_{[0,4]}(\mathbf{p}_{j}\in\textit{Goal}_{j})\
\wedge\ \square_{[0,4]}\neg(\mathbf{p}_{j}\in\textit{Wall})\vspace{-2pt}$

A pairwise separations requirement of $\delta=0.1$ meters is enforced for all
UAS, therefore, the overall mission specification is:

(28) $\varphi_{\text{mission}}=\bigwedge_{j=1}^{4}\varphi_{j}\ \wedge\
\bigwedge_{j\not=j^{\prime}}\square_{[0,4]}||\mathbf{p}_{j}-\mathbf{p}_{j^{\prime}}||\geq
0.1\vspace{-3pt}$

(a) 3D representation of the scenario

(b) 2D projection onto $XoY$

Figure 11. Reach-avoid mission. Non-colliding trajectories for 4 UAS generated
by LNF. All UAS reach their goal sets (green boxes) within 4 seconds, do not
crash into the vertical wall (in red) and satisfy pairwise separation
requirement of $0.1$m. Initial UAS positions marked by magenta “$\star$”.
Simulations are available at https://tinyurl.com/reach-av.

First, we solved the planning problem for all four UAS in a centralized manner
following approach from (Pant et al., 2018). Next, we solved the planning
problem for each UAS $j$ and its specification $\varphi_{j}$ independently,
with calling LNF on-the-fly, after planning is complete. This way, independent
planning with the online collision avoidance scheme guarantees the
satisfaction of the overall mission specification (28).

Simulation results. We have simulated the scenario for 100 different initial
conditions. Computation time results are presented in Table 2. The average
computation time to generate trajectories in a centralized manner was $0.35$
seconds. The average time per UAS when planning independently (and in
parallel) was $0.1$ seconds. These results demonstrate a speed up of
$3.5\times$ for the individual UAS planning versus centralized (Pant et al.,
2018). Scenario simulations are available https://tinyurl.com/reach-av.

| Centralized planning (Pant et al., 2018) | Decentralized planning with CA
---|---|---
| Independent planning | CA with LNF
Comput. time (mean$\pm$ std)(ms) | 345.8$\pm$ 87.2 | 138.6$\pm$ 62.4 | 9.97 $\pm$ 0.4
Table 2. Reach-avoid mission. Computation times (mean and standard deviation)
comparison between centralized planning following (Pant et al., 2018) and
decentralized planning (independent planning with LNF) over 100 runs of the
scenario.

####  6.3.3. Case study 3: UAS operations in high-density airspace

Figure 12. 3D representation of the unit cube scenario with 20 UAS. All UAS
must reach their goal sets within 4 seconds, avoid the no-fly zone and satisfy
pairwise separation requirement of $0.1$m. Initially planned trajectories
(dashed lines) had 5 violations of the mutual separation requirement. LNF
succesfully resolved all detected violations and led to non-colliding
trajectories (solid lines). Simulations are available at
https://tinyurl.com/unit-cube.

To verify scalability of LNF, we perform evaluation of the scenario with high-
density UAS operations. The case study consists of multiple UAS flying within
the restricted area of 1m3 while avoiding a no-fly zone of $(0.2)^{3}$=0.08m3
in the center, see Figure 12. Such scenario represents a hypothetical
constrained and highly populated airspace with heterogeneous UAS missions such
as package delivery or aerial surveillance.

Each UAS’ $j$ start position $\textit{Start}_{j}$ and goal set
$\textit{Goal}_{j}$ are chosen at (uniform) random on the opposite random
faces of the unit cube. Goal state should be reached within $4$ second time
interval and the no-fly zone must be avoided during this time interval. Same
as in the previous case studies, we first solve the planning problem for each
UAS $j$ separately following trajectory generation approach from (Pant et al.,
2018). The STL specification for UAS $j$ is captured as follows:

(29) $\varphi_{j}=\Diamond_{[0,4]}(\mathbf{p}_{j}\in\textit{Goal}_{j})\
\wedge\ \square_{[0,4]}\neg(\mathbf{p}_{j}\in\textit{NoFly})$

After planning is complete and trajectories $\mathbf{p}_{j}$ are generated, we
call LNF on-the-fly to satisfy the overall mission specification
$\varphi_{\text{mission}}=\bigwedge_{j=1}^{N}\varphi_{j}\ \wedge\
\varphi_{\text{separation}}$, where $N$ is a number of UAS participating in
the scenario and $\varphi_{\text{mission}}$ is the requirement of the minimum
allowed pairwise separation of $0.1$m between the UAS:

(30) $\varphi_{\text{separation}}=\bigwedge_{j,j^{\prime}:\
j\not=j^{\prime}}\square_{[0,4]}||\mathbf{p}_{j}-\mathbf{p}_{j^{\prime}}||\geq
0.1.$

We increase the density of the scenario by increasing the number of UAS, while
keeping the space volume at 1m3.

Simulation results. We ran 100 simulations for various numbers of UAS, each
with randomized start and goal positions. Trajectory pre-planning was done
independently for all UAS, and LNF is tasked with CA. For evaluation, we
measure the overall number of minimum separation requirement violations before
and after LNF for two different settings of the fraction $\rho/\delta$: narrow
robustness tube, $\rho/\delta=0.5$ and wider tube, $\rho/\delta=1.15$, see
Figure 13. With increasing number of UAS, the number of collisions between
initially pre-planned trajectories increase (before LNF) and the number of not
collisions by LNF, while small, increases as well (figure 13(b)). The
corresponding decay in separation rate over pairs of collisions resolved is
faster for the case of $\rho/\delta=0.5$ which is expected due to less room to
maneuver. Separation rate is higher when the $\rho/\delta$ ratio is higher,
see Figure 13(a). We performed simulations for up to 70 UAS. Average
separation rate for 70 UAS is $0.915$ for $\rho/\delta=0.5$ and $0.987$ for
$\rho/\delta=1.15$. The results show that LNF can still succeed in scenarios
with a high UAS density. Videos of the simulations are available at
https://tinyurl.com/unit-cube.

(a) Separation rate defines the fraction between the number of initial
violations of the minimum separation and the number of resolved violations by
LNF.

(b) Number of minimum separation violations before and after LNF, averaged
over 100 simulations.

Figure 13. Unit cube scenario. Model performance analysis with respect to
variations in the number of UAS for two different settings of $\rho/\delta$. A
higher $\rho/\delta$ implies there is more room within the robustness tubes to
maneuver for CA. Performance is measured in terms of separation rate (a) and
the overall number of minimum separation requirement violations before and
after LNF (b). We plot the mean and standard deviation over 100 iterations.

####  6.3.4. Comparison to MILP-based re-planning

| Re-planning scheme | $N=10$ | $N=20$ | $N=30$ | $N=40$ | $N=50$
---|---|---|---|---|---|---
Comp. times (mean$\pm$std) | MILP-based planner |  $0.6\pm 0.1$s |  $8.8\pm 9.6$s |  $175.5\pm\\!149.9$s |  $1740.\pm 129.3$s | Timeout
CA with LNF | 15.2$\pm$ 5.1ms | 73.1$\pm$23.5ms | 117.3$\pm\\!$ 45.6ms | 198.7$\pm$ 73.6ms | 211.1$\pm$82.3 ms
Table 3. Computation times (mean and standard deviation) demanded by the re-
planning scheme (MILP-based re-planning or CA with LNF) averaged over $100$
random runs. Time taken by the MILP-based re-planner to encode the problem is
not included in the overall computation time. ‘Timeout’ stands for a timeout
after $35$ minutes.

LNF requires the new trajectories after CA to be be within the robustness
tubes of pre-planned trajectories to still satisfy other high-level
requirements (problem 1). While this might be restrictive, we show that online
re-planning is usually not an option in these multi-UAS scenarios. A MILP-
based planner, similar in essence to (Raman et al., 2014b), was implemented
and treated as a baseline to compare against LNF through evaluations on the
scenario of Section 6.3.3. Unlike the decentralized LNF, such MILP-planner
baseline is centralized as it plans for all the UAS in a single optimization
to avoid the NoFly-zone, reach their destinations and also avoid each other.

We ran 100 simulations for various numbers of UAS, with each iteration having
randomized start and goal positions. Simulations are available at
https://tinyurl.com/re-milp. The computation times are presented in Table 3.
As the number of UAS increases, it is clear the online re-planning is
intractable. For example, the baseline takes on average $8.8$ seconds to
produce trajectories for $20$ UAS, in contrast with $73.1$ milliseconds for
LNF to perform CA. For 50 UAS and higher the MILP baseline solver could not
return a single feasible solution, while LNF could. LNF outperforms the MILP-
based re-planning baseline since it can perform CA with small computation
times, even for a high number of UAS.

##  7\. Conclusions

Summary: We presented Learning-to-Fly (L2F), an online, decentralized and
mission-aware scheme for pairwise UAS Collision Avoidance. Through Learning-
And-Flying (LNF) we extended it to work for cases where more than two UAS are
on collision paths, via a systematic pairwise application of L2F and with a
set-shrinking approach to avoid live-lock like situations. These frameworks
combine learning-based decision-making and decentralized linear optimization-
based Model Predictive Control (MPC) to perform CA, and we also developed a
fast heuristic to repair the decisions made by the learing-based component
based on the feasibility of the optimizations. Through extensive simulation,
we showed that our approach has a computation time of the order of
milliseconds, and can perform CA for a wide variety of cases with a high
success rate even when the UAS density in the airspace is high.

Limitations and future work: While our approach works very well in practice,
it is not complete, i.e. does not guarantee a solution when one exists, as
seen in simulation results for L2F. This drawback requires a careful analysis
for obtaining the sets of initial conditions over the conflicting UAS such
that our method is guaranteed to work. In future work, we aim to leverage
tools from formal methods, like falsification, to get a reasonable estimate of
the conditions in which our method is guaranteed to work. We will also explore
improved heuristics for the set-shrinking in LNF, as well as the CR-decision
repairing procedure.

## References

  * (1)
  * Administration (2018) Federal Aviation Administration. 2018\.  Concept of Operations: Unmanned Aircraft System (UAS) Traffic Management (UTM).  {https://utm.arc.nasa.gov/docs/2018-UTM-ConOps-v1.0.pdf}.
  * Aksaray et al. (2016) Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta. 2016.  Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications. In _IEEE Conference on Decision and Control_.
  * Alonso-Mora et al. (2015) Javier Alonso-Mora, Tobias Naegeli, Roland Siegwart, and Paul Beardsley. 2015.  Collision avoidance for aerial vehicles in multi-agent scenarios.  _Autonomous Robots_ 39, 1 (2015), 101–121.
  * Chakrabarty et al. (2019) Anjan Chakrabarty, Corey Ippolito, Joshua Baculi, Kalmanje Krishnakumar, and Sebastian Hening. 2019\.  Vehicle to Vehicle (V2V) communication for Collision avoidance for Multi-copters flying in UTM –TCL4.  https://doi.org/10.2514/6.2019-0690
  * Dahleh et al. (2004) Mohammed Dahleh, Munther A Dahleh, and George Verghese. 2004\.  Lectures on dynamic systems and control.  _MIT Lecture Notes_ 4, 100 (2004), 1–100.
  * DeCastro et al. (2017) Jonathan A. DeCastro, Javier Alonso-Mora, Vasumathi Raman, and Hadas Kress-Gazit. 2017.  Collision-Free Reactive Mission and Motion Planning for Multi-robot Systems. In _Springer Proceedings in Advanced Robotics_.
  * Desai et al. (2017) Ankush Desai, Indranil Saha, Yang Jianqiao, Shaz Qadeer, and Sanjit A. Seshia. 2017.  DRONA: A Framework for Safe Distributed Mobile Robotics. In _ACM/IEEE International Conference on Cyber-Physical Systems_.
  * Fabra et al. (2019) Francisco Fabra, Willian Zamora, Julio Sangüesa, Carlos T Calafate, Juan-Carlos Cano, and Pietro Manzoni. 2019.  A distributed approach for collision avoidance between multirotor UAVs following planned missions.  _Sensors_ 19, 10 (2019), 2404.
  * Fainekos and Pappas (2009) G. Fainekos and G. Pappas. 2009.  Robustness of temporal logic specifications for continuous-time signals.  _Theor. Computer Science_ (2009).
  * Fainekos et al. (2005) G. E. Fainekos, H. Kress-Gazit, and G. J. Pappas. 2005\.  Hybrid Controllers for Path Planning: A Temporal Logic Approach. In _Proce. of the 44th IEEE Conf. on Decision and Control_. 4885–4890.  https://doi.org/10.1109/CDC.2005.1582935
  * Gers et al. (2002) Felix A Gers, Nicol N Schraudolph, and Jürgen Schmidhuber. 2002\.  Learning precise timing with LSTM recurrent networks.  _Journal of machine learning research_ 3, Aug (2002), 115–143.
  * Hackenberg (2018) Davis L Hackenberg. 2018\.  ARMD Urban Air Mobility Grand Challenge: UAM Grand Challenge Scenarios.  https://evtol.news/__media/PDFs/eVTOL-NASA-Revised_UAM_Grand_Challenge_Scenarios.pdf.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ 9, 8 (1997), 1735–1780.
  * Karaman and Frazzoli (2011) S. Karaman and E. Frazzoli. 2011.  Linear temporal logic vehicle routing with applications to multi-UAV mission planning.  _International Journal of Robust and Nonlinear Control_ (2011).
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kloetzer and Belta (2006) M. Kloetzer and C. Belta. 2006.  Hierarchical abstractions for robotic swarms. In _Proc. of 2006 IEEE Inter. Conf. on Robotics and Automation_. 952–957.  https://doi.org/10.1109/ROBOT.2006.1641832
  * Kloetzer and Belta (2008) M. Kloetzer and C. Belta. 2008.  A Fully Automated Framework for Control of Linear Systems from Temporal Logic Specifications.  _IEEE Trans. Automat. Control_ 53, 1 (Feb 2008), 287–297.  https://doi.org/10.1109/TAC.2007.914952
  * Kochenderfer et al. (2012) Mykel J Kochenderfer, Jessica E Holland, and James P Chryssanthacopoulos. 2012.  _Next-generation airborne collision avoidance system_.  Technical Report. MIT-Lincoln Laboratory, Lexington, US.
  * Li et al. (2018) M. Z. Li, W. R. Tam, S. M. Prakash, J. F. Kennedy, M. S. Ryerson, D. Lee, and Y. V. Pant. 2018.  Design and implementation of a centralized system for autonomous unmanned aerial vehicle trajectory conflict resolution. In _Proceedings of IEEE National Aerospace and Electronics Conference_.
  * Lofberg (2004) Johan Lofberg. 2004\.  YALMIP: A toolbox for modeling and optimization in MATLAB. In _2004 IEEE international conference on robotics and automation (IEEE Cat. No. 04CH37508)_. IEEE, 284–289.
  * Luukkonen (2011) Teppo Luukkonen. 2011\.  Modelling and control of quadcopter.  _Independent research project in applied mathematics, Espoo_ 22 (2011).
  * Ma et al. (2016) Xiaobai Ma, Ziyuan Jiao, and Zhenkai Wang. 2016.  Decentralized prioritized motion planning for multiple autonomous UAVs in 3D polygonal obstacle environments. In _Inter. Conf. on Unmanned Aircraft Systems_.
  * Maler and Nickovic (2004) Oded Maler and Dejan Nickovic. 2004.  _Monitoring Temporal Properties of Continuous Signals_.  Springer Berlin Heidelberg.
  * Manfredi and Jestin (2016) G. Manfredi and Y. Jestin. 2016.  An introduction to ACAS Xu and the challenges ahead. In _2016 IEEE/AIAA 35th Digital Avionics Systems Conference (DASC)_. 1–9.  https://doi.org/10.1109/DASC.2016.7778055
  * Mueller et al. (2015) Mark W Mueller, Markus Hehn, and Raffaello D’Andrea. 2015\.  A computationally efficient motion primitive for quadrocopter trajectory generation.  _IEEE Transactions on Robotics_ 31, 6 (2015), 1294–1310.
  * NASA (2018) NASA. 2018.  Executive Briefing: Urban Air Mobility (UAM) Market Study.  https://www.nasa.gov/sites/default/files/atoms/files/bah_uam_executive_briefing_181005_tagged.pdf.
  * Pant et al. (2017) Yash Vardhan Pant, Houssam Abbas, and Rahul Mangharam. 2017\.  Smooth operator: Control using the smooth robustness of temporal logic. In _Control Technology and Applications, 2017 IEEE Conf. on_. IEEE, 1235–1240.
  * Pant et al. (2015) Yash Vardhan Pant, Houssam Abbas, Kartik Mohta, Truong X Nghiem, Joseph Devietti, and Rahul Mangharam. 2015\.  Co-design of anytime computation and robust control. In _2015 IEEE Real-Time Systems Symposium_. IEEE, 43–52.
  * Pant et al. (2018) Yash Vardhan Pant, Houssam Abbas, Rhudii A Quaye, and Rahul Mangharam. 2018.  Fly-by-logic: control of multi-drone fleets with temporal logic objectives. In _Proceedings of the 9th ACM/IEEE International Conference on Cyber-Physical Systems_. IEEE Press, 186–197.
  * Raman et al. (2014a) V. Raman, A. Donze, M. Maasoumy, R. M. Murray, A. Sangiovanni-Vincentelli, and S. A. Seshia. 2014a.  Model predictive control with signal temporal logic specifications. In _53rd IEEE Conf. on Decision and Control_. 81–87.  https://doi.org/10.1109/CDC.2014.7039363
  * Raman et al. (2014b) Vasumathi Raman, Alexandre Donzé, Mehdi Maasoumy, Richard M Murray, Alberto Sangiovanni-Vincentelli, and Sanjit A Seshia. 2014b.  Model predictive control with signal temporal logic specifications. In _53rd IEEE Conference on Decision and Control_. IEEE, 81–87.
  * Rodionova et al. (2020) Alena Rodionova, Yash Vardhan Pant, Kuk Jang, Houssam Abbas, and Rahul Mangharam. 2020\.  Learning to Fly - Learning-based Collision Avoidance for Scalable Urban Air Mobility.  _Proceedings of the IEEE International Conference on Intelligent Transportation Systems_ (2020).  http://arxiv.org/abs/2006.13267
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. 2015\.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_ 115, 3 (2015), 211–252.  https://doi.org/10.1007/s11263-015-0816-y
  * Saha et al. (2014) Indranil Saha, Ramaithitima. Rattanachai, Vijay Kumar, George J. Pappas, and Sanjit A. Seshia. 2014.  Automated Composition of Motion Primitives for Multi-Robot Systems from Safe LTL Specifications. In _IEEE/RSJ International Conference on Intelligent Robots and Systems_.
  * Saha and Julius (2016) S. Saha and A. Agung Julius. 2016.  An MILP approach for real-time optimal controller synthesis with Metric Temporal Logic specifications. In _Proceedings of the 2016 American Control Conference (ACC)_.

##  Appendix A Robustness Tubes Shrinking

###### Definition 3.

The distance between two sets $A$ and $B$ is defined as:

(31) $\mathbf{dist}(A,B)=\inf\left\\{||a-b||_{\infty}\ |\ a\in A,\ b\in
B\right\\}$

###### Definition 4.

Two robustness tubes $\mathbf{P}_{1}$ and $\mathbf{P}_{2}$ are said to be
$\delta$-separate from each other if at every time step $k$ the distance
between them is at least $\delta$, i.e.

(32) $\mathbf{dist}(P_{1,k},P_{2,k})\geq\delta\ \forall k=0,\ldots,H.$

For brevity we use $\mathbf{dist}(\mathbf{P}_{1},\mathbf{P}_{2})\geq\delta$
for denoting being $\delta$-separate across all time indices $k=0,\ldots,H$.

###### Proof of Theorem 5.3.

By construction of RTS, see Algorithm 4. If initial tubes are
$\delta$-separate then no shrinking is required and therefore, both properties
(13) and (12) are satisfied. If the initial tubes are not $\delta$-separate,
property (13) comes from the fact that for any time step $k$,
$P_{j,k}^{\prime}=P_{j,k}\setminus\varPi_{k}$ for UAS $j=1,2$. Property (12)
is a consequence of the zero-slack solution and Theorem 4.2 which states that
resulting trajectories are non-conflicting,
$||p_{1,k}^{\prime}-p_{2,k}^{\prime}||\geq\delta$, $\forall
k\in\\{0,\ldots,H\\}$, therefore, $msep\geq\delta$. Following Algorithm 4, for
any time step $k$ box’s $\varPi_{k}$ smallest edge is
$\min(msep,\delta)=\delta$ and since for both UAS $j=1,2$ the tubes update is
defined as $P_{j,k}^{\prime}=P_{j,k}\setminus\varPi_{k}$, the shrinked tubes
$P_{j,k}^{\prime}$ are $\delta$-separate. ∎

###### Proof of Lemma 5.4.

From the CA-MPC definition (6) it follows that
$\mathbf{p}_{j}^{\prime}\in\mathbf{P}_{j}$, $\forall j\in\\{1,2\\}$. The
updated tubes are defined as
$\mathbf{P}_{j}^{\prime}=\mathbf{P}_{j}\setminus\boldsymbol{\varPi}$, see
Algorithm 4. By the definition of 3D cube $\boldsymbol{\varPi}$, for any time
step $k$, ${p}_{j,k}^{\prime}\not\in\varPi_{k}$, therefore,
$\mathbf{p}_{j}^{\prime}\in\mathbf{P}_{j}^{\prime},\ \forall j\in\\{1,2\\}$. ∎

###### Proof of Lemma 5.5.

Following the Definition 4, tubes are $\delta$-separate if
$\mathbf{dist}(P_{1,k},P_{2,k})\geq\delta,\ \forall k\in\\{0,\ldots,H\\}$.
Therefore, due to (31) the following holds:

(33) $\inf\left\\{||p_{1,k}-p_{2,k}||\mid\ p_{1,k}\in P_{1,k},\ p_{2,k}\in
P_{2,k}\right\\}\geq\delta.$

By the definition of the infimum operator, $\forall p_{1,k}\in P_{1,k},\forall
p_{2,k}\in P_{2,k}$:

(34) $||p_{1,k}-p_{2,k}||\geq\inf\left\\{||p_{1,k}-p_{2,k}||\mid\ p_{1,k}\in
P_{1,k},\ p_{2,k}\in P_{2,k}\right\\}\geq\delta,$

which completes the proof. ∎

###### Proof of Lemma 5.6.

  1. (1)

Property (21) directly follows from Theorem 4.2.

  2. (2)

Due to Theorem 5.3, RTS application (17) leads to tubes
$\mathbf{P}^{\prime\prime}_{1}$ and $\mathbf{P}^{\prime}_{3}$ being
$\delta$-separate. RTS (18) leads to
$\mathbf{P}^{\prime\prime}_{3}\subseteq\mathbf{P}^{\prime}_{3}$. Therefore,
$\mathbf{P}^{\prime\prime}_{1}$ and $\mathbf{P}^{\prime\prime}_{3}$ are
$\delta$-separate and following Lemma 5.5, property (20) holds.

  3. (3)

Analogously, due to Theorem 5.3, RTS application (16) leads to tubes
$\mathbf{P}^{\prime}_{1}$ and $\mathbf{P}^{\prime}_{2}$ being
$\delta$-separate. RTS (17) leads to
$\mathbf{P}^{\prime\prime}_{1}\subseteq\mathbf{P}^{\prime}_{1}$ and RTS (18)
leads to $\mathbf{P}^{\prime\prime}_{2}\subseteq\mathbf{P}^{\prime}_{2}$.
Therefore, $\mathbf{P}^{\prime\prime}_{1}$ and $\mathbf{P}^{\prime\prime}_{2}$
are $\delta$-separate and following Lemma 5.5, property (19) holds.

  4. (4)

Tube belonging property (22) follows directly from Lemma 5.4.

∎

##  Appendix B Links to the videos

Table 4 has the links for the visualizations of all simulations and
experiments performed in this work.

Scenario | Section | Platform |  $\\#$ of UAS | Link
---|---|---|---|---
L2F test | Sec. 6.2 | Sim. | 2 | https://tinyurl.com/l2f-exmpl
Crazyflie validation | Sec. 6.2 | CF 2.0 | 2 | https://tinyurl.com/exp-cf2
Four UAS position swap | Sec. 6.3.1 | Sim. | 4 | https://tinyurl.com/swap-pos
Four UAS reach-avoid mission | Sec.6.3.2 | Sim. | 4 | https://tinyurl.com/reach-av
High-density unit cube | Sec.6.3.3 | Sim. | 10, 20, 40 | https://tinyurl.com/unit-cube
MILP re-planning | Sec 6.3.4 | MATLAB | 20 | https://tinyurl.com/re-milp
Table 4. Links for the videos for simulations and experiments. “Sim.” stands
for Python simulations, “CF2.0” for experiments on the Crazyflies.

  *[UAS]:
  *[UAM]:
  *[UTM]:
  *[CA]:
  *[MILP]:
  *[CR]: