Decentralised Traffic Management for Constrained Urban Airspace: Dynamically Generating and Acting Upon Aggregate Flow Data
Abstract
There are several efforts to explore employing drones to replace ground transportation in cities. However, this would mean that the expected traffic densities would be significantly higher than existing air traffic management. A decentralised system for traffic management may be necessary in this future because (1) not all airspace actors will want to freely share data, (2) the uncertainty of missions due to wind or other factors could make a previous plan inoperable, and (3) the ad hoc nature of urban missions makes them difficult to plan in advance. This work focuses on the challenges of drone operations within constrained urban airspace. We define constrained airspace as a virtual network overlaid on the physical environment, where tall buildings and urban infrastructure dictate the allowed routes. Drones are restricted to flying within this virtual network, either above the existing street network or along other predetermined segments. A dynamic and decentralised traffic management method is presented. The method uses current aggregate flow data to identify and alter the cost of travelling through high-density clusters. The goal is to reduce local traffic density and complexity by encouraging alternate routes. Three different clustering strategies are presented that look at the current position of aircraft and recent safety events. The dynamic traffic management method is first illustrated with two simple example scenarios. Then an experiment is conducted with different traffic demand levels within the city of Rotterdam. It was observed that when using traffic complexity indicators, the method is able to reduce safety events by 30 percent while only increasing the distance travelled by 6 percent.
Introduction
Ground transportation within urban areas creates congestion, which worsens air quality due to the increased number of vehicles on the road and results in economic losses [Creutzig et al. 2020]. A solution may be to transfer a portion of ground transportation to the air, as it has the potential to be more beneficial for the environment [Stolaroff et al. 2018; Raghunatha et al. 2023]. Several government-led research initiatives focusing on drone operations [DLR 2017; Undertaking 2017a; Kopardekar et al. 2016; FAA 2023] illustrate that there is significant interest in exploring urban drone operations to mitigate issues arising from ground transportation.
An estimate by the European Union predicts 400,000 drones in operation by 2040 [Undertaking 2017b]. This would result in urban air traffic densities that are significantly higher than traditional air traffic management [Doole et al. 2020]. Moreover, a significant difference with conventional aviation is that air traffic in cities will need to regularly avoid both dynamic (other aircraft) and static (buildings and geofences) obstacles
In major urban areas, aircraft may need to operate within a constrained airspace, defined here as a virtual network overlaid on the physical environment. This virtual network primarily aligns with and exists above the existing road network, but may also include other predetermined segments. In cities with tall buildings (e.g., New York), flying above the tallest structures could be inefficient. Also, even in areas with shorter buildings, it may still be necessary to fly above the road network, as these paths are typically on public property and may be required by urban regulators. Furthermore, in areas where there are no roads, such as over busy waterways, aircraft may also need to follow the virtual network to ensure predictability. This may help the adoption of drones in cities that do not currently allow flights over busy waterways, such as the Nieuwe Mass River in Rotterdam[Government of the Netherlands].
A virtual network creates a constrained airspace that can be described as a graph with nodes and edges. The edges are generally aligned with the streets and the intersections of the edges are nodes (Fig. 1). In this constrained airspace, the manoeuvrability of aircraft is greatly limited. Aircraft are not able to perform heading changes to solve any potential conflicts with other aircraft. Therefore, it is important to have an even spread of traffic over the available airspace to minimize the local traffic complexity and density, as this will lead to a lower conflict probability[Sunil et al. 2018].
The Metropolis II project [Morfin Veytia et al. 2022] studied how separation management, flight planning, and airspace structure can be managed in a constrained urban airspace. The project concluded that a hybrid system that combines a central entity, which deconflicts aircraft prior to take-off, and allowing aircraft to perform decentralised conflict resolution was able to combine the benefits of both a centralised and decentralised system.
A question that remains, however, is to what extent central strategic planning is (economically and practically) feasible. It is for instance likely that not all airspace actors will want to freely share operational data, which would be required for central planning. Also, uncertainty of missions due to wind or other factors can make the current plan inoperable. Finally, the ad hoc nature of urban missions makes them difficult to plan in advance in a centralised manner [Bharadwaj et al. 2021]. As such, the current work focuses on a decentralised system in which a set of dynamic rules are incorporated into the current traffic situation.
It has been observed that when following a virtual network [Badea et al. 2021; Doole et al. 2022], drones typically share similar travel legs towards their destination, which creates hot-spots in the airspace and increases the local traffic density and complexity. Traffic complexity attempts to describe the disorder in the airspace based on aircraft interactions [Delahaye and Puechmorel 2000; Wang et al. 2022]. Some measures of traffic complexity try to capture the disorder by observing the proximity and convergence of aircraft [Vidosavljevic et al. 2015]. The more convergence present in the airspace, the more unsafe it can become. Additionally, following a virtual network may force aircraft trajectories to converge at the intersections. This makes it a difficult problem to mitigate, especially in a decentralised system.
Previous work in traditional air traffic management [Bilimoria and Lee 2005] created a method for defining dynamic sectors based on the local density. Other works, in urban airspace, used static and historical data to identify zones of high-density traffic [Patrinopoulou et al. 2023] and perform capacity management in those zones to reduce local traffic density and complexity. The current work will present a novel dynamic traffic management method that attempts to decentrally reduce local density and complexity by dynamically identifying high-density zones. The method uses real-time aggregate flow information to subdivide the airspace into low and high density zones and applies an additional cost of travel on high density areas.
The dynamic traffic management method can be summarized as follows. (1) Observations of current positions or safety incidents are gathered. The safety incidents are indicators of traffic complexity, and position is an indicator of traffic density. (2) The observations are clustered to create dynamic zones that can receive an additional cost of travel depending on the relative density. (3) Aircraft can then check (decentrally / autonomously) whether their future route intersects these dynamic clusters and update their route taking into account the updated costs. Note that this process happens continuously, the clusters always reflect a recent snapshot of the airspace. This is similar to how highway operators apply speed limits or metering of lanes during rush hour.
The individual agents or drones are responsible for adjusting their own routes that account for the additional cost of travel and find a new optimal path. This will increase the flight distance as aircraft are incentivized to avoid the clustered areas. This creates a trade-off between safety and efficiency when a longer route is chosen.
The dynamic traffic management method will be tested in a simulated urban environment. First, the overall method will be presented along with two example scenarios. The example scenarios are meant to illustrate how the dynamic traffic management method behaves under simplified traffic patterns. Then, the method will be tested in an experiment using a city-wide demand estimation of the city of Rotterdam [de Bok and Tavasszy 2018].
Method: Using aggregate flow data for dynamic traffic management
This section will outline the method used for performing dynamic traffic management in a constrained urban environment. The method uses aggregate flow statistics to identify and apply additional cost of travel to high-density zones in the airspace. The aggregate flow statistics can be the current position of aircraft or safety events.
Two different but related safety events (conflicts and intrusions) are considered. State-based conflict detection linearly extends the position of aircraft using their current state to check if an intrusion will occur in the near future. A conflict is detected when it is predicted that an aircraft will enter the protected zone of another within a certain look-ahead time. An intrusion occurs when an aircraft actually enters the protected zone of another aircraft.
The difference is illustrated in Figure 2. The protected zone is the dashed circle, in which the radius is the horizontal safe separation distance between aircraft (32 metres, refer to Section 3.2.4 for more information). It is up to the conflict resolution algorithm to ensure that conflicts are solved before they become intrusions. This can be done tactically by performing speed, heading, or altitude changes. In constrained airspace, this is limited to only speed or altitude changes.
The overall goal of this method is to incentivise aircraft to fly around areas with a high likelihood for conflicts, as this will lead to fewer intrusions and create additional space to tactically solve conflicts. The overall steps of this method are illustrated in Figure 7 and are as follows:
Aggregate flow data from urban airspace is gathered into clusters. Figure 3.
The airspace is categorised into a high or low category based on the relative density observed in the clusters. An additional cost of travel is applied to high density zones, Figure 4.
Individual aircraft check if their path will go through areas categorised as high density, Figure 5.
Aircraft find a new optimal plan considering the additional cost of travel of the clusters, Figure 6.
These steps are continuously repeated over time to provide an updated view of the airspace, occurring every 10 seconds. As a result, different clusters with varying categories are generated every 10 seconds. This 10-second interval comes from the methodology used in [Morfin Veytia et al. 2022; Patrinopoulou et al. 2023] to update the densities of high-density zones.
Gathering aggregate flow data
The first step in the method is to make the observation of the aggregate flow data. This work considers three different types of observation strategies to create clusters:
Position-based observations: This strategy gathers the current position of all aircraft.
Conflict-based observations: This strategy gathers the positions of all conflict events that have occurred in the past ten minutes.
Intrusion-based observations: This strategy gathers the position of all intrusion events that have occurred in the past ten minutes.
The observations are gathered into an observation vector, :
Each row contains the Cartesian coordinates of each observation and is the total number of observations. For the position-based strategy is the number of aircraft in the air. Alternatively, for the conflict-based and intrusion-based strategies, the observation vector containts the Cartesian coordinates of aircraft when they entered into a conflict or intrusion, respectively, within the past ten minutes.
The conflict-based and intrusion-based based observations are indicators of traffic complexity. They indicate locations where aircraft may converge (conflicts) or have converged (intrusions). On the other hand, the position-based observations are an indicator of the traffic density and does not include any past information.
Clustering the observations
In this study, hierarchical clustering, specifically Ward clustering [Ward 1963], is employed for its distinct advantage over other methods like K-means, which require a predetermined cluster count. Ward clustering involves iteratively merging clusters to minimize the with-in cluster variance during merging. The Ward cluster distance is defined as the Euclidean distance variance when clusters are merged. A Ward distance threshold can be applied to prevent merging of clusters if the variance exceeds this threshold. This approach is similar to the variance-minimizing principle in K-means clustering. Specifically, the Ward cluster distance corresponds to half the squared Euclidean distance between the clusters [Mirkin 2011].
This work sets a Ward cluster distance threshold of 4000 , which is about 90 metres, for all three strategies. Note that a sensitivity analysis can be found in the supporting data set [Morfin Veytia 2024]. The sensitivity analysis shows how other cluster distances affect the effectiveness of the method. In general, a larger cluster distance corresponds to larger clusters. It was seen in [Patrinopoulou et al. 2023] that relatively smaller clusters are preferred in dynamic traffic flow management because it allows for more flexibility to plan around them.
Applying this clustering algorithm to the 2D observation vector will return an array that contains a cluster label for each observation. These clusters are called position-based, conflict-based or intrusion-based clusters depending on the observation vector information.
Categorising the airspace
After each entry of the observation vector has been placed into a cluster, the airspace can be categorised into areas of relatively lower and higher density airspace. This is illustrated in Figure 4. Each cluster is represented by a convex hull polygon that contains all observations inside it [Lay 1982].
Density calculation
The aircraft are operating in a constrained environment in which a virtual network is followed (Fig. 1). Therefore, the density of a cluster is calculated by considering the summed length of the edges that intersect the cluster convex polygon as shown in Equation [eq:density]:
Note that it is possible for clusters to intersect with the same edge or with each other. When this happens, the edge is given the categorisation of the cluster where the edge has its longest segment. Figure 4 illustrates how edges are linked to a convex polygon. The advantage of using 2D space for clustering and 1D space for the density calculation is that the 2D distance matrix is symmetric. This gives a clear indication of the distance between two nodes in the graph. A distance matrix in a one-way fully-connected graph may not be symmetric [Reinhart 2021]. For example, the distance from a given node A to node B may not the same as from node B to node A. This makes the graph distance matrix non-trivial for clustering. The reason for choosing a one-way virtual network is that it has been shown to be safer than a two-way virtual network [Doole et al. 2021].
Apply an additional cost of travel
After the density of each cluster has been calculated, they can be categorised as low- or high-density based on their relative density calculated from Equation [eq:density]. For this work, the densities are categorised based on percentiles. The clusters in the lower 25th percentile are labelled as low-density and no cost multiplier is applied. Clusters that are above the 25th percentile are labelled as high-density (refer to the sensitivity analysis for other percentiles).
The unaltered cost of travel is simply equal to the length of the path. At the start of the mission, all aircraft plan their route with the Dijkstra algorithm [Dijkstra 1959]. The additional cost of travel applies a cost multiplier to the edges that are part of a high-density cluster. The cost multiplier used in the city-wide scenarios is 2 (refer to the sensitivity analysis for effects of the other cost multipliers).
This method ensures that only a current view of the airspace affects the additional cost multipliers, and this is only related to the observation method. An ideal cost multiplier would increase the safety of the airspace while not forcing aircraft to fly needlessly long routes.
Checking and modifying the original plan
After the airspace has been categorised, each individual aircraft performs a check to see if their path goes through any high density edges. If the new plan intersects any of the high-density clusters, then a new plan is calculated. The new plan uses the Dijkstra algorithm to calculate an updated path, considering the length and additional cost multipliers.
Note that the method acts every ten seconds, therefore, there is a possibility that all aircraft replan at the same time and get into a formation where they all move to the same areas. This oscillation has been observed to happen in road traffic when people use route planning mobile apps like Google Maps [Bianchin and Pasqualetti 2020].
Example scenarios
This section will illustrate two example scenarios that showcase how the concept behaves in two simple cases. The example scenarios are illustrated in Figure 10. They are simulated in a small section of the Rotterdam virtual network using the BlueSky software (refer to Section 3 for more information about the airspace and software). For a more detailed analysis of the example scenarios, refer to the supporting dataset [Morfin Veytia 2024].
