Aerial cargo delivery operating airspace sector in a hypothetical city. The operating height would ideally be above most buildings and having minimal interaction with the airspace of low-flying aircraft.

Air Traffic Management for Collaborative Routing of Unmanned Aerial Vehicles via Potential Fields

Electrical Engineering and Systems Science > Systems and Control

[Submitted on 17 Mar 2024]

Josue N. Rivera, Dengfeng Sun

Aerial cargo transport is anticipated to play a pivotal role in the distribution of goods within urban environments. The shift is propelled by the surge in e-commerce, the imperative to deliver essential supplies to isolated areas, and the growing demand for expedited and more accessible deliveries.

Our research introduces a quantifiable standard for defining routing restrictions for Unmanned Aircraft System Traffic Management (UTM) using the concept of repulsive potential fields. Furthermore, we propose a scalable infrastructure that facilitates collaborative routing of cargo Unmanned Aerial Vehicles (UAVs) by independent shareholders. The practicality of the infrastructure is validated through a functional prototype implemented at a national scale.

Comments:	Submitted to ICRAT 2024
Subjects:	Systems and Control (eess.SY)
Cite as:	arXiv:2403.11086 [eess.SY]
	(or arXiv:2403.11086v1 [eess.SY] for this version)

Submission history

From: Josue N Rivera [view email]
[v1] Sun, 17 Mar 2024 04:36:20 UTC (22,496 KB)

This paper introduces a standard for defining routing restrictions for Unmanned Aircraft System Traffic Management (UTM) using the concept of repulsive potential fields. It also proposes a scalable infrastructure that facilitates collaborative routing of cargo Unmanned Aerial Vehicles (UAVs) by independent shareholders. The key contributions are:

A standard for defining Urban Air Mobility (UAM) routing restrictions using repulsive potential fields, where areas to avoid have high energy values and other locations have decaying energy values based on distance from restricted areas.
An infrastructure for scalable and quantifiable UTM of cargo UAVs, consisting of clients (UAVs, software systems), a back-end server for managing the shared potential field and validating routes, and databases for storing geographical restrictions in a custom RGeoJSON format.
A functional prototype implementation of the proposed infrastructure, with a client displaying the potential field state, a back-end server handling queries and managing the field, and a database storing restrictions.

The work aims to address regulatory concerns for UAM by enabling airspace governance and providing a quantifiable approach to validate independent third-party routes. It discusses limitations like the assumption of constant altitude operation and identifies future research directions like optimized routing using potential field gradients and large-scale simulations.

data used, verification, and artifacts resulting

The paper does not explicitly mention datasets used for verification or resulting artifacts. However, some relevant details about data and implementation are:

Data:

The geographical restriction databases store infrastructure information and routing restrictions using the proposed RGeoJSON format, which is a variant of the standard GeoJSON format.
For the prototype implementation, an augmented version of multiple infrastructure datasets from the Homeland Infrastructure Foundation-Level Data (HIFLD) repository was used, including data on aviation facilities, fire stations, hospitals, law enforcement, and public schools in the United States.

Verification/Implementation:

A functional prototype of the proposed UTM infrastructure was implemented as a proof of concept.
The prototype consists of three components:

A potential field state client - A React web application that displays the potential field state for a queried U.S. location by sending requests to the back-end server.
A back-end server - A Python Flask application that listens for client queries, manages the shared potential field, and handles communication with databases.
A database - A MongoDB database populated with the HIFLD infrastructure data encoded in RGeoJSON format.

The source code for the client and back-end server is available on GitHub (links provided in the paper).

The paper does not explicitly mention artifacts like datasets or benchmarks resulting from the research, beyond the prototype implementation itself serving as a proof of concept.

RGeoJSON

RGeoJSON (Restriction GeoJSON) is a custom variant of the standard GeoJSON format proposed in this paper. It is used for encoding and storing the geographical restrictions that form the basis of potential field units in the UTM infrastructure.

The key differences between RGeoJSON and standard GeoJSON are:

Addition of properties for the repulsion matrix A and the matrix defining an ellipse shape B to the geometry objects. These matrices parameterize the repulsive force field associated with the geographical restriction.
Removal of support for polygon geometry objects.
Introduction of two new geometry object types - Rectangle and Ellipse. These compensate for the removal of polygons by allowing approximation of polygon shapes using combinations of rectangles and ellipses.

The paper provides examples of all RGeoJSON geometry object types, including Point, LineString, Rectangle, Ellipse, MultiPoint, MultiLineString, MultiRectangle, MultiEllipse, and GeometryCollection.

The motivation behind RGeoJSON is to extend GeoJSON to represent the parameters required to construct the fundamental potential field units corresponding to geographical restrictions, while maintaining some compatibility with the standard GeoJSON format used by many geospatial databases and tools.

Homeland Infrastructure Foundation-Level Data (HIFLD)

The Homeland Infrastructure Foundation-Level Data (HIFLD) is a geographic data repository provided by the Homeland Infrastructure Data Analytics Program under the Department of Homeland Security.

Some key points about the HIFLD repository:

It contains geospatial data for various infrastructure assets across the United States like transportation networks, federal & tribal lands, utilities, structures, and more.
The data is collected from multiple authoritative sources and integrated into a comprehensive database.
It provides a common source of infrastructure geospatial data that can be leveraged by different stakeholders like government agencies, private sector partners, and the public.
The data is available in multiple formats including file geodatabases, shapefiles, and web services.
It covers infrastructure categories like aviation, boundaries, cultural, energy, natural areas, structures, transportation, and utilities infrastructure.
The data repository is designed to assist in activities like security and resilience planning, visualization, analysis, and operations.

In the context of this paper, an augmented version of certain HIFLD datasets like aviation facilities, fire stations, hospitals, law enforcement, and schools was used to populate the geographical restrictions database of the prototype UTM infrastructure implementation.

Authors

Both authors are affiliated with the School of Aeronautics and Astronautics at Purdue University, West Lafayette, Indiana, USA. The paper lists two authors:

Josue N. Rivera - appears to be a graduate student or researcher.
Dengfeng Sun - research interests, based on his faculty page, lie in the areas of air transportation systems, airline operations, unmanned aircraft systems traffic management, and autonomous aerial cargo operations. Some of his relevant publications include:

Some of his relevant publications include:

Sun, D. et al. (2023) "Air Traffic Management for Urban Air Mobility: A Review." Progress in Aerospace Sciences.
Sun, D. et al. (2022) "Dynamic Urban Air Mobility Trajectory Planning Under Wind Uncertainties." AIAA SciTech Forum.
Patel, P.S., Sun, D. et al. (2022) "Network Design for Multi-Modal Aerial Cargo Mobility Systems." AIAA Aviation Forum.
Sun, D. et al. (2021) "Dynamic Rerouting of Unmanned Aircraft in Urban Environments." Journal of Aerospace Information Systems.

So while this specific paper does not cite the authors' prior work directly, it appears to be related to Dr. Sun's broader research program on urban air mobility and unmanned traffic management at Purdue. Josue Rivera is likely a student/researcher collaborating on this effort.

Air Traffic Management for Collaborative Routing of Unmanned Aerial Vehicles via Potential Fields

††thanks: This research has been financially supported by NASA University Leadership Initiative for the project ”Autonomous Aerial Cargo Operations at Scale”.

Josue N. Rivera, Dengfeng Sun School of Aeronautics and Astronautics
Purdue University
West Lafayette, IN, USA
{river264, dsun}@purdue.edu

Keywords:

air traffic management; unmanned aircraft system traffic management; path planning; air transportation governance; information management; drone delivery

I Introduction

Aerial cargo delivery is anticipated to play a pivotal role in urban goods transportation. The surge in e-commerce over the past few years and the escalating demand for expedited delivery from customers have catalyzed the need for sustainable alternatives to traditional delivery methods [1, 2]. The demand for cargo unmanned Aerial Vehicles (UAVs) to deliver critical medicines and other essential goods to remote areas remains as another significant driving force [3, 4]. However, regulatory and privacy concerns present substantial obstacles to the evolution of aerial delivery systems [5]. It is imperative to establish an infrastructure that is scalable and adaptable to a diverse set of policy requirements [6, 7, 5].

A primary motivation for this research is to translate such policies into quantifiable metrics. Metrics that can establish limitations for cargo UAVs and assist in formulating routing solutions for Unmanned Aircraft System Traffic Management (UTM). As such, our work introduces a standard for defining these restrictions and proposes an air traffic management infrastructure that takes advantage of it. The infrastructure would facilitate the deployment of a collaborative platform, enabling independent parties involved in aerial cargo deliveries to operate within the same airspace. This research primarily focuses on last-mile cargo delivery, where UAVs transport packages within an urban environment.

I-A Background

Distinct approaches have been proposed for a UTM infrastructure that can support aerial cargo deliveries operations. One such approach is the design of a hybrid truck-drone model [8, 9, 10, 11]. The design primarily consists of equipping delivery trucks with the capability to launch UAVs that can deliver packages and returns to their vehicle as the trucks travels through an urban space. A few limitations arise from the approach. The coordination of such system would require solving complex variances of the well-known traveling salesmen problem at a large scale for diverse environments [12]. The optimization problem may prove to be a challenging task in a scalable infrastructure. A different popular approach is the use of aerial corridors [13, 14, 15, 16]. It primarily consists of defining an aerial network of predefined paths through which cargo UAVs can travel to their destination. The infrastructure can be made scalable, however, the rigid fly paths may lead to inefficient routes and may not be feasible for the limited range of some UAVs. Additionally, variances of the approach do not take advantage of the often unobstructed airspace.

To address some of the limitations with the designs of these UTM infrastructures, we propose the use of potential fields. Artificial repulsive potential fields are a concept that treats agents as particles moving within a space, influenced by repulsive forces emitted from obstacles [17]. Potential fields are commonly used in path planning and the development of routing algorithms for ground vehicles and robots moving in obstructed spaces [18, 19]. In the realm of traffic management, repulsive artificial potential fields have also been employed to manage coordination of multiple agents. [20, 21], among others, have successfully explored them for non-aerial traffic management systems and demonstrated their success as a traffic management tool. Our work distinguishes itself by being one among a selected few exploring potential fields in aerial routing and presenting a scalable UTM infrastructure that relies on them.

Recently, [22, 23] proposed the use of potential fields for UTM. These approaches present UTM infrastructures that consider moving UAVs or high-density areas as obstacles within a 3D potential field. They demonstrate collision-free collaborative aerial routing in various urban scenarios. Our work expands upon the ideas presented by the authors in three significant ways. First, we standardize the creation of potential fields to ensure a scalable approach. Second, we simplify the problem to enhance adaptability to distinct urban environments by considering aerial routing on a 2D plane. Lastly, we extend the discussion on the applicability of potential fields in existing low-altitude airspace and their use in collaborative aerial cargo deliveries by independent parties.

I-B Assumptions and Context

In our study, we make the assumption that cargo UAVs operate at a constant altitude (e.g., 500+ feet) from the ground and in low-altitude airspace. This altitude forms a plane for a potential field that associates intercepting buildings and other constraints as restrictions. The research primarily focuses on unidirectional cargo delivery trips. The UAVs are assumed to be equipped with Vertical Take-Off and Landing (VTOL) capabilities, or alternatively, they possess a mechanism that enables precise pick-up and drop-off of cargo at their destination and origin. Although the ideal operating height would be above most buildings, the presence of unavoidable structures is anticipated. The shared airspace with other low-altitude aircraft is also factored into consideration. Fig. 1 provides a visualization of the operating airspace sector.

Refer to caption — Figure 1: Aerial cargo delivery operating airspace sector in a hypothetical city. The operating height would ideally be above most buildings and having minimal interaction with the airspace of low-flying aircraft.

I-C Contributions

Our work brings forth the following main contributions:

•

A standard for defining Urban Air Mobility (UAM) routing restrictions.
•

An infrastructure for scalable and quantifiable UTM of cargo UAVs.
•

A functional prototype of the proposed infrastructure.

II Potential Field and Geographical Restriction

To define UAM routing restrictions, we propose a standardized repulsive potential field as a quantifiable representation of the limitations. The field reflects geographical constraints and the desired behavior of UAVs in their vicinity. It associates regions to avoid with a high energy state, while all other locations are associated with an energy value that decays the further they are from these regions. In this proposed standard, an energy value of 1 signifies a complete restriction, while a value of 0 indicates complete freedom for flight. The potential field aims to represent the diverse requirements of stakeholders in an unified format. Fig. 2 illustrates an example of a potential field and a route that has a minimal area under its path.

II-A Fundamental Units for Potential Field

The standardized potential field is built from smaller fundamental units. The units $σ_{i}$ represent individual physical or virtual restrictions in an urban environment that affect the travel of cargo UAVs. Each distinct unit has a set of parameters that defines their impact in the potential field such as where it is placed and the shape of the repulsive force. Examples of the potential field for these fundamental units are presented in Fig. 3. These units may be integrated to form complex fields $Ω$ via a maximum operator (or a variance of it).

Ω (x) = \max (σ_{1} (x | \cdot, A_{1}), σ_{2} (x | \cdot, A_{2}), \dots, σ_{N} (x | \cdot, A_{N}))

(1)

In (1), $x$ represents a given point to evaluate, and $A_{i}$ a positive definite matrix that describes the repulsion from a high energy state. It should be noted that all potential field units have a maximum and minimum energy value of 1 and 0, respectively, to maintain a normalized scale.

II-A1 Point

The most basic potential field unit is the point. It highlights a spot in a map to avoid and is described by,

σ_{p} (x | \hat{x}, A) = e^{- {(x - \hat{x})}^{T} A^{- 1} (x - \hat{x})}

(2)

where $x$ is an evaluated point, $\hat{x}$ is the unit location, and $A$ is a positive definite matrix that expresses the repulsive force.

As a point is impractical as a barrier, the potential field is intended to discourage travel through a given area without applying a strict restriction. The potential field can be view in Fig. 2(a).

II-A2 Line

The potential field unit for a line is defined by three parameters. Two points, ${\hat{x}}_{1}$ and ${\hat{x}}_{2}$ , indicate the start and end of a line, respectively. The positive definite matrix $A$ , as with a point, expresses the repulsive force. The process of determining the potential field unit begins by finding the point on the line that is closest to a given point x. This is achieved by,

\begin{matrix} P_{l} (x | {\hat{x}}_{1}, {\hat{x}}_{2}) & = \frac{({\hat{x}}_{2} - {\hat{x}}_{1}) \cdot (x - {\hat{x}}_{1})}{{‖ {\hat{x}}_{2} - {\hat{x}}_{1} ‖}^{2}} \\ g_{l} (x | {\hat{x}}_{1}, {\hat{x}}_{2}) & = {\hat{x}}_{1} + clamp (P_{l} (x | {\hat{x}}_{1}, {\hat{x}}_{2}), 0, 1) ({\hat{x}}_{2} - {\hat{x}}_{1}) \end{matrix}

(3)

where $clamp (α, a, b)$ is a function that limits a given value $α$ to the range $a$ to $b$ . Following this, the point $x$ is then evaluated with respect to new point $\hat{x} = g_{l} (x | {\hat{x}}_{1}, {\hat{x}}_{2})$ .

σ_{l} (x | {\hat{x}}_{1}, {\hat{x}}_{2}, A) = e^{- {(x - g_{l} (x | \cdot))}^{T} A^{- 1} (x - g_{l} (x | \cdot))}

(4)

The potential field for a line can be used to restrict flights along paths in a map. Paths can often be simplified into a set of points with segmented lines connected in-between. For instance, roads, rivers, and highways can be marked for avoidance by generating strings of segmented lines along their paths. An example of the potential field can be view in Fig. 2(b).

II-A3 Rectangle

The potential field unit for a rectangle is more restrictive than that of a point or line. It defines a rectangular sector by ${\hat{x}}_{1}$ and ${\hat{x}}_{2}$ where any point $x$ inside it is classified as a high energy state. To define the field, we must first describe a new vector that signals the repulsion from the restricted area by,

\begin{matrix} {\bar{x}}_{e} (x | {\hat{x}}_{1}, {\hat{x}}_{2}) & = \frac{1}{2} (| x - {\hat{x}}_{1} | + | x - {\hat{x}}_{2} | - | {\hat{x}}_{1} - {\hat{x}}_{2} |) \\ g_{r} (x | {\hat{x}}_{1}, {\hat{x}}_{2}) & = sign (x - {\hat{x}}_{1}) ⊙ {\bar{x}}_{e} (x | {\hat{x}}_{1}, {\hat{x}}_{2}) \end{matrix}

(5)

where $| x |$ and $sign (x)$ are the element-wise absolute value and sign operations, respectively, of the vector $x$ . This new vector is then used to describe the potential field unit for a rectangle.

σ_{r} (x | {\hat{x}}_{1}, {\hat{x}}_{2}, A) = e^{- g_{r} {(x | \cdot)}^{T} A^{- 1} g_{r} (x | \cdot)}

(6)

The rectangle potential field unit is designed to restrict entities that can be accurately represented by rectangular shapes. These entities can include structures such as buildings, tracts of land, and other physical entities. Fig. 2(c) showcases an example of the potential field.

II-A4 Ellipse

The ellipse serves as an alternative to a rectangle. Given the shape of an ellipse, we define a new vector that signals the repulsion from the restricted area by,

g_{e} (x | \hat{x}, B) = max (1 - \frac{1}{‖ B^{- 1} (x - \hat{x}) ‖}, 0) (x - \hat{x})

(7)

where $\hat{x}$ is the center of the ellipse, and $B$ is a positive definite matrix that describes its shape. As with a rectangle, this new vector is then used to describe the potential field unit.

σ_{e} (x | \hat{x}, A, B) = e^{- g_{e} {(x | \cdot)}^{T} A^{- 1} g_{e} (x | \cdot)}

(8)

The ellipse unit is designed for restricting entities that possess, or can be more accurately estimated by, ellipsoidal shapes. These entities can include structures such as mountains, domes, and alike. A potential field for an ellipsoidal restriction can be seen in Fig. 2(d).

II-B Virtual and Time-Dependent Potential Fields

Potential fields are not necessarily tied to physical entities or restrictions at or above the operating altitude. They can be used to fully restrict or discourage UAV flights across chosen sectors. For example, they can deter or prevent flights across residential areas, parks, airports, runways, venues, open fields, and/or forests.

Moreover, potential fields, while not necessarily linked to physical entities, do not need to be static either. They can impose temporary restrictions around agents in the airspace, such as cargo UAVs and other low-altitude aircraft. They can also vary over time in response to certain virtual entities, such as shifts in population density throughout the day, or to discourage the use of similar flights within a short time frame.

II-C Geographical Restriction Encoding

To encode and store the restrictions that form the basis of potential fields units, we propose a variant of the well-known GeoJSON format [24]. GeoJSON, based on the JSON file format, is an open standard designed for representing simple geographical features and storing their non-spatial attributes. These features include points (representing addresses and locations), line strings (describing streets and boundaries), polygons (defining tracts of land and counties), and multi-polygons. Hence, to maintain interoperability, we introduce Restriction GeoJSON (RGeoJSON).

RGeoJSON brings three significant changes to the standard. First, it amends geometry objects to include properties for the repulsion matrix $A$ (explored in Section II-A) and the matrix defining an ellipse shape $B$ (discussed in Section II-A4). Secondly, it removes support for polygon geometry objects. Lastly, it introduces two novel geometry objects: Rectangle and Ellipse. The addition of these objects compensates for the removal of GeoJSON polygons. Polygon shapes may be estimated by the use of multiple rectangles and ellipses as demonstrated in Fig. 4.

As a variation, standard No-SQL databases that support GeoJSON offer some functionalities for RGeoJSON, such as geospatial queries for shared geometry object types. In Appendix -C, a comprehensive list and examples of all RGeoJSON geometry objects are provided.

III Urban Air Mobility Infrastructure

In addition to the standard for defining UAM routing restrictions using potential fields, we propose an infrastructure to manage the airspace occupied by UAVs engaged in aerial cargo deliveries. The UTM infrastructure’s role is to facilitate the routing collaboration among independent third parties and to update the shared potential field as needed. This infrastructure consists of clients, a back-end server with distributed nodes, and databases for geographical restrictions. An overview of the infrastructure is presented in Fig. 5.

III-A Clients

Clients in the infrastructure represent software and/or hardware that are participants or stakeholders in the airspace. These can be cargo UAVs, low-altitude manned vehicles, supply chain applications, among other systems. Each client has the ability to observe the state of the shared potential field and request updates to it. However, the level of authority and the type of requests a client can make are determined by the clearance they are assigned. Any physical client participating in the airspace must periodically transmit its current state and expected near-future behavior. It is the responsibility of the back-end server’s governing body to define the interface through which clients can communicate.

III-B Server

The back-end server acts as the governing body of the infrastructure, managing the coordination of independent third parties seeking to influence the shared airspace. It has three primary functions: generating routes given an origin and destination, validating clients’ requested routes, and managing the shared potential field for collision avoidance and desired policies.

When generating optional routes, the server applies a path-finding algorithm that uses the potential field to determine a low-energy route while minimizing its distance. However, when clients provide their own routes, the server shifts to evaluating the route compliance instead. This is achieved by calculating, or approximating, the area under the route in the potential field. To capture violations of the restriction, the field may first be transformed in such a way that it scales towards infinity near an energy value of 1, ensuring that any restriction violation results in an infinite value by the area approximation. In terms of managing the shared potential field, the server may introduce temporary changes to ensure coordination. One such change, similar to [23], involves requesting the transmission of the current and near-future locations of clients participating in the airspace and developing temporary potential fields around them. This would ensure some level of collision avoidance for any participating UAV.

To accommodate the scale of the shared potential field, the server may operate as a distributed system in which different nodes to support distinct geographical regions.

III-C Geographical Restriction Databases

The geographical restriction databases stores infrastructure information of all locations of interest using the RGeoJSON format. These databases store the parameters needed to build the individual potential field unit while the back-end server decides how to serve them to the clients. As opposed to a client’s requested changes, restrictions stored in the databases server are not considered temporary. These restrictions may be static or time-dependent for local regions. They may also either attached to physical or virtual obstacles to ensure safe aerial routing. Additionally, the databases may contain non-spatial information of the system, such as the operating altitude of given regions.

III-D Deployment

The UTM infrastructure is designed to enable communication between any participant in the airspace and the server. The server holds the responsibility of assigning authority and/or clearance to clients for the types of queries they are allowed make. As the central governing unit, the back-end server’s administration and operations must be overseen by an agency with the authority to manage airspace (e.g., Federal Aviation Administration or FAA). We recommend a distributed deployment of geographical restriction databases. This approach allows the back-end server to request data selectively, focusing only on the sectors relevant to the third-party operations. For practicality, counties and local municipalities with capable information technology (IT) departments are encouraged to host and maintain these databases. Such close integration would facilitate some governance of low-altitude airspace and ensure up-to-date information on restrictions affecting cargo UAVs. When a client submits a potential field state request, the server gets to consider the restrictions before providing a response.

IV Implementation

As a proof of concept, a prototype of the proposed infrastructure was implemented. It showcases the aforementioned components: a client, a server, and a geographical database.

IV-A Potential Field State Client

The implemented client, serving as a front-end web server, projects the state of the potential field for any queried location within the United States. It is designed as a React application that dispatches HTTPS requests to the back-end server and utilizes the returned data to construct the potential field for the specified area. The potential field is then overlaid on the corresponding map region using a translucent filter. Fig. 6 showcases the user interface of the application.

IV-B Back-End Server

The implemented back-end server’s software was developed using the Python language and its Flask package. Its primary function is to listen for client queries, create a thread to serve them, and then return to standby mode awaiting for the next client. In this infrastructure, HTTPS requests serve as the main communication interface, influencing the state of the potential field. For demonstration purposes, we implemented three primary HTTPS REST API queries:

GET /test/:adds confirms the authority and clearance to communicate with the server for the provided address.
GET /adds/:adds/:dbs returns the parameters defining the potential field for the provided address and infrastructure database collections.
GET /locs/:lat,:lon,:radius/:dbs returns the parameters defining the potential field for the provided latitude, longitude, radius, and infrastructure database collections.

While not indicative of a fully deployed UTM at a large scale, for this prototype, clients are permitted to submit a list of infrastructures for consideration. Both the list of infrastructures and a geospatial bounding restriction are utilized to search the geographical restrictions databases for the RGeoJSON Objects within the specified region.

IV-C Database

The geographical restrictions are stored in a MongoDB No-SQL database using the aforementioned RGeoJSON format. Among other features, MongoDB supports geospatial queries to filter results by their geographical location. If the server software used for this demonstration is connected to a MongoDB database, it will automatically download the presented dataset and upload it the database if it does not already exist. The dataset is an augmented version of multiple infrastructure datasets collected by the Homeland Infrastructure Foundation-Level Data (HIFLD) repository¹¹1HIFLD homepage: https://hifld-geoplatform.opendata.arcgis.com/. The datasets for US-based aviation facilities, fire stations, hospitals, law enforcement, and public schools were used. Geospatial search queries for any location within the United States is supported, but not all locations may have appropriate restriction parameters due to lack of data.

V Conclusion

In this paper, we proposed a standard for defining routing restrictions in UAM, coupled with a UTM infrastructure that leverages it for the operation of collaborative and scalable aerial cargo deliveries. The applicability of the infrastructure is demonstrated by a functional prototype that coordinates a shared potential field and operates at a national scale.

The proposed infrastructure addresses regulatory concerns by: (1) operating in a manner that allows for governance of low-altitude airspace, and (2) offering functionalities to validate the compliance of independent third-party routes through a quantifiable approach. This work also seeks to mitigate some of the shortcomings of other UTM approaches by considering the scalability of the infrastructure and striving to avoid restrictions to predefined paths.

V-A Limitations

While our research provides valuable insights, it is not without its limitations. One such limitation is the assumption of a near-constant operating altitude. Under this assumption, the search space of feasible routes outside of the operating altitude is unaccounted for, leading to sub-optimal routes. The assumption is a trade-off made to facilitate an adaptable solution to a wide range of urban environments and simplify the complexity of the problem. The limitation may be mitigated by the introduction of multiple potential fields at different altitudes and allowing UAVs to change layers depending on their departure and destination points. However, the implications of having multiple potential field layers in the proposed infrastructure falls outside the scope of this paper.

V-B Future works

The research opens up several avenues for further exploration. One potential direction involves the development of optimized routing strategies that take full advantage of the newly introduced standard. For example, the repulsive gradient of the fundamental potential field units could be utilized to enhance the efficiency of route searches. Another promising avenue is the execution of complex, large-scale routing simulations for major cities. Such simulations could provide deeper insights into the practicality of implementing the proposed infrastructure within an urban environment. In a similar vein, investigating the impact of implementing multiple potential field layers at various altitudes is warranted. Lastly, with respect to the infrastructure and shared potential field, the real-time adaptation to changing conditions presents a compelling opportunity for future research.

Acknowledgment

We extend our gratitude to Pruthvi S. Patel²²2Email: pate1533@purdue.edu for his valuable contributions to this research. Patel assisted in various technical aspects of the project and supported its development.

References

[1] Nils Boysen, Stefan Fedtke, and Stefan Schwerdfeger. Last-mile delivery concepts: a survey from an operational research perspective. Or Spectrum, 43:1–58, 2021.
[2] Eleonora Morganti, Saskia Seidel, Corinne Blanquart, Laetitia Dablanc, and Barbara Lenz. The impact of e-commerce on final deliveries: alternative parcel delivery services in france and germany. Transportation Research Procedia, 4:178–190, 2014.
[3] Judy Scott and Carlton Scott. Drone delivery models for healthcare. In Proceedings of the 50th Hawaii International Conference on System Sciences, pages 3297–3304, 2017.
[4] Boualem Rabta, Christian Wankmüller, and Gerald Reiner. A drone fleet model for last-mile distribution in disaster relief operations. International Journal of Disaster Risk Reduction, 28:107–112, 2018.
[5] Bhawesh Sah, Rohit Gupta, and Dana Bani-Hani. Analysis of barriers to implement drone logistics. International Journal of Logistics Research and Applications, 24(6):531–550, 2021.
[6] Khaled Telli, Okba Kraa, Yassine Himeur, Abdelmalik Ouamane, Mohamed Boumehraz, Shadi Atalla, and Wathiq Mansoor. A comprehensive review of recent research trends on unmanned aerial vehicles (uavs). Systems, 11(8):400, 2023.
[7] Rakesh Shrestha, Inseon Oh, and Shiho Kim. A survey on operation concept, advancements, and challenging issues of urban air traffic management. Frontiers in Future Transportation, 2:1, 2021.
[8] Batool Madani and Malick Ndiaye. Hybrid truck-drone delivery systems: A systematic literature review. IEEE Access, 2022.
[9] Kangzhou Wang, Biao Yuan, Mengting Zhao, and Yuwei Lu. Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach. Journal of the Operational Research Society, 71(10):1657–1674, 2020.
[10] Shan-Huen Huang, Ying-Hua Huang, Carola A Blazquez, and Chia-Yi Chen. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm. Advanced Engineering Informatics, 51:101536, 2022.
[11] Desheng Wang, Peng Hu, Jingxuan Du, Pan Zhou, Tianping Deng, and Menglan Hu. Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones. IEEE Internet of Things Journal, 6(6):10483–10495, 2019.
[12] Niels Agatz, Paul Bouman, and Marie Schmidt. Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4):965–981, 2018.
[13] Zhengyi Wang, Daniel Delahaye, Jean-Loup Farges, and Sameer Alam. Route network design in low-altitude airspace for future urban air mobility operations a case study of urban airspace of singapore. In International Conference on Research in Air Transportation (ICRAT 2020), 2022.
[14] David Sacharny, Thomas C Henderson, and Michael Cline. Large-scale uas traffic management (utm) structure. In 2020 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), pages 7–12. IEEE, 2020.
[15] Hossein Rastgoftar, Hamid Emadi, and Ella M Atkins. A finite-state fixed-corridor model for uas traffic management. IEEE Transactions on Intelligent Transportation Systems, 2023.
[16] Samiksha R Nagrare, Ashwini Ratnoo, and Debasish Ghose. Multi-intersection planning with durational speed scheduling for drone corridors. In AIAA SCITECH 2023 Forum, page 1053, 2023.
[17] Yong K Hwang and Narendra Ahuja. A potential field approach to path planning. IEEE transactions on robotics and automation, 8(1):23–32, 1992.
[18] Varsha Dubey, Brijesh Patel, and Snehlata Barde. Path optimization and obstacle avoidance using gradient method with potential fields for mobile robot. In 2023 International Conference on Sustainable Computing and Smart Systems (ICSCSS), pages 1358–1364. IEEE, 2023.
[19] Shubhani Aggarwal and Neeraj Kumar. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges. Computer Communications, 149:270–299, 2020.
[20] Sen Han, Lei Wang, and Yiting Wang. A potential field-based trajectory planning and tracking approach for automatic berthing and colregs-compliant collision avoidance. Ocean Engineering, 266:112877, 2022.
[21] Chenxi Hu, Yongzhao Hua, Qing Wang, Xiwang Dong, Jianglong Yu, and Zhang Ren. Potential field-based formation tracking control for multi-ugv system with detection behavior and collision avoidance. Journal of the Franklin Institute, 360(17):13284–13317, 2023.
[22] Sajid Ahamed M A, Satya Prakash K, Shuvrangshu Jana, and Debasish Ghose. Numerical potential fields based multi-stage path planning for utm in dense non-segregated airspace. Journal of Intelligent & Robotic Systems, 109(1), August 2023.
[23] Jun Tang, Jiayi Sun, Cong Lu, and Songyang Lao. Optimized artificial potential field algorithm to multi-unmanned aerial vehicle coordinated trajectory planning and collision avoidance in three-dimensional environment. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 233(16):6032–6043, 2019.
[24] H. Butler, M. Daly, A. Doyle, Sean Gillies, T. Schaub, and Stefan Hagen. The GeoJSON Format. RFC 7946, August 2016.

-C RGeoJSON Geometry Object Examples

Following a conversion akin to GeoJSON, we present examples of UAM routing restrictions encoded using the RGeoJSON format [24]. These examples illustrate the schema of the geometry objects used in the routing restrictions data storage.

-C1 Point

{
    "type": "Point",
    "coordinates": [100.0, 0.0],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ]
}

-C2 LineString

{
    "type": "LineString",
    "coordinates": [
        [100.0, 0.0],
        [101.0, 1.0]
    ],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ]
}

-C3 Rectangle

{
    "type": "Rectangle",
    "coordinates": [
        [100.0, 0.0],
        [101.0, 1.0]
    ],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ]
}

-C4 Ellipse

{
    "type": "Ellipse",
    "coordinates": [100.0, 0.0],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ],
    "shape": [
        [50.0, 0.0],
        [0.0, 50.0]
    ]
}

-C5 MultiPoint

{
    "type": "MultiPoint",
    "coordinates": [
       [100.0, 0.0],
       [101.0, 1.0]
    ],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ]
}

-C6 MultiLineString

{
   "type": "MultiLineString",
   "coordinates": [
        [
           [100.0, 0.0],
           [101.0, 1.0]
        ],
        [
           [102.0, 2.0],
           [103.0, 3.0]
        ]
    ],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ]
}

-C7 MultiRectangle

{
    "type": "MultiRectangle",
    "coordinates": [
        [
           [100.0, 0.0],
           [101.0, 1.0]
        ],
        [
           [102.0, 2.0],
           [103.0, 3.0]
        ]
    ],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ]
}

-C8 MultiEllipse

{
    "type": "MultiEllipse",
    "coordinates": [
        [100.0, 0.0],
        [101.0, 1.0]
    ],
    "repulsion": [
        [25.0, 0.0],
        [0.0, 25.0]
    ],
    "shape": [
       [
            [50.0, 0.0],
            [0.0, 50.0]
       ],
       [
            [50.0, 50.0],
            [ 0.0, 50.0]
       ]
   ]
}

-C9 GeometryCollection

{
   "type": "GeometryCollection",
   "geometries": [{
        "type": "Point",
        "coordinates": [100.0, 0.0],
        "repulsion": [
            [25.0, 0.0],
            [0.0, 25.0]
        ]
   }, {
        "type": "LineString",
        "coordinates": [
           [101.0, 0.0],
           [102.0, 1.0]
        ],
        "repulsion": [
            [10.0, 0.0],
            [0.0, 10.0]
        ]
   }]
}

Tuesday, March 19, 2024