Conflict-Free Trajectory Planning Based on a Data-Driven Conflict-Resolution Model

a)

b)

Vertical resolution (ft)

-6000 -5000 -4000 -3000 -2000 -1000

0

1000 2000 3000 4000 5000 6000

Vertical resolution (ft)

-6000 -5000 -4000 -3000 -2000 -1000

0

1000 2000 3000 4000 5000 6000

Vertical resolution (ft)

-6000 -5000 -4000 -3000 -2000 -1000

0

1000 2000 3000 4000 5000 6000

Vertical resolution (ft)

-6000 -5000 -4000 -3000 -2000 -1000

0

1000 2000 3000 4000 5000 6000

% Conflicts

0

5

10

15

20

25

30

% Conflicts

0

10

20

30

c)

d)

% Conflicts

0

5

10

15

20

25

% Conflicts

0

10

20

30

40

Fig. 15

Histograms. Breakdown of vertical deviations for aircraft on a) same track; b) crossing tracks (45

–90 deg); c) crossing tracks (90–135 deg); and

d) reciprocal track.

CALVO-FERNÁNDEZ ET AL.

623

Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691 

conflicts in terms of the flight phase of each aircraft involved in the

conflict.

The study focused on the en route environment because almost

two-thirds of real operational conflicts occurred when both aircraft

were in the cruise phase. By considering only those conflicts in which

both aircraft were in the cruise phase, we detected an average of 250

conflicts per day. This gave a total of 18,000 conflicts over the entire

period.

2.

Conflict Resolution Based on Historical Data

To identify the resolution applied by the controllers to each conflict

in the dataset, we defined a set of criteria to assess the adherence of the

actual trajectory flown (radar track) to the theoretical trajectory as

given by the flight plan. The criteria, set out in Eqs. (4) and (5), were

used to classify the conflict-resolution maneuvers (temporal or

vertical) performed by the controller.

The histograms in Fig. 13 give the breakdown of the temporal

and vertical deviations of the conflicts. As previously explained,

horizontal conflict-resolution actions are not included in

the model.

Any conflict with a vertical deviation of within 1000 ft will not

be resolved vertically. However, it is not easy to determine the

temporal deviation limit below which a conflict will not be solved

temporally, as this will depend on the aircraft involved in the conflict.

Thus, every temporal deviation is considered when developing the

temporal conflict-resolution model. However, when the model is

applied, if the temporal maneuver does not solve the conflict, it is not

considered a potential optimal resolution.

In Fig. 13a, a negative value of temporal resolution means that the

flight passes over the geometric point where the conflict was detected

(GPC) later than the estimated time, whereas a positive value means

that it passes over the point earlier than predicted. In Fig. 13b, a

negative value of vertical resolution means that the flight passes

below at the time when the conflict was detected (TC), whereas a

positive value means that it passes over at the TC.

3.

Development of Model

Figure 14 gives the histograms of the temporal deviation as a

function of the relationship between the trajectories of the aircraft

involved in the conflict. The most common temporal resolutions are

those with a small temporal deviation.

We applied the k-means algorithm to the histograms in order to

detect k clusters. The cluster centroids are indicated in Fig. 14,

reflecting the highest density regions.

Table 3

Breakdown of vertical deviation of conflicts as a function of relationship

between aircraft

Same track

Crossing tracks

(45

–90 deg)

Crossing tracks

(90

–135 deg)

Reciprocal track

Feet

% Conflicts

Feet

% Conflicts

Feet

% Conflicts

Feet

% Conflicts

−10;000

0.3

−11;000

0.4

−7;000

0.7

−7;000

0.2

−7;000

0.5

−9;000

0.5

−6;000

1.1

−6;000

0.4

−6;000

0.8

−7;000

0.4

−4;000

3.0

−5;000

0.8

−5;000

0.4

−6;000

0.5

−3;000

0.5

−4;000

1.6

−4;000

1.6

−5;000

1.0

−2;000

6.8

−3;000

1.1

−3;000

1.0

−4;000

2.4

−1;000

4.2

−2;000

6.0

−2;000

8.9

−3;000

1.8

1,000

2.2

−1;000

2.0

−1;000

2.8

−2;000

12.0

2,000

7.8

1,000

1.8

1,000

0.9

−1;000

6.7

4,000

0.6

2,000

11.7

2,000

9.4

1,000

1.1

6,000

0.4

3,000

0.4

4,000

1.2

2,000

5.8

13,000

0.4

4,000

1.1

6,000

0.3

4,000

0.6

14,000

0.4

6,000

0.2

0

50

100

150

200

250

300

0

1

2

3

4

5

6

1

4

8

13

19

27

36

47

63

79

102

121

147

183

261

tan ( )

Frequency (%)

Fig. 16

Breakdown of Pareto frontier slopes for all conflicts in the study.

Additional fuel (kg)

-20

-15

-10

-5

0

5

x 10

3

tan( )

1

tan( )

4

tan( )

8

tan( )

13

tan( )

19

tan( )

27

tan( )

36

tan( )

47

tan( )

63

tan( )

79

tan( )

102

tan( )

121

tan( )

147

tan( )

183

Maximum

likelihood

Minimum

fuel

tan( )

261

Fig. 17

Daily additional fuel consumed as a function of different criteria.

624

CALVO-FERNÁNDEZ ET AL.

Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691 

Table 2 gives the breakdown of temporal deviation of conflicts as a

function of the relationship between the trajectories of the aircraft

involved in the conflict. Thus, the model gives a discrete number of

temporal resolutions with the corresponding likelihood based on

actual controller performance. The discrete number of temporal

resolutions is equal to the number of centroids.

Figure 15 gives the vertical deviation as a function of the relationship

between the trajectories of the aircraft involved in the conflict.

We applied the k-means algorithm to the histograms and, once

again, the centroids are shown. The vertical conflict-resolution model

(Table 3) gives a discrete number of vertical resolutions with the

corresponding likelihood of their being implemented.

This model was specifically developed for use in the operational

scenario described. It would need to be tested further to ensure its

applicability to different environments, with similar conflict-

resolution protocols.

B.

Multiobjective Optimization of Proposed Solutions

The conflict-resolution model was applied to the conflicts detected

in the strategic phase (over 48 randomly selected days), resulting in a

set of potential resolutions per conflict. We used the

ε-constraint

method to detect the Pareto frontier for each particular conflict.

We then populated a number of optimal solutions along the

Pareto frontiers of each conflict to find the global optimal solution

for all the conflicts. As mentioned in Sec. II.E, there are

intermediate solutions between the solutions that satisfy the

requirement for minimum fuel and maximum likelihood of ATC

resolution. We used Pareto frontiers slopes (tan

α) to populate the

intermediate solutions.

Figure 16 shows the histogram with the Pareto frontiers slopes for

all conflicts. This enabled us to choose the values of tan

α used in this

study to populate a number of intermediate solutions along the Pareto

frontiers.

The next step was to apply the k-means algorithm to the histogram.

The centroids detected were used as the values of tan

α to populate a

number of intermediate solutions along the Pareto frontiers of each

conflict.

Then, we applied minimum fuel consumption, maximum

likelihood of ATC resolution, and the intermediate criteria by setting

the values of tan

α. The fits of the results after applying each criterion

are represented in Figs. 17 and 18.

Figure 17 shows the daily additional fuel consumed after applying

the aforementioned criteria to solve the conflicts.

The continental Spain FIR is divided into a number of sectors, and

each one is assigned to an active control working position. To analyze

the fit of the likelihood of ATC resolution, we calculated the

occupancy (number of aircraft) of each sector. This was done using

time intervals of 5 min.

We also calculated the occupancy of the most congested sector for

each interval and each criterion. Using optimal flow management, we

could reduce the occupancy of the most congested sectors, thereby

reducing congestion, and consequently the controller

’s workload.

By incorporating efficient ATC practices to the model, it is safe to

assume that the greater the likelihood of ATC resolution, the more

homogeneous the flow distribution.

Figure 18 gives the percentage of intervals in which the most

congested sector (for each criterion) has a greater occupancy than the

most congested sector when the criterion is the maximum likelihood

of ATC resolution. From the figure, it is clear that, when the criterion

is closer to the maximum likelihood of ATC resolution, the number of

congested sectors is reduced, as is the controller

’s workload.

By converting the quantities used in both cases to a common unit of

measure, we can obtain the overall optimal solution. For example, in

Fig. 17, the kilograms of additional fuel consumed are easily

converted to monetary units. Similarly, in Fig. 18, we may be able to

assign some financial cost to or benefit from an increase or decrease

in congestion. The resulting conflict-free plan would be the global

optimal solution: in other words, the one that best balances the needs

of all the actors in the ATM system.

IV.

Conclusions

This study proposes a methodology for conflict-free planning

using a data-driven approach. The model is built with 72 days of

operational data from the continental Spain flight information

region. This contained information on the conflict-resolution

actions, in the tactical phase of more than 300,000 flights, taken by

air traffic controllers. The methodology is consistent with a

reference business trajectory scenario in which conflict-free planning

is addressed.

This methodology is divided into three processes: the first process

develops the data-driven conflict-resolution model. This is applied, in

the strategic phase, to a specific traffic forecast. Finally, we identify

the optimal solution using a multiobjective optimization.

The data-driven air traffic control model allows incorporation of

ATC expertise into the conflict-resolution models. This avoids the

need for specific conflict-resolution algorithms. A benefit of this

approach is that the data-driven methodology is able to incorporate

new operational procedures, due to the fact that they are intrinsically

contained within the operational data used to generate or update

the model.

The model balances the (sometimes competing) needs of the

different actors in the ATM system. In particular, it attempts to

provide more efficient air traffic flow management to the benefit of

the air navigation service providers. The main benefit to the ANSPs is

the reduction in the number of conflicts during the strategic phase. By

applying the conflict-resolution model in the strategic phase, an 85%

reduction in conflicts can be achieved as compared with the original

flight plan. In the en route sectors of the continental Spain FIR,

workload studies have shown that 15

–30% of control actions were

due to conflict resolution. It is, therefore, safe to say that, by using a

plan in which conflicts are considerably reduced, an increase in

capacity can be expected. In other words, there will be fewer tactical

resolution actions and an increase in less labor-intensive activities,

such as monitoring.

The model also takes the airlines

’ perspective into account by

permitting tradeoffs between competing criteria via a multi-

objective

optimization

process.

Specifically,

the

airlines

’

perspective is taken into account through the use of the minimum

fuel consumption criterion when resolving conflicts. By focusing

on minimum fuel consumption rather than trying to maximize the

% Intervals

0

2

4

6

8

1 additional aircraft

2 additional aircraft

3 additional aircraft

tan( )

1

tan( )

4

tan( )

8

tan( )

13

tan( )

19

tan( )

27

tan( )

36

tan( )

47

tan( )

63

tan( )

79

tan( )

102

tan( )

121

tan( )

147

tan( )

183

Maximum

likelihood

Minimum

fuel

tan( )

261

Fig. 18

Breakdown of intervals with additional aircraft in the most congested sectors as a function of different criteria compared with the criterion of the

maximum likelihood of ATC resolution.

CALVO-FERNÁNDEZ ET AL.

625

Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691 

likelihood of ATC resolution, it is possible to achieve a 0.35%

reduction in the fuel consumed, which equates to a savings of more

than 20 ton (ton refers metric tons) of fuel each day within the

continental Spain FIR cruise phase.

The incorporation of multiobjective criteria into the planning

phase is a significant step forward in the implementation of

trajectory-based operations and extended ATC planning within a

reference business trajectory/shared business trajectory scenario.

Acknowledgment

All the calculations carried out in this study are available from the

authors on request by sending an email to the addresses provided.

References

[1] SESAR Joint Undertaking,

“European ATM Master Plan: The Roadmap

for Delivering High Performing Aviation for Europe: Executive View:

Edition 2015,

” Bruxelles, Feb. 2016.

doi:10.2829/240873

[2] Isaacson, D., and Robinson, J.,

“A Knowledge-Based Conflict

Resolution Algorithm for Terminal Area Air Traffic Control Advisory

Generation,

” AIAA Guidance, Navigation, and Control Conference and

Exhibit, Guidance, Navigation, and Control and Co-Located

Conferences, AIAA Paper 2001-4116, 2001.

doi:10.2514/6.2001-4116

[3] SESAR Joint Undertaking,

“P07.06.01-D37 Step 2 V1 Network

Performance Monitoring & Management Report,

” Bruxelles, 2014.

[4] Sesar Consortium,

“SESAR Concept of Operations,” Document

No. DLT-0612-222-01-00, Bruxelles, July 2007.

[5] Arnaldo, R., Sáez, F. J., and García, E.,

“Towards Higher Levels of

Automation in ATM,

” 28th International Congress of the Aeronautical

Sciences, ICAS Paper 2012-10.1.1, Sept. 2012.

[6] Kuchar, J. K., and Yang, L. C.,

“A Review of Conflict Detection and

Resolution Modeling Methods,

” IEEE Transactions on Intelligent

Transportation Systems, Vol. 1, No. 4, Dec. 2000, pp. 179

–189.

doi:10.1109/6979.898217

[7] Xiangmin, G., Xuejun, Z., Dong, H., Yanbo, Z., Ji, L., and Jing, S.,

“A

Strategic Flight Conflict Avoidance Approach Based on a Memetic

Algorithm,

” Chinese Journal of Aeronautics, Vol. 27, No. 1, Feb. 2014,

pp. 93

–101.

doi:10.1016/j.cja.2013.12.002

[8] Valenzuela, A., and Rivas, D.,

“Conflict Resolution in Converging Air

Traffic Using Trajectory Patterns,

” Journal of Guidance, Control, and

Dynamics, Vol. 34, No. 4, 2011, pp. 1172

–1189.

doi:10.2514/1.50751

[9] Matsuno, Y., Tsuchiya, T., and Matayoshi, N.,

“Near-Optimal Control

for Aircraft Conflict Resolution in the Presence of Uncertainty,

” Journal

of Guidance, Control, and Dynamics, Vol. 39, No. 2, 2016, pp. 326

–338.

doi:10.2514/1.G001227

[10] Durand, N., and Barnier, N.,

“Does ATM Need Centralized

Coordination? Autonomous Conflict Resolution Analysis in a

Constrained Speed Environment,

” Air Traffic Control Quarterly,

Vol. 23, No. 4, 2015, pp. 325

–346.

[11] Frazzoli, E., Mao, Z.-H., Oh, J.-H., and Feron, E.,

“Resolution of

Conflicts Involving Many Aircraft via Semidefinite Programming,

”

Journal of Guidance, Control, and Dynamics, Vol. 24, No. 1, 2001,

pp. 79

–86.

doi:10.2514/2.4678

[12] Clements, J. C.,

“Optimal Simultaneous Pairwise Conflict Resolution

Maneuvers in Air Traffic Management,

” Journal of Guidance, Control,

and Dynamics, Vol. 25, No. 4, 2002, pp. 815

–818.

doi:10.2514/2.4950

[13] Raghunathan, A. U., Gopal, V., Subramanian, D., Biegler, L. T., and

Samad, T.,

“Dynamic Optimization Strategies for Three-Dimensional

Conflict Resolution of Multiple Aircraft,

” Journal of Guidance,

Control, and Dynamics, Vol. 27, No. 4, 2004, pp. 586

–594.

doi:10.2514/1.11168

[14] Hu, J., Prandini, M., and Sastry, S.,

“Optimal Coordinated Maneuvers

for Three-Dimensional Aircraft Conflict Resolution,

” Journal of

Guidance, Control, and Dynamics, Vol. 25, No. 5, 2002, pp. 888

–900.

doi:10.2514/2.4982

[15] Green, S., and Grace, M.,

“Conflict-Free Planning for en Route Spacing

—A Concept for Integrating Conflict Probe and Miles-in-Trail,”

Guidance, Navigation, and Control Conference and Exhibit, Guidance,

Navigation, and Control and Co-Located Conferences, AIAA Paper

1999-3988, 1999.

doi:10.2514/6.1999-3988

[16] Flicker, R., and Fricke, M.,

“Improvement on the Acceptance of a

Conflict Resolution System by Air Traffic Controllers,

” The 6th USA/

Europe Air Traffic Management Research and Development Seminar,

EUROCONTROL/FAA Paper 27, June 2005.

[17] Huang, H., and Tomlin, C.,

“A Network-Based Approach to En-Route

Sector Aircraft Trajectory Planning,

” AIAA Guidance, Navigation, and

Control Conference, Guidance, Navigation, and Control and Co-

Located Conferences, AIAA Paper 2009-6169, 2009.

doi:10.2514/6.2009-6169

[18] Yokoyama, N.,

“Decentralized Model Predictive Control for

Planning Three-Dimensional Conflict-Free Trajectories,

” AIAA

Guidance, Navigation, and Control Conference, AIAA Paper 2014-

0970, 2014.

doi:10.2514/6.2014-0970

[19] Marzuoli, A., Gariel, M., Vela, A., and Feron, E.,

“Data-Based Modeling

and Optimization of En Route Traffic,

” Journal of Guidance, Control,

and Dynamics, Vol. 37, No. 6, 2014, pp. 1930

–1945.

doi:10.2514/1.G000010

[20] Salaun, E., Gariel, M., Vela, A. E., and Feron, E.,

“Aircraft Proximity

Maps Based on Data-Driven Flow Modeling,

” Journal of Guidance,

Control, and Dynamics, Vol. 35, No. 2, 2012, pp. 563

–577.

doi:10.2514/1.53859

[21] Solomatine, D. P., and Ostfeld, A.,

“Data-Driven Modelling: Some Past

Experiences and New Approaches,

” Journal of Hydrodynamics,

Vol. 10, No. 1, 2008, pp. 3

–22.

[22] Liu, J., and Han, D.,

“On Selection of the Optimal Data Time Interval for

Real-Time Hydrological Forecasting,

” Hydrology and Earth System

Sciences, Vol. 17, 2013, pp. 3639

–3659.

doi:10.5194/hess-17-3639-2013

[23] Batterson, J. G., and Klein, V.,

“Partitioning of Flight Data for

Aerodynamic Modeling of Aircraft at High Angles of Attack,

” Journal

of Aircraft, Vol. 26, No. 4, 1989, pp. 334

–339.

doi:10.2514/3.45765

[24] Dong, J., Wang, G., and Li, D.,

“Optimal Pilot Interval Design for the

Dedicated Pilot Channel,

” IEEE Pacific Rim Conference on

Communications, Computers and Signal Processing (PACRIM 2003),

Vol. 2, IEEE, Piscataway, NJ, Aug. 2003, pp. 635

–637.

[25] Ivanescu, D.,

“Conflict Detection Tools Impact on Controller Taskload

—Fast Time Study,” EUROCONTROL Experimental Centre, EEC

Note No. 010/10, Bruxelles, June 2010.

[26] Durand, N., and Gotteland, J. B.,

“Genetic Algorithms Applied to Air

Traffic Management,

” Metaheuristics for Hard Optimization, Springer,

New York, 2006, pp. 277

–306.

[27] Barnier, N., and Allignol, C.,

“4-D—Trajectory Deconfliction Through

Departure Time Adjustment,

” The 8th USA/Europe Air Traffic

Management Research and Development Seminar, EUROCONTROL/

FAA Paper 143, July 2009.

[28] Isaacson, D. R., and Erzberger, H.,

“Design of a Conflict Detection

Algorithm for the Center/TRACON Automation System,

” AIAA/IEEE

Proceedings 16th Digital Avionics Systems Conference, Vol. 2,

Oct. 1997, pp. 9.3-1

–9.3-9.

[29] Maimon, O., and Rokach, L., Data Mining and Knowledge Discovery

Handbook, Springer, New York, 2010, pp. 269

–270.

[30]

“Air Traffic Management,” 15th ed., International Civil Aviation

Organization Doc. 4444-ATM/501, Montreal 2007.

[31] Berkhin, P.,

“A Survey of Clustering Data Mining Techniques,” edited

by

Kogan,

J.,

Nicholas,

C.,

and

Teboulle,

M.,

Grouping

Multidimensional Data, Springer, New York, 2009, pp. 25

–71.

[32] Li, L., Das, S., Hansman, R. J., Palacios, R., and Srivastava, A. N.,

“Analysis of Flight Data Using Clustering Techniques for Detecting

Abnormal Operations,

” Journal of Aerospace Information Systems,

Vol. 12, No. 9, 2015, pp. 587

–598.

doi:10.2514/1.I010329

[33] Sammut, C., and Webb, G. I., Encyclopedia of Machine Learning,

Springer, New York, 2010, pp. 270

–273.

[34] Nirmala, A. M., and Saravanan, S.,

“A Study on Clustering Techniques

on Matlab,

” International Journal of Science and Research, Vol. 3,

No. 11, Nov. 2014, pp. 1497

–1502.

[35] Rizvi, F.,

“Reducing Earth Topography Resolution for SMAP Mission

Ground Tracks Using K-Means Clustering,

” AIAA Infotech@Aerospace

(I@A) Conference, Guidance, Navigation, and Control and Co-Located

Conferences, AIAA Paper 2013-4823, 2013.

doi:10.2514/6.2013-4823

[36] He, Z., Xu, X., and Deng, S.,

“Squeezer. An Efficient Algorithm for

Clustering Categorical Data,

” Journal of Computer Science and

Technology, Vol. 17, No. 5, 2002, pp. 611

–624.

doi:10.1007/BF02948829

[37] Hyndman, R. J.,

“The Problem with Sturges Rule for Constructing

Histograms,

” Monash Univ., Australia, Jan. 1995.

626

CALVO-FERNÁNDEZ ET AL.

Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691 

[38] Sturges, H.,

“The Choice of a Class-Interval,” Journal of American

Statistical Association, Vol. 21, No. 153, 1926, pp. 65

–66.

doi:10.1080/01621459.1926.10502161

[39] Nuic, A.,

“User Manual for the Base of Aircraft Data (BADA),” Rev. 3.6,

EUROCONTROL Experimental Centre, EEC Note No. 10/04,

Bruxelles, July 2004.

[40] Doush, I. A., and Bataineh, M. Q.,

“Hybridized NaGa-II and MOEA/D

with Harmony Search Algorithm to Solve Multi-Objective Optimization

Problems,

” ICONIP 2015, Part I, LNCS 9489, edited by Arik, S., et al.,

Springer International Publ., Switzerland, pp. 606

–614.

[41] Marceau, G., and Schoenauer, M.,

“Strategic Planning in Air Traffic

Control as a Multi-Objective Stochastic Optimization Problem,

” The

10th USA/Europe Air Traffic Management Research and Development

Seminar, EUROCONTROL/FAA Paper 315, June 2013.

[42] Devi, S., and Jagadev, A. K.,

“Comparison of Various Approaches in

Multi-Objective Particle Swarm Optimization (MOPSO): Empirical

Study. Multi-Swarm Intelligence,

” Multi-Objective Swarm Intelligence,

Springer, New York, 2015, pp. 75

–103.

[43] Van Veldhuizen, D. A., and Lamont, G. B.,

“Multiobjective

Evolutionary Algorithm Research: A History and Analysis,

” Dept. of

Electrical and Computer Engineering, Air Force Inst. of Technology

TR-98-03, 1998.

[44] Messac, A., and Mattson, C. A.,

“Normal Constraint Method with

Guarantee of Even Representation of Complete Pareto Frontier,

” AIAA

Journal, Vol. 42, No. 10, 2004, pp. 2101

–2111.

doi:10.2514/1.8977

[45] Hazelrigg, G. A., Systems Engineering: An Approach to Information-

Based Design, Prentice

–Hall, Upper Saddle River, NJ, 1996, p. 10.

CALVO-FERNÁNDEZ ET AL.

627

Downloaded by UNIV. OF ARIZONA on March 14, 2017 | http://arc.aiaa.org | DOI: 10.2514/1.G000691