Abstract

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:

1. Aggregate flow data from urban airspace is gathered into clusters. Figure 3.

2. 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.

3. Individual aircraft check if their path will go through areas categorised as high density, Figure 5.

4. 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:

1. Position-based observations: This strategy gathers the current position of all aircraft.

2. Conflict-based observations: This strategy gathers the positions of all conflict events that have occurred in the past ten minutes.

3. 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, $v_{observation}$:

$$\label{eq:2dvector} v_{observation} = \begin{bmatrix} (x_{1},y_{1}) \\ (x_{2}, y_{2}) \\ .. \\ (x_{N} , y_{N}) \end{bmatrix}$$

Each row contains the Cartesian coordinates $(x_{j},y_{j})$ of each observation and $N$ is the total number of observations. For the position-based strategy $N$ 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].

$$\label{eq:clustdist} d_{ward} = \frac{d_{euclidean}^{2}}{2}$$

This work sets a Ward cluster distance threshold of 4000 $m^2$, 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]:

$$\label{eq:density} \text{Linear cluster density} = \frac{\text{Number of observations in cluster}}{\text{Summed length of {edges} intersecting polygon}}$$

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].

Example scenario 1

Figure 8 shows the first example scenario. This scenario illustrates how the dynamic traffic management method behaves under the three different clustering strategies. The aircraft following the blue route originally pass through a conflict generation area (red polygon). In the conflict generation area, aircraft spawn and randomly choose a destination within the area. This will create complex traffic in the conflict generation areas as aircraft are converging. The dynamic traffic management method will act and apply an additional cost of travel to observed clusters. The next shortest route that does not pass through the conflict generation area is shown in the blue dashed line.

Figure 15 shows a snapshot of a simulation for the three clustering strategies and a baseline case that does not use the dynamic traffic management method. The red arrows represent individual aircraft flying in the conflict generation area. The blue arrows represent individual aircraft that were initially given the shortest route through the conflict generation area. Figure 11 shows the baseline case. Since the dynamic traffic management method is disabled, the blue aircraft pass through the conflict generation area. Figure 12 shows the conflict-based clustering strategy. Here it is clear that the aircraft in blue are avoiding the high complexity traffic in the conflict generation area. Figure 13 shows the intrusion-based strategy. There are usually fewer intrusions than conflicts, and conflicts between aircraft occur before an intrusion. This is why the blue aircraft in the intrusion-based strategy take both paths to their destination (the shortest route and the adjusted segment). Finally, Figure 14 shows the position-based strategy. The clusters are created using the positions of the aircraft. Therefore, the aircraft in blue are also part of a cluster. This is why some blue aircraft take a parallel route compared to the adjusted segment. These blue aircraft are also avoiding the high complexity area. However, by taking a parallel route, the method is also making the traffic more complex for the blue aircraft.

Example scenario 2

Figure 9 shows the set-up for Example scenario 2. This scenario illustrates how the dynamic traffic management method may not always be able to avoid clusters without taking an excessively long route. In this case, the blue aircraft cross a stream of red aircraft. The scenario is designed so that even with an additional cost multiplier, the blue aircraft cannot avoid the red aircraft. The aim of this example scenario is to only focus on benefits provided to the blue aircraft. The red aircraft in this scenario are not allowed to replan.

Figure 18 shows a snapshot of a simulation for the baseline case and the conflict-based strategy. The red arrows represent individual aircraft flying the conflict generation route. The blue arrows represent individual aircraft that were initially given the shortest route through the conflict generation route. Figure 16 shows that the blue aircraft in the baseline case do not change their route in response to the red aircraft. Figure 17 shows the conflict-based clustering strategy. It is clear that some aircraft in blue are taking a different route compared to the shortest routes. These new routes are in response to the clusters created by the observed conflicts. However, this route does not avoid crossing the red aircraft. The traffic complexity of the scenario is not simplified by the dynamic management method. Nevertheless, the dynamic traffic management method is spreading out the blue traffic to parallel edges, thereby reducing the local density at the intersections. If there is a robust conflict resolution strategy, the additional space created by the dynamic traffic management method may improve the effect of the conflict resolution algorithm.

Experimental design

The previously presented method aimed to identify and mitigate traffic hotspots to reduce the number of safety incidents (conflicts and intrusions). By dynamically redistributing aircraft, the local traffic density and complexity may be reduced, and more space can be provided for conflict resolution.

An experiment was designed to test the dynamic traffic management method under several city-wide scenarios with varying traffic demand level. The three clustering strategies will be compared against each other and to the baseline case that does not use the method.

Hypotheses

H1: It is hypothesized that all three clustering strategies will have higher safety levels than the baseline (no clustering). The method is expected to be able to identify locations with conflict, intrusion, and positional hot-spots.

H2: It is hypothesized that traffic complexity clusters (conflicts and intrusions) will have higher safety levels than density clusters (position). This is because complexity clusters will identify sectors where aircraft are converging. On the other hand, density clusters may increase the cost of travel to areas with a relative high traffic density but low complexity.

H3: It is hypothesized that the intrusion-based clustering will have higher safety levels than the conflict-based clustering strategy. The usage of state-based conflict detection in constrained airspace has been known to create false conflicts. Therefore, using conflicts may increase the cost of travel in more low traffic complexity areas as compared to clustering with intrusions.

These three hypotheses will be evaluated with a Wilcoxon signed-rank test [Wilcoxon 1945]. The null hypothesis is that the differences between strategies is not statistically significant, therefore the listed hypotheses will be accepted when $p_{value} < 0.01$. Refer to 7 for the detailed results of the hypothesis testing.

Common Elements

The common elements of the experiment will be shown in the following section. They include the urban airspace, the traffic demand patterns, origins and destinations, the conflict resolution algorithm, aircraft models, and the simulation software.

Rotterdam Airspace

This work simulates air traffic in the centre of Rotterdam. The Rotterdam airspace is particularly interesting because the city is traversed by the Nieuwe Maas river, see Fig. 19. The airspace illustrates that when the virtual network is over land, it is aligned with the street network. Additionally, in Rotterdam there are a limited number of land bridges connecting north and south. Therefore, several new drone "bridges" have been proposed to ease congestion and ensure that the graph is well-connected (all nodes can reach all other nodes). Currently, the government of the Netherlands does not allow any drone flights over the river due to maritime operations [Government of the Netherlands]. Therefore, enhancing the predictability of drones over waterways could lead to increased acceptance over these areas.

The process of adapting a street network to a virtual network is derived from [Badea et al. 2021]. The street network is download from OpenStreetMap [OpenStreetMap contributors 2017] with osmnx [Boeing 2017]. After downloading, the street network is simplified by removing parallel streets, roundabouts, and dead-ends. Following the simplification, several edges are added to the virtual network that are in parallel to waterways. The distance between these parallel edges is three times the safe separation distance of aircraft. This is about the distance that an aircraft would travel with their average speed for the conflict look-ahead time of 10 seconds. Finally, the edges above land that are dead-ends are extended to the ones parallel to the waterways.

This work assumes that all edges are one-way, since it is generally safer than two-way edges [Doole et al. 2021]. However, in a one-way non-orthogonal network, it is not apparent what the direction of each edge should be to ensure that all intersections are reachable from each other. The process of choosing the direction of the edges is described in detail in [Badea et al. 2021] and [Morfin Veytia et al. 2022] and involves two important steps.

The first step is to group the edges so that edges in the same group are continuous at intersections. This is done with the Continuity in Street Networks algorithm [Tripathy et al. 2020] which uses the edge geometry to assign the groups based on continuity. The second step is to use a genetic algorithm to decide the direction of each group. The goal of the genetic algorithm is to (1) create a network that is strongly connected, and (2) find a suboptimal solution where the overall cost of travel between all intersections is minimized, and (3) ensure that head on situations are not created as those create high relative velocities which lead to decreased safety [Hoekstra et al. 2018]. The result is a one-way and fully-connected virtual network with intersections that do not create head-on collisions. The final network used in this work is seen in Fig. 19.

Note that, the traffic management system proposed in Sec. 2 should be independent of the virtual network that it operates in. Therefore, the sensitivity analysis [Morfin Veytia 2024] shows how the method performs in the virtual network of Vienna, from [Morfin Veytia et al. 2022], in which the virtual network is always above the existing street network.

Traffic demand pattern

This section will present the results of testing the method on city-wide traffic scenarios. The MASS-GT [de Bok and Tavasszy 2018; Bok et al. 2021] project made an estimate of the daily parcel demand for South Holland. With this data, each neighbourhood of Rotterdam can be given a demand percentage relative to other neighbourhoods. The relative demand of each neighbourhood can be seen in Fig. 20.

Origins and destinations

About two-hundred random intersections are selected as possible take-off locations (Fig. 20), they are at least 300 metres away from each other. Then for each possible origin, a path is created to all other intersections in the network with the following constraints. For each mission, the origin and destination are at least 1000 metres apart, and it cannot start or end in a node that is inside water. This creates around 500.000 possible routes. Each route is created with the Dijkstra algorithm [Dijkstra 1959] using the length as a cost to select the shortest route.

To create the scenarios, random origins are selected from the possible take-off locations, then a destination is selected considering the weighted probabilities of the destination nodes based on the parcel demand. All missions take place at 30 feet above the ground.

Conflict detection and resolution

This work uses state-based conflict detection. This method linearly extrapolates the current position of all aircraft with a given look-ahead time and checks if they will violate the protected zone (Fig. 2). A known effect of using state-based conflict detection in non-orthogonal constrained airspace is that it may detect false conflicts [Badea et al. 2021]. These are detected conflicts that do not actually become intrusions.

The drones in this work use a tactical speed-based conflict resolution algorithm from [Badea et al. 2023] to solve conflicts in constrained airspace. This method has a horizontal protected radius of 32 metres based on the horizontal accuracy signal-in-space requirements (Table 3.7.2.4-1) [International Civil Aviation Organisation 2018]. The work uses a 10 second lookahead time that was used in previous urban airspace research works [Badea et al. 2021; Morfin Veytia et al. 2022; Patrinopoulou et al. 2023; Badea et al. 2023]. Note that the tactical conflict resolution is independent of the dynamic traffic management method, as it only forces aircraft to slow down or speed up.

Aircraft models

This work used a performance model based on the DJI Matrice 600 Pro hexacopter [DJI Accessed 2024]. The model parameters are shown in Table 1.

Simulation software

This work used the BlueSky air traffic simulator for the experiments [Hoekstra and Ellerbroek 2016]. BlueSky is a fast-time simulator that can be extended via plugins so that a cluster observation strategy and flight planning module can be added. This work also made use of the Metropolis II developments for BlueSky to improve the capabilities of simulating traffic in urban environments [Morfin Veytia et al. 2022].

Independent variables

• Dynamic traffic management method clustering strategy: baseline (no clustering), position-based, conflict-based, intrusion-based.

• Imposed traffic demand level: 100, 200, 300, 400, 500 instantaneous aircraft.

Moreover, each case is repeated 20 times with a different random seed that generate different origin-destination pairs. This creates 4 (clustering strategies + baseline) x 5 (traffic demand levels) x 20 (randomly selected random seeds) = 400 different scenarios. Each scenario has a simulation time of 2 hours. The work was simulated on an AMD Ryzen 9 5950X 16-Core Processor with 96 GB of RAM. It took about 25 hours of real time to simulate 800 hours (400 scenarios * 2 hours).

Dependent variables

This section will present the dependent variables used in the city-wide scenario experiment. There are three different overall categories of dependent variables (safety, efficiency and clustering). Note that the results of the first 10 minutes are ignored because that is the observation time required for the conflict-based and intrusion-based clustering strategies.

Safety: conflicts and intrusions

The safety metrics used to evaluate the results are conflicts and intrusions. However, these are not presented as absolute values. Note that because the number of intrusions and conflicts scales with the separation distance and look-ahead time, it is more useful to consider the relative difference between concepts when comparing them.

The metrics are presented in terms of conflicts and intrusions per flight. These are calculated by dividing the total amount of conflicts and intrusions by the amount of flights. Additionally, the safety metrics are also presented per distance travelled as a percentage of the baseline (no clustering). For example, assume that the conflict-based strategy shows 105 conflicts per distance percentage. This indicates that aircraft in this clustering strategy have 5 percent more conflicts per distance travelled than aircraft travelling in the baseline.

Finally, a heat-map of the intrusions is also presented to show how the clustering strategy visually change the traffic patterns. It uses the kernel density estimation [Gramacki 2018] with a radius of 300 metres.

Efficiency: distance travelled and number of replans

The distance travelled percentage is presented as a percentage of the total distance travelled by aircraft in the baseline.

The number of replans per flight is also presented. A replan generally indicates that the aircraft took a longer route. Note that by definition, aircraft in the baseline case do not make any replans. Note that an aircraft may receive a flight plan that it does not execute because a newer plan is issued before the previous update is implemented. Consequently, the number of replans per flight reflects only the executed updates, not the attempts.

Clustering: cluster percentage and stability

Since there is a new observation vector made every 10 seconds (Section 2), the clusters at one time may differ from the clusters at the next time step. If the clusters change significantly, this may affect the stability of the airspace, because there will be less coherence in replanning.

Therefore, two metrics are presented. The first is the percent of clustered airspace. This shows on average how much of the airspace is part of a cluster during each observation. The second is the cluster temporal stability. This represents the average percentage overlap of the clusters from one observation to the next. A value of 100 percent would indicate that the cluster polygons are completely identical from one observation time step to the other.

Finally, an example map of the clusters with a high density categorisation at 400 aircraft for each of the three strategies is presented to help visualise the method.

Results

This section presents the results of the city-wide scenarios. Unless noted otherwise, the box plots show the metric on the vertical axis and the imposed traffic demand level on the horizontal axis.

Safety: Conflicts and intrusions

Fig. 21 shows the conflict occurrence per flight. It shows that the number of conflicts per flight increase with traffic demand level for all cases. Also, the conflict-based strategy resulted in the lowest number of conflicts per flight, starting from 200 aircraft. The position-based and intrusion-based strategies both have a number of conflicts per flight that is similar to the baseline (no clustering) at most demand levels, except at 500 aircraft, where they are slightly lower.

Fig. 22 shows the number of intrusions per flight. This plot shows that the number of intrusions per flight increase with traffic demand level. Moreover, the conflict-based strategy resulted in the lowest number of intrusions per flight at most traffic demands. The intrusion-based and position-based clustering strategies are only better than the baseline, starting at 400 aircraft. At these higher demands, the intrusion-based clustering strategy is slightly better than the position-based strategy.

Fig. 23 shows the occurrence of conflicts per distance as a percentage of the baseline. The baseline is illustrated by a dashed line at 100 percent. Similar to the previous plots, the conflict-based strategy has the lowest conflicts per distance percentage. Reaching the maximum improvement of 85 percent at 300 aircraft. The position-based and intrusion-based strategies are slightly below 100 percent at 300 aircraft, but are not able to reach the level of the conflict-based strategy.

Fig. 24 shows the occurrence of intrusions per distance as a percentage of the baseline. This plot shows that the conflict-based strategy has a 70 percent improvement from the baseline at most traffic demand levels. The position-based and intrusion-based strategies have similar values and show improvement over the baseline case at 300 aircraft. Again, they are not able to reduce the number of intrusions per distance travelled as much as the conflict-based strategy.

Fig. 28 shows a cumulative intrusion map for one scenario of 400 aircraft in the air. Figs. 26, 27, show the baseline and conflict-based, strategies, respectively. It can be seen that the baseline case has noticeably brighter hot-spots relating to a higher number of intrusions. Note that the position-based and intrusion-based clustering strategies had a similar map as the conflict-based, so they are not shown here. (refer to the supporting dataset [Morfin Veytia 2024]).

Efficiency: Distance travelled and replans

Fig. 29 shows the distance travelled as a percentage of the baseline case. The plot shows that all clustering strategies force aircraft to travel longer than the baseline. However, this increase never exceeds 10 percent of the baseline value. The intrusion-based clustering strategy forces aircraft to travel the least amount of distance at 100 and 200 aircraft as compared to the other strategies. Interestingly, it has the highest distance travelled at 400 and 500 aircraft. The conflict-based strategy has slightly lower distances than the position-based at most traffic demand levels. The conflict-based strategy is also the lowest at 400 and 500 aircraft.

Fig. 30 shows the number of replans per flight. The position-based clustering strategy has the highest number of replans per flight at low demand levels. Conversely, at the low demand levels, the intrusion-based strategy has the lowest number of replans per flight. However, starting at 300 aircraft in the air, the conflict-based strategy has the lowest number of replans per flight, while the intrusion-based has the highest. It is also interesting to note that the conflict-based and position-based strategies show a similar decreasing trend of replans per flight. On the other hand, the replans per flight in the intrusion-based strategy increases from 100 to 300 aircraft and then tapers at 400 and 500 aircraft.

Clustering: Cluster percentage and stability

Fig. 32 shows the percent of the airspace that is part of a cluster. Note that at all traffic demand levels, the intrusion-based strategy has the least amount of airspace in a cluster. Varying from 5 percent to a maximum value of around 20 percent. At 100 aircraft, the position-based strategy has the highest amount of clustered airspace. However, at higher demand levels the conflict-based strategy tends to have more clustered airspace, up until almost 50 percent at 500 aircraft.

Fig. 33 shows the cluster temporal stability. The results show that the intrusion-based strategy has a large amount of variation at 100 aircraft, this is because there are few intrusions at this density. It then stabilizes at around 65 percent for higher demand levels. The temporal stability of the conflict-based strategy slightly increases, with traffic demand reaching around 70 percent. The temporal cluster stability of the position-based strategy is the lowest for all traffic demand levels, with a maximum of 35 percent.

Fig. 38 shows clusters categorised as high density, at 50 minutes of a simulation with 400 aircraft in the air. Note that these plots only show a single moment in time so they should be analysed in conjuction with Figs. 32 and 33. Fig. 35 shows that the conflict-based clusters are concentrated in the middle of the airspace. Fig. 36 shows that there significantly less clusters identified with the intrusion-based strategy. Finally, Fig. 37 shows that the position-based clusters tend to spread over more of the airspace.

Discussion

The dynamic traffic management method aimed to improve the overall safety of the airspace by applying an additional cost of travel to high-density clustered zones. These clustered zones are created and continually updated by using current observations of positions, conflicts, and intrusions. Each individual aircraft checks if it will intersect clustered areas and makes a new plan to avoid them. The goal is for aircraft to avoid areas with high local traffic density and complexity.

Hypothesis H1 can only be partially accepted because the clustering strategies did not show improvements over the baseline at all traffic demand levels. When comparing the baseline to the conflict-based clustering strategy, the safety improvements over the baseline case are only significant starting at 200 aircraft in the air ($p_{value} < 0.01$). The intrusion-based and position-based strategies are only better than the baseline, starting at 300 aircraft in the air. These results indicate that the method’s effectiveness depends on the presence of sufficient safety event data to form meaningful clusters.

Interestingly, the method is able to limit the extra distance travelled to less than 110 percent of the baseline case. At higher demand levels, when the method is effective for all cluster strategies, the extra distance travelled is around 106 percent of the baseline, while the intrusions per distance percentage is on average lower than 90 percent of the baseline. This shows the trade-off made in the dynamic management method between efficiency and safety.

The intrusion maps show that the clustering strategies are able to dissipate the intrusion hot-spots seen by the baseline case. At higher demand levels, all the strategies are better than the baseline case. The method has achieved the goal of dissipating the intrusion hot-spots without creating new ones due to the replanning at high demand levels. The supplemental documents [Morfin Veytia 2024] show the other heat-maps and some animations of the traffic.

Additionally, the results highlight the reactive nature of the dynamic traffic management method. The airspace must have clusters of positions or safety events to be able to solve them. Clusters mean that aircraft are close to each other, which then leads to conflicts and intrusions. A strategic approach might be able to solve these issues before they happen. However, for a strategic planner to work, the flight plans will need to be provided to a central entity to deconflict them prior to take-off. This could make it more difficult to deal with uncertainties such as wind. Moreover, if urban air traffic is meant to replace a portion of ground operations, the dynamic and ad-hoc nature of ground operations will also add some complexity to the strategic planner.

Hypothesis H2 can be partially accepted. The conflict-based clustering strategy has higher safety levels than the position-based strategy, starting at 200 aircraft in the air, ($p_{value} < 0.01$). However, the intrusion-based strategy only performs better than the position-based at 500 aircraft in the air. The clusters that take into account traffic complexity tend to have higher safety levels than those that consider traffic density for clusters. This can be seen in Example scenario 1 which shows that the position-based clustering forces aircraft to replan even when they are in a relatively low traffic complexity situation. However, it can also be seen that as the traffic demand level increases, the position-based clustering moves closer to the safety level of the conflict-based clustering.

It was observed that the aircraft replans in the position-based clusters has a similar trend than that of the conflict-based concepts. However, these replans are not as effective as reducing the number of intrusions as in the conflict-based strategy. This can be explained by two reasons: (1) the percent of clustered airspace is relatively high (maximum at 50 percent) and the cluster temporal stability is relatively low (maximum 30 percent). Therefore, the location of the clusters is not generally overlapping, causing some oscillatory effects that change the locations of the high-cost airspace. Also, because the traffic demand pattern is not uniform, the location of the high traffic density areas will vary, making traffic density a less effective clustering strategy than traffic complexity. Note that for the intrusion-based strategy, there is only a statistically significant difference with the position-based strategy at 500 aircraft in the air. Therefore, complexity metrics that indicate locations where aircraft may converge (conflicts) are generally more effective than traffic density clustering strategies. The conflict-based complexity indicator is less likely to cluster areas where there is a high traffic density but aligned aircraft (Example scenario 1).

Hypothesis H3 is rejected. The results show that the conflict-based clustering strategy achieved a higher level of safety than the intrusion-based strategy, starting at 200 aircraft in the air. While the null hypothesis is rejected, meaning there is statistically significance when comparing these two strategies ($p_{value} < 0.01$), the trend is the opposite to what was hypothesized. It has been shown that using state-based conflict detection in constrained urban airspace tends to create false conflicts (conflicts that never become intrusions) [Badea et al. 2021]. However, the conflict-based strategy is more effective at avoiding areas with higher traffic complexity and density than the intrusion-based strategy at most traffic demands.

At lower demand levels, the number of intrusions per flight is an order of magnitude less than the conflicts per flight. Therefore, for the intrusion-based strategy, the method does not have enough information to avoid complex traffic areas. This is also why the distance travelled and replans per flight is initially low for the intrusion-based strategy, there are not many intrusion events that create clusters and force aircraft to replan at the low demand levels. At higher demand levels, there is enough information about complex traffic areas, since there are many more intrusions. This is why the intrusion-based strategy is reaching the safety levels of the conflict-based strategy.

The conflict-based strategy has both a high percent of clustered airspace and a high temporal stability. This means that the conflict-based strategy limits the oscillatory effects seen in the position-based strategy and has enough clustered airspace to redistribute aircraft through lower cost routes. Note that the highest percentage of clustered airspace is never more than 50 percent of the total airspace. In contrast, the intrusion-based strategy has a very low amount of clustered airspace at low demand levels. This is also why aircraft travel the least amount of distance and replan the least amount of times at these low densities. There is simply not enough data to identify the high traffic complexity areas. However, as the traffic demand level increases, and there are more intrusions events, the replans per flight are the highest for the intrusion-based strategy. At these high demand levels, the intrusion-based strategy has higher safety levels than the position-based strategy and is approaching the level of the conflict-based strategy.

It is interesting to note that the intrusion-based strategy has a downward trend for the conflicts and intrusions per distance percentage. In contrast, the conflict-based strategy achieves its lowest relative gain of intrusions per distance at 200-300 aircraft. With increasing demand levels, the conflict-based strategy is not able to decrease more than 70 percent. While it shows that the conflict-based strategy is robust with the increasing demand level, it is possible that the false conflicts detected are making it difficult to keep improving.

Conclusion

It was observed that the dynamic traffic management method improves the safety of the airspace. The maximum improvement reduced the intrusions per distance to 70 percent of the baseline (no clustering). It accomplishes this without suggesting excessively long alternate routes. The distance travelled was always less than 10 percent higher than the baseline, and around 6 percent for the best performing strategy (conflict-based).

The work shows that using different aggregate flow data strategies has varying success in avoiding intrusions between aircraft. The clustering strategies that take into account traffic complexity (conflict-based and intrusion-based) were more successful than considering only traffic density (position-based). Amongst the complexity cluster strategies, the conflict-based strategy was the most successful at reducing the number of observed intrusions while limiting extra distance travelled. It is better performing than the intrusion-based strategy because it provides more information about complex traffic areas. This also means that even false conflicts, which are generally seen as unfavourable, can have some beneficial effect. However, they may also limit the performance of the method when the traffic demand levels are high. It is also possible to create a traffic complexity metric by smoothing the traffic density over a certain time limit. This adjusted position-based strategy may mitigate the issues caused by false conflicts.

The proposed method is able to show that a decentralised traffic management system is able to improve upon a baseline (no clustering) case, especially when using traffic complexity metrics. However, this should be compared against other decentralised capacity management system such as those in [Patrinopoulou et al. 2023] that use static zones. Additionally, the reactive nature of the method means that there must be a certain number of safety events observed to work effectively. This is illustrated by the improved safety performance in the intrusion-based strategy with traffic demand level. Therefore, research that combines this strategy with a more strategic planner could further improve the safety.

Further research should focus on trying to improve the understanding of this method. Mainly, it can focus on studying how the parameters, such as additional cost and cluster distance threshold, affect the effectiveness of the method on different virtual networks. It is also possible to further refine how the zones are categorised. Currently, a convex polygon is used to categorise groups of edges. This means that some edges without any traffic may be categorised as high density. However, it might be better to only consider edges where aircraft are actually flying and creating conflicts or intrusions. Moreover, rather than having two airspace categories, making the additional cost multiplier proportional to the measured density of the edges may improve the method.

Moreover, data transmission latency was not considered in this work. It should be studied in concurrence with the cluster update rate to learn the feasibility of the level of communication required. As it was observed that not all aircraft actually make new plans, further research can also focus on limiting the ratio of aircraft that are allowed to replan. It might be that only a certain number of aircraft need to alter their plans in order to see a beneficial effect on safety.

Hypothesis testing results

This appendix will illustrate the formal hypothesis testing results for the hypotheses presented in Section 3.1. The safety levels of the clustering strategies and baseline case will be compared based on the observed intrusions per flight with a Wilcoxon signed-rank test [Wilcoxon 1945]. The intrusions per flight metric is chosen as the relevant metric because it represents aircraft converging at distances less than the safe separation distance.

The null hypothesis is that the differences between strategies is not statistically significant, therefore the null hypotheses will be rejected when $p_{value} < 0.01$

H1 hypothesis test

Hypothesis H1 states that all three clustering strategies will be safer than the baseline case. The null hypothesis is that the baseline case is not statistically different from any of the three clustering strategies. The $p_{value}$ comparing the baseline case to the three clustering strategies is seen in Table 2. Each column represents how that particular strategy compares to the baseline. Hypothesis H1 was partially accepted because the clustering strategies only have higher safety levels at the higher traffic demand levels.

H2 hypothesis test

Hypothesis H2 states that two traffic complexity clustering strategies (conflict-based and intrusion-based) will have higher safety levels than the traffic density strategy (position-based). The null hypothesis is that the position-based strategy is not statistically different from the conflict-based and intrusion-based strategy. The $p_{value}$ comparing the position-based case to the two traffic complexity clustering strategies is seen in Table 3. Each column represents how that particular strategy compares to the position-based strategy. Hypothesis H2 was partially accepted because the conflict-based strategy has higher safety levels than the position-based, starting at 200 aircraft in the air.

H3 hypothesis test

Hypothesis H3 states that the intrusion-based strategy will have higher safety level than the conflict-based strategy. The null hypothesis is that the strategies are not statistically different from each other. The $p_{value}$ comparing both complexity strategies is seen in Table 4. Hypothesis H3 was rejected because the conflict-based strategy had a higher level of safety at most traffic demand levels.

Acknowledgement

The authors would like to thank their reviewers for all their helpful and insightful comments that led to the improvement of this work. Moreover, we would like to thank Calin Andrei Badea for being a helpful outside eye when finding programming bugs.

Author contributions

• Andres Morfin Veytia: Conceptualization, Data Curation, Formal Analysis, Investigation, Methodology, Project Administration, Software, Visualization, Writing (Original Draft), Writing (Review and Editing).

• Joost Ellerbroek: Supervision, Software, Writing (Review and Editing), Project Administration

• Jacco Hoekstra: Supervision, Software, Writing (Review and Editing), Project Administration.

Open data statement

The accompanying sensitivity analysis, software, scenario logs, and additional figures set are provided in [Morfin Veytia 2024]¹. We have also created a small video demonstration of the method here.

Reproducibility statement

The method for reproducing the result is explained in the supplementary repository [Morfin Veytia 2024]. In summary, the process is as follows:

1. Install the python packages required by BlueSky [TUDelft-CNS-ATM] and those required by this paper. There is a list of packages provided in the repository.

2. Use the BlueSky source code provided in the repository.

3. Run the scenarios provided in the repository. The HOWTOSCENARIOS.md document explain how to run scenarios in detail.

4. Create the plots with the logs created by the scenarios. The HOWTOCREATEPLOTS.md document explains how to use the post-processing python code to generate the plots in this paper and some additional ones.