Received June 20, 2019, accepted July 4, 2019, date of publication July 11, 2019, date of current version August 14, 2019. Digital Object Identifier 10.1109/ACCESS.2019.2928355 A Methodology to Perform Air Traffic Complexity Analysis Based on Spatio-Temporal Regions Constructed Around Aircraft Conflicts THIMJO KOCA , MIQUEL ANGEL PIERA, AND MARKO RADANOVIC Logistic and Aeronautics Group, Department of Telecommunications and System Engineering, Autonomous University of Barcelona, 08202 Sabadell, Spain Corresponding author: Thimjo Koca (thimjo.koca@uab.cat) This work was supported by the Logistic and Aeronautics Group, Department of Telecommunications and System Engineering, Autonomous University of Barcelona. ABSTRACT One of the main missions of air traffic management is to guarantee en route safety. This safety is quantified through some minimum separation distance between pairs of flying aircraft. Current systems are human-based, i.e., have human air traffic controllers assuring minimum separation is maintained and in cases a loss of separation is predicted, they take actions to prevent the occurrence of such events. The constant and rapid increment of the air traffic demand is pushing current air traffic control systems to their limits. Development of automatic decision support systems, which can be used to automate, or support aircraft conflict detection and resolution, is considered a possible solution. However, the combinatorial nature of the problem poses several challenges for such a task. Metrics or various analytical procedures to produce information about the complexity of given scenarios can be used to guide the solution search process. In this paper, we present a complexity analysis based on the spatio-temporal interdependencies identified by the use of spatio-temporal regions constructed around the aircraft conflicts. INDEX TERMS Aircraft conflict, complexity metrics, continuous space-time regions. I. INTRODUCTION propose an alternative that is more adequate within the new Air traffic management’s (ATM) mission is to make air generation of ATM systems, where automated CD&R will transportation possible. This is attained by the means of be deployed and the role of the ATCo will be more of a efficient, environmentally friendly, and socially valuable monitoring nature. There, complexity is defined as a measure systems, which have safety as their principal goal [1], [2]. of the air traffic disorder. Such a definition can fit in the In en-route traffic, safety is quantified through a minimum tactical and also the strategic level of ATM. Providing such separation distance that need to be maintained between air- an information at tactical level, and more specifically on the craft. A violation of the minimum separation is called a con- time horizon after a potential loss of separation has been flict. Current ATM provides minimum pairwise separation identified, can allow an automated system, or a human ATCo through a system with human air traffic controllers (ATCo) to adapt its/her solving strategies according to the geometry at the core of its decision making. and complexity of a given scenario and make better use In a context where air traffic demand is increasing in a rapid of the capacity. Moreover, in the case of automatic CD&R and continuous manner, a higher level of automation to sup- solvers, given the combinatorial nature of the problem, such port conflict detection and resolution (CD&R), is considered an adaptation is crucial in providing a fast, efficient, and safe a way to make use of the latent capacity, while maintaining resolution procedure. safety levels [3]. After a potential loss of separation occurs, the aircraft Complexity in ATM is defined in various ways. It can be that might be affected by an issued resolution to the conflict seen as a ‘‘measure of the difficulty that a particular traffic sit- need to be identified and further be considered during the uation will present to an ATCo’’ [4]. This approach fits within conflict resolution procedure. In several proposed resolu- the current, ground-based ATM system, where ATCo are tion methodologies presented in literature, including the actively resolving conflicts. Delahaye and Puechmorel [5] Mixed Integer Nonlinear Programming (MINP) family of approaches [6]–[13], the reach sets family of approaches The associate editor coordinating the review of this manuscript and [14]–[16] and various other approaches, such as the light approving it for publication was Haluk Eren. propagation model [17], one of the main issues raised is the 104528 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see http://creativecommons.org/licenses/by/4.0/ VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis long time needed to find a resolution as the system scales, i.e. Aircraft Density (AD) [20], [21], probably the most widely more aircraft need to be considered in the conflict resolution. used metric, is such an example. It expresses the number of In [18] a methodology to identify surrounding conflict and aircraft flying in a given area, or sector. It is very simple to analyze how the number of possible resolutions evolve over calculate, but it does not consider other factors that can affect time is presented. The proposed approach, however, suffers complexity beyond the number of the aircraft and neither from two main issues. Firstly, initially filtering through the the evolution in time of these factors. The former among cluster window, the way it is performed, might not capture these issues is solved by the introduction of Dynamic Density all the relevant aircraft. Secondly, the possible resolutions are (DD) [22], [23], which is a metric that combines various sought in a discretized space-time, which results in a signifi- traffic characteristics to produce a scalar complexity value. cant computational effort to treat all possible maneuvers. DD metrics, which can perform this combination in a linear In this work, we propose a methodology which overcomes manner [22], or a nonlinear one, using quite often state of the two drawbacks of [18]. Firstly, to avoid missing any the art machine learning techniques [24], still fail to consider relevant member, we define the proposed structures, cluster evolution over time. The temporal element is introduced in and ecosystem, in a hierarchical way. Secondly, to reduce the Interval Complexity (IC) [25], a dynamic density-like metric required computational effort, we introduce a way to con- equipped with a time dimension. IC is calculated on a sector struct spatio-temporal regions that contain possible maneu- level and it is defined as the average over a 5–10 minutes vers an aircraft can perform around a part of its trajectory, time window of the linear combination of the number of given a time interval. We use these regions further to define aircraft flying within the sector; the number of aircraft that and express spatio-temporal interdependencies between air- fly on nonlevel segments; and the number of aircraft that craft at tactical level. We use these interdependencies to fly close to the border of the sector. So even though a time identify the aircraft that should be considered by a CD&R dimension is added, the factors that are considered are not far solver, or an ATCo during a conflict resolution. The obtained from the simplistic AD metric. Fractal Dimension (FD) [26] information, which is significantly richer than the one [18] is another metric, which intents to measure the geometrical provides, can be used to reduce the number of aircraft that complexity. It tries to capture the degrees of freedom of an are considered at tactical level by them in a conflict resolution aircraft given its route and constraints. FD considers time, process, to get a clearer insight on the level of complexity they but comes with the drawback of being dependend on the will face in a specific configuration, and eventually make a airspace structure (it requires an airspace structure made up more efficient use of capacity. of piece-wise linear segments). A quite different approach is The rest of this paper is organized as follows: section II the Input-Output Approach (IO Approach), presented in [27]. contains a review of complexity metrics used in literature and The IO Approach quantifies complexity through the effort some desired characteristics of a complexity metric proposed needed by controller in case a new aircraft is introduced in the in [19]. We present in section III the idea of continuous airspace. More specifically, a new aircraft is introduced in the space-time regions. In section IV, we present clusters, as the sector and in such a way that some loss of separation with the methodology deployed in various works to identify the rel- existent aircraft occurs. A Mixed Integer Linear Program is evant aircraft to a conflict resolution process and further, further utilized to solve the conflict. The amount of total we use the idea of the continuous space-time regions to deviation introduced in the system in the worst case scenario define some finer sets of relevant members, ecosystems, is taken as the complexity metric. This method comes at a based on the corresponding spatio-temporal interdependen- considerable computational cost. cies. We then give in section V some results of identifying Intrinsic Complexity (InComp) [5], [28] is a methodology clusters and ecosystems in real and forecast traffic, and that captures the level of disorder of the air traffic and quanti- perform an analysis of the interdependencies in two detected fies it in vector fields. It is the only one, among the mentioned ecosystems. In section VI, we provide the concluding remarks metrics, that ignores the relation of complexity to air traffic of this work and some possible future ideas to investigate. controller’s workload. As the IO Approach however, it comes Appendix contains some concrete implementations of spatio- at some high computational cost. temporal regions based on heading alteration. Considering further works on CD&R, we notice that in all of the approaches mentioned during the introduction sections II. A REVIEW OF CURRENT METRICS & SOME DESIRED some way of identify the relevant aircraft to the resolution CHARACTERISTICS OF A COMPLEXITY METRIC process, or some complexity information that could guide the There are several ATM complexity metrics that are frequently solution process are absent. An approach is presented in [29], used in literature. Most of them are intended to be used at but being a AD-like approach it is too simplistic and therefore tatical level, within a sector, and independent of identified results in a big number of aircraft that are considered during conflicts. Our main interest lies in cases where a detected con- the resolution process. flict is already detected. However, we choose to present first In [18], after a conflict is detected, the surrounding rel- the following metrics, to provide a broader perspective on evant traffic is identified and some complexity analysis is approaches to qunatify complexity. Most of the constructed performed. The relevant traffic identification is divided in metrics try to relate complexity to the ATCo workload. two steps. On the first step, a big spatio-temporal window VOLUME 7, 2019 104529 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis that includes the trajectories (the parts of the trajectories we applying the stereographic projection [34] on the its latitude are interested in) of the conflict aircraft is constructed and and longitude. The z coordinate represents the aircraft’s alti- all the other aircraft that pass through this are identified. The tude. During the flight, the involved aircraft are assumed to set of all the identified aircraft plus the two conflict aircraft have piece-wise constant velocity between two consecutive make what the authors call the ‘‘cluster’’. On the second step, waypoints. Moreover, planar maneuverability constraints are using a simulation, discrete maneuvers in space and time modeled by the impose of a maximum angle by which an of the conflict aircraft are used to deviated them from their aircraft can deviate. original trajectory. The proposed concept of ‘‘ecosystem’’ is Given the above, the flight state variables of the aircraft is based on these deviations. In case some deviation leads to a specified as (x, y, z, vx , vy , vz ), where (x, y, z) are its coordi- new loss of separation between one of the aircraft involved nates and (vx , vy , vz ) its velocity components. in the initial conflict with some aircraft AC3 , then AC3 is declared member of the ecosystem and should be considered B. ASSIGNING CONTINUOUS SPACE-TIME REGIONS TO during the resolution process. This approach presents two EN ROUTE AIRCRAFT issues. Firstly, taking the cluster cannot guarantee, especially The core idea of continuous space-time regions lies in the in dense scenarios, that all relevant aircraft will be identified. observation that instead of trying to assign a single trajectory Secondly, the use of discretization leads to not considering all to each aircraft that must maneuver to solve a detected con- possible maneuvers, or procedures with a high computational flict, a space-time region can be given to each one of them. cost. Mathematically, classical approaches assign to each In this work, we present a methodology that deals with aircraft a function describing their motion: both these issues. Firstly, to not miss any relevant member,  we propose the use of clusters and ecosystems in hierarchical x = x(t)  structures. Secondly, to decrease computational costs we sub- y = y(t) (1)  z = z(t)  stitute the discrete maneuvers of the second step by continu- ous spatio-temporal regions. The reduction in computational Assigning a region instead, as suggested in [35]–[37] could cost is significant and therefore more realistic cases, with be expressed as: non-linear trajectories can be treated. [x(t), y(t), z(t)] ∈ V (t) (2) A. DESIRED CHARACTERISTICS OF A where V (t) is a dynamic volume, evolving over time. COMPLEXITY METRIC Fig. 1 illustrates a safe space-time region assigned to an aircraft in a world with a single spatial dimension (z coor- In [19] five characteristics, which are desired within the new dinate) and time. The black continuous curves represent the generation air traffic management systems, are discussed. border of AC1 safe region (i.e. a guaranteed conflict-free The first one states that a complexity metric should account area), the green dashed lines represent feasible legs that AC1 for the traffic dynamics, property which AD and DD do not can fly, the red dashed lines represent legs which might cause possess. Independence of the airspace structure, which could a loss of separation, i.e. a conflict and the black dots are make operation in a sector-free context possible, is the second feasible, conflict-free waypoints for AC1 . one and IC and FD are the methodologies that fail based on this criterion. The third one pays attention to the fact IV. IDENTIFICATION OF AIRCRAFT RELEVANT that different time horizons should have different complexity TO A CONFLICT RESOLUTION USING treatments. None of the introduced metrics can be judged SPATIO-TEMPORAL REGIONS under this criterion, since their scope is at sector level only. We propose, in this section, a two-step procedure, similar The forth property is the independence of the control effort, to [18], to detect aircraft that are relevant to a conflict res- property which, only the IntComp metric possesses. Since the olution procedure. Different than [18], here the concepts of system will have a higher level of automation, it is not neces- cluster and ecosystem contain hierarchical structures. sary to relate complexity to the air traffic controller’s effort. Both the cluster and the ecosystem are sets of aircraft based The last property concerns the output format and claims that on pairwise spatio-temporal interdependencies. The concept different output formats are required in different space and of spatio-temporal interdependencies was the object of inves- time horizons. tigation in several European projects, such as PHARE [35], 4DCo-GC [36], PARTAKE [38], and AGENT [37]. Even III. SAFE SPACE-TIME REGIONS though the time horizons and purpose of use vary between A. TRAJECTORY DYNAMICS MODEL them, in all of these projects two aircraft were declared We employ a widely used technique to model the aircraft interdependent if their assigned space-time regions (which dynamics [6], [11], [30]–[33]. The trajectory of the flight can consist of a single trajectory, an assemble of trajecto- is modeled as a series of 4D (space-time) waypoints. The ries, or some continuous space-time region) were closer than aircraft is treated as a point mass in a 3D Euclidean space, they should be (different distance metrics were used in each evolving over time. We obtain its x and y coordinates by project). 104530 VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis FIGURE 1. Assigned safe region for AC1 and examples of various legs it can construct (green segments), or not (red segments). More concisely, let ACi and ACj be two aircraft which spatio-temporal regions we use to define the interdependen- can be en route, or have a planned flight. Let Ri and Rj be cies. Let F denote the set of aircraft we will consider and the space-time regions assigned to ACi and ACj respectively. ACi and ACj be two aircraft in it. Let further Bi and Bj be Then: two spatio-temporal boxes constructed respectively around the trajectories of ACi and ACj , big enough to contain all the ACi ⊥ ⊥ ACj ⇐⇒ Ri ∩ Rj 6 = ∅ (3) possible locations of the aircraft after feasible maneuvers are possibly performed. Then: where ⊥ ⊥ stands for ‘‘interdependent’’. Based on the concept of the interdependency, we will ACi ⊥⊥cl ACj ⇐⇒ Bi ∩ Bj 6 = ∅ (5) construct a hierarchical structure over aircraft. Let there be a potential conflict between at least two en route aircraft. where ⊥⊥cl stands for ‘‘dependent on clustering level’’. We will denote the set of aircraft involved in this conflict by In Fig. 2 an example is given, by representing the hori- C and define a hierarchy over the traffic, based on C, and zontal components (x and y) of the spatio-temporal boxes. denoted by HC . The members of the first order of HC are In this example, the blue box is the box of AC1 , the red the members of C. Members of the ith order, where i 6 = 1, one of AC2 and the green one of AC3 . There is a cluster- are the aircraft that are not members of a lower order, but level interdependency between AC1 and AC2 , another one have an interdependency with a member of the (i − 1)th order. between AC2 and AC3 , but no cluster-level interdependency Formally, given that HC is the defined hierarchy, and HC (i) is exists between AC1 and AC3 . the set of members of the ith order of this hierarchy, we define:  HC (1) := C  HC (i) := {AC ∈ F|AC ∈ HC− (i) ∧ (∃AC0 ∈ (4) 0  HC (i − 1) : AC ⊥⊥ AC )}  where F is the set of all aircraft we can consider, and HC− (i) := F \ ∪i−1 j=1 HC (j)). In other words, HC contains at its first order the preselected set of aircraft C. At its second order it contains aircraft which are not members of the first order, but have at least an interde- pendency with a member of the first order. In the third order we find aircraft that are not members of the first, or second order, but have at least one interdependency with a member FIGURE 2. Example to illustrate cluster pairwise interdependencies. of the second order. The logic goes on recursively. Based on the given interdependency definition (5), and the A. CLUSTER IDENTIFICATION hierarchy definition (4), we will construct the hierarchical Concrete implementations of the hierarchical traffic idea, structure over aircraft, called cluster. Let there be a potential defined above, depend on concrete implementation of the conflict between at least two en route aircraft. We will denote VOLUME 7, 2019 104531 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis the set of aircraft involved in this conflict by C. Members of C (i.e. the spatio-temporal boxes) and the ones proposed here then, are members of the first order of the cluster. Members of contain all feasible heading maneuvers, the spatio-temporal the ith order, where i 6 = 1, are the aircraft that are not members boxes claim a lot of extra space which the aircraft cannot of a lower order, but have an interdependency with a member actually utilize. These claims are eliminated in the spatio- of the (i − 1)th order. Formally, given that Cl is the set of temporal regions used in the ecosystem, the construction of cluster members and Cl(i) is the set of cluster members of which is given in appendix. the ith order, we define: Given the ecosystem interdependency definition, the  ecosystem can be also defined. Let Cl be a given cluster. Cl(1) := C  The aircraft which are first order members of the cluster are Cl(i) := {AC ∈ F|AC ∈ Cl − (i) ∧ (∃AC0 ∈ (6) also first order members of the ecosystem. Members of the ith 0  Cl(i − 1) : AC ⊥ ⊥cl AC )} order, where i 6 = 1, are the aircraft that are members of Cl(i)  and that exists an ecosystem member of (i − 1)th order with where Cl − (i) := F \ ∪i−1 j=1 Cl(j)). which they have an interdependency at the ecosystem level. In the example of Fig. 2, if we assume that AC1 is a conflict Formally, if Ec is the set of ecosystem members and Ec(i) the aircraft,1 but AC2 and AC3 are not, then AC1 will be a member set of ecosystem members of ith order, then: of the first order, AC2 a member of the second order and AC3 a member of the third one. ( Ec(1) := Cl(1) B. ECOSYSTEM IDENTIFICATION Ec(i) := {AC ∈ Cl(i)|(∃AC0 ∈ Ec(i − 1) : AC ⊥⊥ec AC0 )} The cluster structure, from the way its interdependencies are (8) constructed, is too conservative. The use of spatio-temporal boxes, even though it is computationally efficient, results An ecosystem can be clearly defined directly in a given in an overestimation of the complexity of a given scenario. traffic, without the need of a corresponding, predefined In order to provide a better estimation of the scenario cluster. Because on the implemtation used for this work, complexity and the interdependencies between the aircraft, to identify pairwise interdependencies we use a brute force we introduce here the ‘‘ecosystem’’ structure. The difference approach and check all the pairs, the use of a cluster comes between a cluster and its corresponding ecosystem lies on the with high computational advantages. The introduction, how- nature of their interdependencies. While to construct a cluster, ever, of more sophisticated techniques, like the hextree sub- spatio-temporal boxes were used, as a mean of approximating divisions [39] can vanish this advantage and even increase the results of performing some maneuvers, to construct an further the computational efficiency. In such a scenario, ecosystem we will check the actual possible maneuvers. the ecosystem structure can be constructed directly from the Let F be the set of all aircraft we will consider. Let tr(ACk ) traffic, without the cluster structure being a mediator. denote the original trajectory of an aircraft ACk in F, and Note that, because of the more complex structure of the Mk the set of possible maneuvers for ACk . Furthermore, let ecosystem windows, which are changing shape in time, tr(ACk , m) be the modified trajectory of ACk after performing a schematic representation, similar to the one provided a maneuver m ∈ Mk . Then, given two aircraft ACi and ACj in Fig. 2 for the cluster case, could be misleading. We there- from F and their corresponding set of possible maneuvers Mi fore, decide not to provide one. and Mj , 1) THE ECOSYSTEM STRUCTURE AS A COMPLEXITY ⊥ec ACj ⇐⇒ ∃mk ∈ Mi , ACi ⊥ INFORMATION PROVIDER ml ∈ Mj : conf(ACi , ACi , mk , ml ) (7) From the way we construct it, an ecosystem demonstrates the ability to identify latent capacity, if there is some, and guide where ⊥ ⊥ec denotes an ‘‘interdependency in ecosystem the search for a resolution. If, furthermore, regions of other level’’ and conf(ACi , ACj , mk , ml ) denotes that aircraft ACi maneuvers are constructed, with velocity module adjustment and ACj will be in conflict if they perform maneuvers mk and for example, altitude change or other complex maneuvers, ml respectively. the most promising among them can be identified. Spatio-temporal regions become relevant in the calculation Moreover, even though the ecosystem is not a metric of interdependecies at the ecosystem level. Instead of consid- (it is not a function by which we can obtain a numerical ering all possible pairs of trajectories, it is enough to check value), from the five proposed properties, the ecosystem for an inter-regional conflict, between regions that include structure and the related interdependencies account for the all possible maneuvers for each aircraft. This will suffice to air traffic dynamics and provide independence of the airspace consider all physically feasible simple heading maneuvers structure and the control effort. The other two properties, that a CD&R system can issue. Note that, while both the are irrelevant since the construction is proposed for tactical spatio-temporal regions proposed in the clustering procedure level only. The ecosystem structure therefore, can provide 1 We assume AC is in conflict with aircraft AC . AC is not depicted 1 0 0 some valuable complexity information regarding conflict in Fig. 2. resolution. 104532 VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis V. SIMULATION RESULTS is used to construct the aircraft’s space-time regions. A. DATA AND THE PARAMETERS USED Three regions are build for each aircraft, region ‘‘left’’ We evaluate the method using traffic data from Eurocontrol’s bounded by aircraft’s original trajectory and its leftmost tra- Demand Data Repository II (DDR II). We present two sce- jectory that the aircraft can achieve, given its configuration, narios, one with real historical traffic from 12.02.2019 and region ‘‘right’’ bounded by aircraft’s original trajectory and another one with synthetic dense traffic generated using its rightmost trajectory it can achieve given its configuration, Eurocontrol’s STATFOR.2 The predicted traffic is a high and region straight including only the original trajectory of density estimate on the date 10.09.2021. In both scenarios, the aircraft. we consider en route conflicts around London TMA, more To check if a pair of aircraft has an interdependency at specifically aircraft flying between 51.01 and 52.05 degrees cluster, or ecosystem level, a brute-force approach was used of latitude, −0.85 and −0.14 degrees of longitude and above and each pair of aircraft was investigated. This procedure flight level 245 (i.e. above 24500 feet). exhibits a computational complexity of 2(n2 ), where n is Conflicts are detected using the methodology proposed the number of aircraft we consider. This performance can in [40] with an added filter to discard the false positive significantly be improved by the use of more sophisticated results, and conflicts with a conflict interval larger than one techniques, as the hextree subdivision method [39], which minute. As soon as a conflict is detected, the originally displays a computational complexity of 2(n) on usual setup planned trajectory of each involved aircraft is filtered from and 2(n2 ), in the unlikely case of having near identical five minutes before entering the conflict interval until two trajectories. minutes after exiting the conflict interval. The time length of the cluster is therefore seven minutes plus the length B. COMPARISON OF CLUSTERS TO THE ECOSYSTEMS of the conflict. Fig. 3 illustrates the planar cluster window. 3306 conflicts, out of which 3275 short enough,4 were For each geographic direction (North, South, East, West) detected in the historical traffic scenario and 12848 conflicts, out of which 12746 short enough, were detected in the futur- istic traffic scenario. An analysis was performed for all the detected cases, however 2000 conflicts were sampled from each scenario and used to construct the histograms provided in this section. Fig. 4 contains the histogram of the identified clusters in the scenario with the historical traffic, while Fig. 5 con- tains the histogram of the corresponding ecosystems. In the clustering step, 7.25% (i.e. 145 out of 2000) of the clusters have more than forty members each and 37.35% of them (i.e. 747 out of 2000) have only two members. The corre- sponding ecosystems have a maximum of six members, found in three cases, and 90.3% of the total amount (i.e. 1806 out of 2000) have only two members. The reduction is drastic. The futuristic scenario exhibits a similar reduction tendency, where in the clustering case we have 7.25% (i.e. 145 out of 2000) of the clusters with more than forty members and 34.9% (i.e. 698 out of 2000) of them with two mem- bers only. The corresponding ecosystems have a maximum of seven members in ten cases and 88.55% (i.e. 1771 out of 2000) of the total with only two members. What the clustering structure does essentially is count FIGURE 3. The planar part of the cluster box. the amount of aircraft flying in a given space-time volume relevant to a detected conflict. In this sense, the number of we take the furthest waypoint and add to it 25 nautical cluster members is a measure similar to the dynamic aircraft miles (NM). The vertical cluster window, which is not illus- density. An interesting observation, in both scenarios, is that trated in Fig. 3 for clarity reasons, is formed in a simi- even though the clustering structure can have significantly lar manner with a margin of 3000 feet.3 We extend both large amount of members, counting the possible dependen- clusters and ecosystems up to a third level. On ecosystem cies that can come by performing feasible maneuvers of the level, the time window is kept the same as in the clus- aircraft through the ecosystem structure, reduces drastically ter case and a maximum deviation angle of 60 degrees the amount of aircraft that need to be considered in a conflict 2 STATFOR is a tool that predicts future traffic demand based on the resolution procedure. current one and airport constraints. 3 Both spatial values were chosen based on experimentation. 4 With a duration shorter than two minutes. VOLUME 7, 2019 104533 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis FIGURE 5. Histogram of ecosystems identified in the historical traffic. The first ecosystem is taken from the historical traffic. The corresponding cluster contains 39 members, 2 of which of the first order, 23 of the second, and 14 of the third one. The members of the ecosystem are classified in 2 members of the first order, 3 of the second, and 2 of the third one. Fig. 8 shows the graph of interdependencies for ecosystem 1. Each node of the graph represents an aircraft of the ecosystem. Two nodes are connected via an edge if there exist an interdependency between them at ecosystem level, i.e. if there exist a pair of feasible maneuvers, one for each aircraft, that can put them into conflict. For example in a certain scenario a left FIGURE 4. Histogram of clusters identified in the historical traffic. maneuver of AC1 could result in a loss of separation with AC3 . In this case, AC1 and AC3 are declared interdependent and the vertices that represent them in the graph of the interde- C. ANALYSIS OF AN ECOSYSTEM FOR EACH TRAFFIC pendencies are connected through an edge. We see that even Going further than the number of members of each struc- though there are 7 members, they are loosely connected to ture, the dependencies between various regions used in the each other and the chances of finding an efficient solution ecosystem can give us a deeper insight. Two ecosystems, quickly are high. An interesting observation comes if we each with 7 members are analyzed and compared for this constrain ourselves to seek solutions only by maneuvering the purpose. A similar analysis can be also performed at the ecosystem members of the first order and letting the rest of cluster level. However, the over-conservative approached by the members maintain their original trajectories. This case is which the clusters are constructed, would result in minimal depicted in Fig. 9. Interestingly, AC2 can perform a maneuver insights. without inducing a new conflict. 104534 VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis FIGURE 7. Histogram of ecosystems identified in the futuristic traffic. FIGURE 6. Histogram of clusters identified in the futuristic traffic. FIGURE 8. Graph of ecosystem 1 in the historical traffic. The situation is different for ecosystem 2, the ecosystem extracted from the futuristic scenario, even though it also has 7 members. The corresponding cluster contains 35 members of first order, 4 of the second order, and 1 of the third order. (i.e. less than the 39 members in the first case), 2 of which are Moreover, as shown in Fig. 10 the graph of interdependen- of the first order, 18 of the second, and 15 of the third one. cies is denser, almost fully connected. Constraining to single The members of the ecosystem are classified in 2 members maneuver solutions, reduce the number of aircraft we need VOLUME 7, 2019 104535 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis polygon, i.e. a set of points, each of which has an initial location, a constant velocity (in module and direction), and the time interval during which it exists. To validate the construction process of the proposed spatio-temporal regions for the treated scenarios, using an exhaustive generation of points, we simulate possible trajec- tories and check if they lie inside the defined regions. More precisely, we create a class validation-point, which contains 4D coordinates, a cumulative angle, and the accumulated delay. The 4D coordinates hold the current location of the point during the validation simulation, the cumulative angle holds the sum of all the angles that the validation-point has performed so far in the simulation. An example is given in Fig. 12. The blue line is the initial trajectory. Poin A lies on the initial trajectory, point B lies on the trajectory obtained FIGURE 9. Graph of ecosystem 1 constrained to after a turn of 30 degrees, point C lies on the trajectory single-maneuver-solutions. obtained after taking another turn of 20 degrees, and point D lies at the trajectory obtained after performing another turn of −30 degrees. In this scenario the cumulative angle value is 0 degrees at point A, 30 degrees at point B, 50 degrees at point C, and 20 degrees at point D. FIGURE 10. Graph of ecosystem 2. to consider, but still leaves the rest of the members heavily connected, Fig. 11. Therefore, solving this ecosystem is not FIGURE 12. Example of an aircraft taking several turns. as straightforward as solving the previous one. The above comparative analysis hints the power that spatio-temporal To calculate the accumulated delay of the scenario interdependencies, based on only feasible maneuvers of the in Fig. 13, we use the following procedure: Let the blue aircraft, have. line be the original trajectory of the aircraft and the black one the trajectory after some deviation is performed. Let B1 be the projection of B in the original trajectory, and B2 the location of the aircraft if it would have maintained its original trajectory. Let VE be the original velocity, α the deviation angle, and dt1 the time interval it took the aircraft to fly from point A to point B. Then the accumulated delay, denoted by d, at point B is: |B1 B2 | (||VE || − ||VE cos α||)dt1 d= = ||VE || ||VE || FIGURE 11. Graph of ecosystem 2 constrained to single-maneuver-solutions. D. VALIDATION OF THE SPATIO-TEMPORAL REGIONS Velocities of different directions are used for different parts of the regions, therefore, we implemented the spatio-temporal regions through several sub-regions. A sub-region is a moving FIGURE 13. Example to illustrate accumulated delay. 104536 VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis The generation of trajectories to be validated works as Construction of spatio-temporal regions based on altitude follows: We start from the initial state of the expanding sub- change, or velocity module change only, given piecewise region, i.e. the first 4D point after which we are allowed linear trajectories, are a direct adaptation of the provided to perform a maneuver. Discretizing in time by one second methodology, therefore, regions based on simple maneuvers and in deviation angles by 5 degrees, we generate possible are defined. Also enlarging the time horizon can be addressed locations of the point, updating its cumulative angle and its by changing the initial state of the constructed regions accumulated delay. We perform this step recursively until (provide an initial state in the form of a polygon instead of an end point is reached, or until no more subsequent valid a single point). A topic to be investigated is the construction points exist, keeping the cumulative angle less than the max- of such regions based on combination of simple maneuvers, imum allowed (in our simulations it was 60 degrees) and the i.e. based on compound maneuvers which are sometimes accumulated delay less than the maximum allowed delay (it necessary in practice. can be calculated using the outer most deviation angle). For Complexity information needs also to be available at a the regions to be valid, all the generated points need to lie higher level. Another topic to investigate, therefore, is how within it. interdependencies between ecosystems can be constructed We performed this validation procedure for all the regions based on the aircraft interdependencies, i.e. how solving one we generated in both simulated traffic scenarios and in all ecosystem can affect the solution of another one. This anal- cases the generated points lied within the corresponding ysis can certainly be performed at tactical level. It needs to spatio-temporal region. be investigated if it can be performed at strategic level, too. In that case, a definition of an ecosystem which does not lie VI. CONCLUSIONS & FUTURE WORK on a detected conflict might be necessary. New automatic decision support systems are essential in the quest to modernization of the airspace to reduce congestion APPENDIX and delays and handle denser traffic flows. A key element in CONTINUOUS SPACE-TIME REGIONS IMPLEMENTATION such a system would be a tool which provides information BASED ON HEADING CHANGES regarding the complexity of given scenarios. We propose in Using the trajectory dynamics model and the general con- this work a methodology by which we can identify the aircraft tinuous space-time region ideas presented in section III, that should be considered in a conflict resolution process. we develop here a concrete implementation of regions that This is done using the sets of all possible maneuvers that an include all feasible heading alteration maneuvers for an air- aircraft can perform in a given time interval. Based on that craft. Our assumptions include constant velocity and linear methodology, we enrich and reinforce the ecosystem concept, trajectories of the involved aircraft.5 found in [18], and use it to show firstly that even in cases We consider maneuvers with heading alterations only. of high aircraft density of current traffic and forecast one, Maneuvers based on altitude alteration, planar velocity mod- the amount of aircraft that can be affected by a resolution is ule change, or combinations of some of the above, can be drastically lower than the amount of aircraft a density-like treated in a similar manner. metric would suggest. Secondly, using the actual interdepen- Let x0 , y0 , z0 , t0 be the starting 4D waypoint from where dencies information, deeper insight can be achieved, regard- we can consider possible heading alterations. Modeling phys- ing the coupling of the involved conflict aircraft with the ical limitations of the aircraft by the imposition of a maximal surrounding traffic aircraft, applying the interdependencies angle of deviation αmax , results in a situation where if the graphs of an ecosystem. aircraft performs a heading change at t0 , at a given time t, An interesting, in our opinion, path for future work is it will be found on the arc bounded by the radius forming to investigate how more information can be included in the an angle of αmax with the original trajectory and the radius ecosystem graphs. The methodology that calculates inter- forming an angle of −αmax with the original trajectory. The regional conflicts can provide information about time dura- arc will lie on the circle with center [x0 , y0 ] and has a radius tion of each conflict and which parts of the regions are of ||Ev||(t − t0 ). Fig. 14 depicts the situation. involved in the conflict. These pieces of information need to For construction reasons, we want to divide this family of be utilized in the construction of the interdependencies graph. arcs into two subfamilies, each one of them being bounded, Another issue to be investigated is how these graphs can be as depicted in Fig. 15 and 16, by the original trajectory and used in actual conflict solvers and the impact they might have the limits of the original arcs. in computational efficiency terms. While in solvers based on While constructing regions in space-time, there are two Mixed-Integer Non-linear Programming (MINLP), or Con- constraints we need to initially consider. The first one is that a straint Programming (CP), the graphs can be used to control change of heading can be performed at various time instances, the constraints the model will have, the utility they can bring as shown in Fig. 17. The second one is the necessity for a way in other type of solvers needs to be investigated. A study on to return to the original 3D trajectory. how the adaptation of the proposed concept and utilization of the provided information in different solvers, can result in a 5 These constraints are relaxed in the subsection where piece-wise linear finite number of complexity classes is also of high interest. trajectories and piece-wise constant velocities are assumed. VOLUME 7, 2019 104537 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis FIGURE 18. Constructed linear bounds. FIGURE 14. Resulting arcs by performing a heading change at t0 . FIGURE 19. A heading change can be performed at various time instances. To deal with the second constraint, at each time instance, regions as the one shown in Fig. 19 need to be considered. FIGURE 15. Family of upper arcs. The depicted space region is bounded by the arc CD ˆ and the segments [BC] and [DB] and is assigned to the aircraft at time instance ti . ti is the time when the aircraft would have reached point C, if it would have followed its original trajectory. More formally, we would assert: Theorem: Let the region R(ti ), bounded by [DB], [BC], and ˆ depicted in Fig. 19, be the space region assigned to the CD, aircraft at the time instance ti . Let the aircraft be at time instance t = tA : tA ≤ ti at the point A, which lies on its FIGURE 16. Family of lower arcs. original trajectory. Moreover, let E be an arbitrary point that the aircraft want to reach at t = ti by maneuvering at t = tA . Then 6 EAC ≤ 6 DAC H⇒ E ∈ R(ti ). where 6 EAC is the small angle formed by the segments EA and AC. The space-time region, R(t), we want to assign to an aircraft is therefore an evolving arc surface, which can be divided in three sub-regions, Fig. 20. Re (t) has an arc which moves in the direction defined by the aircraft’s initial velocity and is expanding as time evolves, Rp (t) has an arc that only moves in the direction defined by the aircraft’s velocity and FIGURE 17. A heading change can be performed at various time Rsh (t) has an arc that moves and also shrinks as time evolves. instances. Time instances t1 and t2 are the instances of change between the regions and defined by the time when the aircraft would Dealing with the first constraint is more straightforward. We can define some linear bounds6 as the one depicted in Fig. 18. The outer bound can be interpreted as the worst trajectory (in terms of divergence from the original trajectory) that the aircraft can be assigned in the given space-time region. 6 In a practical situation bounds are used to describe acceptable delays with respect to the RBT. To measure this maximal delay, some global perspective of the system considering the business model of the airline, the TTA’s and CTA’s, and the traffic conditions is required and this goes beyond the scope of this work. FIGURE 20. The three sub-regions of the defined region. 104538 VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis have reached points A1 and A2 respectively, if it would follow 2) LOSS OF SEPARATION BETWEEN A MOVING POINT AND its original trajectory. AN INNER POINT OF A MOVING SEGMENT, WHEN THE CLOSEST POINT BETWEEN THE POINT AND THE A. LOSS OF HORIZONTAL SEPARATION SEGMENT IS AN INTERNAL SEGMENT POINT BETWEEN REGIONS Let pEij := pEi − pEj and nE(t) = pEn + t vEn be the normal to the In order to provide safety, we need a way of defining and line that includes [pE1 (t), pE2 (t)], which means that pEn (t) := detecting pairs of unsafe regions, i.e. inter-regional con- [x21 (t), y12 (t)] and vEn := [vx21 (t), vy12 (t)], then the procedure flicts. To define the inter-regional conflict, we propose to is the following: approximate the arcs by series of segments. In this • Find the time intervals during which the closest point way a region R(t) will be approximated by an evolving between the line on which the segment lies and the point polynomial P(t). is an interior segment point. There are well-known methods in Computational Geom- The condition to be satisfied is sign(En(t) · pE31 (t)) 6= etry to find the distance between two fixed polygons [41], sign(En(t) · pE32 (t)),7 which transforms in a pair of second however in this section, to avoid time-discretization, we will order polynomial inequalities with respect to time and make use of the fact that the vertices of the polygon evolve can be solved analytically. in a linear manner. A loss of separation between the evolving • Find the time intervals during which there’s a loss of polygons can be seen as a loss of separation between pairs of separation between the line and the point moving segments. The distance between a point p = (x0 , y0 ) and a line The distance between two arbitrary segments [P1,1 P1,2 ] l : (a, b, c is: and [P2,1 P2,2 ] can be expressed as: |ax0 + by0 + c| d= √ d([P1,1 P1,2 ], [P2,1 P2,2 ]) := min d([Pi,1 Pi,2 ], P3−i,j ) (9) a2 + b2 i,j∈1,2 which translates in our case to: which in our case would translate: |En(t) · pE31 (t)| |En(t) · pE32 (t)| ∨ ||En(t)|| ||En(t)|| d([P1,1 (t)P1,2 (t)], [P2,1 (t)P2,2 (t)]) and can be further transformed in forth order polynomial := min d([Pi,1 (t)Pi,2 (t)], P3−i,j (t)) (10) with respect to time, which can be solved analytically. i,j∈1,2 • Find their intersections t1 . where Pi,j (t) = vi,j ∗ t + p0,i,j is a vertex of a polygon • Find the intersections t2 of t1 with the interested time belonging to ACi , vi,j its velocity and p0,i,j its initial position. interval. The closest point of a segment from a point can be one of • Find the intersection of t2 with the time interval during the segment’s end-points, or an inner point of the segment. which there is a vertical loss of separation. Let our segment be [pE1 (t), pE2 (t)] and the point pE3 (t), where pEi (t) = pE0i + t vEi , then the procedure to check if there is a loss B. GENERALIZATION TO PIECE-WISE LINEAR of separation between a moving point and a moving segment TRAJECTORIES is the following: In this section we present a more general model. We will con- • Check if there is a loss of separation between the sider piece-wise linear trajectories with piece-wise constant point pE3 (t) and each of the two end-points. velocity. • Check if there is a loss of separation between pE3 (t) and an inner point of the segment [pE1 (t), pE2 (t)]. • Calculate the conflict interval as the union of the three resulting conflict interval 1) LOSS OF SEPARATION BETWEEN TWO MOVING POINTS The distance between two points is: d(pEi (t), pE3 (t)) := ||(pE0i − pE03 ) + t(vEi − vE3 )|| FIGURE 21. The space region before and after the change of the segment. To have a loss of separation we require: As can be seen in Fig. 21, to pass the region from one d(pEi (t), pE3 (t)) < H linear segment of the trajectory to the next one, a rotation must be performed if we want to maintain the inner bound where H is the required minimum horizontal separation. on the original trajectory. Such a rotation would introduce This is expression can be easily transformed in a polyno- mial equation of second order with respect to t and can be 7 Intuitively we are asking the point to be on opposite sides of the lines, solved analytically. perpendicular to our segment and passing each from one of its end-points. VOLUME 7, 2019 104539 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis non-linearities in the velocity of the regions for the transi- REFERENCES tion period, which for now, considering piece-wise constant [1] G. Di Gravio, M. Mancini, R. Patriarca, and F. Costantino, ‘‘Overall velocities, we want to avoid. There are various ways to get safety performance of the air traffic management system: Indicators and analysis,’’ J. Air Transp. Manage., vols. 44-45, pp. 65–69, May/Jun. 2015. through such a problem, one of which is by constraining [2] A. Cook, S. Belkoura, and M. Zanin, ‘‘ATM performance measurement in the expanding part of the space-time region to happen only Europe, the US and China,’’ Chin. J. Aeronaut., vol. 30, no. 2, pp. 479–490, during the time interval of one particular segment. As soon Apr. 2017. [3] J. Tang, M. A. Piera, and T. Guasch, ‘‘Coloured Petri net-based traffic as the next segment starts, the parallel motion begins. And it collision avoidance system encounter model for the analysis of potential continues until the segment during which we want the region induced collisions,’’ Transp. Res. C, Emerg. Technol., vol. 67, pp. 357–377, to shrink, as seen in Fig. 22. Caution should be taken so that Jun. 2016. [4] C. Meckiff, R. Chone, and J. Nicolaon, ‘‘The tactical load smoother for time interval during which the region has to shrink is long multi-sectorplanning,’’ in Proc. 2nd USA/Eur. Air Traffic Manage. RD enough. Seminar, Dec. 1998, pp. 1–12. [5] D. Delahaye and S. Puechmorel, ‘‘Air traffic complexity: Towards intrin- sic metrics,’’ in Proc. 3rd USA/Eur. Air Traffic Manage. RD Seminar, Jun. 2000, pp. 1–11. [6] L. Pallottino, E. M. Feron, and A. Bicchi, ‘‘Conflict resolution prob- lems for air traffic management systems solved with mixed integer pro- gramming,’’ IEEE Trans. Intell. Transp. Syst., vol. 3, no. 1, pp. 3–11, Mar. 2002. [7] M. Christodoulou and C. Costoulakis, ‘‘Nonlinear mixed integer program- ming for aircraft collision avoidance in free flight,’’ in Proc. 12th IEEE Mediterranean Electrotechn. Conf., 2014, pp. 327–330. [8] A. E. Vela, S. Solak, J.-P. B. Clarke, W. E. Singhose, E. R. Barnes, FIGURE 22. The evolution of a space region in a piece-wise linear and E. L. Johnson, ‘‘Near real-time fuel-optimal en route conflict reso- trajectory. lution,’’ IEEE Trans. Intell. Transp. Syst., vol. 11, no. 4, pp. 826–837, Dec. 2010. [9] S. Cafieri and N. Durand, ‘‘Aircraft deconfliction with speed regulation: New models from mixed-integer optimization,’’ J. Global Optim., vol. 58, C. USED DATA STRUCTURES TO REPRESENT MOVING no. 4, pp. 613–629, Apr. 2014. POLYGONS & COMPLEXITY ANALYSIS OF INTER- [10] A. Alonso-AyusoLaureano, F. Escudero, F. J. Martín-Campo, and POLYGON CONFLICT IDENTIFICATION N. Mladenović, ‘‘A VNS metaheuristic for solving the aircraft conflict detection and resolution problem by performing turn changes,’’ J. Global Each spatio-temporal region is represented as an array of Optim., vol. 63, no. 3, pp. 583–596, Nov. 2015. moving polygons. Each one of them representing the spatio- [11] A. Alonso-Ayuso, L. F. Escudero, and F. J. Martín-Campo, ‘‘Exact and temporal part that an aircraft claims during one of the seg- approximate solving of the aircraft collision resolution problem via turn changes,’’ Transp. Sci., vol. 50, no. 1 pp. 263–274, Oct. 2016. ments of its trajectory. A moving polygon, as explained above [12] A. Alonso-Ayuso, L. F. Escudero, and F. J. Martín–Campo, ‘‘An exact is an array of moving points. A moving point has an initial multi-objective mixed integer nonlinear optimization approach for aircraft position, a velocity and a time interval during which it exists. conflict resolution,’’ TOP, vol. 24, no. 2, pp. 381–408, Jul. 2016. [13] S. Cafieri and R. Omheni, ‘‘Mixed-integer nonlinear programming for To detect potential losses of separation between given aircraft conflict avoidance by sequentially applying velocity and head- regions a brute-force approach was used, i.e. each pair of ing angle changes,’’ Eur. J. Oper. Res., vol. 260, no. 1, pp. 283–290, regions is checked. Such a procedure exhibits a computational Jul. 2017. [14] I. M. Mitchell, A. M. Bayen, and C. J. Tomlin, ‘‘A time-dependent complexity of O((nrp)2 ), where n is the number of aircraft Hamilton-Jacobi formulation of reachable sets for continuous dynamic and r is the maximum number of regions each aircraft can games,’’ IEEE Trans. Autom. Control, vol. 50, no. 7, pp. 947–957, have, and p is the maximum number of moving polygons Jul. 2005. each region can have. The core procedure used is the one [15] Y. Yang, J. Zhang, K.-Q. Cai, and M. Prandini, ‘‘A stochastic reachability analysis approach to aircraft conflict detection and resolution,’’ in Proc. that checks for conflicts between two moving polygons. This IEEE Conf. Control Appl. (CCA) Oct. 2014, pp. 2089–2094. procedure has a computational complexity O(s2 ), where s is [16] Y. Yang, J. Zhang, K.-Q. Cai, and M. Prandini, ‘‘Multi-aircraft conflict the maximum number of segments the polygon can have. detection and resolution based on probabilistic reach sets,’’ IEEE Trans. Control Syst. Technol., vol. 25, no. 1, pp. 309–316, Jan. 2017. The calculation of distances between the moving segments, [17] N. Dougui, D. Delahaye, S. Puechmorel, and M. Mongeau, ‘‘A light- as explained in the previous subsection, translates to the propagation model for aircraft trajectory planning,’’ J. Global Optim., solution of some polynomial inequalities of second and forth vol. 56, no. 3, pp. 873–895, Jul. 2013. [18] M. Radanovic, M. A. P. Eroles, T. Koca, and J. J. R. Gonzalez, ‘‘Surround- order. The existence of analytic solutions for such cases [42] ing traffic complexity analysis for efficient and stable conflict resolution,’’ reduces their computational complexity to O(c), where c is Transp. Res. C, Emerg. technol., vol. 95, pp. 105–124, Oct. 2018. constant. [19] M. Prandini, L. Piroddi, S. Puechmorel, and S. L. Brazdilova, ‘‘Toward air traffic complexity assessment in new generation air traffic management The used methodologies resulted in satisfactory running systems,’’ IEEE Trans. Intell. Transp. Syst., vol. 12, no. 3, pp. 809–818, times. The use, however, of more sophisticated methods (such Sep. 2011. as the hextree subdivisions methodology [39]) instead of the [20] B. Sridhar, K. S. Sheth, and S. Grabbe, ‘‘Airspace complexity and its application in air traffic management,’’ in Proc. 2nd USA/Eur. Air Trafic brute-force approach, could reduce the computational com- Manage. RD Seminar, Dec. 1998, pp. 1–9. plexity for usual setups to O(nrp) and O(s) respectively.8 [21] C. Bonaceto, ‘‘Cognitive Complexity in Air Traffic Control a Literature Review,’’ EEC note, vol. 4, no. 4, pp. 1–80, Mar. 2013. [22] A. J. Masalonis, M. B. Callaham, and C. R. Wanke, ‘‘Dynamic density and 8 In the worst case of near identical trajectories, which is unlikely to happen complexity metrics for realtime traffic flow management,’’ in Proc. 5th in practice, the complexities will be O((nrp)2 ) and O(s2 ). USA/Eur. Air Traffic Manage. RD Seminar, Jun. 2003, pp. 1–10. 104540 VOLUME 7, 2019 T. Koca et al.: Methodology to Perform Air Traffic Complexity Analysis [23] P. Kopardekar and S. Magyarits, ‘‘Dynamic density: Measuring and pre- THIMJO KOCA received the bachelor’s degree dicting sector complexity [ATC],’’ in Proc. 21st Digit. Avionics Syst. Conf., in computer engineering from the Polytechnic Oct. 2003, p. 2C4. University of Tirana, Tirana, Albania, 2014, [24] X. Cao, X. Zhu, Z. Tian, J. Chen, D. Wu, and W. Du, ‘‘A knowledge- and the master’s degree in mathematical mod- transfer-based learning framework for airspace operation complexity eval- eling, specialized in stochastic and optimization uation,’’ Transp. Res. C, Emerg. Technol., vol. 95, pp. 61–81, Oct. 2018. from a joint program between the University of [25] P. Flener, J. Pearson, M. Ågren, C. Garcia-Avello, M. Çeliktin, and L’Aquila, L’Aquila, Italy, Hamburg University, S. Dissing, ‘‘Air-traffic complexity resolution in multi-sector planning,’’ Hamburg, Germany, and Autonomous University J. Air Transp. Manage., vol. 13, no. 6, pp. 323–328, Nov. 2007. of Barcelona, in 2016. He is currently pursuing the [26] S. Mondoloni and D. Liang, ‘‘Airspace fractal dimension and applica- tions.,’’ in Proc. 4th USA/Eur. Air Traffic Manage. RD Seminar, Dec. 2001, Ph.D. degree with the Department of Telecommu- pp. 4–7. nications and System Engineering, Autonomous University of Barcelona, [27] K. Lee, E. Feron, and A. Pritchett, ‘‘Air traffic complexity: An input-output Barcelona, Spain. His research line is on application of multi-agent systems approach,’’ in Proc. Amer. Control Conf., Jul. 2007, pp. 474–479. in air conflict resolution. [28] S. Puechmorel and D. Delahaye, ‘‘New trends in air traffic complexity,’’ in Proc. Int. Workshop ATM/CNS (EIWAC), 2009, pp. 17–23. [29] D. Gekht and M. Idan, ‘‘Tactical replanning algorithms for four- dimensional contracts in air traffic control,’’ J. Guid., Control, Dyn., MIQUEL ANGEL PIERA received the degree vol. 17, no. 6, pp. 1050–1062, Apr. 2014. (Hons.) in computer engineering from the [30] J. Hu, M. Prandini, and S. Sastry, ‘‘Optimal coordinated maneuvers for Autonomous University of Barcelona, Barcelona, three-dimensional aircraft conflict resolution,’’ J. Guid., Control, Dyn., Spain, in 1988, the M.Sc. degree in control vol. 25, no. 5, pp. 888–900, Sep. 2002. engineering from the University of Manchester, [31] ‘‘Report on AGENT functional and non-functional requirements,’’ Institute of Science and Technology, Manchester, Autonomous Univ. Barcelona, Bellaterra, Spain, Tech. Rep., 2016. England, 1991, and the Ph.D. degree from the [32] C. Munoz, A. Narkawicz, and J. Chamberlain, ‘‘A TCAS-II resolution Autonomous University of Barcelona, in 1993. advisory detection algorithm,’’ in Proc. AIAA Guid., Navigat., Control Conf. (GNC), 2013, p. 4622. He was a Deputy Director of the Autonomous [33] E. Koyuncu, M. Uzun, and G. Inalhan, ‘‘Cross-entropy-based cost-efficient University of Barcelona Engineering School and 4D trajectory generation for airborne conflict resolution,’’ Proc. Inst. Mech. a Director of LogiSim (Research Group on Modeling and Simulation of Eng., G, J. Aerosp. Eng., vol. 230, no. 9, pp. 1605–1631. Feb. 2016. Complex Systems). He is a delegate for Technical Innovation Cluster with [34] T. H. Kosel, ‘‘Computational techniques for stereographic projection,’’ the Autonomous University of Barcelona, where he is currently a full-time J. Mater. Sci., vol. 19, no. 12, pp. 4106–4118, Dec. 1984. Professor with the System Engineering Department. He is also active in the [35] Eurocontrol. PHARE. Accessed: Jul. 29, 2019. [Online]. Available: https:// innovation sector, contributing as the scientific advisor to the ASLOGIC www.eurocontrol.int/phare/public/subsite_homepage/homepage.html Company. [36] University of Patras. 4DCo-GC. Accessed: Jul. 29, 2019. [Online]. Avail- able: http://www.4dcogc-project.org/ [37] Autonomous University of Barcelona. AGENT. [Online]. Available: http://www.agent-aero.eu/ [38] Autonomous University of Barcelona. PARTAKE. [Online]. Available: MARKO RADANOVIC received the degree in air http://www.partake-aero.eu/s transportation engineering from the University of [39] P.-J. Du, T. Fang, H. Tang, and P.-F. Shi, ‘‘Encoding methods of spectral Belgrade, Belgrade, Serbia, the master’s degree in vector in hyperspectral romote sensing image,’’ J. Shanghai Univ., vol. 9, satellite navigation from the Politecnico di Torino, no. 1, pp. 52–57, Feb. 2005. Doi: 10.1007/s11741-005-0104-0. Torino, Italy, and the Ph.D. degree in air traffic [40] N. Schefers and J. J. R. González, P. Folch, and J. L. Munoz-Gamarra, ‘‘A constraint programming model with time uncertainty for cooperative management from the Autonomous University of flight departures,’’ Transp. Res. C, Emerg. Technol., vol. 96, pp. 170–191, Barcelona, Barcelona, Spain, where he is currently Nov. 2018. a Postdoctoral Researcher with the Department [41] M. De Berg, O. Cheong, M. Van Kreveld, and M. Overmars, ‘‘Computa- of Telecommunications and Systems Engineering. tional geometry,’’ in Algorithms Applications. Berlin, Germany: Springer, His research interests include automation in air 2008. traffic management and control, modeling and simulation of air transporta- [42] L. Euler and S. L. Hecht, Elements Algebra. Scotts Valley, CA, USA: tion systems, and air traffic safety. CreateSpace, 2015. VOLUME 7, 2019 104541