ENRI Int. Workshop on ATM/CNS. Tokyo, Japan (EIWAC2010)[EN-023] Aircraft Conflict Resolution by Genetic Algorithm
and B-Spline Approximation+

D. Delahaye ∗ C. Peyronne ∗∗ M. Mongeau ∗∗∗ S. Puechmorel ∗∗∗∗∗

Applied Math Lab
Ecole Nationale Aviation Civile(ENAC)
Toulouse, France
delahaye@recherche.enac.fr∗∗

Applied Math Lab
Ecole Nationale Aviation Civile(ENAC)
Toulouse, France
clement.peyronne@capgemini.com∗∗∗

IMT (UPS) UMR 5219
F-31062 TOULOUSE (FRANCE)
marcel.mongeau@math.univ-toulouse.fr∗∗∗∗

Applied Math Lab
Ecole Nationale Aviation Civile(ENAC)
Toulouse, France
puechmor@recherche.enac.fr
Abstract Conflict resolution has always been a sensitive matter in air-traffic management. Current European projects
aim partial or total automation of air traffic control to deal with the constant growth of air traffic. Technological advanceson flight management system allows us to consider an automatic conflict resolution using continuous trajectories. In
this paper, we present a new methodology that, first, relies on B-splines to model trajectories, secondly models air-traffic
conflict resolution as an optimization problem whose decision variables are the spline control points. Finally, we use
genetic algorithms to tackle this optimization problem in order to generate optimal conflict-free situations.
Keywords Air traffic conflict resolution, genetic algorithm, B-Spline approximation

1

INTRODUCTION

traffic management (ATM) will have to deal with thisoverload while ensuring at least equivalent standardsof safety [1]. The SESAR European project aims at
finding solutions to this problem by providing a decision support to air traffic controllers in order to decrease their workload. Considering the technological advances on the aircraft flight management system(FMS), we will explore in this paper the possibility ofa full automation generating continuous trajectories
that new FMS can follow.

From the beginning, the most critical point of air
traffic control was to ensure safety separation between
airplanes. To achieve this goal a safety standard separation distance has been defined: 5 Nm (Nautical
miles) horizontally and 1000 feets vertically. Air traffic controllers are responsible for ensuring the respectof these separation rules.
1.1

Context

Air traffic being constantly increasing, controllers
in charge of an aviation sector must handle more andmore flights. Up to now, decreasing the size of aviation sectors could compensate the growth of traffic
but we are reaching the point where a decrease of thesize of sectors is no longer efficient.
Nowadays, air traffic management has already usedevery available ressource to increase airspace capacity. However, from now to 2020, air traffic is expected
to be multiplied by two or three. Consequently, air

1.2

Previous Related Works

Eversince 1981 and the famous air traffic US controller strike (where more then 6000 controllers were
fired by Ronald Reagan), numerous projects of air
traffic control (ATC) automation have been led. However, no definitive results have been found. Two kindsof method have become predominant for their goodresults : genetic algorithms (GA) [3] and navigation
functions [8]. By the past, two kinds of method have
171

D. Delahaye, C. Peyronne, M. Mongeau, S. Puechmorel

charges, its destination. As a result, each airplane is
attracted to its destination while being repulsed by obstacles which enables to the automatic generation of
conflict-free trajectories (see figure 1).
It has been demonstrated that navigation function
methods ensure collision avoidance and connection
between departure and destination. The major drawback of this method is that the obtained solution does
not respect the ATM constraints such as limited speed,
or trajectory smoothness. Evenmore, they can lead tomajor delays and overcosts as they tolerate any deviation from the business trajectories (BT : the straightline between the departure and arrival points).
In this paper, we present a new methodology that,first, relies on B-splines to model trajectories, secondly models air-traffic conflict resolution as an optimization problem whose decision variables are thespline control points. Finally, we use genetic algorithms to tackle this optimization problem in order togenerate optimal conflict-free situations.
We present our trajectory model in Section 2. Section 3 presents the optimization method we chose tosolve our optimization problem: genetic algorithms(GA). We detail in Section 4 the objective function(conflict detection) of our optimization problem. Numerical results are presented in Section 5. We draw
conclusions in Section 6.

Figure 2 Control points, its convex envelope, control
polygon and resulting B-spline

Figure 1 Principle of navigation functions between
two aircrafts (left), between an aircraft and an obstacle (right)

2

TRAJECTORY MODEL

In this section, we will describe our B-spline trajectory model. We choose a smooth trajectory model
fitted to future FMS abilities. In order to obtain FMS
flyable trajectories, we use B-splines, the mathematical tool which provides the most interesting properties
for our concerns. We shall first present the B-spline
concept and then we shall describe how we use it in
our model.
B-spline was primarily introduced to find a curveinterpolating a set of points of R2 called control points.
It was later extended to approximation, thereby avoiding the undesirable oscillation inherent to interpolation. In our study, we shall focus on this use of splines
to approximate a set of control points. The control
polygon, the piecewise linear curve linking the control points, completely defines the curve [7], [5]. The
B-spline curve always remains in the convex envelopeof the control points (see figure 2).
Basically, B-splines are parameterized curves generalizing the Bezier curve concept. It is an efficientapproximation tool which is constructed from polynomial pieces joined at certain parameter’s values calledknots, stored in a knot vector. In a very simplified
way, if we consider a set of control points (Xi , Yi ) =Pi ∈ R2 (i = 0, 1, ..., n), and a parameter u, we candefine the B-spline as follows :become predominant in automatic air traffic conflict
resolution for their good results : genetic algorithms(GA) [3] and navigation functions [8]. Genetic algorithms are part of what is known as natural computation or evolutionary methods. This optimization
method is based on the evolution theory and uses concepts such as mutation, crossover and, of course, selection. Each possible solution of our optimization
problem is encoded as a chromosome via a specificencoding (for example, number and duration of simple maneuvers). The algorithm creates randomly afirst chromosome population. Each chromosome ability to solve the problem (fitness) is then evaluated.
The best individuals (according to their fitness) areselected and mutation, crossover are applied to obtaina new population of chromosome (next generation).
The user chooses the necessary generation number
for the algorithm to converge (this choice is usually
done empirically). The obtained trajectories’ velocity
stays within acceptable bounded range with respect
to ATM operational constraints. However, these techniques have not been tested yet with curved trajectories.
Navigation functions use a different representation. Indeed, the airspace is considered as a potential field, and airplanes like particles navigating in it.
Naturally, negative charges represent obstacles to the
airplane (other aircrafts, congested areas) and positiveC(u) = (σ x (u), σy (u)), u ∈ [a, b]

2

72

ENRI Int. Workshop on ATM/CNS. Tokyo, Japan (EIWAC2010)very efficient tool for curve approximation in terms ofboth approximation quality and computational time.
Moreover, B-splines feature interesting properties suchas C2 -continuity (crucial for modeling smooth aircraft
trajectories), robustness and flexibility (if one control
point is displaced, only a small part of the curve will
be affected). The last good point in favor of B-splines
is its compatibility with GA : the curve is completely
determined by few control points only, which will be
the optimization parameters of the GA. In our study,
we use a fixed maximal number of control points between the departure and the arrival points.

Figure 3 In bold, we have the B-splines functions used
to calculate the B-spline for u ∈ [1, 2] (the only ones
with nonzeroes values on this interval)Control points,
its convex envelope, control polygon and resulting Bspline

3

When several aircraft are involved in a conflict,the conflict resolution problem has been shown to be
NP-hard [3]. Moreover, the optimization variables
being the B-splines control-point location, we shallsee that our objective function (4) is not differentiablewith respect to these variables. Consequently, we must
rely on black box (direct) optimization methods to address our problem. In this paper, we choose to use
a stochastic global optimization method, genetic algorithms, to guide the control-point location. As we
mentioned in the previous part, GA seem to be appropriate with B-splines. In this section, we explain
briefly GA theory and then we shall detail how weadapt the different operators (selection, mutation andcrossover) to our air traffic conflict resolution problem.

where σ x (u) and σy (u) are the B-splines approximations of the couples (i, Xi )i=0:n and (i, Yi )i=0:n foru ∈ [a, b] . We choose to rely on B-splines modelingtrajectories because it is a very efficient tool for curve
approximation in terms of both approximation quality
and computational time. Moreover, B-splines featureinteresting properties such as C2 -continuity (crucial
for modeling smooth aircraft trajectories, robustness
and flexibility and the use flexibility (if one control
point is displaced, only a small part of the curve will
be affected).
Theoretically, the B-spline is calculated using the
B-spline function basis. To build it, we use the interpolation natural cubic spline of the following points:(−2, 0),(−1, 16 ), (0, 32 ), (1, 61 ), (2, 0), and its translation.We
obtain the basis represented in Figure 3.
Theoritically, the curve is calculated by multiplying the B-splines basis functions by the control points
coordinates. For σ x :σ x (u) =n+1
X

Xi Bi (u)

3.1

(1)

However, in practice, Bi construction is made byrecurrence. Consequently, we used a more numerically convenient way to calculate the B-spline values
only using control points values. The B-spline and its
derivative values at knot ui are defined by :−Xi−1
σ0i = Xi+12hX
i+2 −3Xi+1 +3Xi −Xi−1
σ000
i =
h3

Basis of Genetic Algorithms

Evolutionary algorithms use techniques inspiredby evolutionary biology such as inheritance, mutation, natural selection, and recombination (or crossover)to find approximate solutions to optimization problems [4], [6]. An individual, or solution to the problem to be solved, is represented by a list of parameters, called chromosome or genome. Initially several
such individuals are randomly generated to form thefirst initial population (POP(k) with k = 0 on Figure 4).
Then each individual is evaluated, and a value offitness is returned by a fitness function (generally, theobjective function of our optimization problem). Thisinitial population undergoes a selection process which
identifies the most adapted individuals. The selection
process which has been used in our experiments is adeterministic (λ, µ)-tournament selection. This selection begins by randomly selecting λ individuals fromthe current population POP(k) and keeps the µ bests(λ > µ). These two steps are repeated until a newintermediate population (POPi ) is completed. Following selection, one of the three following operators
is applied : nothing, crossover, and mutation. The
associated probability of application are respectively(1 − pc − pm )), pc and pm . Crossover results in twoi=−1

σi = Xi+1 +4X6 i +Xi−1
i +Xi−1σ00i = Xi+1 −2X
h2

OPTIMIZATION METHOD(2)Therefore, by using Taylor series, we obtain the
B-spline value for all u ∈ [ui ,i+1 ] :
σ00xi
σ000
x
+ (u − ui ) i ))2
6
(3)
We have analogous formulae for σy . We choose to
rely on B-spline modeling trajectories because it is a
σ x (u) = σ xi + (u − ui )(σ0xi + (u − ui )(373

D. Delahaye, C. Peyronne, M. Mongeau, S. Puechmorel

Aircraft List

Control Point List

3.2

In this section we detail the link between our modeling method and genetic algorithms. Indeed, our optimization method is using B-splines to calculate theaircraft trajectories in order to determine each individuals fitness. To define this interaction, we first define
an encoding.
A chromosome will represent the trajectories of
N aircrafts using a matrix of N × Nc where Nc is the
maximal number of control points we wish to consider. For example, the case where N = 3 airplanes
and Nc = 4 we encode the trajectories as shown on
figure 5.
Obviously, departure and arrival points are not encoded in the chromosome as they are not meant to
move, they are not optimization variable.
Let us now define precisely how we specify thecontrol points Pij . We want a compromise between
allowing the trajectory to deviate freely (in any directions) from the business trajectory (BT) and staying
as close as possible from it. For that purpose, we define a fixed width band (Dmax ), depending on the BT
length (Dtot ), around the BT trajectory where the control points are allowed to lie.
A matter for the control point location is that, if
there are all gathered in the same region, it can create
oscillations on the resultant trajectory. Consequently,
we distribute uniformly the control points along theBT.
To summarize, a control point can be defined by asingle parameter representing a bandwidth percentaged% ).
(± Dmax
Moreover, it is desirable to be able to have a different number of control points for a given chromosome.
In order to satisfy this goal, we used a convention:
percentage are generated within [−200%; 200%], if
the percentage is between −100% and 100%, then wecreate a control point, if it belongs to [−200%; −100%[∪[100%; 200%], we do not. Consequently, our chromosome is a N × Nc matrix of percentage. Several
cases are presented in Figure 6 and 7.

1
2
3

Figure 5 Chromosome coding. In such exemple 3 aircraft are involved in a conflict and for each of them thecoding contains le list of the control points which define the associated trajectory (here 4 control points).

Figure 6 Chromosome encoding and corresponding
B-spline with one percentage exceeding 100%POP(k)
Tournament
SelectionλµNothing1−(Pm+Pc)

CrossoverPc

Chromosome Encoding and Fitness Calculus

POP i

MutationPm

POP(k+1)

Figure 4 Genetic algorithm with tournament selection. The first step consists in the selection of the bestindividuals from population POP(k). Afterwards, recombination operators are applied in order to produce
the POP(k + 1) population.

3.3

Crossover and Mutation

Let us now describe how we adapted the genetic
operators we use in our GA.

new child chromosomes, which are added to the next
generation population. The chromosomes of the parents are mixed during crossover. These processes ultimately result in the next generation population ofchromosomes (POP(k+1) on Figure 2) that is different from the initial generation. This generational process is repeated until a termination condition has beenreached. The next section presents the application ofthis algorithm to our specific problem.

Figure 7 Another chromosome encoding and its corresponding B-spline with both percentages within[−100%, −100%]
4

74

ENRI Int. Workshop on ATM/CNS. Tokyo, Japan (EIWAC2010)

3.3.1

Slicing crossover

The crossover operator aims at finding better solutions by mixing two good individuals of the previous generation. Therefore, we decide to keep trajectory consistencies by inverting only complete trajectories using a slicing crossover (we do not separate
control points belonging to the same trajectory). Accordingly, the crossover consists in picking a plane
number randomly and inverting the parent trajectories corresponding to the next aircrafts. An example
is given in Figure 8 :MUTATION

3.3.2
Figure 9 Initial and mutated chromosome. In this example the fourth control point has been change on thesecond aircraft trajectory.

Mutation

The mutation operator aims at diversifying the genes
in the population in order to explore as much as possible the problem space. Thus, mutation consists inchoosing randomly one control point in the chromosome and to assign to it a new random number (usinga uniform distribution) in the interval [−200%; 200%].
(see Figure 9).

4

OBJECTIVE FUNCTION :CONFLICT DETECTIONMETHOD

In order to evaluate each chromosome fitness, we
decode it into N trajectory curves (one per aircraft)and evaluate two quantities. First, how many conflicts
the situation engenders and secondly what is the total
extra distance induced with respect to the BT. To calculate these quantities, we discretize the airspace into
square cells of size half the standard separation (notedd). Our conflict detection is performed in two steps :• First, for each airplane, we store the grid’s cells
through which the aircraft flies, the aircraft number (its label), the entry and exit times in andout each of the stored cell,

Figure 10 Conflict detection basic illustration

Parent 1

Parent 2• Then, we select each stored cell and we check
whether any other airplane goes through any ofthe eight neighboring cells for other airplanes.
If there are such airplanes, we check the timeto see whether there is a conflict between these
two airplanes. If so, we calculate the conflict
duration.

CROSSOVER

Child 1

An example of a conflict detection with two airplanes is given in Figure 10. The circle represents theapproximate conflict zone, the bold cells are the cells
where spatial conflict is detected and where time conflict must be checked. d = S ep standard2
Our conflict detection procedure send back the chromosome fitness to the GA. Here is the formula we use
to calculate the fitness:

Child2

Figure 8 Parent and children chromosomes. In thisexample, the third aircraft trajectory has been exchanged between chromosomes.

f (X) = −(CN + (

N
X
NRi
i=1

5

75

BT i

− N))

(4)

D. Delahaye, C. Peyronne, M. Mongeau, S. Puechmorel

the number of conflict and the route lengthening, thebetter is the chromosome.

5

RESULTS AND PERSPECTIVESIn this section, we present several results we obtained using our methodology. First, we test our methodon the roundabout test problem which is a very common test on automatic conflict-detection method. It
consists in making a certain number of planes fly tothe diametrically opposed point at a common speed(each point on the circle has an outgoing and an incoming trajectory).
A diagram of the situation is shown in Figure 11
10 (each point on the circle has an outgoing and an
incoming trajectory) :We choose to fly N = 16 aircrafts for results’readability) equidistributed on a circle of 100Nm(=
185200m) radius To address this conflict resolution,
we use the following parameters :Figure 12 The roundabout configuration after resolution• Number of generation : 100• Size of the population : 500• Mutation probability : pm = 0.3• Crossover probability : pc = 0.6
Figure 13 The fitness evolution with respect the generation• Maximal number of control points : Nc = 2
To compute the conflict resolution, we used a 2.53GHzIntel(R) Core(TM)2 Duo on a Windows Vista Operating System and we coded in Java. The obtained
conflict-free situation is presented in meter-scale (1Nm =1852m) in Figure 12. This whole resolution computation required approximately 4 minutes.
The fitness’ evolution with respect to generations
is shown in Figure 13. The fitness is meant to increase to 0 as formula (4) shows. Moreover, when
the fitness is in [−1, 0] the situation is conflict-free.
Consequently, the algorithm stops only when the bestindividual fitness is in [−1, 0].
Although one can easily solve intuitively this academic problem due to its symmetry, our automatic
implementation does not exploit any symmetry here.
This result shows that our methodology is promisingas the obtained conflict resolution is consistent withexperts’ experience.
We also test our methodology on a more realistic
operational problem where N = 15 aircrafts are involved in a fuzzy convergence. In this situation, foreach aircraft, we have its departure point, its heading and its speed. To calculate the arrival points, we
make the 15 aircrafts fly for one hour at a constant
speed, on a straight line following the initial direction(heading). We present the conflict-free situations ouralgorithm obtains is displayed in Figure 14.
We can see on Figure 15 that on an operational
application, our method converges far more rapidly in

Figure 11 The 16-aircraft roundabout configuration

where CN is the number of conflict, NRi the lengthof the new route calculated by the algorithm for theaircraft i, while BT i the length of the business trajectory (straight line from the departure to the arrival
point) and N the number of aircraft. High fitness corresponds to good individuals. Indeed, the lower are

676

ENRI Int. Workshop on ATM/CNS. Tokyo, Japan (EIWAC2010)as proper optimization variables). Furthermore, weplan to exploit our B-spline model of trajectory to address the conflict resolution problem with deterministic derivative-free optimization methods [2]. Indeed,
despite the local aspect of these methods, they canalso be adapted to global optimization.

References[1] J. Alliot and D. Colin de Verdière, L’ATM : 20 ans
d’efforts et perspectives, Vers l’automatisation duvol et de sa gestion, 2003.

Figure 14 The operational problem after resolution[2] A. Conn, K. Scheinberg, and L. Vicente, Introduction to derivative-free optimization, 2009.
[3] N. Durand, Algorithmes génétiques et autres outils d’optimisation appliqués à la gestion du traficaérien, Ph.D. thesis, CENA, Toulouse, Octobre
2004.
[4] D.E. Goldberg, Genetic algorithms in search optimization and machine learning, Reading MA
Addison Wesley, 1989.
[5] T. Guillod, Interpolations, courbes de Bézier etB-splines, Bulletin de la Société des enseignants
Neuchâtelois de Sciences, 2008.

Figure 15 The fitness evolution with respect the generation[6] J.R. Koza, Genetic programming, MIT press,
1992.
[7] C. Rabut, Courbes, outils pour la CAO, approximation à une variable, INSA-Toulouse lecturenotes, 2008.

three generations (90 generations for the roundabout
test problem). This results shows that our method canbe very efficient from an operational point of view.
Indeed, in operational problems, there are never morethan four aircrafts involved in the same conflict. Consequently, our algorithm will be able to deal very efficiently with operational air traffic. For this situation,
we used a different number of generations because of
its extremely quick convergence (number of generation: 20). Moreover, we can see that few aircrafts
are deviated, which is consistent with a controller behaviour, who would prefer to deviate largely one aircraft instead of deviating lightly several aircrafts tosolve conflicts.

6[8] K. Zeghal, Vers une théorie de la coordinationd’actions, application à la navigation aérienne,
Ph.D. thesis, Université Paris VI, 1994.

Acknowledgements
This work has been supported by French National
Research Agency (ANR) through COSINUS program(project ID4CS ANR-09-COSI-005) and Capgemini
through the first author PhD funding.

Copyright

CONCLUSION

The authors confirm that they, and/or their company or institution, hold copyright of all original material included in their paper. They also confirm they
have obtained permission, from the copyright holder
of any third party material included in their paper, topublish it as part of their paper. The authors grantfull permission for the publication and distribution of
their paper as part of the EIWAC 2010 proceedings or
as individual off-prints from the proceedings.

We have shown in this paper that the combinationof B-splines and genetic algorithms can be a promising methodology for automatic conflict resolution in
air traffic control. However, we have in mind several developments to improve our approach such as
using sharing in GA (deals with equirepartition of the
population on the different maximums) in our GA or
implementing a self-adaptative GA (every parameter such as bandwidth, control points’ number, etc
will be considered within the chromosome encoding,

77778