# Control Protocol Design and Analysis for Unmanned Aircraft System Traffic
Management

Jiazhen Zhou, Dawei Sun, Inseok Hwang, Dengfeng Sun Jiazhen Zhou, Dawei Sun,
Inseok Hwang and Dengfeng Sun are with the School of Aeronautics and
Astronautics, Purdue University, West-Lafayette, IN 47906 USA; Emails:
{zhou733, sun289, ihwang<EMAIL_ADDRESS>
###### Abstract

Due to the rapid development technologies for small unmanned aircraft systems
(sUAS), the supply and demand market for sUAS is expanding globally. With the
great number of sUAS ready to fly in civilian airspace, an sUAS aircraft
traffic management system that can guarantee the safe and efficient operation
of sUAS is still at absence. In this paper, we propose a control protocol
design and analysis method for sUAS traffic management (UTM) which can safely
manage a large number of sUAS. The benefits of our approach are two folds: at
the top level, the effort for monitoring sUAS traffic (authorities) and
control/planning for each sUAS (operator/pilot) are both greatly reduced under
our framework; and at the low level, the behavior of individual sUAS is
guaranteed to follow the restrictions. Mathematical proofs and numerical
simulations are presented to demonstrate the proposed method.

##  1 Introduction

With the vast investment of financial support and research effort, sUAS are
envisioned to achieve autonomy based on the rapid development of technologies
including guidance, communication, sensing, and control. Commercial sUAS have
been developed for a variety of tasks, such as package delivery, rescue
operations, photography, surveillance, infrastructure monitoring, and etc. The
market for sUAS of civilian purposes is expanding rapidly with the potential
users including companies, governments, and hobbyists. With expectation of a
great number of sUAS operating in the airspace system, especially in the urban
environment, the control of sUAS behavior and management of their traffic are
crucial for safety and efficiency [1]. With the above concerns, some rules and
laws to regulate the operation of sUAS in the civil domain have been published
by the Federal Aviation Administration (FAA) [2]. However, a traffic
management system that can ensure the enforcement of the rules and the
efficiency of the system is still at absence.

The need for sUAS Traffic Management (UTM) System has long been recognized
with the increasing number of registered sUAS. The FAA and NASA are leading
efforts for making the rules and conducting the research on the large scale
sUAS operations. A build-a-little-test-a-little strategy is currently used to
address the scalability [3]. The UTM research is divided into four Technology
Capability Levels (TCL) [4]:

  * •

achieve rural UAS operations for agriculture, firefighting and infrastructure
monitoring.

  * •

realize beyond-visual line-of-sight operations in sparsely populated areas,
and provide flight procedures and traffic rules for longer-range applications.

  * •

include cooperative and uncooperative UAS tracking capabilities to ensure
collective safety of manned and unmanned operations over moderately populated
areas.

  * •

involve UAS operations in higher-density urban areas for tasks such as news
gathering and package delivery, and large-scale contingency mitigation.

The flight tests for TCL 1 and TCL 2 have been successfully conducted in
NASA’s test cites, and basic requirements for sUAS operation in less populated
areas have been proposed based on test results [3, 5]. The discussion and test
on airspace design, corridors, geofencing, severe weather avoidance,
separation management, spacing, and contingency management are the main focus
and most challenging parts in TCL 3 and TCL 4 research. However, no results on
TCL 3 and TCL 4 have been reported, to the best of our knowledge. On the other
hand, a few works have conceptually discussed the architecture of UTM system
and identified its basic elements [6, 7, 8]. These works envision UTM based on
the existing Air Traffic Management (ATM) system for crewed aircraft.
Nevertheless, such a design may not be feasible for large scale operation or
dense traffic in the sense that it requires features like flight
authorizations, flight plan review/approval, external data services (weather,
intruder), which may suffer from the curse of dimensionality.

To improve the scalability of UTM, we note some key characteristics
differentiating sUAS operation from the existing crewed aircraft operation.
For crewed aircraft, the human pilot is capable of directly controlling the
behavior of an aircraft. In contrast, the human operator for sUAS with remote
control has to rely on the system’s autonomous control and/or decision
supporting tools to cope with the large scale operation and complicated
operational environment [9]. Although this autonomous nature brings more
challenges to sUAS hardware/software requirements and risk evaluation, it
brings an opportunity for UTM to administrate the sUAS from a control systems
prospective. The fact that the behavior of an sUAS is more governed by the
autopilot instead of the human operator reveals that UTM may regulate the
collective sUAS traffic behavior by adopting certain control protocols: if the
sUAS can agree on predefined control protocols in certain airspace, then
collective safety/efficiency assurance for sUAS traffic can be converted to a
control protocol design problem. By directly regulating the sUAS traffic
behavior in the control level, UTM can reduce the effort for trajectory
planning and reviewing significantly.

According to the aforementioned idea, we propose a control protocol design and
analysis method to improve the scalability for UTM. In this framework, we
envision that UTM is responsible for publishing control protocols for sUAS
operating in each basic traffic element such that the desirable collective
traffic behavior is assured without reviewing the high dimensional
trajectories of all sUAS explicitly. The basic element of sUAS traffic network
considered here is called a single link, which is an abstraction of “road” or
“lane”, proposed by NASA [10]. The main ingredient of our framework is based
on the artificial potential field (APF) approach to control the behavior of
sUAS in each link, which is motivated by successes of the APF approach in
various aerospace applications such as aircraft guidance law design [11],
conflict resolution [12], and multi-agent control [13]. Upon the agreement of
a set of APF functions in the control protocol, sUAS can achieve desired
collective behaviors, such as collision avoidance, boundary clearance, and
speed regularization. Our framework, on its core, converts the problem of sUAS
traffic control to an APF-based decentralized protocol design problem, similar
to flocking control. A commonly accepted definition for flocking behavior is
given by Reynolds rules [14]: 1) stay close to nearby flockmates, 2) avoid
collision with nearby flockmates, and 3) attempt to match the velocity with
nearby flockmates. For safe UTM operation, collision avoidance is crucial, and
the velocity of each sUAS should conform to the desired/reference speed
associated with the link. A representative design of APF-based flocking
control has been introduced by Olfati-Saber [15]. Following the idea, variants
of distributed flocking algorithms have been proposed, i.e., the flocking
algorithm under time varying communication network topology [16], the flocking
algorithm that considers complex robotics models with non-holonomic
constraints [17, 18, 19, 20, 21], and the hybrid flocking algorithm for fixed-
wing aircraft [22].

It should be noted that our problem of APF-based control protocol design and
analysis for UTM is different from any existing flocking control problems. For
flocking algorithm design, even though the collective system of interest has a
multi-agent nature, the system consists of a fixed group of sUAS. However, in
our problem, the system of interest consists of sUAS in a certain traffic
link, which is time varying in the sense that some sUAS may enter the link and
some sUAS may leave the link at some time instances. From the traffic
management perspective, it is desired to investigate the sufficient conditions
for the sUAS to enter the traffic link without causing collision. The answer
to such a problem is related to the analysis of the APF-based control protocol
design using the Hamiltonian function (which is commonly used as an analogue
to the concept of “energy” [15]. Since it is known that the collision
avoidance can be guaranteed by limiting the “energy”, the convergence rate for
energy is especially important for estimating the capacity and entry rate for
safe operation in a link. Indeed, the most challenging part of our theoretic
analysis lies in establishing the convergence rate of the proposed control
protocol, which has not been discussed in general flocking control problems.

The contributions of this work are: 1) We develop a control protocol design
and analysis method which can safely manage sUAS traffic, while improving the
scalability of UTM. The problem of collective behavior regularization and
safety assurance is formally defined based on control theory; 2) After a
formal definition of the sUAS traffic regularization, we design a distributed
control protocol for sUAS in a single traffic link. Based on the convergence
property of our control algorithm, we propose conditions on sUAS for safely
entering a traffic link; and 3) Based on our control protocol, we propose
hardware/software requirements on sUAS operating in the large scale traffic
system.

The rest of the paper is organized as follows. Section 2 identifies the roles
and responsibilities of each element in the sUAS traffic system in our
framework. Section 3 formally introduces the formulation of the sUAS traffic
regularization in a single traffic link and offers theoretical results.
Section 4 demonstrates the results via illustrative numerical simulations.
Finally, Section 5 draws conclusions.

##  2 Elements in the sUAS Traffic System

We consider a basic network structure of the future large scale sUAS traffic.
A network is a fundamental structure of ground traffic and air traffic, and
thus the usage of such structure in sUAS traffic has been envisioned by NASA
[4]. The traffic network is defined as a set of nodes and links, and each link
connects two nodes with specified locations. Each link commits a specified
altitude block and corridor width where sUAS can be flown from one location to
the other. For each link, the authority may specify the desired speed, top
speed, desired separation, and minimum separation for collision avoidance. One
way to ensure all requirements are satisfied is to review every filed flight
plan and make sure every restriction is satisfied. The flight plan is often a
time-position 4D trajectory, and a certain resolution of the trajectory is
required to achieve safety assurance. Such high-dimension, high-resolution
trajectory checking can be overburdening for UTM, which should be responsible
for managing large scale sUAS operations. Another way to efficiently manage
the traffic is to assign sUAS control protocols to each individual traffic
link, by which the collective safety of sUAS traffic within each link can be
guaranteed and restrictions can be satisfied via theoretical analysis.

Figure 1: Proposed UTM framework

Our framework redefines the roles and responsibilities of four main components
in the future sUAS traffic system, which are sUAS operators, infrastructure,
sUAS, and UTM. We explain each component in the order of design process:

  1. 1.

UTM design

     * •

Network Definition: A UTM system needs first define the network whose elements
include the location of the nodes, and virtual boundary of each link. Each
traffic has regulations/rules for sUAS traveling in it, e.g., the speed limit,
minimum separation between sUAS, minimum distance to the virtual boundaries,
and feasible landing areas. Those regulations may or may not be shared through
all links. Separated networks will be necessary for sUAS of different types.
For example, fixed-wing sUAS and multi-copters will need different networks
due to their distinct flight dynamics, cruising speeds and take-off/landing
processes. The construction of the networks needs to be done in collaboration
with law makers, such as the FAA.

     * •

Control Protocol Design: A set of control protocols can be designed for each
link once the rules are defined. In order to have control protocols that are
feasible for all sUAS traveling in the network, a basic physical dynamics of
sUAS will be assumed. One can assume that the sUAS are equipped with low level
autopilot system such that a multi-copter can be viewed as a single integrator
model [23], and a fixed-wing sUAS follows a Dubins car model on the horizontal
plane and a double integrator on the vertical direction [22]. It is desired
that under a common control protocol, sUAS can achieve collective safety
assurance and operational efficiency. During the operation, the control
protocol is broadcast for each link, and sUAS follow the control protocol
after entering the link. Based on the control protocol, UTM can propose
hardware/software requirements on the on-board measurement/estimation or
communication for sUAS.

     * •

Control Protocol Selection: Different sets of control protocols need to be
designed for each link to take into account different factors, such as
weather, human activities, emergencies, etc [2]. During the operations, the
best suited control protocols are selected for links and broadcast.

  2. 2.

Operator

     * •

Low Level Control Design: The operators design low level controllers, such as
from thrust/voltage to accelerations, in order to follow the high level
control protocol broadcast by UTM.

     * •

Equipment: Each sUAS should be equipped with necessary sensors and filters to
estimate its states and relative information such as the distance to
neighboring sUAS or obstacles so that the high level control protocol from UTM
can be properly implemented. The sUAS will need to equip with ports that can
receive supervisory command from UTM broadcast.

     * •

Operation: An operator will need to specify the origin, destination, and the
sequence of links the sUAS will travel.

  3. 3.

Infrastructure

     * •

Broadcast: It is envisioned that broadcasting will be a good practice for
sharing control protocols. By broadcast, control protocols are not hard-coded
on each sUAS. The response is immediate if emergency occurs and different
control protocols are broadcast.

     * •

Monitor: Cameras, LIDAR, and/or radars can also be equipped in the
infrastructure to monitor the sUAS traffic and alert for any intruder or
malfunction.

  4. 4.

sUAS

     * •

State Estimation: During a mission, an sUAS needs to take measurements and
estimate the states of itself and relative information with respect to other
sUAS or obstacles.

     * •

Control Execution: An sUAS receives and executes the control protocol from
broadcast.

     * •

Control Protocol Switching: When arriving at a junction, multiple control
protocols will be available. sUAS select the one specified by the operator
before the mission and complete the transition from one link to another.

The overall framework of our design is summarized in Figure 1. It can be seen
that in our framework, the operators will only need to determine the sequence
of transitions between links. UTM will only need to monitor the real time
traffic situations during the daily operation. Collision free, speed limits
and other requirements are fulfilled by the design of control protocols. The
shift of control design from operators to UTM allows UTM to have a high
authority over the behaviors of the sUAS traveling in the network, and thus
safety and efficiency can be guaranteed by the collective behavior of sUAS in
each link resulting from the common control strategy.

Each element of the future sUAS traffic system discussed above can be
extensively studied. In this article, we limit our attention to one of the
most important and challenging elements: the control protocol design and
analysis. We develop models and theoretical frameworks for analyzing the sUAS
traffic behavior in a single link from a control systems perspective. Our
results can be applied to more common and complicated traffic network elements
such as merge links and split links [24]. We present our results in details in
the following section.

##  3 Problem Formulation and Controller Design

In this section, we formulate the problem of sUAS traffic regularization and
present details about how to design and analyze control protocols to regulate
the sUAS behavior in a link using artificial potential functions. The
objective of this section is to offer a guideline about how to design the APF
for each link in an sUAS traffic network and what condition sUAS should
satisfy at entry of the link under a certain communication protocol structure
such that the speed of all sUAS in the link is regulated and there is no
collision or boundary violations.

###  3.1 Dynamic model for sUAS

In this section, we formally introduce the problem of regularization of sUAS
traffic in a single link model. Let $\mathcal{I}$ be the index set of all the
sUAS in the traffic system. We consider a fixed-wing sUAS whose kinematics is
described as:

$\displaystyle\dot{x}_{i}$ $\displaystyle=v_{i}\cos\theta_{i}$ (1)
$\displaystyle\dot{y}_{i}$ $\displaystyle=v_{i}\sin\theta_{i}$
$\displaystyle\dot{z}_{i}$ $\displaystyle=w_{i}$ $\displaystyle\dot{v}_{i}$
$\displaystyle=a_{i}$ $\displaystyle\dot{\theta}_{i}$ $\displaystyle=\phi_{i}$
$\displaystyle\dot{w}_{i}$ $\displaystyle=\delta_{i},$

where $x_{i}$ and $y_{i}$ are the horizontal coordinates, $z_{i}$ is the
vertical coordinate, $\theta_{i}$ is the horizontal heading angle, $v_{i}$ is
the horizontal velocity, $w_{i}$ is the vertical speed, and $a_{i}$,
$\phi_{i}$ and $\delta_{i}$ are control inputs. By feedback linearizion, the
horizontal dynamics can be converted to a double integrator model. Define
$v_{xi}\triangleq v_{i}\cos\theta_{i}$, and $v_{yi}\triangleq
v_{i}\sin\theta_{i}$. Then, we have:

$\displaystyle\begin{bmatrix}\dot{v}_{xi}\\\
\dot{v}_{yi}\end{bmatrix}=\begin{bmatrix}\cos\theta_{i}&-v_{i}\sin\theta_{i}\\\
\sin\theta_{i}&v_{i}\cos\theta_{i}\end{bmatrix}\begin{bmatrix}a_{i}\\\
\phi_{i}\end{bmatrix}.$ (2)

Let $[u_{xi},\,u_{yi}]=[\dot{v}_{xi},\,\dot{v}_{yi}]$ be our new control
input. We then have the following relation between the new and original
control inputs:

$\begin{bmatrix}a_{i}\\\
\phi_{i}\end{bmatrix}=\begin{bmatrix}\cos\theta_{i}&\sin\theta_{i}\\\
\frac{-\sin\theta_{i}}{v_{i}}&\frac{\cos\theta_{i}}{v_{i}}\end{bmatrix}\begin{bmatrix}u_{xi}\\\
u_{yi}.\end{bmatrix}$ (3)

The transformation is not defined for $v_{i}=0$, which will not be the case
for the fixed-wing sUAS. Now we have a double integrator dynamics for the
fixed-wing sUAS:

$\displaystyle\ddot{x}_{i}$ $\displaystyle=u_{xi}$ (4)
$\displaystyle\ddot{y}_{i}$ $\displaystyle=u_{yi}$ $\displaystyle\ddot{z}_{i}$
$\displaystyle=\delta_{i}.$

Finally we let $q_{i}\triangleq[x_{i},y_{i},z_{i}]^{T}$ be the state vector,
and let the stack vector $q\triangleq\text{col}(q_{1},\,q_{2},\,\dots)$. The
above model simplifies our process for designing control protocols. This also
admits that our following approaches can be easily adopted to control protocol
design for multi-copters whose dynamics can be approximated by a double
integrator.

###  3.2 Problem Formulation

Here we introduce the problem formulation for traffic regulation for a single
link. A single link is defined as a tuple
$L\triangleq(\Omega,\hat{v},\hat{d},d_{\min},d_{b,\min},\hat{d}_{b})$, where
$\Omega$ is the physical space the link takes, $\hat{v}$ is the desired
velocity for all sUAS in $\Omega$, $\hat{d}$ is the desired separation between
the sUAS, and $d_{\min}$ is the minimum separation allowed between sUAS.
$\hat{d}_{b}$ is the desired distance to the boundary of the link, and
$d_{b,\min}$ is the minimum separation to the boundary of the link. Note that
$\hat{v}$ is a velocity vector. We assume that $\Omega$ is a convex
polyhedron, i,e., $\Omega=\\{x|Ax\leq b,\,\partial Ax\leq\partial b\\}$, where
$A\in\mathbb{R}^{m\times 3}$ and $b\in\mathbb{R}^{m}$ representing the
wall/boundary; $\partial A\in\mathbb{R}^{{m^{\prime}}\times 3}$ and $\partial
b\in\mathbb{R}^{m^{\prime}}$ denote the entrance/exit. When the link is
described by a rectangular tube, then $m=4$, and $m^{\prime}=2$. Let $A_{n}$
and $b_{n}$ be the $n_{th}$ row of $A$ and $b$, respectively. Denote the
distance from the $i_{th}$ sUAS to the plane $A_{n}x=b_{n}$ as $d_{in}$. Then,
$d_{in}$ can be given as:

$d_{in}=\frac{A_{n}q_{i}-b_{n}}{A_{n}A_{n}^{T}}.$ (5)

We assume that the set

$\mathcal{A}\triangleq\bigcap_{n=1}^{m}\\{x|\frac{A_{n}x-b_{n}}{A_{n}A_{n}^{T}}\leq\hat{d}_{b}\\}$
(6)

is not empty. It is clear that the reference velocity should be parallel to
each plane, i.e., $\forall n,\,\hat{v}^{T}A_{n}=0,$. We define the set:

$\mathcal{I}_{\Omega}(t)\triangleq\\{i\in\mathcal{I}|\exists\tau\in[t_{0},t],q_{i}(\tau)\in\Omega\\}$
(7)

as the set of all the sUAS which entered the link up to time $t$. The
objective of sUAS traffic control can be divided into two cases. First, if
there is no sUAS entering $\Omega$ after $t_{0}$, i.e., $\forall
t>t_{0},\;\mathcal{I}_{\Omega}(t)=\mathcal{I}_{\Omega}(t_{0})$. We have the
following objectives.

$\displaystyle O_{1}:$ $\displaystyle\forall
i\in\mathcal{I}_{\Omega}(t_{0}),\;\dot{q}_{i}(t)\to\hat{v}\;\text{as
}t\to\infty,$ $\displaystyle O_{2}:$ $\displaystyle\forall
i,\,j\in\mathcal{I}_{\Omega}(t_{0}),\;||q_{i}(t)-q_{j}(t)||\geq\hat{d}\;\text{as
}t\to\infty,$ $\displaystyle O_{3}:$ $\displaystyle\forall
i\in\mathcal{I}_{\Omega}(t_{0}),\;\forall n=1\dots
m,\;d_{in}\geq\hat{d}_{b}\;\text{as }t\to\infty,$

subject to the following constrains:

$\displaystyle C_{1}:$ $\displaystyle\forall
i\in\mathcal{I}_{\Omega}(t_{0}),\;||\dot{q}_{i}(t)-\hat{v}||\in[\underline{v},\overline{v}]\;\forall
t\geq t_{0},$ $\displaystyle C_{2}:$ $\displaystyle\forall
i,\,j\in\mathcal{I}_{\Omega}(t_{0}),\;||q_{i}-q_{j}||\geq d_{\min}\;\forall
t\geq t_{0},$ $\displaystyle C_{3}:$ $\displaystyle\forall
i\in\mathcal{I}_{\Omega}(t_{0}),\;\forall n=1\dots m,\;d_{in}\geq
d_{b,\min}\;\forall t\geq t_{0}.$

$O_{1}$ requires the velocities of all the sUAS in the link converge to the
desired velocity. $O_{2}$ requires that the separations of all the sUAS are
greater than the desired separation given sufficiently long time. $O_{3}$
requires that the positions of all the sUAS in the link converge to the
desired separation from the boundary. $C_{1}$ requires the boundedness of the
velocities of all the sUAS: the upper bound is given from traffic authority,
and the lower bound is required for the flyable trajectory for fixed-wing
sUAS. $C_{2}$ requires that the separations between sUAS must be greater than
or equal to the minimum separation to ensure collision free. $C_{3}$ requires
that all the sUAS in the link must stay away from the boundary greater than or
equal to minimum distance. Second, if there are sUAS entering $\Omega$ at time
$t_{1}$, let $\mathcal{I}_{\Omega}(t_{1}^{-})$ denote the set of the sUAS
already in the link up to time $t_{1}$, i.e.,

$\mathcal{I}_{\Omega}(t^{-})\triangleq\\{i\in\mathcal{I}|\exists\tau\in[t_{0},t),q_{i}(\tau)\in\Omega\\}.$
(8)

Then we have
$\mathcal{I}_{\Omega}(t_{1}^{-})\subsetneq\mathcal{I}_{\Omega}(t_{1})$. In
this case, only $C_{1}$, $C_{2}$, and $C_{3}$ need to be guaranteed under some
conditions on the entry states which will be discussed. It should be remarked
that sUAS $i$ might be in the link initially and leaves the link at
$t^{*}>t_{0}$, but by our definition of $\mathcal{I}_{\Omega}(t)$,
$i\in\mathcal{I}_{\Omega}(t)$ for any $t>t_{0}$. It is equivalent to assume
the link is infinitely long such that whenever an sUAS enters it, it stays in
it. This assumption facilitates the problem formulation and analysis without
loss of generality, and it can be relaxed based on the approach in this work.

###  3.3 Control Protocol Design and Analysis

According to the control objectives and constraints, an APF-based control
protocol will be introduced in this subsection, which ensures $O_{1}$-$O_{3}$
and $C_{1}$-$C_{3}$ are satisfied assuming no sUAS enters the link $\Omega$,
i.e.,

$\mathcal{I}_{\Omega}(t)=\mathcal{I}_{\Omega}(t_{0}),\ \ \forall t>t_{0}.$ (9)

The convergence rate of the control protocol will be discussed, based on which
the entry condition will be established in the next subsection.

For smooth artificial potential field design, the $\sigma$-norm function
$||\cdot||_{\sigma}:\mathbb{R}^{n}\to\mathbb{R}_{+}$ is commonly considered
[15]:

$||z||_{\sigma}=\frac{1}{\varepsilon}(\sqrt{1+\varepsilon||z||^{2}}-1),$ (10)

where $\varepsilon>0$ is a parameter, and $||\cdot||$ is the Euclidean norm.
$\sigma$-norm is an approximation for the Euclidean norm but equipped with the
differentiability at $z=0$. The gradient of $\sigma$-norm is given as:

$\nabla||z||_{\sigma}=\frac{z}{\sqrt{1+\varepsilon||z||^{2}}}.$ (11)

For a nonzero vector $d$, denote $d_{\sigma}=||d||_{\sigma}$, and it can be
shown that $||d||>d_{\sigma}$. We let the monotone function
$\psi:\mathbb{R}^{+}\to\mathbb{R}^{+}$ be the repulsive potential function for
collision avoidance, and $\phi:\mathbb{R}^{+}\to\mathbb{R}$ be the gradient of
$\psi$. $\psi$ and $\phi$ satisfy:

$\displaystyle\psi(d)=0$ $\displaystyle\iff d\geq\hat{d}$ (12)
$\displaystyle\phi(d)=0$ $\displaystyle\iff d\geq\hat{d}$
$\displaystyle\psi(d)>0$ $\displaystyle\iff 0\leq d<\hat{d}.$

Let $V_{p}$ be the accumulated collision potential energy:

$V_{p}=\frac{1}{2}\sum_{i}\sum_{j\neq i}\psi(||q_{ij}||_{\sigma}),$ (13)

where

$q_{ij}=q_{i}-q_{j},$ (14)

then $V_{p}$ achieves the global minimum of $0$ at $\forall
i,j,\in\mathcal{I}_{\Omega}(t_{0})$ with $i\neq j$,
$||q_{ij}||_{\sigma}\geq\hat{d}$, thus, $||q_{ij}||>\hat{d}$. Similarly, we
let $\psi_{b}$ be the potential function for boundary separation and
$\phi_{b}$ be the gradient of $\psi_{b}$ that (12) is satisfied with $\hat{d}$
replaced by $\hat{d}_{b}$. Let $V_{b}$ be the accumulated boundary potential
energy:

$V_{b}=\sum_{i}\sum_{n}\psi_{b}(d_{in}).$ (15)

$V_{b}$ achieves the global minimum of $0$ when $\forall
i\in\mathcal{I}_{\Omega}(t_{0})$, $\forall k\in\left\\{1,...,m\right\\}$,
$d_{in}\geq\hat{d}_{b}$ We define the accumulated kinetic energy as:

$V_{k}=\frac{1}{2}\sum_{i}(\dot{q}_{i}-\hat{v})^{T}(\dot{q}_{i}-\hat{v}).$
(16)

It is clear that $V_{k}$ achieves the global minimum of $0$ if $\forall
i\in\mathcal{I}_{\Omega}(t_{0}),$, $\dot{q}_{i}=\hat{v}$. Then, the feedback
control protocol is designed as:

$\displaystyle u_{i}$ $\displaystyle=-\sum_{j\neq
i}\phi(||q_{ij}||_{\sigma})\hat{q}_{ij}-\sum_{n=1}^{m}\phi_{b}(d_{in})A_{n}^{T}-K_{i}(v_{i}-\hat{v}),$
(17)

where:

$\displaystyle\hat{q}_{ij}$
$\displaystyle=\frac{q_{ij}}{\sqrt{1+\varepsilon||q_{ij}||^{2}}-1},$ (18)

where $K_{i}$ is the damping ratio, which is a tuning parameter whose design
needs to address the physical capability of the sUAS. We can define the
positive semi-definite Hamiltonian function:

$\displaystyle H$ $\displaystyle=V_{p}+V_{k}+V_{b}.$ (19)

The following theorem shows $O_{1}$, $O_{2}$ and $O_{3}$ are achieved given
that constraints $C_{1}$, $C_{2}$ and $C_{3}$ are satisfied all the time under
the case where no sUAS enters the link after $t_{0}$.

######  Theorem 1.

Consider a fixed group of sUAS (1) in the link $\Omega$, with the initial
configuration in $\Omega_{c}=\\{(q(t_{0}),\dot{q}(t_{0}))|H(t_{0})=c\\}$
applied with control protocol (17) for $t>t_{0}$. The following hold:
(i) $\dot{H}(t)\leq 0,\,\forall\,t>t_{0}$.
(ii) Almost every solution of the multi-sUAS dynamics governed by (1)
converges to an equilibrium where $\forall i,j\in\mathcal{I}_{\Omega}(t_{0})$
with $i\neq j,$,
$\dot{q}_{i}=\hat{v},\,d_{in}\geq\hat{d}_{b},\,||q_{ij}||\geq\hat{d}$ as
$t\to\infty$.
(iii) If $c\leq c_{1}^{*}\triangleq\psi(||d_{\min}||_{\sigma})$, no pair of
sUAS violate the minimum separation $\forall t>t_{0}$.
(iv) If $c\leq c_{2}^{*}\triangleq\frac{1}{2}\tilde{v}^{2}$, where
$\tilde{v}=\min\\{\overline{v}-||\hat{v}||,\,||\hat{v}||-\underline{v}\\}$,
then $\forall
i\in\mathcal{I}_{\Omega}(t_{0}),\,t>t_{0},\,||\dot{q}_{i}||\in[\underline{v},\overline{v}].$
(v) If $c\leq c_{3}^{*}\triangleq\phi_{b}(d_{b,\min})$, then $\forall
i\in\mathcal{I}_{\Omega}(t_{0}),t>t_{0},\,d_{in}>d_{b,\min}$.

###### Proof.

(i) Denote $\delta v_{i}\triangleq\dot{q}_{i}-\hat{v}$. We then have:

$\displaystyle\dot{H}(q,\dot{q})$ $\displaystyle=\sum_{i}\delta
v_{i}^{T}u_{i}+\frac{d}{dt}\Big{[}\frac{1}{2}\sum_{j\neq
i}\psi(||q_{ij}||_{\sigma})+\sum_{n=1}^{m}\psi_{b}(d_{in})\Big{]}$ (20)

By definition, we have:

$\displaystyle\frac{d}{dt}\psi(||q_{ij}||_{\sigma})$
$\displaystyle=\phi(|q_{ij}|)\hat{q}_{ij}{}^{T}(\dot{q}_{i}-\dot{q}_{j})$ (21)
$\displaystyle\frac{d}{dt}\psi_{b}(d_{in})$
$\displaystyle=\phi_{b}(d_{in})A_{n}{}^{T}\dot{q}_{i}$

Substituting control protocol (17) into (20) yields:

$\dot{H}=\sum_{i}-K_{i}\delta v_{i}^{T}\delta v_{i}.$ (22)

(ii) Statement (i) implies that $\dot{H}\leq 0$ given that $H$ is positive
semidefinite. From LaSalle’s invariant principle, all the solutions converge
to the largest invariant set contained in
$\mathcal{I}=\\{(q,\dot{q})|\dot{H}=0\\}$. Starting from almost every initial
configuration, the positions of all sUAS eventually satisfy the desired
separation and their velocities match the reference velocity.
(iii) By contradiction, suppose there exists $t_{1}>t_{0}$, sUAS $i^{*}$ and
$j^{*}$ collide, i.e.,
$||q_{i^{*}j^{*}}(t_{1})||_{\sigma}\leq||d_{\min}(t_{1})||_{\sigma}$, and then

$\displaystyle H(t_{1})$
$\displaystyle\geq\psi(||q_{i^{*}j^{*}}||_{\sigma})+\frac{1}{2}\sum_{i\neq
i^{*},j^{*}}\sum_{j\neq i,i^{*},j^{*}}\psi(||q_{i^{*}j^{*}}||_{\sigma})$ (23)
$\displaystyle\geq c_{1}^{*}>c.$

By Statement (ii), $\forall t>t_{0},\;\dot{H}(t)\leq 0$, therefore
$H(t_{1})\leq H(t_{0})=c<c_{1}^{*}$. Absurd.
The proof for Statement (iv) and (v) follows the same argument as the proof
for Statement (iii), therefore omitted. ∎

By letting the level set for initial configuration as
$\\{(q(t_{0}),\dot{q}(t_{0})|H(t_{0})\leq c^{*}\\}$, where
$c^{*}=\min\\{c^{*}_{1},c^{*}_{2},c^{*}_{3}\\}$. One can achieve
$O_{1},\,O_{2},\,O_{3}$ for almost every initial configuration while
$C_{1},\,C_{2},\,C_{3}$ are satisfied.

It can be seen that under the adoption of LaSalle’s invariant principle, the
asymptotic convergence is given but without a convergence rate. The
convergence rate of the Hamiltonian can be crucial for designing the entry
condition for a link or estimating the behaviors of sUAS in a link for any
given time instance. Now we study the convergence property for a fixed group
of multi-sUAS system (4) with control protocol (17). We start with the
augmented system dynamics:

$\ddot{q}+K\dot{q}+\nabla\Psi(q)=0,$ (24)

where $K$ is the collective damping ratio/time constant, and $\Psi$ is the
collective potential function. It can be seen from (17) that $K$ is a diagonal
matrix with positive diagonal entries. Without loss of generality, we assume
the diagonal elements of $K$ are the same, such that $K$ can be reduced to
scalar. We will refer $K$ as a scalar in the proceeding without further
notification. Such system is often referred as the gradient Hamiltonian
system. The asymptotic convergence of (24) of different types has been
extensively discussed; however, the convergence rate is rarely given [25, 26,
27, 28, 29]. It is noted that system (24) can also be viewed as a second order
differential equation method for solving the following optimization problem:
—l— qΨ(q). The convergence rate is still rarely discussed under the continuous
time optimization framework or flocking control framework. Motivated by the
lack of convergence rate analysis, we develop following the convergence result
for the general Hamiltonian system. We start with following assumptions:

######  Assumption 1.

$\nabla\Psi$ is differentiable and Lipschitz with constant $L$.

######  Assumption 2.

$K>\sqrt{\frac{1}{4L}}$.

Our result for convergence rate is given in the following theorem:

######  Theorem 2.

For system (24), if Assumptions 1, 2 hold and
$\Psi(x(0)),\nabla\Psi(x(0)),\dot{x}(0)$ are finite, then:

$\displaystyle\inf_{\tau\in(0,t)}$ $\displaystyle
p\nabla\Psi(q(\tau))^{T}\nabla\Psi(q(\tau))+r\dot{q}(\tau)^{T}q(\tau)\leq$
(25)
$\displaystyle\frac{1}{t}\Big{(}\frac{1}{2}||\alpha\nabla\Psi(q(0))+\dot{x}(0)||^{2}_{2}+(\alpha+K)\Psi(q(0))\Big{)}$

where $p=\frac{2KL-K^{2}}{4L^{2}}$, $r=\frac{K}{4}$, and
$\alpha=\frac{K}{2L}$.

###### Proof.

Given the dynamic system (24), let Lyapunov-like functions be:

$\displaystyle V_{1}$
$\displaystyle=\frac{1}{2}||\alpha\nabla\Psi(q)+\dot{q}||_{2}^{2}$ (26)
$\displaystyle V_{2}$ $\displaystyle=(\alpha k+1)\Psi(q)$ $\displaystyle
V_{3}$
$\displaystyle=\int_{0}^{t}p\nabla\Psi(q)^{T}\nabla\Psi(q)+r\dot{q}^{T}\dot{q}dt.$
$\displaystyle V$ $\displaystyle=V_{1}+V_{2}+V_{3}.$

Thus $V_{1}$, $V_{2}$, and $V_{3}$ are positive semi-definite. The time
derivative of $V_{1}$ is:

$\displaystyle\dot{V}_{1}=$
$\displaystyle(\alpha\nabla\Psi(q)+\dot{q})^{T}(\alpha\nabla^{2}\Psi(q)\dot{q}-K\dot{q}-\nabla\Psi(q))$
(27) $\displaystyle=$
$\displaystyle-\dot{q}^{T}(KI-\alpha\nabla^{2}\Psi(q))\dot{q}-\alpha\nabla\Psi^{T}\nabla\Psi(q)$
$\displaystyle+\nabla\Psi(q)^{T}(\alpha^{2}\nabla^{2}\Psi(q)-\alpha
KI-I)\dot{q}.$

The time derivative of $V_{2}$ and $V_{3}$ are respectively:

$\displaystyle\dot{V}_{2}=$ $\displaystyle(\alpha
k+1)\nabla\Psi(q)^{T}\dot{q}$ (28) $\displaystyle\dot{V}_{3}=$ $\displaystyle
p\nabla\Psi(q)^{T}\nabla\Psi(q)+r\dot{q}^{T}\dot{q}.$

Adding the derivatives gives:

$\displaystyle\dot{V}=$
$\displaystyle-\dot{q}^{T}((K-r)I-\alpha\nabla^{2}\Psi(q))\dot{q}$ (29)
$\displaystyle-(\alpha-p)\nabla\Psi(q)^{T}\nabla\Psi(q)+\alpha^{2}\nabla\Psi(q)^{T}\nabla^{2}\Psi(q)\nabla\Psi(q)$

Given $\Psi(q)$ is $L$-smooth, we have $\nabla^{2}\Psi\leq LI$. Under
Assumption 2, by letting $r=\frac{K}{4}$ and $\alpha=\frac{K}{2L}$, we have:

$\displaystyle\dot{V}\leq$
$\displaystyle-\frac{K}{4}\dot{q}^{T}\dot{q}-(\alpha-p)\nabla\Psi(q)^{T}\nabla\Psi(q)$
(30) $\displaystyle+\alpha^{2}\nabla\Psi(q)^{T}\nabla^{2}\Psi(q)\nabla\Psi(q)$
$\displaystyle=$
$\displaystyle-\frac{K}{4}(\dot{q}^{T}\dot{q}+\frac{K}{L^{2}}\nabla\Psi(q)^{T}\nabla^{2}\Psi(q)\dot{q}$
$\displaystyle-(\frac{2}{L}-\frac{p}{k})\nabla\Psi(q)^{T}\nabla\Psi(q)).$

By letting $p=\frac{2KL-K^{2}}{4L^{2}}$, we have

$(\frac{2}{L}-\frac{p}{k})I\geq(\frac{K}{2L})^{2}\nabla^{2}\Psi(q)^{T}\nabla^{2}\Psi(q).$
(31)

Thus,

$\dot{V}\leq-\frac{K}{4}||\dot{q}+\frac{K}{2L^{2}}\nabla^{2}\Psi(q)\nabla(q)||_{2}^{2}\leq
0.$ (32)

By the monotonicity of $V$ and the positive semi-definiteness of $V_{1}$ and
$V_{2}$, We have:

$\displaystyle\int_{0}^{t}p\nabla\Psi(q)^{T}\nabla\Psi(q)+r\dot{q}^{T}\dot{q}dt\leq
V_{1}(0)+V_{2}(0),$ (33)

which implies (25). ∎

######  Remark 1.

The significance of Theorem 2 does not limit to UTM applications. It is the
first attempt for establishing the convergence rate result for a general class
of Hamiltonian systems, as well as for the continuous time algorithm for
solving non-convex optimization problem. It is not surprising that
$O(\frac{1}{t})$ convergence is achieved, since such speed is well established
for the first order methods for solving non-convex optimization problem. This
result can be applied to the analysis for the behavior of general classes of
controlled system, such as flocking control, nonlinear control for dissipative
systems, to name a few. It can offer more interpretations for the system
behavior under different contexts while specific understanding or structure of
the system is present.

Note that Theorem 2 is not directly useful in our problem because it only
provides an upper bound for the velocities and gradient forces, not for the
Hamiltonian function. The following proposition provides an insight for
convergence rate of Hamiltonian function under a proper assumption:

######  Proposition 1.

Consider system (24) with Assumptions 1, 2. Suppose there are positive numbers
$\underline{\alpha}$, $\overline{\alpha}$ for the trajectory $q(t)$ such that

$\underline{\alpha}\Psi(q)\leq\nabla\Psi(q){}^{T}\nabla\Psi(q)\leq\overline{\alpha}\Psi(q).$
(34)

Then there is a positive number $\lambda$ such that

$H(t)\leq\frac{\lambda}{t-t_{0}}H(t_{0}).$ (35)

###### Proof.

The proof is purely algebraic since both the left-hand-side and right-hand-
side of (25) involve the quadratic terms of $\nabla\Phi$ and $\dot{q}$.
“$inf$” is removed since $H$ is monotonically decreasing. ∎

######  Remark 2.

It is clear that when the sUAS system is at a desired configuration, condition
(34) holds. For $q$ near the desired configuration, condition (34) can also be
achieved by choosing proper artificial potential functions (e.g., locally
quadratic functions near the desired configuration). The existence of
$\underline{\alpha}$ and $\overline{\alpha}$ allows us to establish a direct
convergence bound on the total Hamiltonian of the system. For $\lambda$, it
can be either algebraically derived or estimated via test or numerical
experiments if a less conservative result is desired. The inequality (34) may
not be necessary for the convergence rate to hold, as one can see in the
simulation results. Such results allow us to offer theoretical completeness
for the proceeding results on sUAS entry condition design.

###  3.4 Entry Condition Design

In the last subsection, we have designed a control protocol based on APF and
we have shown that the state of a fixed group of sUAS converges to an
invariant set in which all sUAS maintain the desired separation and track the
desired speed for almost every initial configuration. The convergence rate of
the Hamiltonian is proved for a fixed group of sUAS. The reason for deriving
this rather stronger convergence property is to quantify the speed of
regulating the behaviors of the sUAS in a link. For almost every initial
condition, we are able to bound the total energy/Hamiltonian in a link at a
given time instance. It allows us to derive the time when the system is ready
to accept more sUAS into the link and to estimate the total amount of energy
the incoming sUAS can bring into the system. By bounding the energy carried by
the incoming sUAS for each fixed time interval, we are able to bound the total
number of incoming sUAS under assumptions. In this way, our framework can not
only account for the micro level regularization of the sUAS behaviors, but
also offer theoretical characterization to the macro level traffic property,
in particular, the flow rate of each traffic link. Such characterization
allows further evaluation of the efficiency of the whole traffic network.

Let

$\\{t|\mathcal{I}_{\Omega}(t)\subsetneq\mathcal{I}_{\Omega}(t^{-})\\}$ (36)

be the set of time instances when sUAS enter $\Omega$. This set is called the
set of time instances of regular entry. Denote the $k$-th entry instance as
$t_{k}$. To limit the entry frequency for sUAS, we consider the following
assumption:

######  Assumption 3.

$\forall k\in\mathbb{Z}_{\geq 0},\,t_{k+1}-t_{k}\geq T.$

According to Proposition 35, we have

######  Proposition 2.

Consider the sUAS in a link with Assumption 2. Assume the conditions in
Proposition 35 hold. Suppose $H(t_{0})<h_{0}$ and for each entry instance
$t_{k}$, $H(t_{k})-H(t_{k}^{-})\leq h_{\epsilon}<h_{0}$. If $T$ given in the
Assumption satisfies

$T\geq\frac{\lambda h_{0}}{h_{0}-h_{\epsilon}},$ (37)

then $H(t)\leq h_{0}$, $\forall t\geq t_{0}$.

Such a result is desirable in the sense that if the entry rate is bounded, the
Hamiltonian function value is bounded such that collision and boundary
violations are excluded. Note that our definition of entry event allows
multiple sUAS enter the link simultaneously and Proposition 2 still applies.
However, the result will be conservative considering the cases where there may
be multiple sUAS enter the link intermittently in a short time period with
relatively regulated configuration. To address such cases, we consider the
following definition for the intermittent entry event of multiple sUAS in a
short time period.

$t_{k}$ is said to be a time instance for a multiple entry event if there are
multiple sUAS enter the link at $t_{k}$ and before $t_{k}+t_{\epsilon}$, where
$t_{\epsilon}$ is a design parameter that should be small. Denote
$\mathcal{I}_{\partial\Omega}(t_{k})$ as the index set for the sUAS enter the
link during $[t_{k},t_{k}+t_{\epsilon})$. Let
$t_{k+1}-(t_{k}+t_{\epsilon})\geq T$ and $T>>t\epsilon$. Since $t_{\epsilon}$
is small, it is of interest to establish entry conditions such that the sUAS
traffic behavior satisfies the constraints during $[t_{k}+\epsilon,t_{k+1})$.
It is done by the following proposition:

######  Proposition 3.

Consider sUAS with dynamics (1) in the link $\Omega$ with conditions in
Proposition 35 valid. Let $t_{k}$, $k\in\mathbb{Z}_{\geq 0}$ be the time
instances of entry events (either regular entry or multiple entry) with
Assumption 3 valid. For all $k\in\mathbb{Z}_{\geq 0}$, assume $\forall
i\in\mathcal{I}_{\partial\Omega}(t_{k+1}),\;j\in\mathcal{I}_{\Omega}(t_{k+1}^{-}),\;\psi(||q_{ij}(t_{k+1}+t_{\epsilon})||_{\sigma})=0$.
Let

$\displaystyle\kappa$
$\displaystyle=\max_{i\in\mathcal{I}_{\partial\Omega}(t_{k+1}+t_{\epsilon})}\frac{1}{2}||\delta
v_{i}(t_{k+1}+t_{\epsilon})||_{2}^{2}+\sum_{n=1}^{m}\psi_{b}(d_{in})$ (38)
$\displaystyle\gamma$ $\displaystyle=\max_{i\neq
j\in\mathcal{I}_{\partial\Omega}(t_{k+1}+t_{\epsilon})}\frac{1}{2}\psi(||q_{ij}(t_{k+1}+t_{\epsilon}))||_{\sigma}).$

If

$M\kappa+M(M-1)\gamma\leq c^{*}(1-\frac{\lambda}{T}),$ (39)

where $M$ is a upper bound for the number of sUAS for all entry events, and
then $\forall t\in\cup_{k}[t_{k}+t_{\epsilon},t_{k+1})$, $C_{1}$, $C_{2}$,
$C_{3}$ are satisfied.

###### Proof.

By the given conditions, we have:

$\displaystyle H(t_{k+1}+t_{\epsilon})=$
$\displaystyle\sum_{i\in\mathcal{I}_{\Omega}(t_{k+1}^{-})}\frac{1}{2}\delta
v_{i}^{T}\delta v_{i}+\sum_{n=1}^{m}\psi_{b}(d_{in})$ (40)
$\displaystyle+\frac{1}{2}\sum_{j\in\mathcal{I}_{\Omega}(t_{k+1}^{-}),j\neq
i}\psi(||q_{ij}||_{\sigma})$
$\displaystyle+\sum_{i\in\mathcal{I}_{\partial\Omega}(t_{k+1}+t_{\epsilon})}\frac{1}{2}\delta
v_{i}^{T}\delta v_{i}+\sum_{n=1}^{m}\psi_{b}(d_{in})$
$\displaystyle+\sum_{{i\in\mathcal{I}_{\Omega}^{\partial}(t_{k+1}+t_{\epsilon})},j\neq
i}\psi(||q_{ij}||_{\sigma})$

for any $k\in\mathbb{Z}_{\geq 0}$. Given that $H(t_{k})\leq c^{*}$, and by
Proposition 35, we have:

$\displaystyle H(t_{k+1}^{-})\leq$ $\displaystyle\frac{c^{*}\lambda}{T}.$ (41)

Thus,

$\displaystyle H(t_{k+1}+t_{\epsilon})\leq$
$\displaystyle\sum_{i\in\mathcal{I}_{\partial\Omega}(t_{k+1}+t_{\epsilon})}\frac{1}{2}\delta
v_{i}^{T}\delta v_{i}+\sum_{n=1}^{m}\psi_{b}(d_{in})$ (42) $\displaystyle+$
$\displaystyle\frac{1}{2}\sum_{{j\in\mathcal{I}_{\partial\Omega}(t_{k+1}+t_{\epsilon})},j\neq
i}\psi(||q_{ij}||_{\sigma})$ $\displaystyle+\frac{c^{*}\lambda}{T}$
$\displaystyle\leq$ $\displaystyle
M\kappa+M(M-1)\gamma+\frac{c^{*}\lambda}{T}.$

Given $M\kappa+M(M-1)\gamma\leq c^{*}(1-\frac{\lambda}{T})$, we conclude that
$H(t_{k+1}+t_{\epsilon})\leq c^{*}$. By Theorem 1, $C_{1}$, $C_{2}$, and
$C_{3}$ are satisfied $\forall t\in\cup_{k}[t_{k}+t_{\epsilon},t_{k+1})$. ∎

######  Remark 3.

The above proposition assumes that the distance between any sUAS entering the
link at $t_{k+1}$ and any sUAS already in the link before $t_{k+1}$ is greater
than or equal to the desired separation. Such assumption can be realized by
the design of $T$ for any given $\hat{v}$. It is also assumed that the
boundedness of the Hamiltonian is satisfied all the time before the entry of
the group of sUAS. This assumption shall not be violated in practice to ensure
safety.

Proposition 3 serves a practical tool for entry condition regularization and
link transition design. It is intuitive that two very “different” links should
not be connected. The following discussion quantifies the maximum difference
between two links in order to be connected. Let the upstream link and
downstream link be
$L_{1}=(\Omega_{1},\hat{v}_{1},\hat{d}_{1},d_{1\min},\hat{d}_{1b},d_{1b,\min})$
and
$L_{2}=(\Omega_{2},\hat{v}_{2},\hat{d}_{2},d_{2\min},\hat{d}_{2b},d_{2b,\min})$,
respectively. Let $\psi^{1},\,\psi_{b}^{1}$ and $\psi^{2},\psi_{b}^{2}$ be the
potential energy functions used for collision avoidance and boundary
separation for $L_{1}$ and $L_{2}$, respectively. Assume that the $L_{1}$ is
long enough that the exiting sUAS are at desired configuration. We also define
the event of link transition. sUAS $i$ is said to transit from $L_{1}$ to
$L_{2}$ if:

$q_{i}\in\mathcal{A}_{1}\cap\mathcal{A}_{2}.$ (43)

This admits that $\mathcal{A}_{1}\cap\mathcal{A}_{2}\neq\emptyset$, and
$\psi_{b}^{1}(d_{in})=\psi_{b}^{2}(d_{in})=0$ for $n=1,\dots,m$. After a
transition, sUAS will start using the control protocol defined on $L_{2}$.
Then $\kappa$ and $\gamma$ in (38) can be quantified based on the definitions
of $L_{1}$ and $L_{2}$, that is:

$\displaystyle\kappa$
$\displaystyle=\frac{1}{2}(\hat{v}_{1}-\hat{v}_{2})^{T}(\hat{v}_{1}-\hat{v}_{2})$
(44) $\displaystyle\gamma$ $\displaystyle=\frac{1}{2}\psi^{2}(\hat{d}_{1})$

It can be observed from (39) that if $\kappa\geq(1-\lambda/T)c^{*}$, then no
more than one sUAS can enter $L_{2}$ from $L_{1}$ to ensure constrains
satisfaction. This phenomenon explains that a high speed link should not be
connected to a low speed link immediately, but another transitional link will
be necessary. The idea of the transitional link resembles the on/off ramp of
the highway in ground traffic. The maximum number of sUAS that can enter
$L_{2}$ from $L_{1}$ in every $[t_{k},t_{k}+t_{\epsilon})$ is then the maximum
integer solution to inequality (39). This identity connects our analysis on
the entry condition to the marco flow control between two connected links.

Figure 2: Configurations of sUAS in every 20s after the entry of a new group
of sUAS

###  3.5 Hardware/Software Requirement

In this section, we briefly discuss the hardware and software requirements of
the implementation of our framework. Based on the control protocol we
designed, we now propose hardware and software requirements on the sUAS.
First, under our current framework, a receiver is required on sUAS to receive
the broadcast control protocol in each traffic link. Certain encoding and
decoding protocols need to be designed in this process to prevent any
potential cyberattack. The control protocol (17) first assumes that position
and velocity are estimated. This can be achieved by the integration of inertia
measurement sensors, such as gyroscope, accelerometer, along with a Global
Positioning System, which are typical equipped on an sUAS. Sensor fusion and
state estimation techniques can be applied to achieve accurate state
information for each sUAS. The subject of state estimation for highly non-
linear sUAS dynamics is non trivial, and we refer to [30, 31] for more
details. Second, for the inter-sUAS separation, the relative distance
measurement is required. Unlike classic formation control or flocking control
problems where a cooperative information exchange protocol is assumed, it may
not be practical to assume that all sUAS traveling in a traffic network can
send and receive state information directly from a communication network.
Furthermore, the relative position is required for our control protocol to be
implemented. The existence of other sUAS and obstacles are not differentiated,
and obstacle sensing techniques can be used to achieve collision avoidance and
desired separation. Detection sensors like radar, LIDAR, or sonar can be used
to measure relative distances of approaching objects. Combinations of sensors
and data fusion techniques can be used to get more accurate state estimates. A
comprehensive survey on sUAS sensing technologies can be found in [32].

##  4 numerical experiments

In this section, we demonstrate the proposed control protocol for UTM with an
illustrative numerical simulation. In the simulation, the potential function
we chose is:

$\psi(x)=\begin{cases}\log(\cosh(x-\hat{d}))\;&\text{if }x<\hat{d}\\\
0\;&\text{otherwise}\end{cases}$ (45)

the gradient of $\psi$ is given by:

$\phi(x)=\begin{cases}\tanh(x-\hat{d})\;&\text{if }x<\hat{d}\\\
0\;&\text{otherwise}\end{cases}$ (46)

We let $\psi_{b}=\psi$ and $\phi_{b}=\phi$. Let $\Omega$ be the polyhedron
whose walls are defined by:

$\displaystyle A=\begin{bmatrix}0&1&0\\\ 0&-1&0\\\ 0&0&1\\\
0&0&-1\end{bmatrix},b=\begin{bmatrix}40\\\ -40\\\ 40\\\ -40\end{bmatrix}.$
(47)

Other parameters for numerical simulation are given as:

Table 1: Parameters for simulation $\hat{v}$ |  $[10,\,0,\,0]^{T}$ [m/s]
---|---
$\overline{v}$ | 25 [m/s]
$\underline{v}$ | 5 [m/s]
$d_{\min}$ | 1.5 [m]
$\hat{d}$ | 10 [m]
$d_{b,\min}$ | 0 [m]
$\hat{d}_{b}$ | 20 [m]
$K_{i}$ | 0.1
$\varepsilon$ | 0.9
$T$ | 20 [s]

Based on the parameters, we can achieve the feasible $c^{*}=8.3069$. The
configurations of sUAS for every $20$ seconds after a new group of sUAS are
presented in Figure 2.

In this experiment, the set $\mathcal{A}\triangleq\\{(x,y,z)|-20\leq y\leq
20,\,-20\leq z\leq 20,\,0\leq x\leq 1000\\}$, and it be observed that the
configuration converges. We also plot the minimum pairwise separation between
sUAS in the traffic link in Figure 3. It can can be observed that all the sUAS
satisfy the minimum separation rule at all time.

Figure 3: Minimum Pairwise Separation

Similarly, it can be seen in Figure 4 that the minimum and maximum velocity
constraints are always satisfied.

Figure 4: Time history of Minimum Velocity and Maximum Velocity

This simulation shows that with our designed control protocol and entry
condition, sUAS are able to enter a single link safely and regulate their
speeds and separations. The fundamental benefit of our control protocol based
sUAS traffic management is not limited to achieve a collective behavior, but
increase the amount of traffic a single link can take under a short period of
time. Under our simulation, at least 2 sUAS can enter the link at every 20
seconds, which allows 360 sUAS to travel across this link per hour. Such a
great amount of traffic is formidable in the classical trajectory file/review
process for traffic management if all the operators file their trajectory
individually. The trajectory reviewing for this amount of traffic can also be
overburden for UTM.

##  5 Conclusion

In this article, we have proposed a new control protocol design and analysis
method which can safely manage a large amount of sUAS, thereby improving
scalability of UTM. By taking the benefits of the autonomous nature of the
sUAS, the traffic management problem is reformulated as a distributed
coordination control for multi-agent systems. We formally defined the sUAS
behavior regularization problem in a single traffic link and proposed a
control protocol to achieve control objectives without violating operating
constraints. Further, we have analyzed the proposed control protocol and
developed the condition for sUAS entering a traffic link. This entry condition
could be successfully converted to traffic management criteria/rules. In the
numerical experiments, the proposed control protocol has been shown to be
effective, and the entry condition is validated. This work offers a
fundamental framework and theoretical results for studying a micro-scope
traffic regularization problem in more complex traffic network elements, such
as merge links and split links.

## References

  * [1] Arwa S Aweiss, Brandon D Owens, Joseph Rios, Jeffrey R Homola, and Christoph P Mohlenbrink.  Unmanned aircraft systems (uas) traffic management (utm) national campaign ii.  In 2018 AIAA Information Systems-AIAA Infotech@ Aerospace, page 1727\. 2018.
  * [2] Federal Aviation Administration (FAA).  Summary of small unmanned aircraft rule (part 107).  2016\.
  * [3] Marcus Johnson, Jaewoo Jung, Joseph Rios, Joey Mercer, Jeffrey Homola, Thomas Prevot, Daniel Mulfinger, and Parimal Kopardekar.  Flight test evaluation of an unmanned aircraft system traffic management (utm) concept for multiple beyond-visual-line-of-sight operations.  2017\.
  * [4] National Aeronautics and Space Administration.  Utm: Air traffic management for low-altitude drones.  2015\.
  * [5] National Aeronautics and Space Administration.  NASA Conducts ‘out of sight’ drone tests in nevada, 2015.
  * [6] Tao Jiang, Jared Geller, Daiheng Ni, and John Collura.  Unmanned aircraft system traffic management: Concept of operation and system architecture.  International journal of transportation science and technology, 5(3):123–135, 2016.
  * [7] Liling Ren, Mauricio Castillo-Effen, Han Yu, Yongeun Yoon, Takuma Nakamura, Eric N Johnson, and Corey A Ippolito.  Small unmanned aircraft system (suas) trajectory modeling in support of uas traffic management (utm).  In 17th AIAA Aviation Technology, Integration, and Operations Conference, page 4268, 2017.
  * [8] Corey A Ippolito, Kalmanje Krishnakumar, Vahram Stepanyan, A Chakrabarty, and J Baculi.  An autonomy architecture for high-density operations of small uas in low-altitude urban environments.  In 2019 AIAA Modeling and Simulation Technologies Conference. San Diego, CA. Jan, volume 2109, 2019.
  * [9] Bernhard Weiß, Michael Naderhirn, and Luigi del Re.  Global real-time path planning for uavs in uncertain environment.  In 2006 IEEE Conference on Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control, pages 2725–2730. IEEE, 2006\.
  * [10] National Aeronautics and Space Administration.  Unmanned aircraft system (uas) traffic management (utm) enabling civilian low-altitude airspace and unmanned aircraft system operations, 2020.
  * [11] Ismael Lopez and Colin R Mclnnes.  Autonomous rendezvous using artificial potential function guidance.  Journal of Guidance, Control, and Dynamics, 18(2):237–241, 1995\.
  * [12] Jason Ruchti, Robert Senkbeil, James Carroll, Jared Dickinson, James Holt, and Saad Biaz.  Unmanned aerial system collision avoidance using artificial potential fields.  Journal of Aerospace Information Systems, 11(3):140–144, 2014.
  * [13] Murat Arcak.  Passivity as a design tool for group coordination.  IEEE Transactions on Automatic Control, 52(8):1380–1390, 2007.
  * [14] Craig W Reynolds.  Flocks, herds and schools: A distributed behavioral model.  In Proceedings of the 14th annual conference on Computer graphics and interactive techniques, pages 25–34, 1987.
  * [15] Reza Olfati-Saber.  Flocking for multi-agent dynamic systems: Algorithms and theory.  IEEE Transactions on automatic control, 51(3):401–420, 2006.
  * [16] Herbert G Tanner, Ali Jadbabaie, and George J Pappas.  Flocking in fixed and switching networks.  IEEE Transactions on Automatic control, 52(5):863–868, 2007.
  * [17] Bin Lei, Wenfeng Li, and Fan Zhang.  Flocking algorithm for multi-robots formation control with a target steering agent.  In 2008 IEEE International Conference on Systems, Man and Cybernetics, pages 3536–3541. IEEE, 2008.
  * [18] Qin Li and Zhong-Ping Jiang.  Flocking control of multi-agent systems with application to nonholonomic multi-robots.  Kybernetika, 45(1):84–100, 2009.
  * [19] Josiel A Gouvea, Fernando Lizarralde, and Liu Hsu.  Potential function formation control of nonholonomic mobile robots with curvature constraints.  IFAC Proceedings Volumes, 44(1):11931–11936, 2011.
  * [20] Jingfu Jin, Yoon-Gu Kim, Sung-Gil Wee, and Nicholas Gans.  Consensus based attractive vector approach for formation control of nonholonomic mobile robots.  In 2015 IEEE International Conference on Advanced Intelligent Mechatronics (AIM), pages 977–983. IEEE, 2015.
  * [21] Silvia Mastellone, Dušan M Stipanović, Christopher R Graunke, Koji A Intlekofer, and Mark W Spong.  Formation control and collision avoidance for multi-agent non-holonomic systems: Theory and experiments.  The International Journal of Robotics Research, 27(1):107–126, 2008\.
  * [22] Dawei Sun, Cheolhyeon Kwon, and Inseok Hwang.  Hybrid flocking control algorithm for fixed-wing aircraft.  Journal of Guidance, Control, and Dynamics, 42(11):2443–2455, 2019\.
  * [23] Yasuhiro Kuriki and Toru Namerikawa.  Consensus-based cooperative formation control with collision avoidance for a multi-uav system.  In 2014 American Control Conference, pages 2077–2082. IEEE, 2014\.
  * [24] Tom Van Woensel and Nico Vandaele.  Modeling traffic flows with queueing models: a review.  Asia-Pacific Journal of Operational Research, 24(04):435–461, 2007\.
  * [25] Kazunaga Tanaka.  Homoclinic orbits in a first order superquadratic hamiltonian system: convergence of subharmonic orbits.  Journal of Differential Equations, 94(2):315–339, 1991.
  * [26] Valery Vasil’evich Kozlov and DV Treshchev.  Weak convergence of solutions of the liouville equation for nonlinear hamiltonian systems.  Theoretical and mathematical physics, 134(3):339–350, 2003.
  * [27] CG Broyden.  A new method of solving nonlinear simultaneous equations.  The Computer Journal, 12(1):94–99, 1969.
  * [28] Uwe Helmke and John B Moore.  Optimization and dynamical systems.  Springer Science & Business Media, 2012.
  * [29] Felipe Alvarez.  On the minimizing property of a second order dissipative system in hilbert spaces.  SIAM Journal on Control and Optimization, 38(4):1102–1119, 2000\.
  * [30] Gerasimos G Rigatos.  Nonlinear kalman filters and particle filters for integrated navigation of unmanned aerial vehicles.  Robotics and Autonomous Systems, 60(7):978–995, 2012.
  * [31] Marco Bibuli, Gabriele Bruzzone, Massimo Caccia, and Lionel Lapierre.  Path-following algorithms and experiments for an unmanned surface vehicle.  Journal of Field Robotics, 26(8):669–688, 2009.
  * [32] Xiang Yu and Youmin Zhang.  Sense and avoid technologies with applications to unmanned aircraft systems: Review and prospects.  Progress in Aerospace Sciences, 74:152–166, 2015.