Aircraft Conflict Resolution by Genetic Algorithm and
B-Spline Approximation
ENRI/EIWAC Workshop 2010

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Applied Math Laboratory, ENAC, Capgemini, IMT (Toulouse Mathematical Institute)

November 10, 2010

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
1 / Instit
36

AgendaContext
What is our approach ?
Trajectory model: B-splines
Optimization method: Genetic Algorithm
Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
2 / Instit
36

AgendaContext
What is our approach ?
Trajectory model: B-splines
Optimization method: Genetic Algorithm
Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
3 / Instit
36

Air traffic management context

Environment
Air traffic control (ATC) has always been a critical safety matter
Previously, ATC dealt with traffic growth by reducing airspace sectors’size
The number of flights is going to double over the next 20 years,
The airspace will reach its limits with the current means of control.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
4 / Instit
36

Air traffic management context

Environment
Air traffic control (ATC) has always been a critical safety matter
Previously, ATC dealt with traffic growth by reducing airspace sectors’size
The number of flights is going to double over the next 20 years,
The airspace will reach its limits with the current means of control.
Air Traffic Management requirements
Aircraft Separation,
Staying close to the original trajectory.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
4 / Instit
36

NextGen and SESAR Context

More automation :delegation of some spacing and separation tasks to aircraft,
decision support for controllers.

Integration of new technologies,
A new concept of air traffic control: Trajectory-based operations

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
5 / Instit
36

Previous related works: Navigation Functions

How does it work ?
The Navigation Function produces a potential field which drives theaircraft toward the destination and away from obstacles,

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
6 / Instit
36

Previous related works: Navigation Functions

Benefits
Provable convergence to a desired configuration,
Guaranteed collision avoidance.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
7 / Instit
36

Previous related works: Navigation Functions

Benefits
Provable convergence to a desired configuration,
Guaranteed collision avoidance.
Drawbacks
It does not take into account constraints present in ATC such as:
Bounded velocity,
Smoothness requirement for the path.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
7 / Instit
36

Previous related works: Genetic Algorithm

How does it work ?
Two types of simple maneuvers are used :The Turning point model:
The Offset model:
Operation of crossover and mutation are applied to the initial trajectories.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
8 / Instit
36

Previous related works: Genetic Algorithm

Benefits
Generates path with feasible operational maneuvers (ATC),
The magnitude of the speed is within a bounded range.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
9 / Instit
36

Previous related works: Genetic Algorithm

Benefits
Generates path with feasible operational maneuvers (ATC),
The magnitude of the speed is within a bounded range.
Drawbacks
Is able to manage a limited set of trajectories (straight line segments).

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10,Mathematical2010 ENRI/EIWA
9 / Instit
36

AgendaContext
What is our approach ?
Trajectory model: B-splines
Optimization method: Genetic Algorithm
Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
10 / Instit
36

What is our approach ?
Our objective
Generate N aircrafts trajectories for an en-route conflict situation,
Conflict-free trajectories,
Optimal trajectories regarding distance and time.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
11 / Instit
36

What is our approach ?
Our objective
Generate N aircrafts trajectories for an en-route conflict situation,
Conflict-free trajectories,
Optimal trajectories regarding distance and time.
Optimization problem features
A full-automation strategy.
The conflict resolution has been proven NP-hard,
No derivative available,
Black box stochastic global optimization well suited.
B-splines allows to reduce the solution space dimension.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
11 / Instit
36

What is our approach ?

Our methodology
A combination between a stochastic optimization method: Genetic
Algorithm (GA),and smooth trajectory model: B-splines.
B-splines are controlled by GA via their control points

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
12 / Instit
36

What is our approach ?

Our methodology
A combination between a stochastic optimization method: Genetic
Algorithm (GA),and smooth trajectory model: B-splines.
B-splines are controlled by GA via their control points
Data and constraints
Data: Start and end points, and speed for each aircrafts
Constraint: → Constant speed along the aircraft trajectory,→ No vertical deviation (2D resolution).

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
12 / Instit
36

AgendaContext
What is our approach ?
Trajectory model: B-splines
Optimization method: Genetic Algorithm
Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
13 / Instit
36

Trajectory modelStart and end points

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
14 / Instit
36

Trajectory modelBusiness trajectory

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
15 / Instit
36

Trajectory model

Maximum deviation bandwidth

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
16 / Instit
36

Trajectory model

Uniformly distributed control points along the trajectory

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
17 / Instit
36

Trajectory model

Location of the control points

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
18 / Instit
36

Trajectory model

Corresponding B-splines

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
19 / Instit
36

B-splines benefits

A very efficient tool for curve approximation,
C 2 -continuity (crucial for modeling fliable aircraft trajectories),
Allows to reduce the solution space dimension,
A good compatibility with GA requirements.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
20 / Instit
36

AgendaContext and previous work
What is our approach ?
Trajectory model: B-splines
Optimization method: Genetic Algorithm
Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
21 / Instit
36

Optimization method: Genetic Algorithm
A solution space’s individual is encoded in a chromosome.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
22 / Instit
36

Optimization method: Genetic Algorithm
A solution space’s individual is encoded in a chromosome.
Definition of the encoding for an example N = 20 and Nbpt = 3:

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
22 / Instit
36

Optimization method: Genetic Algorithm

Each point is defined by a bandwidth percentage:

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
23 / Instit
36

Optimization method: Genetic Algorithm

Each point is defined by a bandwidth percentage:abc
Example: P11 = Dmax
, P21 = Dmax
and P31 = Dmax

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
23 / Instit
36

Optimization method: Genetic Algorithm

A population of solution (chromosome) evolves using evolution
concepts

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
24 / Instit
36

Optimization method: Genetic Algorithm

A population of solution (chromosome) evolves using evolution
concepts
Evolution from generation k to k + 1

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
24 / Instit
36

Genetic Algorithm : Operators
Slicing crossover
Aims to exploit the good solutions

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
25 / Instit
36

Genetic Algorithm Operators
Mutation
Aims to explore randomly the solution space

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
26 / Instit
36

Optimization method: Genetic Algorithm

Chromosome evaluation
Necessity to evaluate solution space individuals to make a selection
Fitness = ability to address the problem
Fitness expression:f (X ) = −nXdist(NRi )(α.CNi + β.())
dist(BTi )i=1where CNi is the conflict number involving the aircraft i
NR is the new route corresponding the aircraft i
BT is the business trajectory

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
27 / Instit
36

Optimization method: Genetic Algorithm
Conflict detection
Two-aircraft scheme:

Allows us to calculate each chromosome fitness

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
28 / Instit
36

Optimization method: Genetic Algorithm
Summary

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
29 / Instit
36

AgendaContext and previous work
What is our approach ?
Trajectory model: B-splines
Optimization method: Genetic Algorithm
Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
30 / Instit
36

Results
Roundabout test problem

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
31 / Instit
36

Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
32 / Instit
36

Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
33 / Instit
36

Results

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
34 / Instit
36

Conclusion

Conclusion
The combination between B-splines and optimization method is
promising for conflict resolution.
Our methodology obtains encouraging results on theoretical andoperational situations.
Many researches can be lead from this preliminary work.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
35 / Instit
36

Conclusion

Conclusion
The combination between B-splines and optimization method is
promising for conflict resolution.
Our methodology obtains encouraging results on theoretical andoperational situations.
Many researches can be lead from this preliminary work.
Perspectives
Improve our GA using sofisticated operators.
Try B-splines under tension.
Try other direct optimization method.

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
35 / Instit
36

Thank you for your attention,
Questions?

D. Delahaye, C.Peyronne, M.Mongeau, S.Puechmorel
Aircraft Conflict(AppliedResolution
Math Laboratory,by Genetic
ENAC,
Algorithm
Capgemini,
and B-Spline
IMT
November(Toulouse
Approximation
10, 2010
Mathematical
ENRI/EIWA
36 / Instit
36