A Finite-State Fixed-Corridor Model for UAS Traffic Management

UTM development by the National Aeronautics and Space Administration (NASA) and FAA is summarized in [11],[12] and [13]. In particular, NASA and FAA are developing UTM-specific metrics and protocols to authenticate users, manage datalink and databases, separate UAS from manned aircraft, and provide updated information to users. A candidate UTM concept of operation in  [14] discusses the roles and responsibilities of UTM and UAS pilots. Although the approach in  [14] is fundamentally based on manned air traffic control, relevant methods of UAS control, maneuverability, range, and operational constraints are presented. Reference  [15] compares airspace safety and capacity with different protocols ranging from free-flight to a network of fixed corridors with pre-planned UAS trajectories meeting separation standards. Issues in deploying UTM for autonomous point-to-point UAS traffic are discussed in [16].

A primary UTM challenge is to assure operational scalability  [17], particularly for payload transport applications. This has led package transport companies to propose service models of UTM  [18], e.g., low-speed local traffic, high-speed transit layer traffic. Authors in [19] propose a first-come-first-serve procedure to avoid trajectory conflicts. Because UTM will blanket the ground with low-altitude UAS, UTM protocols must also responsibly integrate with a diverse suite of overflown communities mapped by property zoning, a mobile population, navigation signal availability, terrain, man-made infrastructure, and community preferences [20].

A three-dimensional air corridor system is proposed in [21] to safely manage low-altitude UAS traffic. Reference  [22] presents a computationally efficient global subdivision method to organize traffic. Four types of low-altitude air routes are designed with a discrete grid transforming the complex spatial computation problem into a spatial database query. Airspace geofencing has been proposed to assure UAS respect no-fly-zones and remain within their allocated airspace volumes [23, 24, 25]. Reference  [26] presents three-dimensional flight volumization algorithms using computational geometry and offers path planning solutions responsive to dynamic airspace allocation constraints. UAS path planning must be closely coordinated with or performed by UTM to assure collision-free flight plans compatible with existing traffic flows. Graph search methods such as A* search [27] and D*  [28] can efficiently generate solutions with abstract or local-area search spaces. Roadmaps such as Voronoi and visibility graphs  [29] and random sampling approaches  [30] such as RRT* [31] reduce search space complexity in 2-D and 3-D environments.

Markov decision process (MDP) is a discrete system decision making framework applicable to situations where outcomes are not deterministic. The MDP has been used in a variety of applications including but not limited to finance, maintenance, queue management and robotics. MDP models can be used for path planning given a finite discrete state-space. The authors in [32] and [33] have proposed a collision avoidance system using an MDP model. Reference  [34] proposes an MDP for UAS path planning to track multiple ground targets in a dynamic environment.

Researchers have developed different methods for UAS coordination. For example, containment control [35], consensus-based control [36], partial differential-based approach [37], graph-based methods [38] and continuum deformation approach [39][40]. We adopt a compact Eulerian continuum mechanics model for UAS coordination in this paper.

This paper proposes defining UAS traffic coordination for UTM as a spatiotemporal planning problem. For spatial planning, we define UAS coordination as an ideal fluid flow governed by the Laplace partial differential equation (PDE) with inspiration from  [40]. Terrain, buildings, and infrastructure are wrapped by airspace obstacles (i.e., no-fly zones) through which we propose the design of fixed airway corridors. In particular, we divide the airspace into different layers and assign each UAS to transit in a fixed altitude layer along that layer’s prescribed traffic flow streamline. Transitions between air corridor layers are permitted at a cost that encourages each UAS to remain in a single layer when possible. For temporal planning, we define an MDP to authorize safe UAS transitions between air corridors in a centralized manner consistent with current concepts proposed for community-based UTM. Compared to the existing literature and the authors’ previous work, this paper offers the following novel contributions:

1. 1.

   We propose a UTM architecture that includes time-invariant air corridor layers for transiting UAS traffic. Specifically, obstacle-free air corridor geometries are defined by solving a Laplace PDE that safely wraps buildings and no-flight-zones at low computation cost,

2. 2.

   We propose an MDP-based collision-free multi-vehicle path planning strategy that applies a first-come-first-serve prioritization to UAS airway corridor allocation.

This paper is organized as follows. Section II provides a problem statement followed by a description of our methodology in Section III. Operation of the proposed layered UTM airspace is summarized in Section IV. Simulation results are presented in Section V followed by a brief conclusion in Section VI.

Section III-A1 presents the foundations of ideal fluid flow coordination. Next, Section III-A2 discusses how fluid flow coordination can be applied to generate safe air corridors in urban low-altitude airspace.

We define an MDP to maximize the usability of the low-altitude airspace through optimal allocations of air corridors to UAS. Note that although the below formulation supports a general stochastic dynamic programming (SDP) or MDP model, we later define case studies relying on a dynamic programming model for which the MDP/SDP state transition function is deterministic rather than stochastic.

The generalized MDP models decision-making in discrete environments with stochastic or partially stochastic outcomes and is defined by tuple

with the following elements:

1. 1.

   Finite set of states $\mathcal{S}$;

2. 2.

   Finite set of actions $\mathcal{A}$;

3. 3.

   State transition dynamics defined by probability tensor

   $$P=\bigcup_{s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}}P_{a}(s,s^{\prime})$$

   where $P_{a}(s,s^{\prime})$ assigns transition from current state $s\in\mathcal{S}$ to state $s^{\prime}\in\mathcal{S}$ under action $a\in\mathcal{A}$;

4. 4.

   Cost function

   $$J=\bigcup_{s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}}J_{a}(s,s^{\prime})$$

   where $J_{a}(s,s^{\prime})$ assigns numerical cost at state $s\in\mathcal{S}$ under action $a\in\mathcal{A}$;

5. 5.

   Discount factor $\gamma\in\left[0,1\right]$.

Note that cost function $J$ can equivalently be defined by a negative reward function $R$ in an MDP. The MDP policy specifying a mapping from states to actions maximizes expected value at each state. Note that some researchers [43] define an MDP formulation that minimizes cost and expected cost instead. We use a minimum cost MDP formulation in this paper. MDP value function $V:\mathcal{S}\rightarrow\mathbb{R}^{+}$ defines total expected value corresponding to the sequence of states ${\color[rgb]{0,0,0}s}=(s_{1},\dots,s_{t},\dots)$ and actions $a=(a_{1},\dots,a_{t},\dots)$:

Using the value iteration algorithm, we can compute a function $V_{i}(s):\mathcal{S}\rightarrow\mathbb{R}^{+}$ that associates to each state $s$ a lower bound to the optimal cost $V^{*}(s)$. In particular, by updating $V_{i}(s)$ in the following way

$V_{i}(s)$ converges monotonically and in polynomial time to $V^{*}(s)$. Threshold $\epsilon$ specifies the numerical convergence requirement for value in each state:

The optimal policy $\pi^{*}(s)$ is defined as the sequence of actions that provide the optimal total cost $V^{*}(s)$ starting at state $s$ and is computed from:

Although, we assume that transitions over the state space are deterministic, we can indirectly incorporate uncertainty into planning by updating the geometry of the unplanned space without changing the dimension of the state space. In other words, if a UAS cannot admit or follow the desired corridor assigned by the authorized decision-maker, it is contained by an unplanned airspace and safely excluded from the planned airspace. Note that this problem has been previously investigated by the second and third authors in Ref. [40].

For the UAS traffic management, without loss of generality, the low altitude airspace is projected on eight layers ($n_{l}=8$), denoted by $\mathcal{C}_{1}$, $\cdots$, $\mathcal{C}_{8}$, where:

1. 1.

   Streamlines are elongated along the $x$ axis on $\mathcal{C}_{1}$, $\mathcal{C}_{3}$, $\mathcal{C}_{5}$, and $\mathcal{C}_{7}$;

2. 2.

   Streamlines are elongated along the $y$ axis on $\mathcal{C}_{2}$, $\mathcal{C}_{4}$, $\mathcal{C}_{6}$, and $\mathcal{C}_{8}$.

We define $\mathcal{L}_{i}$ as a finite set identifying the air corridors at $\mathcal{C}_{i}\subset\mathbb{R}^{2}$ ($i\in\left\{1,\cdots,8\right\}$). Also, we define $\mathcal{X}$ and $\mathcal{Y}$ as finite sets representing discrete values of $x$ and $y$ coordinates, respectively, and finite set $\mathcal{T}$ defines future discrete times.

The state set $\mathcal{S}$ is finite and defined by

where “$\times$” is the Cartesian product symbol.

We define four possible actions $\mathcal{A}=\{a_{1},a_{2},a_{3},a_{4}\}$ with the following functionality:

• •

  $a_{1}$: Move forward in the current corridor,

• •

  $a_{2}$: Stay at the current position for the next time,

• •

  $a_{3}$: Move to the next higher level,

• •

  $a_{4}$: Move to the next lower level.

Note that the actions are constrained to satisfy the following limitations:

1. 1.

   At the highest level $a_{3}$ must not be selected.

2. 2.

   At the lowest level $a_{4}$ must not be selected.

3. 3.

   Transition from the current state $s\in\mathcal{S}$ to the next state $s^{\prime}\in\mathcal{S}$ is allowed only if $s^{\prime}$ has not already been allocated to another UAS.

Without loss of generality, case studies in this paper assume transitions over the states are deterministic, which in turn implies that probability $P_{a}\left(s,s^{\prime}\right)$ is a binary variable, either $0$ or $1$ for $a\in\mathcal{A}$ and $s,s^{\prime}\in\mathcal{S}$. More specifically, when transition from $s$ to $s^{\prime}$ is feasible, $P_{a}(s,s^{\prime})=1$, otherwise $P_{a}(s,s^{\prime})=0$. We assume that the next state $s^{\prime}$ is feasible, if $d(s,s^{\prime})\leq\delta_{0}$, where $\delta_{0}$ is a threshold value, and $d(s,s^{\prime})$ is the Euclidean distance between two states $s$ and $s^{\prime}$ that is defined as follows:

where $\left(x,y\right)$ and $\left(x^{\prime},y^{\prime}\right)$ are positions associated with current state $s\in\mathcal{S}$ and next state $s^{\prime}\in\mathcal{S}$, respectively.

To optimally allocate air corridors to a new UAS, we define cost $J_{a}(s,s^{\prime})$ as follows:

where $s_{g}$ is the target state for a new UAS, $d(s^{\prime},s_{g})$ is the metric distance between the next state $s^{\prime}$ and target state $s_{g}$, and $J_{0}$ is constant and considered to penalize unnecessary layer change, where $\alpha_{a}$ is a binary variable defined as follows:

In this paper, we choose $\gamma=1$ to optimally assign the air corridors to the UAS. The optimal policy $\pi^{*}(s)$ obtained by (13) is assigned by the value iteration method.