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

with its flight plan, the aircraft trajectory passes through fixed points

p

1

; p

2

; : : : ; p

n

, for which the geographical coordinates are known in

advance. The 4-D coordinates 

φ; λ; h; t are calculated between each

waypoint pair (Fig. 3).

We used pairwise conflict detection to calculate the distance

between each pair of 4-D trajectories. Where loss of separation was

detected, we registered the conflict parameters: that is, the geometric

points (GPCs) and the conflict times (TCs).

The pairwise conflict detection algorithm was described in

[27,28]. In these, a sampling time of 10 s was used. We reduced this to

5 s to improve the accuracy.

Figure 4 shows two pairwise-processed trajectories, corre-

sponding to the trajectories of aircraft 1 and 2. A cross indicates a

conflict. The dotted lines indicate the 4-D coordinates at the same

time instant.

The results indicate that over half of the operational conflicts,

which require controller deconfliction, occur when both aircraft are

in the cruise phase. Therefore, this study will focus on the en route

environment. This is to avoid the effects of other parameters, such as

distance to destination or possible climb, which mainly affect the

climb and descent phases and may mask the results obtained due to

induced complexity.

3.

Conflict Resolution Based on Historical Data

Possible conflict-resolution maneuvers performed by controllers

include 1) speed changes, i.e., temporal deviation of radar tracks vs

flight plans; 2) vertical maneuvers, i.e., vertical deviation of radar

tracks vs flight plans; and 3) two-dimensional turns, i.e., horizontal

deviation of radar tracks with respect to the flight plans. The conflict-

resolution model in this study deals with the first two maneuvers.

We identified the historical conflicts and then categorized them

according to the tactical resolution applied in each case. Equations (4)

and (5) were used to assess the adherence of the actual trajectory

flown to the updated flight plan, using radar track data. So, for each

conflict, we calculated the following:

1) We first calculated the temporal deviation (TD) of the trajectory

flown (radar track) compared to the latest updated flight plan at the

geometric point where the conflict was detected (GPC); see Fig. 5:

TD  t

GPC

FP

− t

GPC

RT

(4)

where t

GPC

FP

is the time estimated by the flight plan in the GPC; and

t

GPC

RT

is the actual time indicated by the radar track.

A temporal deviation of 0 min means that the flight passed over the

geometric point, where the conflict was detected, at the same time as

that estimated by the flight plan.

2) We then calculated the vertical deviation (VD) of the trajectory

flown (radar track) compared to the latest updated flight plan at the

time when the conflict was detected (TC); see Fig. 6;

VD  h

TC

FP

− h

TC

RT

(5)

where h

TC

FP

is the altitude estimated by the flight plan at TC; and h

TC

RT

is

the actual altitude indicated by the radar track.

A vertical deviation of 0 ft means that the flight passed over the

geometric point, where the conflict was detected, at the same altitude

as that estimated by the flight plan. Any conflict with a vertical

deviation of within 1000 ft would not be resolved vertically.

These criteria were contrasted with the experience of experts

involved in day-to-day ATC operations and found to have a valid

theoretical and empirical basis.

4.

Development of Model

This section describes the methodology used to develop the

conflict-resolution model. The model uses the large database of

conflicts and controller actions to resolve them, and it performs two

fundamental tasks: classification and clustering [29].

We classified the conflict resolutions according to the relationship

between the aircraft trajectories involved in the conflict. Although we

are dealing with a radar-controlled environment, we considered it

valid to classify the conflicts using the International Civil Aviation

Organization

’s document 4444-ATM/501 [30] criteria of “applicable

for procedural control in the en-route phase.

” Specifically, for the

purpose of application of longitudinal separation, the terms

“same

track,

” “reciprocal tracks,” and “crossing tracks” are consid-

ered (Fig. 7).

Finally, we took the tactical component of the controller conflict-

resolution strategy into account by using an unsupervised learning

method (clustering) [31,32]. The goal of clustering is to determine the

intrinsic grouping in a set of data. Thus, clustering identifies

distinctive groups/clusters in the data, based on the hypothesis that a

cluster in a data space is a contiguous region of high point

density [33].

The k-means algorithm [34–36], which is one of the most

frequently used clustering algorithms, is classified as a partitional

clustering method, presenting two distinct advantages:

1) It is easy to implement and works with any of the

standard norms.

2) It allows straightforward parallelization.

Flight Plan

4-D Trajectory

p

1

(

1

,

1

,h

1

,t

1

)

p

2

(

2, 2,

h

2,

t

2

)

p

1

p

3

p

2

p

4

p

5

p

6

5s

Fig. 3

Four-dimensional trajectory based on the flight plan.

Aircraft 1

Aircraft 2

Conflict

Fig. 4

Sample pairwise algorithm.

The flight passes over the

GPC 1 min earlier than

the time estimated by the FP

The flight passes over the

GPC 1 min later than the

time estimated by the FP

-2 min

-1 min

0 min

1 min

2 min

Temporal

deviation

Fig. 5

Temporal deviation.

The flight passes over at the

TC 1000 ft above the altitude

estimated by the FP

The flight passes over at the

TC 1000 ft below the altitude

estimated by the FP

-2,000 ft

-1,000 ft

0 ft

1,000 ft

2,000 ft

No vertical resolution

Vertical

deviation

Fig. 6

Vertical deviation.

618

CALVO-FERNÁNDEZ ET AL.

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

A drawback of the k-means algorithm is that the solution reached

often depends on the starting points. Therefore, it is possible to reach

a local minimum, where reassigning any one point to a new cluster

would increase the total sum of point-to-centroid distances when, in

fact, a better solution may exist. To avoid local minima, a parameter

called

“replicates” is used to overcome the problem.

¶

For each of the

replicates, the k-means algorithm starts from a different randomly

selected set of initial centroids. Sometimes, the algorithm finds more

than one local minimum. However, the final solution returned by k

means is the one with the lowest total sum of distances.

To determine the number of clusters, we used Sturges

’s rule

[37,38], which is a rule for determining the desirable number of

groups into which a distribution of observations should be classified.

As Sturges

’s rule (or formula) is frequently applied to histograms, it is

suitable for use with the k-means algorithm.

Sturges

’s formula [38] is derived from a binomial distribution and

implicitly assumes an approximately normal distribution:

k  1  log

2

o

(6)

where k is the number of classes (clusters); and o is the number of

observations used to build the histogram.

In the end, we produced a conflict-resolution model based on 1) the

relationship between the aircraft tracks involved in the conflict; 2) the

t

n

t

i

t

f

t

x

t’

n

=t

n

t’

x

=t

x

t’

f

=t’

f

-2 min

t’

i

=t’

i

-2 min

New FP

(Conflict-free)

Actual FP

(Conflicted)

Fig. 8

Illustration of temporal (speed) conflict resolution.

h’

CR

=h

CR

+2,000 ft

h

CR

h’

CR

=h

CR

-2,000 ft

h

CR

New FP

(Conflict-free)

Actual FP

(Conflicted)

New FP

(Conflict-free)

Actual FP

(Conflicted)

Fig. 9

Illustration of vertical conflict resolution.

Fig. 10

Possible resolutions to an individual conflict (based on the data-

driven model).

Likelihood of ATC resolution (%)

0

2

4

6

8

10

12

Additional fuel consumed (kg)

-100

-50

0

50

100

150

200

250

300

f

1

(x)

f

2

(x)

Solutions ‘out of

bounds’ due to

i

constraint

Optimal

solution

Fig. 11

ε-constraint method.

Fig. 12

Pareto frontier of an individual conflict. Intermediate solutions

as a function of

tan α.

45º

45º

90º

135º

90º

135º

Less

than 45º

More than

135º

45º to

90º

90º to

135º

tải về 0.87 Mb.

Chia sẻ với bạn bè của bạn: