ICAS 2000 CONGRESS
193.1
TRAJECTORY GENERATION AND DISPLAY FOR
FREE FLIGHT
Mohammad Shahzad*, Félix Mora-Camino*!
!!
!, Jules G. Slama# and Karim Achaibou*
* LAAS du CNRS, Toulouse, France.
# Programa de Engenharia Mecânica, COPPE/UFRJ, Rio de Janeiro, Brazil.
!
!!
! Air Transportation Department, ENAC, Toulouse, France.
e-mail: shahzad@laas.fr, mora@laas.fr, jules@rionet.com.br & achaibou@laas.fr
Keywords : Relative Guidance of Aircraft, Trajectory Generation, Neural Networks
Abstract
In this study a new approach is proposed
for the generation of aircraft trajectories.
The relative guidance of an aircraft, which
is aimed to join in minimum time the track
of a leader aircraft, is particularly
considered. In a first place, a minimum
time relative convergence problem is
considered and optimal trajectories are
characterized. Then the synthesis of a
neural 
approximator 
for 
optimal
trajectories is discussed. Trained neural
networks are used in an adaptive manner
to generate intent trajectories during
operation. 
Finally 
simulation 
results
involving two wide body aircraft are
presented.
1
Introduction
In order to absorb the increasing air traffic
flows, the innovative concept of Free
Flight (“Safe and efficient flight operations
in which the aircraft have the freedom to
select their path and speed in real time”)
has been under study over the last years
[1]. The implementation of Free Flight has
been made possible by the emergence of
new navigation technologies such as GPS,
ADS-B, TCAS and of new onboard
computation capabilities [2]. Hence the
absolute position of an aircraft as well as
its short term intents can be communicated
to other aircraft in the neighborhood
through data links, while precise relative
positions can be computed on line. Then
aircraft should be able to realize relative
maneuvers such as minimum separation
crossings, mergings and meterings along
common tracks. In this communication,
the case of the convergence maneuver is
considered more particularly.
Time and cost optimization of aircraft
trajectories has been of great interest for
many decades and various numerical
solution techniques have been developed
[3-6]. However these techniques are not in
general 
compatible 
with 
an 
on-line
operation which is here a necessity since
the leading aircraft may modify at any
time its guidance parameters (speed,
heading and flight level) in accordance
with new atmospheric conditions (wind
and temperature) or following instructions
issued by ATC. On the other hand, simple
proportional 
navigation 
techniques,
developed for missile homing, provide
direct solutions to a similar problem [7-8].
However air transportation regulations
(load factor limitations and standard
maneuvers) 
as 
well 
as 
economical,
structural and comfort considerations,
prevent their utilization in the case
considered in this study [9]. The control
strategy proposed in this communication is
adaptive and makes use of a neural
network structure to get an on line
approximation of the optimal trajectory
associated to the current relative situation
[10].
M. Shahzad, F. Mora-Camino, J.. Slama and K. Achaibou
193.2
In section 2, the minimum time
optimization 
problem 
considered 
is
displayed and analyzed. It is shown in
section 3 that the adoption of a simplified
flight mechanics model for its formulation
allows 
the 
analysis 
and 
subsequent
characterization of the optimal trajectory
in terms of turns and straight line
segments.
Then in section 4 the synthesis of the
neural approximator of optimal trajectories
is discussed. A selected set of initial
situations 
to 
cover, 
through 
neural
generalization, a region corresponding to
10 minutes of flight.
In section 5, simulation results of the
proposed approach for different situations
are displayed.
2
Problem Formulation and
Conditions of Optimality
In the case considered, a pursuer aircraft
(P) is attempting to follow a leader aircraft
(L). Both aircraft are supposed to keep
their speed constant until the completion
of the maneuver which is characterized by
the final conditions :
- 
the velocity vector of the pursuer
aircraft is parallel to the leader
aircraft’s velocity,
- 
the pursuer has reached the same route
as the leader,
- 
the pursuer is at a given distance D ≥
dmin from the leader.
The geometry of the convergence is shown
in Fig. 1 and the equations of motion, in
relative polar co-ordinates, are [9] :
   
(
)
(
)
P
P
L
L
V
V
d
ψ
θ
ψ
θ
−
−
−
=
cos
cos
!
   (1)
(
)
(
)
{
} d
V
V
P
P
L
L
ψ
θ
ψ
θ
θ
−
+
−
−
=
sin
sin
!
      (2)
P
P
r
=
ψ!
      (3)
where VL and VP are the speeds of the
leader 
and 
of 
the 
pursuer 
aircraft
respectively, d(t) is the instantaneous
separation between the two aircraft, ψL and
ψP are their headings, θ is the line of sight
angle. θ, ψL, and ψP are measured with
respect to a common earth reference.
The minimum time convergence trajectory
is then solution of the optimization
problem :
minimize ∫
ft
dt
0
 with (1), (2), (3) with the
constraints :
max
min
φ
φ
φ
≤
≤
P
      (4)
  
0
min
≤
−d
d
      (5)
Figure 1. Representation of relative positions.
P
L
ψ
θ
ψL
VL
VP
x
d
y
TRAJECTORY GENERATION AND DISPLAY FOR FREE FLIGHT
193.3
the initial conditions :
( )
0
0
d
d
=
 with 
min
0
d
d ≥
( )
0
0
θ
θ
=
,  
( )
0
0
P
P
ψ
ψ
=
     (6)
and the final conditions of convergence :
( )
L
f
P t
ψ
ψ
=
,  ( )
L
ft
ψ
θ
=
  
  ( )
D
t
d
f =
           (7)
Here the time t is the independent variable
and 
the 
control 
variable 
is 
the
instantaneous rate of change of heading
the Pursuer, rP, which is associated to the
bank angle, φ, during a zero side-slip turn
by the following relation :
φ
tan
⋅
=
P
P
V
g
r
     (8)
The 
Hamiltonian 
for 
this 
dynamic
optimisation problem is given by [11] :
(
)
(
)
(
)
{
}
(
)
(
)
{
}
(
)
d
d
r
d
V
V
V
V
r
d
H
P
P
P
L
L
P
P
L
L
d
P
d
P
−
+
+
−
+
−
−
+
−
−
−
+
=
min
sin
sin
cos
cos
1
,
,
,
,
,
,
µ
λ
ψ
θ
ψ
θ
λ
ψ
θ
ψ
θ
λ
λ
λ
λ
ψ
θ
ψ
θ
ψ
θ
    (9)
where λd, λθ et λψ are adjoint variables
associated to the state variables d, θ et ψ.
In order to take into account the constraint
of minimum separation an influence
variable, µ, is introduced:
0
≥
µ
if
(
)
0
min
=
−d
d
    (10)
0
=
µ
if
(
)
0
min
<
−d
d
The necessary conditions of optimality are
defined by Euler-Lagrange equations :
(
)
(
)
{
}
µ
ψ
θ
ψ
θ
λ
λ
θ
+
−
+
−
−
=
P
P
L
L
d
V
V
d
sin
sin
2
!
   (11)
(
)
(
)
{
}
(
)
(
)
{
}
P
P
L
L
d
P
P
L
L
V
V
V
V
d
ψ
θ
ψ
θ
λ
ψ
θ
ψ
θ
λ
λ
θ
θ
−
+
−
−
−
−
+
−
−
−
=
sin
sin
cos
cos
!
   
     (12)
(
)
{
}
(
)
P
P
d
P
P
V
V
d
ψ
θ
λ
ψ
θ
λ
λ
θ
ψ
−
+
−
=
sin
cos
!
     (13)
with the final conditions of adjoint
variables :
( )
θ
θ
ν
λ
=
ft
, 
( )
ψ
ψ
ν
λ
=
ft
, 
( )
d
f
d t
ν
λ
=
  (14)
where νθ , νψ and νd are the constants
which must be specified in order to satisfy
final conditions of the state variables.
The above system of equations should be
solved numerically in order to get desired
minimum time trajectories. Anyhow, by
interpreting the optimality conditions, H
can be written as :
(
)
P
d
P
r
d
H
H
ψ
θ
λ
λ
λ
ψ
θ
+
=
,
,
,
,
     (15)
the minimization of H leads to the
conditions :
if 
0
* >
ψ
λ
 then 
min
*
φ
φ =
P
,
if 
0
* <
P
λ
 then 
max
*
φ
φ =
P
.
    (16)
The case where 
0
* =
ψ
λ
 is more complex to
analyse, however this singular situation
can be clarified through the manipulation
of the optimality conditions [11], leading
to the conclusion that when 
0
* =
ψ
λ
 then
0
* =
P
φ
 and ψP remains constant.
3
Characterisation of Minimum Time
Convergence Trajectories
The optimality conditions obtained in the
previous section show that a constant
speed time-optimal convergence trajectory
consists of a sequence of maximum bank
angle turns (right or left) linked by straight
line segments.
M. Shahzad, F. Mora-Camino, J.. Slama and K. Achaibou
193.4
Figure 2. Parametric representation of a regular trajectory.
A trajectory composed of a sequence
of pairs of straight line segments and
maximum bank angle turns is here called
“regular trajectory” and is said to be of
order n if it contains (n – 1) such pairs. An
example of a regular trajectory of order 4
is represented in figure 2. This class of
trajectory can be parameterized by a
sequence of triplets (εi, θi, li), i = 1 to n –
1, where :
- 
εi gives the direction of the turn (εi =
+1 : left turn, εi = -1 : right turn,
according 
to 
trigonometric
orientation),
- 
θi is the absolute value of the turn
angle realised at a nominal value of the
bank angle,
- li is the length of ith straight line segment.
A 
minimum 
time 
regular 
trajectory
satisfying initial constraints, convergence
constraints as well as minimum separation
constraints is solution of the optimization
problem :
(
)
(
)
∑
−
=
+
−
=
1
1
min
,
,
1
1
min
n
k
k
k
l
R
l
n
à
i
i
i
i
θ
θ
ε
 with
0
≥
il
,
0
≥
iθ
, 
1
±
=
iε
i = 1 à n-1
     (17)
with the following constraints :
- 
initial state : 
P
n
x
x
0
=
,
P
n
y
y
0
=
and  
P
n
0
ψ
ψ =
    (18)
- 
final convergence :
 
(
)








=
=
−
+
+
=
∑
−
=
L
n
k
k
k
L
y
D
R
l
x
x
ψ
ψ
θ
α
1
1
1
1
min
1
0
)
0
(
    (19)
with
P
L V
V
=
α
 and 
0
)
0
(
=
Lx
- 
minimum separation : 
min
d
d ≥
    (20)
This last constraint is expressed according
to the value of the nth minimum separation
time 
*
nT  given by :
•
•
•
•
•
initial position of
the pursuer
ψ3
l3
M4(x4, y4)
θ1
y
x
initial position
of the leader
M3(x3, y3)
M2(x2, y2)
M1 (x1, y1)
θ3
θ2
l2
l1
final position
of the leader
final position of
the pursuer
ψ4
ψ2
ψL
TRAJECTORY GENERATION AND DISPLAY FOR FREE FLIGHT
193.5
(
)
(
)(
)
(
)
(
)
(
)
n
P
L
n
P
n
n
n
n
L
n
P
n
L
n
n
n
n
n
V
V
V
R
l
y
V
V
x
R
l
x
T
ψ
ψ
ψ
θ
ψ
ψ
θ
2
2
2
min
1
min
*
cos
sin
cos
sin
sin
+
−
+
+
+
−
−
+
+
−
=
−
         (21)
1)
if 
0
* ≤
nT
 then 
(
)
(
)
(
)
(
)
min
2
min
2
1
min
cos
sin
d
R
l
y
x
R
l
x
n
n
n
n
n
L
n
n
n
n
≥
+
+
+
−
+
+
−
ψ
θ
ψ
θ
    (22)
2)
if 
S
n
n
V
l
T ≥
*
 then (
)
( )
min
2
2
d
y
x
x
n
n
L
n
≥
+
−
      (23)
3)
if 
S
n
n
V
l
T <
<
*
0
 then
(
)
(
)
(
)
(
)
(
)
(
)(
)
(
)
(
)
(
)
2
min
2
2
2
min
1
min
2
min
2
1
min
cos
sin
cos
sin
sin
cos
sin
d
V
V
V
R
l
y
V
V
x
R
l
x
R
l
y
x
R
l
x
n
P
L
n
P
n
n
n
n
L
n
P
n
L
n
n
n
n
n
n
n
n
n
L
n
n
n
n
≥
+
−
+
+
+
−
−
+
+
−
+
+
+
−
+
+
−
−
ψ
ψ
ψ
θ
ψ
ψ
θ
ψ
θ
ψ
θ
      (24)
From 
the 
point 
of 
view 
of
Mathematical Programming this problem
presents major difficulties :
- 
it is a mixed variable programming
problem (εi are binary variables while
angles θi and lengths li are real positive
variables),
- 
the admissible domain generated by
the different constraints is non convex
and its complexity grows explosively
with an increasing value of n,
- 
the minimum separation constraints
depend on logical conditions.
The only exact method which seems
applicable here is Dynamic Programming
[12] and only in the forward direction
(initial conditions to final convergence)
because 
of 
constraints 
of 
minimum
separation which destroy the property of
separability 
and 
sequenciability 
of
problem. 
Methods 
of 
stochastic
optimisation like genetic algorithms [13]
can also be considered to solve the
problem numerically. In the case where an
on line and on board resolution of this
problem is pursued, it is clear that such
numerical solution approaches cannot be
considered.
It 
appears 
then 
interesting 
to
investigate the techniques of Artificial
Intelligence such as :
- 
Expert Systems [14] which can make
use of a base of rules dedicated to the
generation of time 
efficient 
and
admissible convergence trajectories
through guidance directives.
- 
Neural Networks which can memorise
the parameters of minimum time
convergence trajectories and produce
from them, interpolated trajectories.
This last approach is adopted here.
4
Reverse Dynamic Programming
and Neural Restitution of Convergence
Trajectories
Since the Leader may modify at any time
its guidance parameters (speed, heading
and flight level) in accordance with new
atmospheric 
conditions 
(wind 
and
temperature) or following instructions
issued by the traffic control service, on
line trajectory generation is required here.
Considering 
the 
complexity 
of 
the
problem, it appears impracticable to get
optimal trajectories in real time. However,
the nature of the convergence maneuver
imply the need to dispose at any time of
guidance 
directives 
which 
can 
be
immediately displayed to the pilot or taken
into account by the autopilot. A neural
network fulfils this requirement as it can
be trained to memorize input-output
relationships for a system and afterwards
can be used as an interpolator to generate
outputs corresponding to current inputs. In
fact since the early 1990s, neural networks
have been used in a variety of applications
and there has been a growing interest in
M. Shahzad, F. Mora-Camino, J.. Slama and K. Achaibou
193.6
Figure 3. Reverse generation of regular convergence trajectories.
using neural networks to solve optimal
guidance problems [15].
Then appears the problem of generation of
training data for a neural structure. This
point is tackled here using a reverse
Dynamic Programming approach.
If a problem identical to the minimum time
regular trajectory optimization problem,
except that initial relative conditions are
not prefixed (relation 18), is considered, it
is possible to use in a simple way Dynamic
Programming in the reverse direction to
generate in a sequential manner a set of
points (
)
P
P
P y
x
0
0
0
,
,
ψ
 which start at the final
point of convergence and are  reached
through a n order regular trajectory.
Here possible headings and lengths of the
straight line segments are discretized
(
(
) θ
θ
∆
−
=
1
k
k
, 
k 
= 
1 
to 
N 
and
(
) l
h
lh
∆
−
=
1
, h = 1 to M). The structure of
the 
proposed 
iterative 
algorithm 
to
generate such points is given in figure 3.
The set of generated trajectories is
represented by a tree in ℜ3 with root at
(-D, 0, ψL).
The next figure provides a view of the
convergence area obtained by reverse
Dynamic Programming.
Iteration with respect to the
trajectory order : n = 2 to n
Iteration
with
respect to :
εn = ± 1
S0 = {(-D, 0,
n = 1
nmax
Sn = Sn-1
Generation of a new point
(
)
n
kh
n
kh
n
kh Y
X
ψ
,
,
Verification of the separation
constraint
If point is already stored, selection of
the minimum time trajectory
Storage of its parameters and
max
n
S
TRAJECTORY GENERATION AND DISPLAY FOR FREE FLIGHT
193.7
Figure 4. Representation of the convergence area.
Figure 5. The feedforward structure of the adopted neural networks.
So, a data base can be made available
for the training of a neural structure which
will provide a solution to the original
problem each time a convergence situation
is proposed.
The reverse Dynamic Programming
generation of convergence trajectories
provides input/output pairs composed of :
Outputs : the relative initial position
and heading of the Pursuer.
Inputs : 
the 
parameters 
of 
the
minimum time convergence trajectory.
The general structure of the neural
networks 
adopted 
here 
is 
of 
the
feedforward class  [16] and is shown in
figure 5.
5
Simulation Results
A simulation study has been performed
considering two Airbus A300 aircraft. It
has been supposed that after the beginning
of the convergence maneuver, the Leader
aircraft makes a right turn to take a new
constant heading. The guidance system of
the Pursuer makes use of a neural
trajectory generator to define, every
second, new references (either a turn rate
or a constant heading) for the autopilot.
The guidance laws implemented in its
autopilot are classical superposed PID
loops (a fast piloting loop and a slower
guidance 
loop) 
similar 
to 
those
encountered in aircraft of this class [17].
inputs
output
Neural networks
∆x
∆y
∆
M. Shahzad, F. Mora-Camino, J.. Slama and K. Achaibou
193.8
Simulation results are shown in Fig. 6a
and 6b. Initial position of the Leader is
taken as coordinate (0, 0) with a heading
of 90o. The Pursuer is initially at 40 km
behind and 40 km North of the Leader,
with an absolute heading of 90o. In the
case of Fig. 6a, it is assumed that the
Pursuer has no knowledge of the Leader’s
flight plan. With the activation of the
relative guidance mode, the Pursuer makes
an initial right turn and starts convergence.
When the Leader modifies its heading to
135o, the Pursuer changes progressively its
own heading and then after convergence
turns right to follow the Leader. This
results in a very swaying trajectory, which
is much undesirable in ATC standards.
While in the case of Fig. 6b, the Pursuer
knows exactly the intent of the Leader so,
the pursuit trajectory can be generated
taking into account the final route of the
Leader. In the second case, the Pursuer
avoids excessive maneuvering while the
convergence time is much smaller than in
the previous case.
6
 Perspective
The 
proposed 
approach 
allows 
the
development of a new on board system
whose function can be :
- 
to provide directives to an on board
guidance system such as a Flight
Director operating in a “Relative
Guidance” mode when the aircraft is
under manual control,
- 
to provide references for the autopilot
operating in a “Relative Guidance”
mode when the aircraft is under its
control. In this case, this function is
very similar with other functions
already available on advanced flight
management systems.
- 
to visualize the convergence trajectory
in real time on a navigation screen,
with a display such as the one
suggested in figure 7.
Fig. 6b. Simulation with Leader’s intent
      information.
Fig. 6a. Simulation without Leader’s intent
      information.
TRAJECTORY GENERATION AND DISPLAY FOR FREE FLIGHT
193.9
Figure 7. Presentation of a proposed or planned convergence maneuver to the pilot.
- 
to transmit the intentions of the
Pursuer (convergence trajectory) to the
Air Traffic Control system so that it
can validate the convergence maneuver
and integrate it into the traffic.
References
[1] RTCA Inc, Report of the RTCA Board of
Director’s Select Committee on Free Flight,
Washington, 1994.
[2] Krozel, J, and Peters, M, Conflict Detection
and Resolution for Free Flight, Air Traffic
Control Quarterly Journal, Special Issue on
Free Flight, 1997.
[3] Slattery, R and Zhao, Y, Trajectory Synthesis
for Air Traffic Automation, Journal of
Guidance, Control, and Dynamics, Vol. 20(2),
pp 232-238, 1997.
[4] Shapiro, I, and Ben-Asher, J Z, Near-Optimal
Horizontal Trajectories for Autonomous Air
Vehicles, Journal of Guidance, Control, and
Dynamics, Vol. 20(4), pp 735-741, 1997.
[5] Grimm, W, and Hans, M, Time-Optimal Turn
to a Heading: An Improved Analytical
Solution, Journal of Guidance, Control, and
Dynamics, Vol. 21(6), pp 940-947, 1998.
[6] Betts, J T, Survey of Numerical Methods for
Trajectory Optimization, Journal of Guidance,
Control, and Dynamics, Vol. 21(2), pp 193-
207, 1998.
[7]  Guelman, M and Shinar, J, Optimal Guidance
Law in the Plane, Journal of Guidance,
Control, and Dynamics, Vol. 7, No. 4, pp 471-
476, 1984.
[8] Yuan, 
Pin-Jar, 
Optimal 
Guidance 
of
Proportional Navigation, IEEE Transactions
on Aerospace and Electronic Systems, AES-
33, Vol. 33(3), pp 1007-1011, 1997.
[9] Hale, 
F 
J, 
Introduction 
to 
Aircraft
Performance, Selection and Design, Wiley,
New York, 1984.
[10] Shahzad, M, Slama, J G, and Mora-Camino, F,
A New Approach for the Automation of
Relative 
Guidance 
of 
Aircraft, 
13th
International 
Conference 
on 
Systems
Engineering, Las Vegas, USA, Aug. 1999.
[11] Bryson, A E, and Ho, Y C, Applied Optimal
Control, Hemisphere Publishing Corporation,
Washington, D.C., 1969.
[12] Bellman, R, Dynamic Programming, Princeton
University Press, Princeton, NJ, 1957.
[13] Goldberg, D E, Genetic Algorithms in Search,
Optimization and Machine Learning, MA
Addison Wesley, 1989.
[14] Farreny, H, Les Systèmes Experts : Principes
et Exemples, Cepadues-Editions, Toulouse,
France.
[15] Youmans, E A, and Lutze, F H, Neural
Network Control of Space Vehicle Intercept
and Rendezvous Maneuvers, Journal of
Guidance, Control, and Dynamics, Vol. 21,
No. 1,  pp 116-121, 1998.
[16] Demuth, H, and Beale, M, MATLAB Neural
Network Toolbox, Math-Works Inc., Natick.
MA, 1994.
[17] Mora-Camino, F, Systèmes de Conduite
Automatique et de Gestion du Vol, Ecole
Nationale de l’Aviation Civile, 1995.
1
20
30
AF 332
285
AF 332
40 NM
5min20
BOL
50 NM
18h52
predicted
F PLAN
predicted
convergenc
e data