Mathematical Models for Aircraft Trajectory Design : A
SurveyEIWAC 2013 Tokyo
D. Delahaye and S.Puechmorel and P.Tsiotras and E.Feron
Applied Mathematics Laboratory (MAIAA)
French Civil Aviation University
Toulouse, France
School of Aerospace Engineering
Georgia Institute of Technology
Atlanta, USA

February, 21 2013

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
1Universit/ 146AgendaSome Trajectory Models

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
2Universit/ 146AgendaSome Trajectory Models
Strategic Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
2Universit/ 146AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
2Universit/ 146AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
2Universit/ 146AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design
Emergency Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
2Universit/ 146AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design
Emergency Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
3Universit/ 146Trajectory Models

Aircraft Trajectory Features
Dimension Reduction Approaches
Front Propagation Approaches
Optimal Control Approaches

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
4Universit/ 146Classical representation

t=b

t

x

y

z

t=a

Trajectory data is expressed as an ordered list of plots (no aircraft
dynamics in such representation)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
5Universit/ 146Trajectories as functional data
Trajectories are infinite dimension mathematical objects
Trajectories as mappingsγ( t )

t0

t1

Intuitive approach : a trajectory maps a bounded time interval [t0 , t1 ]to the state space (R3 or R6 ).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
6Universit/ 146Trajectories as functional data
Trajectories are infinite dimension mathematical objects
Trajectories as mappingsγ( t )

t0

t1

Intuitive approach : a trajectory maps a bounded time interval [t0 , t1 ]to the state space (R3 or R6 ).
Smoothness assumptions are made for trajectories (C 2 ).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
6Universit/ 146Trajectories as functional data
Trajectories are infinite dimension mathematical objects
Trajectories as mappingsγ( t )

t0

t1

Intuitive approach : a trajectory maps a bounded time interval [t0 , t1 ]to the state space (R3 or R6 ).
Smoothness assumptions are made for trajectories (C 2 ).
Trajectories as shapes

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
6Universit/ 146Trajectories as functional data
Trajectories are infinite dimension mathematical objects
Trajectories as mappingsγ( t )

t0

t1

Intuitive approach : a trajectory maps a bounded time interval [t0 , t1 ]to the state space (R3 or R6 ).
Smoothness assumptions are made for trajectories (C 2 ).
Trajectories as shapes
The paths flown by aircraft are considered as curves in R3 .

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
6Universit/ 146Trajectories as functional data
Trajectories are infinite dimension mathematical objects
Trajectories as mappingsγ( t )

t0

t1

Intuitive approach : a trajectory maps a bounded time interval [t0 , t1 ]to the state space (R3 or R6 ).
Smoothness assumptions are made for trajectories (C 2 ).
Trajectories as shapes
The paths flown by aircraft are considered as curves in R3 .
Such time independant trajectories are called shapes.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
6Universit/ 146Aircraft Trajectories Features

Notations
t=b

t=aD. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
7Universit/ 146Aircraft Trajectories Features

Notationst=b

t=aTrajectory ~γ : ~γ [a, b] → E ([a, b] time interval, E : R3 or R6 )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
7Universit/ 146Aircraft Trajectories Features

Notationst=b

t=aTrajectory ~γ : ~γ [a, b] → E ([a, b] time interval, E : R3 or R6 )Rb 0
Trajectory length l(~γ ) = a k~γ (t)kdt

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
7Universit/ 146Aircraft Trajectories Features

Notationst=b

t=aTrajectory ~γ : ~γ [a, b] → E ([a, b] time interval, E : R3 or R6 )Rb 0
Trajectory length l(~γ ) = a k~γ (t)kdt
Parametrization: s(a, b) → (0, l(~γ ))R t 0 by arclength00s(t) = a k~γ (x)kdx (s (t) = k~γ (t)k > 0 ∀t ∈ (a, b))

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
7Universit/ 146Aircraft Trajectories Feature

Unit tangent vector

τ

t=b

t=a

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
8Universit/ 146Aircraft Trajectories Feature

Unit tangent vector

τ

t=b

t=a

~τ (s) = ~γ 0 (s)D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
8Universit/ 146Aircraft Trajectories Feature
Curvature
000(t)∧~γ (t)k
K (s) = k~γ (s)k = k~γ k~
γ 0 (t)k3
00

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
9Universit/ 146Aircraft Trajectories Feature
Curvature
000(t)∧~γ (t)k
K (s) = k~γ (s)k = k~γ k~
γ 0 (t)k300

Aircraft trajectories have piecewise constant curvature.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
9Universit/ 146Aircraft Trajectories Feature
Curvature
000(t)∧~γ (t)k
K (s) = k~γ (s)k = k~γ k~
γ 0 (t)k300

Aircraft trajectories have piecewise constant curvature.
Unit normal vector
τ

t=b

ν
t=a

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
9Universit/ 146Aircraft Trajectories Feature
Curvature
000(t)∧~γ (t)k
K (s) = k~γ (s)k = k~γ k~
γ 0 (t)k300

Aircraft trajectories have piecewise constant curvature.
Unit normal vector
τ

t=b

ν
t=a

00

(s)
~ν (s) = ~γK (s)D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21
Civil
2013
2013
AviationTokyo
9Universit/ 146Aircraft Trajectories Feature
Torsion
β. τ

t=b

ν
t=a

0
~
β(s)
= ~τ (s) ∧ ~ν (s) β~ (s) = T (s).~ν (s)D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
10Universit/ 146Aircraft Trajectories Feature
Torsion
β. τ

t=b

ν
t=a

0
~
β(s)
= ~τ (s) ∧ ~ν (s) β~ (s) = T (s).~ν (s)The real number T (s) is called the torsion of the curve at s andrepresents an obstruction for the curve to be planar.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
10Universit/ 146Aircraft Trajectories Feature
Torsion
β. τ

t=b

ν
t=a

0
~
β(s)
= ~τ (s) ∧ ~ν (s) β~ (s) = T (s).~ν (s)The real number T (s) is called the torsion of the curve at s andrepresents an obstruction for the curve to be planar.
0

00

000

γ (t),~γ (t),~γ (t))
T (t) = − det(~k~γ 0 (t)∧~γ 00 (t)k2

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
10Universit/ 146Aircraft Trajectories Feature
Torsion
β. τ

t=b

ν
t=a

0
~
β(s)
= ~τ (s) ∧ ~ν (s) β~ (s) = T (s).~ν (s)The real number T (s) is called the torsion of the curve at s andrepresents an obstruction for the curve to be planar.
0

00

000

γ (t),~γ (t),~γ (t))
T (t) = − det(~k~γ 0 (t)∧~γ 00 (t)k2

Aircraft have piecewise constant torsion mainly in terminal area.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
10Universit/ 146Aircraft Trajectories Feature
Torsion
β. τ

t=b

ν
t=a

0
~
β(s)
= ~τ (s) ∧ ~ν (s) β~ (s) = T (s).~ν (s)The real number T (s) is called the torsion of the curve at s andrepresents an obstruction for the curve to be planar.
0

00

000

γ (t),~γ (t),~γ (t))
T (t) = − det(~k~γ 0 (t)∧~γ 00 (t)k2

Aircraft have piecewise constant torsion mainly in terminal area.
All the previous derivations rely on the fact that the first threederivatives of the trajectory are available.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
10Universit/ 146Trajectory Models

Aircraft Trajectory Features
Dimension Reduction Approaches
Front Propagation Approaches
Optimal Control Approaches

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
11Universit/ 146

Explicit vs Implicit

Explicity = f (x)Example 2D line y = a.x + b
A curve may not have an explicit representation
Implicitf (x, y ) = 0
Example 2D circle x 2 + y 2 − r 2 = 0

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
12Universit/ 146

Parametric Form

Expresses the value of each spatial variables for points in terms of an
independent parameter u.
x(u)~p (u) =  y (u) z(u)D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
13Universit/ 146

Parametric Polynomial Curve

Consider a curve




x(u)
~p (u) =  y (u) z(u)A polynomial parametric curve of degree n is of the form :~p (u) =nX~ck .u kk=0

where each ~ck has independent x, y , z components : ~ck = [ckx , cky , ckz ]T

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
14Universit/ 146

Advantages of the Parametric Polynomial Curve

Just needs to save a few control points
Local control of shape
Smoothness and continuity
Ability to evaluate derivatives
Stability
Ease of rendering

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
15Universit/ 146Lagrangian Interpolation
Given n + 1 real numbers yi ,0 ≤ i ≤ n, and n + 1 distinct real numbers
x0 < x1 < ... < xn , Lagrange polynomial of degree n associated with {xi }and {yi } is a polynomial of degree n solving the interpolation problem :pn (xi ) = yi , 0 ≤ i ≤ nSolution :Ln (x) =nXf (xi )li (x)

i=0

where
li (x) =Y (x − xj )j6=i(xi − xj )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
16Universit/ 146Hermite Interpolation
Hermite interpolation generalizes Lagrange interpolation by fitting apolynomial to a function f that not only interpolates f at each knot but
also interpolates a given number of consecutive derivatives of f at each
knot.

 j

 j
∂ f (x)∂ H(x)=∂x j∂x j x=xi
x=xi
for all j = 0, 1, ..., m and i = 1, 2, ..., k

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
17Universit/ 146

Runge phenomenon

Interpolation with high degree polynomial is risky...
Solution : Piecewise interpolation

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
18Universit/ 146Piecewise Linear Interpolation

The simplest one

x0

x i−1

xi

x i+1

xn

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
19Universit/ 146Piecewise Linear Interpolation

Given n + 1 real numbers yi ,0 ≤ i ≤ n, and n + 1 distinct real numbers
x0 < x1 < ... < xn , we consider the n linear curves li (x) = ai x + bi on theintervals [xi , xi+1 ] for i = 0, ...n − 1.
each li (x) has to connect two points {(xi , yi ),(xi+1 , yi+1 )}yi = ai xi + bi xi yi+1 = ai xi+1 + bi xi+1

The resulting curves is not derivative.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
20Universit/ 146Piecewise Quadratic Interpolation

Initial slope

x0

x i−1

xi

x i+1

xn

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
21Universit/ 146Piecewise Quadratic Interpolation
We consider the n quadratic curves qi (x) = ai x 2 + bi x + ci on theintervals [xi , xi+1 ] for i = 0, ...n − 1.
Each qi (x) has to connect two points ((xi , yi ),(xi+1 , yi+1 )yi = ai xi2 + bi xi + ci2
yi+1 = ai xi+1
+ bi xi+1 + ci

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
22Universit/ 146Piecewise Quadratic Interpolation
We consider the n quadratic curves qi (x) = ai x 2 + bi x + ci on theintervals [xi , xi+1 ] for i = 0, ...n − 1.
Each qi (x) has to connect two points ((xi , yi ),(xi+1 , yi+1 )yi = ai xi2 + bi xi + ci2
yi+1 = ai xi+1
+ bi xi+1 + ci

On each point the derivative of the previous quadratic has to be equal
to the derivative of the next one.
2ai + bi = 2ai−1 + bi−1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
22Universit/ 146Piecewise Quadratic Interpolation
We consider the n quadratic curves qi (x) = ai x 2 + bi x + ci on theintervals [xi , xi+1 ] for i = 0, ...n − 1.
Each qi (x) has to connect two points ((xi , yi ),(xi+1 , yi+1 )yi = ai xi2 + bi xi + ci2
yi+1 = ai xi+1
+ bi xi+1 + ci

On each point the derivative of the previous quadratic has to be equal
to the derivative of the next one.
2ai + bi = 2ai−1 + bi−1

For the first segment the term 2ai−1 + bi−1 is arbitrarily chosen. (thisaffects the rest of the curve).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
22Universit/ 146Piecewise Cubic Interpolation
Also called Hermite Cubic Interpolation
slope in i
slope in i+1

y i−1

yi

x i−1

xi

h

y i+1
x i+1

y i+2
x i+2

Ci (x) = ai x 3 + bi x 2 + ci x + diCi (xi ) = yi
y −yi−1
Ci0 (xi ) = yi0 = xi+1
i+1 −xi−1

Ci (xi+1 ) = yi+1
−yi0
= yxi+2
Ci0 (xi+1 ) = yi+1
i+2 −xi

Moving a point do not affect all the curve
The curve is C 1 but not C 2 .

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
23Universit/ 146

Curvature radius3
2
1 + dfdx(x)R=  2|| d dxf (x)2

In order to have a continuous curverture one must force curves to be C 2 .

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
24Universit/ 146

Cubic Spline Interpolation
Piecewise cubic interpolation
Developped by General Motor in the 1950s.

y i−1
x i−1

S i (t)

yi

y i+1
xi

x i+1

y i+2
x i+2

Si (xi ) = yi
Si (xi+1 ) = yi+10000
Si (xi ) = Si−1 (xi+1 ) Si (xi+1 ) = Si+1 (xi+1 )
00
00
00
00
Si (xi ) = Si−1 (xi+1 ) Si (xi+1 ) = Si+1 (xi+1 )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
25Universit/ 146

Cubic Spline Interpolation

Si (x) for x ∈ [xi , xi+1 ]
3

3

−x)
(x−xi )Si (x) = σ6i . (xxi+1+ σi+16 . xi+1 −xi
i+1 −xi
σi
i+1 −x+ yi . xxi+1−xi − 6 .(xi+1 − xi )(xi+1 − x)
σi+1
x−xi
+ yi+1 . xi+1
−xi − 6 .(xi+1 − xi )(x − xi )where

d 2 Si (x)dx 2Such spline is also called natural spline because it represents the curve ofa metal spline constrained to interpolate some given points.
σi =D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
26Universit/ 146

Bézier Approximation CurveBézier curves were first developped by automobile designers to
describe the shape of exterior car panels in the 1960s and 70s.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
27Universit/ 146

Bézier Approximation CurveBézier curves were first developped by automobile designers to
describe the shape of exterior car panels in the 1960s and 70s.
~ 0 and P~ 1 , a linear Bézier curve is simply a straight line
Given points P
between those two points. The curve is given by~ 0 + t(P~1 − P~ 0 ) = (1 − t)P~ 0 + tP
~ 1 , t ∈ [0, 1]
B(t) = P

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
27Universit/ 146

Bézier Approximation CurveBézier curves were first developped by automobile designers to
describe the shape of exterior car panels in the 1960s and 70s.
~ 0 and P~ 1 , a linear Bézier curve is simply a straight line
Given points P
between those two points. The curve is given by~ 0 + t(P~1 − P~ 0 ) = (1 − t)P~ 0 + tP
~ 1 , t ∈ [0, 1]
B(t) = PBézier Curve with 2 points
P1
P0

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
27Universit/ 146

Cubic Bézier curves
P0

P1
P1
P0

P2

BÉZIER CURVE
P2

P3~ 0, P~ 1, P~ 2 and P~ 3 in the plane or in higher-dimensional
Four points P
space define a cubic Bézier curve.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
28Universit/ 146

Cubic Bézier curves
P0

P1
P1
P0

P2

BÉZIER CURVE
P2

P3~ 0, P~ 1, P~ 2 and P~ 3 in the plane or in higher-dimensional
Four points P
space define a cubic Bézier curve.
~ 0 going towards P~ 1 and arrives at P
~ 3 coming
The curve starts at P
~ 2 . Usually, it will not pass through P~ 1 or P~2 ;from the direction of P
these points are only there to provide directional information.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
28Universit/ 146

Cubic Bézier curves

The polygon formed by connecting the Bézier points with lines,~ 0 and finishing with P~ n , is called the Bézier polygon
starting with P(or control polygon).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
29Universit/ 146

Cubic Bézier curves

The polygon formed by connecting the Bézier points with lines,~ 0 and finishing with P~ n , is called the Bézier polygon
starting with P(or control polygon).
The convex hull of the Bézier polygon contains the Bézier curve.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
29Universit/ 146

Cubic Bézier curves

The polygon formed by connecting the Bézier points with lines,~ 0 and finishing with P~ n , is called the Bézier polygon
starting with P(or control polygon).
The convex hull of the Bézier polygon contains the Bézier curve.
The start (end) of the curve is tangent to the first (last) section of
the Bézier polygon.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
29Universit/ 146

Cubic Bézier curves
The explicit form of the curve is :~ 0 + 3(1 − t)2 t P~ 1 + 3(1 − t)t 2 P~ 2 + t 3P
~ 3 , t ∈ [0, 1].
B(t) = (1 − t)3 P
B(t) =nX~i,bi,n (t)Pt ∈ [0, 1]

i=0

where the polynomials n ibi,n (t) =t (1 − t)n−i ,ii = 0, . . . n

are known as Bernstein basis polynomials of degree n.
A Bézier curve defined with n + 1 control points is of degree n.
So if there are many points one has to manipulate polynoms with highdegree ⇒ Basis-Splines

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
30Universit/ 146

B-Splines

Powerful tool for generating curves with many control points, B stands forbasis.
A single B-spline can specify a long complicated curve

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
31Universit/ 146

B-Splines

Powerful tool for generating curves with many control points, B stands forbasis.
A single B-spline can specify a long complicated curve
B-splines can be designed with sharp bends and even “corners”

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
31Universit/ 146

B-Splines

Powerful tool for generating curves with many control points, B stands forbasis.
A single B-spline can specify a long complicated curve
B-splines can be designed with sharp bends and even “corners”
B-Spline interpolation is preferred over polynomial interpolation
because the interpolation error can be made small even when using
low degree polynomials for the spline.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
31Universit/ 146

B-Splines

Powerful tool for generating curves with many control points, B stands forbasis.
A single B-spline can specify a long complicated curve
B-splines can be designed with sharp bends and even “corners”
B-Spline interpolation is preferred over polynomial interpolation
because the interpolation error can be made small even when using
low degree polynomials for the spline.
Spline interpolation avoids the problem of Runge’s phenomenon
which occurs when interpolating between equidistant points with highdegree polynomials.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
31Universit/ 146

Uniform B-Splines of Degree Zero

~ = {t0 , t1 , ..., tn } with t0 ≤ t1 ≤, ..., ≤ tn and
We consider a node vector T~
n points Pi .
~ 0 (t) such that
One want to build a curve X~ 0 (ti ) = P~iX~ 0 (t) = P~ i ∀t ∈ [ti , ti+1 ]⇒X~ 0 (t) =X

X~i
Bi,0 (t).Pi

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
32Universit/ 146

Uniform B-Splines of Degree Zero

X 0 (t)
Pi

0

1

2

3

t i =4

1

5

6

7

8

9

B i,0 (t)

ti

t i+1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
33Universit/ 146

Uniform B-Splines of Degree One
We are searching for a piecewise linear approximation :
t − tit − ti~~~ i ∀t ∈ [ti , ti+1 ]X1 (t) = 1 −Pi−1 + 1 −P
ti+1 − titi+1 − tiX~ 1 (t) =~i
XBi,1 (t).Pi
X 1 (t)
Pi

0

1

2

3

t i =4

1

5

6

7

8

9

B i−1,1(t)

t i−1

ti

t i+1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
34Universit/ 146

Uniform B-Splines of Degree Three
Developped at Boeing in the 70s.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
35Universit/ 146

Uniform B-Splines of Degree Three
Developped at Boeing in the 70s.
One of the simplest and most useful cases of B-splines

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
35Universit/ 146

Uniform B-Splines of Degree Three
Developped at Boeing in the 70s.
One of the simplest and most useful cases of B-splines
Degree 3 B-Spline with n + 1 control points :~ 3 (t) =XnX~i 3 ≤ t ≤ n + 1
Bi,3 (t).P

i=0

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
35Universit/ 146

Uniform B-Splines of Degree Three
Developped at Boeing in the 70s.
One of the simplest and most useful cases of B-splines
Degree 3 B-Spline with n + 1 control points :~ 3 (t) =XnX~i 3 ≤ t ≤ n + 1
Bi,3 (t).P

i=0

For degree 3,
Bi,3 (t) = 0 if t ≤ ti or t ≥ ti+4 So~ 3 (t) =XjX~ i t ∈ [j, j + 1], 3 ≤ j ≤ nBi,3 (t).P

i=j−3

When a single control point Pi is moved, only the portion of the~ 3 (t) with ti < t < ti+4 is changed ⇒ local control.
curve X

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
35Universit/ 146

Uniform B-Splines of Degree Three

The basis functions have the following properties :They are translates of each other i.e Bi,3 (t) = B0,3 (t − i)D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
36Universit/ 146

Uniform B-Splines of Degree Three

The basis functions have the following properties :They are translates of each other i.e Bi,3 (t) = B0,3 (t − i)They are piecewise degree three polynomial

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
36Universit/ 146

Uniform B-Splines of Degree Three

The basis functions have the following properties :They are translates of each other i.e Bi,3 (t) = B0,3 (t − i)They are piecewise degree three polynomial
P
Partition of unity i Bi (t) = 1 for 3 ≤ t ≤ n + 1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
36Universit/ 146

Uniform B-Splines of Degree Three

The basis functions have the following properties :They are translates of each other i.e Bi,3 (t) = B0,3 (t − i)They are piecewise degree three polynomial
P
Partition of unity i Bi (t) = 1 for 3 ≤ t ≤ n + 1~ i (t) are of degree 3 for any set of control points
The functions X

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
36Universit/ 146

Uniform B-Splines of Degree Three(t − ti−2 )3 if t ∈ [ti−2 , ti−1 ]
h3 + 3h2 (t − ti−1 ) + 3h(t − ti−1 )2 − 3(t − ti−1 )3 if t ∈ [ti−1 , ti ]1 3
h + 3h2 (ti+1 − t) + 3h(ti+1 − t)2 − 3(ti+1 − t)3
Bi−2,3 (t) =h
if t ∈ [ti , ti+1 ] (ti+2 − t)3 if t ∈ [ti+1 , ti+2 ]
0 otherwise

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
37Universit/ 146

Uniform B-Splines of Degree Three

B 1,3(t)B 2,3(t) B 3,3(t)B 4,3(t)

2/3

1

2

3

4

5

6

7

8

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
38Universit/ 146Homotopy Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
39Universit/ 146Homotopy Trajectory Design
If we consider two (or more) references trajectories (γ1 (t), γ2 (t))joining thesame origine destination pair (past flown trajectories may be considered),
one can create a new trajectory γ(α, t) by using an homotopy :γ(0, t) = γ1 (t)γ(α, t) =γ(1, t) = γ2 (t)γ(α, t) = (1 − α)γ1 (t) + αγ2 (t)

γ2
B
A

γα
γ1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
40Universit/ 146

Functionnal Principal Component Analysis

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
41Universit/ 146

Functionnal Principal Component Analysis

Used for Stochastic Signal Compression (movies, image, voice)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
42Universit/ 146

Functionnal Principal Component Analysis

Used for Stochastic Signal Compression (movies, image, voice)
The goal of principal component analysis is to compute the mostmeaninfugful basis to re-express a noisy data set (maximize
SNR,minimize redundancy).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
42Universit/ 146

Functionnal Principal Component Analysis

Used for Stochastic Signal Compression (movies, image, voice)
The goal of principal component analysis is to compute the mostmeaninfugful basis to re-express a noisy data set (maximize
SNR,minimize redundancy).
If speed is suitable one must work in Sobolev space

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
42Universit/ 146

Functionnal Principal Component Analysis

Used for Stochastic Signal Compression (movies, image, voice)
The goal of principal component analysis is to compute the mostmeaninfugful basis to re-express a noisy data set (maximize
SNR,minimize redundancy).
If speed is suitable one must work in Sobolev space
Extraction of the Probability Density Function of PCA coefficients inorder to be able to randomly generate “flyable trajectories”.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
42Universit/ 146

Optimization Approach
All the previous representations may be used in the following process
Optimization
X (parameters)
Trajectory
Reconstructionγ
Trajectory
Evaluation
y=f(X)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
43Universit/ 146Trajectory Models

Aircraft Trajectory Features
Dimension Reduction Approaches
Front Propagation Approaches
Optimal Control Approaches

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
44Universit/ 146

Method

Propagating front methods : General principle
Methods introduced by J.A. Sethian.
Goal :
Track the motion of a front as it
evolves.
How ?
We caracterize the position of thefront by the computation of thearrival time u(x, y ) at each point(x, y ).
Figure: Curve propagating with speed
F in normal direction.

⇒ Map of isocost.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
45Universit/ 146

Method

Propagating front methods

Fast Marching :→ Isotropic problem
The speed of propagation F is thesame in any directions, it only depends on the position.

Ordered Upwind :→ Anisotropic problem
The speed of propagation depends
on position and direction of the
propagation.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
46Universit/ 146

Method

Fast Marching Method
Statement of the problem in the case of optimal path planning :(J.A. Sethian, 1998)
Let u(x) be the time where the front crosses the point x.
Computation of u → Solving the Eikonal equation :(|∇u(x)|F (x) = 1 in Ω,
F (x) > 0
Γ(u) = {x|u(x) = u0 },where x is the position and F is the propagation speed.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
47Universit/ 146

Method

Fast Marching Method
Statement of the problem in the case of optimal path planning :(J.A. Sethian, 1998)
Let u(x) be the time where the front crosses the point x.
Computation of u → Solving the Eikonal equation :(|∇u(x)|F (x) = 1 in Ω,
F (x) > 0
Γ(u) = {x|u(x) = u0 },where x is the position and F is the propagation speed.
To plan the optimal path γ(t) (back traking) :
dγ(t)
∇u
=−
dt
||∇u||

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
47Universit/ 146

Method

Numerical solving : Godonov Scheme
The principal idea is to construct the solution using only upwind values. For this,
we divide all the mesh points in three sets :Accepted : Set of points where the solution is known ;Considered : Set of points which are adjacent to at least one Accepted
point ;
Far : Set of points where we do not have yet any information about thesolution.

Figure: Construction of the algorithm

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
48Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 1 : Initialization

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 2 : Transfering → Considered

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 3 : Looking for the smallest value u(xi )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 4 : Transfering → Accepted

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 5 : Transfering → Considered

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 6 : Looking for the smallest value u(xi )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 7 : Transfering → Considered

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 8 : Recomputing the value u(xi )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Fast Marching Algorithm

Figure: Step 8 : Recomputing the value u(xi )D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
49Universit/ 146

Method

Trajectory Models

Aircraft Trajectory Features
Dimension Reduction Approaches
Front Propagation Approaches
Optimal Control Approaches

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
50Universit/ 146

Method

Optimal Control for Trajectory Generation

Mainly used for time-parameterized of shapes.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
51Universit/ 146

Method

Optimal Control for Trajectory Generation

Mainly used for time-parameterized of shapes.
Generating time-parameterized paths necessitates the incorporation of
the aircraft dynamics.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
51Universit/ 146

Method

Optimal Control for Trajectory Generation

Mainly used for time-parameterized of shapes.
Generating time-parameterized paths necessitates the incorporation of
the aircraft dynamics.
The objective of optimal control theory is to determine the control
input(s) that will cause a process to satisfy the physical constraints,
while, at the same time, minimize (or maximize) some performance
criterion.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
51Universit/ 146

Method

Optimal Control for Trajectory Generation

Mainly used for time-parameterized of shapes.
Generating time-parameterized paths necessitates the incorporation of
the aircraft dynamics.
The objective of optimal control theory is to determine the control
input(s) that will cause a process to satisfy the physical constraints,
while, at the same time, minimize (or maximize) some performance
criterion.
Feasibility of the trajectories is automatically ensured using thisapproach.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
51Universit/ 146

Method

Optimal Control for Trajectory Generation

Given initial conditions x0 , final conditions xf ∈ X , and an initial timet0 ≥ 0, determine the final time tf > t0 , the control input u(t) ∈ U andthe corresponding state history x(t) for t ∈ [t0 , tf ] which minimize thecost function
RtJ(x, u) = t0f L(x(t), u(t)) dt,
where x(t) and u(t) satisfy, for all t ∈ [t0 , tf ] the differential andalgebraic constraints.
ẋ(t) − f (x(t), u(t)) = 0,
C (x(t), u(t)) ≤ 0.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
52Universit/ 146

Method

Optimal Control for Trajectory Generation

Optimal control has its roots in the theory of calculus of variations,which originated in the 17th century by Fermat, Newton, Liebniz,etc...

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
53Universit/ 146

Method

Optimal Control for Trajectory Generation

Optimal control has its roots in the theory of calculus of variations,which originated in the 17th century by Fermat, Newton, Liebniz,etc...
It was not until the middle of the 20th century when the Soviet
mathematician Pontryagin developed a complete theory that could
handle such problem.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
53Universit/ 146

Method

Optimal Control for Trajectory Generation
Pontryagin’s celebrated Maximum Principle states that the optimal
control for the solution of the problem is given as the pointwise
minimum of the so-called Hamiltonian function, that is :uopt = argminu∈U H(t, x, λ, u)where H(t, x, λ, u) = L(x, u) + λT f (x, u) is the Hamiltonian, and λare the co-states, computed from
λ̇(t) = −∂H(x(t), λ(t), u(t)).
∂x(1)

subject to certain boundary (transversality) conditions on λ(tf ).
Numerical solution

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
54Universit/ 146

Method

AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design
Emergency Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
55Universit/ 146

Strategic Planning

Continental Strategic Planning

Before take-off
Trajectory design for large segment (full trajectory)
Action on time and space
Large scale (30000-50000 aircraft)Continental or Oceanic
Macroscopic congestion criterium
One must take into account uncertainties

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
56Universit/ 146

Strategic Planning

Uncertaintiestt + 10’t + 20’Trajectory prediction limitation Factors
1

~ =T
~ +W
~)
Wind (V2

Temperature, pressure (engine trust, drag d = 21 .cx .ρ.S.v 2 )3

WeightOn-board trajectory prediction
FMS in open loop : +−15Nm after one hour flight.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
57Universit/ 146

Strategic Planning

Continental Strategic Planing

How much can we reduce congestion in the French Airspace ?
Optimization Approach
EUROCONTROL

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
58Universit/ 146

Strategic Planning

Continental Strategic Planing

How much can we reduce congestion in the French
Airspace ?
Approach based on optimization
What are our state space variables ?
2D Route + departure times (' 7000 flights).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
59Universit/ 146

Strategic Planning

Continental Strategic Planing

How much can we reduce congestion in the French
Airspace ?
Approach based on optimization
What are our state space variables ?
2D Route + departure times (' 7000 flights).
What is our objective ?
Airspace congestion minimization

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
59Universit/ 146

Strategic Planning

Continental Strategic Planing

How much can we reduce congestion in the French
Airspace ?
Approach based on optimization
What are our state space variables ?
2D Route + departure times (' 7000 flights).
What is our objective ?
Airspace congestion minimization
What are the constraints ?
Extra distance ≤ 10%
Time shift have to be limited (+− 45 minutes)
The optimization process has to take into account flight connexions(hubs) and equity between airline.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
59Universit/ 146

Strategic Planning

Continental Strategic Planing

Mathematical Modeling

A pair of decision variable (δi , ri ) is associated with each flight n.
δi ∈ ∆n ri ∈ Rn∆n = −δm , −δm + 1, ...., −1, 0, 1, ..., δp − 1, δp
Rn = r0 , r1 , r2 , ..., rmax
(0, r0 ) : airline choice.
State point :X =δ1 δ2 ... δk
r1 r2 ... rk... δN... rND. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
60Universit/ 146

Strategic Planning

Continental Strategic Planing

Objective function
Congestion Minimization

min y (X ) = min

k=P
X
k=1

!
(

X

f t )φ × (max Wf t )ϕ
W
Sk
Sk
t∈T

t∈T

f t : is the maximum reported congestion.
maxt∈T W
SkPtft∈T WSk : is the sector cumulated congestion.
P is the number of elementary sectors, φ and ϕ are weight factors
max y1 (X ) =y (Xref )y (X )(y1 = 2 means that the congestion has been divided by 2)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
61Universit/ 146

Strategic Planning

Continental Strategic Planing

Simulation process

InitialFlight Plans

Alternative
Flight Plans

Airspace
Sectors

Traffic
Simulator
Best
Planning

Genetic Algorithm

SampledTrajectories
Proposed Planning

Congestion
Computation

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
62Universit/ 146

Strategic Planning

Continental Strategic Planing

Genetic Algorithm

POP(k)
Tournament
SelectionλµNothing1−(Pm+Pc)

CrossoverPc

MutationPm

POP(k+1)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
63Universit/ 146

Strategic Planning

Continental Strategic Planing

A Posteriori information
B
S4
A

S2
S1

S5
S3

WA
r

WB
r
Sector congestion

Time
in

out

in

out
Trend

Advance

Delay

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
64Universit/ 146

Strategic Planning

Continental Strategic Planing

State space

R1

RN

Rn

r1
3

rn
k

rN
6

δ12

δnj

δN3

∆1

∆N

∆n

Reported1
Congestion Wr

Wn
r

WN
r

Stochastic
Trend

Tn

TN

T1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
65Universit/ 146

Strategic Planning

Continental Strategic Planing

Test Features and Parameters

One day of traffic 6381 flights (june, 21 1996)
89 elementary sectors with dynamic capacity
Pop size : 50
Generation number : 300
φ = 0.9 and ϕ = 0.1
Max time shift : + or - 45 mn
Alternative route with 10% extradistance
6 computation hours on Pentium 1Ghz

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
66Universit/ 146

Strategic Planning

Continental Strategic Planing

Evolution of best planning with generations
One day of traffic with ' 7000 flights optimized with GA

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
67Universit/ 146

Strategic Planning

Continental Strategic Planing

Multi-objective extension

Delays and extra-distances minimization
Delay on the ground : δs (i) = |t(i) − t0 (i)|Delay on board : δr (i) = 3 ∗ (Tr (i) − Tr0 (i))
Total delay : δ(i) = δs (i) + δr (i)min y2 =

N
X

δ(i)2

i=1

(the square insure equity)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
68Universit/ 146

Strategic Planning

Continental Strategic Planing

Multi-objective extension

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
69Universit/ 146

Strategic Planning

Strategic Conflict Free Planing

Strategic Conflict Free Planning
Optimization Approach
FP7 4D-CO project

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
70Universit/ 146

Strategic Planning

Strategic Conflict Free Planing

Strategic Conflict Free Planning
Consider the traffic over Europe (' 36000 flights)
Picture of Europe Traffic for One Day

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
71Universit/ 146

Strategic Planning

Strategic Conflict Free Planing

Strategic Conflict Free Planning
We propose to design a gate-to-gate conflict free planning by adding
waypoints and/or by shifting the time on departure.
Departure and arrival segments are added to En-Route segments.
Optimal altitude profiles have been used.
Time shift : +- 30 minutes.
Waypoint constraints : max 10% extra distance

y	
  

0	
  

-­‐a	
  

wy2,max	
  wy1,max	
  

a	
  

O	
  

D	
  
wx1,min	
  wx1,max	
  wy1,min	
  
L/3	
  

wx2,min	
  wx2,max	
  wy2,min	
  

2L/3	
  

x	
  

L	
  

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
72Universit/ 146

Strategic Planning

Strategic Conflict Free Planing

Strategic Conflict Free Planning
Direct route planning induces ' 400000 interactions between trajectoires.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
73Universit/ 146

Strategic Planning

Strategic Conflict Free Planing

Strategic Conflict Free PlanningThis problem is NP Hard
One point of the state space requests 2GO memory space.
⇒ Simulated Annealing (20 minutes computing 2.4 Ghz intel CPU)4

18

Evolution of best objective function value

x 10

16

Best objective funciton value

14
12
10
8
6
4
2
0

0

0.5

1
1.5
number of transitions

2

2.5
4

x 10

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
74Universit/ 146

Strategic Planning

Strategic Conflict Free Planing

Strategic Conflict Free Planning

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
75Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Oceanic Strategic Planning
Optimization Approach
ENAC

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
76Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Oceanic Strategic Planning
Continental Airspace ⇒ Radar

Oceanic Airspace ⇒ Procedures based on oceanic tracks network

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
77Universit/ 146

Strategic Planning

Oceanic Strategic Planning

How It Works Today ?

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
78Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Oceanic Network Structure

Ny

1
1

Nx

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
79Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Network Limitation

Congestion Area

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
80Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Time Constraint for Oceanic Traffic

10 minutes

15 minutes 15 minutes

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
81Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Automatic Dependent Surveillance-Broadcast

One measure every second

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
82Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Time Constraint with ADSB

2 minutes

3 minutes

3 minutes

This new system increases the number of valid track changes and the
maximum number of aircraft on the same track (wind optimal).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
83Universit/ 146

Strategic Planning

Oceanic Strategic Planning

The model
Data : For each flight f ∈ F we knowfTrackinf
Trackout
f
tin
FLfin
FLfoutthe entry trackthe exit track
time of entrance in the track
the input flight level
the output flight level

Variablesxif =

1 if flight f changes track at waypoint i
0 otherwisef + δfδ f : time shift at track entry : tin

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
84Universit/ 146

Strategic Planning

Oceanic Strategic Planning

USA

EUROPE

Altitude Profiles

Altitude profiles will be considered as constraints.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
85Universit/ 146

Strategic Planning

Oceanic Strategic Planning

The model

Constraints

NX
X −1

f
f
|
xif = |Trackout− Trackin

i=1

zif =



1 if flight f changes flight level at waypoint i
0 otherwise
NX
X −1

zif = |FLfout − FLfin |i=1

Objective function
Number of conflicts on nodes (Cfn ) and links (Cfl ).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
86Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Induced Combinatorics

For each flight f we have the following
1

about 6 possible slots per flight.

2

an average of 4 track changes which have to be spread among the 10
waypoint positions (= 210 options per flight)3

the total number of options is about 1260.

For 500 flights we have 1260500 options.
No separability ⇒ Heuristic approach (EA)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
87Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Coding

δt

0

0

1

0

0

1

1

0

1

Ci =d iLevel of congestion encountered by flight i

d1

di

dN

N number of aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
88Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Slicing Crossover

CROSSOVER

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
89Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Slicing Crossover
PARENT 1

PARENT 2

SLICINGCROSSOVER

CHILD 1

CHILD 2

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
90Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Mutation

δt

0

0

1

0

0

1

1

0

1

Ci

δt

0

0

0

0

0

1

1

1

1

Ci

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
91Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Fitness Computation

Each aircraft trajectory is computed on the track network based on ;Altitude profile
Aircraft speed
Track changes decision variables
Time delay at network entry (Max +/- 6x5=30 minutes)
Based on such simulation, we compute the conflicts on nodes (Cfn ) and on
links (Cfl ).
fitness =1
1+0.01 + Cfn 0.01 + Cfl

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
92Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Test Framework

387 aircraft trajectories from August 4th 2006 (USA → Europe
traffic)

Evolutionary Algorithm parameters
Pop size
500
Genration number
1000
Selection(λ = 6,µ = 2)
Proba Cross
0.5
Proba Mut
0.1

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
93Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Results for Standard System

Simulation without ADSB
110
Best
Mean

100
90

Best and mean fitness

80
70
60
50
40
30
20
10
0
0

100

200

300

400

500
Generation

600

700

800

900

1000

Remaining conflicts on nodes : 609 (initially 1515)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
94Universit/ 146

Strategic Planning

Oceanic Strategic Planning

Results with ADSB Equiped Aircraft

Simulation with ADSB
200
Best
Mean
180
160

Best and mean fitness

140
120
100
80
60
40
20
0
0

100

200

300

400

500

600

700

800

900

1000

Generation

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
95Universit/ 146

Strategic Planning

Oceanic Strategic Planning

AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design
Emergency Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
96Universit/ 146

Pre-Tactical Planning

Pre-Tactical Planning

After take-off (1, 2 hours planning)

Features
2D route design and speed control (state space)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
97Universit/ 146

Pre-Tactical Planning

Pre-Tactical Planning

After take-off (1, 2 hours planning)

Features
2D route design and speed control (state space)
Congestion or weather areas avoidance (objective)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
97Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Wind Optimal Trajectory Design
Front Propagation Approach
Cap Gemini

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
98Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

What are our objectives ?

Currently
Using predefined air routes.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
99Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

What are our objectives ?

Currently
Using predefined air routes.
⇒ Proposed approach : Wind optimal route design.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
99Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

What are our objectives ?

Currently
Using predefined air routes.
⇒ Proposed approach : Wind optimal route design.
⇒ New problem :Optimization of aircraft trajectories based on weather conditions (wind)which avoid congestion areas (or bad weather phenomena, etc ...)The optimization is based on Travel Time and (or) Fuel Consumption.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): A Survey
February,
French
EIWAC
21Civil2013
2013
AviationTokyo
99Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Statement of problem

InputsStart point A,
End point B ;Constant aircraft speed ;Wind forecast ;Areas to avoid.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
Aviation
Tokyo
100Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Statement of problem

InputsStart point A,
End point B ;Constant aircraft speed ;Wind forecast ;Areas to avoid.

⇒ Goal : Connect the point A to the point B in order to minimize thetravel time.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
Aviation
Tokyo
100Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Adaptation of the Fast Marching Method−−→ −−−→ −−→
VGS = VTAS + VW
with :VTAS (True Airspeed) : speed of theaircraft relative to the airmass inwhich it is flying ;VW (Wind Speed) ;VGS (Ground Speed).

Figure: Speed

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
101Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Adaptation of the Fast Marching Method−−→ −−−→ −−→
VGS = VTAS + VW
with :VTAS (True Airspeed) : speed of theaircraft relative to the airmass inwhich it is flying ;VW (Wind Speed) ;VGS (Ground Speed).

Figure: Speed⇒ The aircraft ground speed is function of the direction !
⇒ Anisotropic problem.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
101Universit
/ 146

→
−
Calculation of the speed function : F = || F ||Pre-Tactical Planning

Trajectory Design in a Wind Field

Calculation of the aircraft
speed in the normal
direction.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
102Universit
/ 146

→
−
Calculation of the speed function : F = || F ||Pre-Tactical Planning

Trajectory Design in a Wind Field

Calculation of the aircraft
speed in the normal
direction.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
102Universit
/ 146

→
−
Calculation of the speed function : F = || F ||Pre-Tactical Planning

Trajectory Design in a Wind Field

Calculation of the aircraft
speed in the normal
direction.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
102Universit
/ 146

→
−
Calculation of the speed function : F = || F ||Pre-Tactical Planning

Trajectory Design in a Wind Field

Calculation of the aircraft
speed in the normal
direction.
Calculation of the cost u :1k∇uk = →−|| F ||

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
102Universit
/ 146

→
−
Calculation of the speed function : F = || F ||Pre-Tactical Planning

Trajectory Design in a Wind Field

Calculation of the aircraft
speed in the normal
direction.
Calculation of the cost u :1k∇uk = →−|| F ||

To plan the optimal path :
−−→
dX
∇u
= −VW − VTASdt||∇u||

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
102Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Taking into account obstacles and weather conditionsk∇u(x)k =1
F (x)⇒ Change of the propagation speed according to obstacles :k∇u(x)k =1((1 − α(x))F (x))

with α(x) ∈ [0; α0 ] and 0 6 α0 < 1.
Interpretation :α(x) = α0 : forbidden areas
α(x) = 0 : free areas
0 ≤ α(x) ≤ α0 penalized areas

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
103Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Example with obstacles

Figure: Obstacles (Forbidden areas then coefficient decreasing to 0.)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
104Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Example with obstacles

Figure: Optimal trajectory (green) without wind

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
104Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Example with obstacles

Figure: Wind

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
104Universit/ 146

Pre-Tactical Planning

Trajectory Design in a Wind Field

Example with obstacles

Figure: Optimal trajectories : with wind and without wind.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
104Universit/ 146

Pre-Tactical Planning

Light Propagation Algorithm

Wave Propagation Algorithm for Trajectory Design

Aircraft Trajectory Design in a Wind Field
Light Propagation Algorithm AIRBUS FMS Division

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
105Universit/ 146

Pre-Tactical Planning

Light Propagation Algorithm

The light propagation method

The light propagation analogy
Light follows Geodesic in time thereby avoiding areas of high index.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
106Universit/ 146

Pre-Tactical Planning

Light Propagation Algorithm

The light propagation method

The light propagation analogy
Light follows Geodesic in time thereby avoiding areas of high index.
Light propagation is controlled by the Descarte law.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
106Universit/ 146

Pre-Tactical Planning

Light Propagation Algorithm

The light propagation method

The light propagation analogy
Light follows Geodesic in time thereby avoiding areas of high index.
Light propagation is controlled by the Descarte law.
Trajectory planning can be achieved by computing wavefronts.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
106Universit/ 146

Pre-Tactical Planning

Light Propagation Algorithm

Principles of the light propagation method

Curent node
Destination
OrigineGeodesic computation (A∗ like algorithm or Triangle mesh algorithm)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
107Universit/ 146

Experimental results

2D

Experimental results

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
108Universit/ 146

Experimental results

2D

AgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design
Emergency Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
109Universit/ 146Tactical Planning

Tactical Planning

After take-off (horizon : 20 minutes))
Features
2D Route design (state space)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
110Universit/ 146Tactical Planning

Tactical Planning

After take-off (horizon : 20 minutes))
Features
2D Route design (state space)
Collision avoidance (objective)

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
110Universit/ 146Tactical Planning

Tactical Planning

After take-off (horizon : 20 minutes))
Features
2D Route design (state space)
Collision avoidance (objective)
One must bring a proof for such algorithms

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
110Universit/ 146Tactical Planning

Tactical Trajectory Design

Time extension of light Propagation Algorithm
Approach based on B-Splines
Approach based biharmonic navigation functions

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
111Universit/ 146Tactical Planning

Light Propagation Algorithm

Approach Based on LPATime extension for dynamic obstacles
Time

td

Obstacletd’Space Y

ts’
s’

d
d’

ts

s

Space X

Light has to propagate one way in time dimension

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
112Universit/ 146Tactical Planning

2D+TimeExperimental results

A 2D + time algorithm version
The algorithm sequentially control conflicting aircraft.
The aircraft are represented by high index discs of radius the standard
separation.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
113Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
114Universit/ 146Tactical Planning

2D+Time7 Conflicting Aircraft

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
115Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a traffic day

How does it work ?
We compute aircraft trajectories for a day of traffic over France.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
116Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a traffic day

How does it work ?
We extract trajectories segments between t et t + 21 min.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
116Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a traffic day

How does it work ?
We identify clusters of conflict.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
116Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a traffic day
How does it work ?
We solve conflicts within each cluster using the light propagation
algorithm.
Modified trajectory segments

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
116Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a traffic day

How does it work ?
We reintroduce the new segments in the database and we recompute theremaining parts of trajectories.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
116Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a traffic day

How does it work ?
The time window is slid by 7 min. t ← t + 7.
Fraction of time window already flown by aircraft
Segment extracted in the next time window

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
116Universit/ 146Tactical Planning

Traffic day

Conflict Resolution for a full day of traffic

Numerical Results
The 8/12/2008 traffic day was tested with 8212 aircraft.
3344 clusters.
99% of clusters were resolved (the last % is due to aircraft already inconflict when algorithm starts ; could be solve initial time shifting
Number of modified trajectories is 1501.
Average extension distance= -4.41 Nm.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
117Universit/ 146Tactical Planning

Traffic day

Stochastic Extension

Open loop FMS error has been used for our simulation (+-15 Nm after 1
Hour)
This algorithm has been extended with such uncertainties and is able
to manage 98% of the conflicts.
The remaining 2% have been solve by RTA setting (closed FMSmode).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
118Universit/ 146Tactical Planning

Traffic day

Tactical Trajectory Design

Time extension of light Propagation Algorithm
Approach based on B-SplinesCap Gemini
Approach based on biharmonic navigation functions

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
119Universit/ 146Tactical Planning

B-Spline Approach

Problem presentation

Our methodology
A combination of an optimization method and a smooth trajectorymodel : B-splines.
B-splines are controlled by the optimization method via theircontrol points

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
120Universit/ 146Tactical Planning

B-Spline Approach

Genetic Algorithm
Structure

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
121Universit/ 146Tactical Planning

B-Spline Approach

Trajectory model

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
122Universit/ 146Tactical Planning

B-Spline ApproachSemi-infinite programming formulation

min

f (x)

s.t.

g (x; t) > αx∀t ∈ [t1 , t2 ](2)where t is continuous, it is the semi-infinite parameter.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
123Universit/ 146Tactical Planning

B-Spline ApproachSemi-infinite programming formulation

Our objective function : relative distance increase.
Insure standard separation between each pair of aircraft at all timeijc ij (u; t) = kγ β (u) (s(t)) − γ β (u) (s(t))k2 > τ

ij∀t ∈ [0, tmax]

SIP is a local optimization method

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
124Universit/ 146Tactical Planning

B-Spline Approach

Results and comparison
32 aircrafts situation

Genetic Algorithm

Semi-infinite programming.

Next : use GA to initialize control points for SIP

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
125Universit/ 146Tactical Planning

Bi-harmanic Approach

Tactical Trajectory Design

Time extension of light Propagation Algorithm
Approach based on B-Splines
Approach based on biharmonic navigation functionsCap Gemini

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
126Universit/ 146Tactical Planning

Bi-harmanic Approach

Collision-free trajectory planning using biharmonicnavigation functions

Objective
Create trajectories guaranteeing obstacle avoidance and enforcing
ATM constraints for several aircraft.
Constraints
1

Speed has to stay in a given range

2

Trajectories have be smooth

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
127Universit/ 146Tactical Planning

Bi-harmanic Approach

Navigation Function
Potential Field Analogy in order to compute the navigation function φ.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
128Universit/ 146Tactical Planning

Bi-harmanic Approach

Navigation function and navigation field
The navigation field is given by : −∇φFigure: Example of navigation field

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
129Universit/ 146Tactical Planning

Bi-harmanic Approach

Navigation function and navigation field
The navigation field is given by : −∇φFigure: Example of navigation field
With these navigation fields, we can be sure that :any trajectory stays in the free space
any trajectory reaching the minimum stays at this minimum
There is no guarantee on the speed and trajectories may not be smooth ⇒Bi-Harmonic Functions.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
129Universit/ 146Biharmonic functions

TheoryMechanical stress field

Figure: The mechanical stress field

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
130Universit/ 146Biharmonic functions

TheoryMechanical stress field

Figure: The mechanical stress field

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
130Universit/ 146Biharmonic functions

TheoryMechanical stress field

Figure: The mechanical stress field

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
130Universit/ 146Biharmonic functions

TheoryMechanical stress field

Figure: The mechanical stress field

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
130Universit/ 146Biharmonic functions

TheoryMechanical stress field

Figure: Stresses representation

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
130Universit/ 146Biharmonic functions

TheoryBiharmonic functions : guideline
Solve 42 F = 0 + boundary conditions
Compute the stresses by :2
σxx = ∂yy
F (x, y )2σyy = ∂xx
F (x, y )2σxy = −∂xy
F (x, y )⇒ Tensor field
Compute the principal stresses(= eigenvalues)σxx σxyσmin
0⇒
σxy σyy0
σmaxCompute the eigenvectors corresponding to σmin
⇒ Navigation field

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
131Universit/ 146Biharmonic functions

TheoryFields with obstacle

Figure: With one obstacle

Figure: For a more complex geometry

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
132Universit/ 146Biharmonic functions

TheoryConclusions

Biharmonic Navigation Functions
Ensure conflict free trajectory design
With mathematical proof
With speed range constraint
With curvature constraint
May be used in tactical phase
Have to be extended to the stochastic framework ⇒ Stochastic
Biharmonic Functions

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
133Universit/ 146Biharmonic functions

TheoryAgendaSome Trajectory Models
Strategic Trajectory Design
Pre-Tactical Trajectory Design
Tactical Trajectory Design
Emergency Trajectory Design

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
134Universit/ 146Biharmonic functions

TheoryOn-Board A/C Optimal Trajectory Generation

Over 70% of fatal aviation accidents are in take-off/landing phases.
Cockpit emergency handling from crew can result in completely
different outcomes : Swissair Flight 111, US Airways Flight 1549
Landing in mountainous terrain (e.g., LinZhi airport in China),
avoiding inclement weather, or other aircraft in the area requires
reliable obstacle avoidance.

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
135Universit/ 146Biharmonic functions

TheoryAircraft Emergency Landing

Time is the most critical factor
Swissair flight 111 : 14min
US Airways flight 1549 : 3min

Fuel may be a limiting factor too
Challenges

Real-Time requirement
Convergence guarantees

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
136Universit/ 146Biharmonic functions

TheoryAn Alternative
Use a hierarchical approach
Geometric planner- State constraints, obstacles- Path generator

Motion planner- Time parameterization- Trajectory generator

Key Idea : First find flyable path to avoid obstacles ; then find afeasible trajectory to follow along this path.
Requires the solution of optimal time parameterization (orvelocity generation) problem.
The latter is a one-dimensional optimal control problem that can besolved very efficiently !

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
137Universit/ 146Biharmonic functions

TheoryOn-Line Optimal Trajectory Generation Schematic

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
138Universit/ 146Biharmonic functions

TheoryInitial Path Guess
Use Dubins paths with continuous descent

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
139Universit/ 146Biharmonic functions

TheoryApplication to Real Test Cases

Swissair 111

US Air 1549

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
140Universit/ 146Biharmonic functions

TheoryTest Case 1 : Swissair 111
Swissair 111 (McDonnell Douglas MD-11) from JFK (NY) to Geneva(Switzerland).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
141Universit/ 146Biharmonic functions

TheoryTest Case 1 : Swissair 111
Swissair 111 (McDonnell Douglas MD-11) from JFK (NY) to Geneva(Switzerland).
On Wednesday, 2 September 1998, the aircraft crashed into the
Atlantic Ocean southwest of Halifax International Airport (due to fireon Board).

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
141Universit/ 146Biharmonic functions

TheoryTest Case 1 : Swissair 111

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
142Universit/ 146Biharmonic functions

TheoryTest Case 1 : Swissair 111

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
143Universit/ 146Biharmonic functions

TheoryTest Case 1 : Swissair 111

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
144Universit/ 146Biharmonic functions

TheoryTest Case 2 : US Air 1549

VIDEO !

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
145Universit/ 146Biharmonic functions

TheoryTest Case 2 : US Air 1549

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
146Universit/ 146Biharmonic functions

TheoryQUESTIONS ?

D. Delahaye and S.Puechmorel and P.Tsiotras
Mathematicaland E.Feron Models( Appliedfor Mathematics
Aircraft Trajectory
Laboratory
Design(MAIAA): AFebruary,
SurveyFrench
EIWAC
21 Civil
2013
2013
AviationTokyo
147Universit/ 146