Behavioral Learning of Aircraft Landing
Sequencing Using a Society of Probabilistic Finite
State Machines
Jiangjun Tang∗ and Hussein A. Abbass†

arXiv:1802.10203v1 [cs.NE] 27 Feb 2018

School of Engineering and Information Technology, UNSW-Canberra, Canberra, Australia
∗ Email: j.tang@adfa.edu.au
† Email: h.abbass@adfa.edu.au
Abstract—Air Traffic Control (ATC) is a complex safety critical
environment. A tower controller would be making many decisions
in real-time to sequence aircraft. While some optimization tools
exist to help the controller in some airports, even in these
situations, the real sequence of the aircraft adopted by the
controller is significantly different from the one proposed by the
optimization algorithm. This is due to the very dynamic nature
of the environment.
The objective of this paper is to test the hypothesis that one can
learn from the sequence adopted by the controller some strategies
that can act as heuristics in decision support tools for aircraft
sequencing. This aim is tested in this paper by attempting to learn
sequences generated from a well-known sequencing method that
is being used in the real world.
The approach relies on a genetic algorithm (GA) to learn these
sequences using a society Probabilistic Finite-state Machines
(PFSMs). Each PFSM learns a different sub-space; thus, decomposing the learning problem into a group of agents that need
to work together to learn the overall problem. Three sequence
metrics (Levenshtein, Hamming and Position distances) are
compared as the fitness functions in GA. As the results suggest,
it is possible to learn the behavior of the algorithm/heuristic that
generated the original sequence from very limited information.

I. I NTRODUCTION
To find optimal landing sequences for arrival aircraft is an
NP-hard problem when the constraints of spacing between
arrivals depend on aircraft types and other conditions [1]. The
First-Come-First-Served (FCFS) heuristic has been used as
the most common approach for sequencing aircraft [2]. FCFS
simply schedules the landing aircraft based on the Estimated
Time of Arrival (ETA) at the runway and the minimum
separation time between two consecutive aircraft as listed in
Table I.
Trailing Aircraft
Heavy
Large
Small
Heavy
96
157
196
Large
60
69
131
Small
60
69
82
TABLE I
M INIMUM TIME SEPARATION ( IN SECONDS ) BETWEEN LANDINGS AND
MANDATED BY FAA [3]
Leading Aircraft

FCFS schedule is easy to be implemented, and it maintains
a sense of fairness. However, the landing efficiency in terms
of runway throughput can’t be guaranteed by FCFS when

unnecessary spacing requirements exist. Therefore, many aircraft landing sequencing approaches have been proposed and
automation tools have been deployed in the operational environment to increase the efficiency of the system by maximizing
runway throughput while maintaining safety.
Constrain Position Shifting (CPS) [4] is a common approach
in practice, which shifts an aircraft forward or backward in the
FCFS schedule by a specified maximum number of positions
in order to achieve a landing sequence with the smallest time
span. These approaches show some advantages over FCFS,
such as providing the Air Traffic Controller (ATC) with additional flexibility and decision support plots to predict landing
times and positions [5]. However, they increase ATC-Pilot
communication and controller workload. Therefore, a mixed
approach combining FCFS and aircraft shifting methods can
be a better option in the operational environment for tradingoff efficiency and ATC-pilot communications. Sequencing of
aircraft landing by ATC is a more complex procedure in the
real world. Many factors can come into play including weather
conditions, emergency situations, and even the personality and
experience of an ATC [6]. Any mistake made for aircraft
landing sequencing can cause critical safety risks in aviation.
Our previous work looked at the risk assessment of aircraft
landing sequencing algorithms [7]. Some critical issues were
recognized by approaches based on the Computational Red
Teaming (CRT) [8] concept. The previous work was not concerned with learning the behaviors that generated a sequence.
CRT usually starts with no or limited knowledge about the
object to be challenged at the beginning. The behavior of an
object needs to be learned by CRT through observations. In
order to understand aircraft landing sequencing behavior and
then provide some assessments, a methodology is needed to
learn and model the behavior, which can enable us to apply
CRT to challenge it specifically and thus, improving it.
In this paper, we present a stochastic approach combined
with a Probabilistic Finite-state Machine (PFSM) [9] and Genetic Algorithm(GA) [10] to represent and learn the behavior
of aircraft landing sequencing. We developed a simulator for
simulating this type of behavior, where either FCFS and CPS
operate on aircraft landing sequencing in order to balance
runway efficiency and ATC-pilot communications. The current
simulator considers some traffic conditions including mixed

Copyright c 2014 IEEE. J. Tang and H. A. Abbass, ”Behavioral learning of aircraft landing sequencing using a society of Probabilistic Finite state
Machines,” 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, 2014, pp. 610-617. doi: 10.1109/CEC.2014.6900597

aircraft types and their ETA sequence.
A Finite-state Machine (FSM) has been widely used as
a representation in many domain of applications such as,
behavioral modelling in simulating autonomous entities [11],
machine learning [12], and pattern recognition [13]. It has also
been applied with Evolutionary Computation for solving various problems [14] [15] [16]. In our approach, PFSM is used
to simulate the behavior for sequencing landing aircraft and
then GA improve it by evolving the transition probabilities for
generating aircraft landing sequences with high similarity to
the targeting landing sequencing from the behavior simulator.
In our approach, the similarity is measured by three sequence
metrics: Levenshtein [17], Hamming [18] and Position based
distances. GA is applied to each of them to evolve PFSM.
A comparison among the metrics is conducted for finding a
better measurement.
This paper is organized as follows. The behavior simulator
and problem definition of aircraft landing sequencing are
described in Section II. This is followed by the proposed
methodology and the three metrics for learning and modelling
the behavior. Finally, the experimental results are presented
for both training and testing.

The objective of this paper is to present an approach
for learning and modelling the behavior of this simulator
using a Probabilistic Finite-state Machine (PFSM) and Genetic
algorithm (GA). The methodology assumes knowledge of the
following information:
• the original arrival aircraft sequences(A1 , A2 , . . . , Am )
and
their
corresponding
wake
turbulence
(W1 , W2 , . . . , Wm ), and
• a new sub-sequences generated by either CPS or FCFS.
These optimized sub-sequences are used to train the
algorithm. (training set).
However, the algorithm doesn’t know any of the following
information:
• The intents of the behavior; that is, whether the objective
is to minimize or maximize the time span for landing all
arrival aircraft,
• the underlying mechanism/algorithm being used for sequencing aircraft landing,
• the threshold that was used to select either CPS or FCFS,
and
• the minimum separation requirements for different wake
turbulence.

II. P ROBLEM D EFINITION AND A IRCRAFT L ANDING
S EQUENCING SIMULATOR

III. M ETHODOLOGY

Given aircraft arrival sequence A(a1 , a0 , . . . , an ) and their
corresponding wake turbulence W (w1 , w2 , . . . , wn ), aircraft
landing sequence A0 (a01 , a00 , . . . , a0n ) can be scheduled by
some approach in order to maximize/minimize certain objectives, e.g. increasing runway throughput and maintaining
safety. The wake turbulence of aircraft is classified into three
catalogs: Heavy (H), Light (L), and Small (S). The minimum
separation is defined in Table I and is required to constrain
the inter-landing time of two subsequent aircraft.
According to the minimum separation requirements and
given sequences (A) and wake turbulence (W ), CPS can search
for and construct a sequence with the minimum time span for
the landing of all aircraft. Sometimes the re-scheduled aircraft
landing sequence (A0 ) is not necessarily better than the FCFS
sequence (A) [7]. The data used in the simulator represent
peak time data; that is, the intervals between every two aircraft
estimated time of arrival (ETA) is always less than 1 minute.
This inter-arrival time constraints the schedule because it is
mostly less than the minimum separation requirement. 1-CPS
is used in the simulator, which means aircraft position can be
shifted forward or backward by 1 position only. If a time span
of an aircraft landing sequence (A0 ) from CPS is better than
the FCFS sequence (A) by a certain level, the CPS sequence
(A0 ) is used otherwise the FCFS sequence (A) is used.
In summary, the aircraft landing sequencing simulator
takes a number of aircraft arrival sequence (A1 , A2 , . . . , Am )
with associated wake turbulence (W1 , W2 , . . . , Wm ) and
generates a number of new aircraft landing sequencing
(A01 , A02 , . . . , A0m ) using a combination of CPS and FCFS
actions in order to balance efficiency and ATC-pilot communications.

A. Probabilistic Finite-state Machine
A Probabilistic Finite-state
Machine (PFSM) can be defined
P
as a tuple A = (QA , , δA , IA , FA , PA ) [13], where
• QA is a finite set of states;
P
•
is a finiteP
input alphabet;
• δA ⊆ QA ×
×QA is a set of transition;
+
• IA : QA → R is the initial-state probabilities;
+
• PA : δA → R is the transition probabilities;
+
• FA : QA → R is a set of acceptable states.
IA , PA and FA are functions as below:
P
q∈QA IA (q) = 1
and
∀q ∈ QA , FA (q) +

P

a∈

P 0
,q ∈QA

PA (q, a, q 0 ) = 1

Our approach manipulates the aircraft landing sequence
according to only two known inputs: (A1 , A2 , . . . , Am ) and
their wake turbulence (W1 , W2 , . . . , Wm ). Here, the sequence
of mixed wake turbulence is the only meaningful information
of traffic conditions. In order to utilize it, a PFSM can be
constructed by taking each combination of wake turbulence as
a state(Q), whose immediate next states are all permutations of
this wake turbulence combination. The transitions δ between
them are governed by a set of given probabilities(P ). However,
the total number of states will be 3n ; given that there are
three wake turbulence types and n aircraft in a sequence. The
computation cost for evaluating and evolving such kind of
PFSM increases exponentially when the number of aircraft
increasing.
Instead of building a very complex PFSM containing all
permutations as states, we construct a number of smaller

S

p 1,1

HLS

p 1,7

p 1,3

HSL

p 1,2

p 1,8

p 1,13

p 1,9 p 1,14

LHS

p 1,4

p 1,6

p 1,15

p 1,19

p 1,12

p 1,18

p 1,10

p 1,20

p 1,17

p 1,5

p 1,33

p 1,27

p 1,21 p 1,16

p 1,25

p 2,1

p 1,11 p 1,26

p 2,9
p 2,3

p 1,36

SLH

S

p 1,30 p 1,35

p 1,24

p 1,34

SHL

p 1,23

LSH

p 1,31

p 1,32

p 1,29

p 1,28

p 2,8

HHL
p 2,5
p 2,2

p 1,22

LHH

E

p 2,7
p 2,4

p 2,6

HLH
E

(a) PFSM1: three aircraft with three wake turbulence (H,L, and S)

(b) PFSM2: three aircraft with two wake turbulence (H and L)

Fig. 1. Two examples of PFSM for scheduling a sub-sequence of landing aircraft with different wake turbulence (H: Heavy, L: Large, and S: Small). pi,j is
the transition probabilities, i is the index of a PFSM, and j is the index of a probability.

PFSMs. Each of them contains a group of related permutations
(as states) containing the same wake turbulence types. Therefore, we decompose the aircraft sequence into a set of subsequences with length of 3. We use this short length to capture
the number of wake turbulence types. There is a total of 27
combinations that can be generated, but three of them (“HHH”,
“LLL”, “SSS”) is not necessary to be included into the PFSM.
This is mainly because regardless of the sequencing algorithm
being used, the wake turbulence constraint is inactive for these
sequences. Hence, a total of 7 PFSMs are constructed as listed
in Table II.
PFSM
PFSM1
PFSM2
PFSM3
PFSM4
PFSM5
PFSM6
PFSM7

States (permutations)
Number of Transitions
HLS, HSL, LHS, LSH, SHL, SLH
36
HHL, LHH, HLH
9
HHS, SHH, HSH
9
LLH, HLL, LHL
9
LLS, SLL, LSL
9
SSH, HSS, SHS
9
SSL, LSS, SLS
9
TABLE II
P ROBABILISTIC F INITE - STATE M ACHINES BASED ON WAKE TUBURLANCE

Figure 1 depicts two examples of the PFSMs (PFSM1 and
PFSM2). Figure 1(a) presents a PFSM for an aircraft sequence
with three aircraft and each of them belongs to one wake
turbulence. Another example of three aircraft with only two
turbulence types H and L is presented in Figure 1(b). The
structure of other PFSMs with only two aircraft turbulence
types is similar.
As shown in the figures, There are no probabilities associated with the transitions between an initial state and its next
states or between a state and the end state. In effect, this means
that there are multiple initial states and multiple end states.
The use of a single start and end state in the representation is
mainly for convenience.

The different proposed PFSMs work together on a given
arrival aircraft sequence to generate an aircraft landing sequence by Algorithm 1. The parameter s defines the number
of aircraft in a temporary sequence that can be saved into the
final aircraft landing sequence.

Algorithm 1 Aircraft landing sequencing by PFSM
1: {Input: arrival aircraft sequence (A(a1 , a2 , . . . , an )) with wake turbulence
(W (w1 , w2 , . . . , wn ))}

2: Initial a empty sequence A00
3: Create two empty lists of T empA and T empW
4: Initial a integer step s, (∈ [1, 3])
5: Get the first three aircraft (a1 , a2 , a3 ) and their (w1 , w2 , w3 )
6: if w1 ≡ w2 ≡ w3 then
7:
Put (a1 , a2 , a3 ) into a new sequence S
8: else
9:
Select a F P SMk has a state of (w1 , w2 , w3 )
10:
F P SMk generate a new sequence of S
11: end if
12: Put the first s aircraft of S into A00
13: Put the rest aircraft into T empA and the associated wake turbulence into T empW
14: for i = 3 to n step 1 do
15:
if length of T empA (l) ≡ 3 then
16:
if all wake turbulenc in T empW are same then
17:
Put T empA into a new sequence of S
18:
else
19:
Select a F P SMk has a state of T empW
20:
F P SMk generate a new sequence of S
21:
end if
22:
Empty T empA and T empW
23:
Put the first s aircraft of S into A00
24:
Put the rest aircraft of S into T empA and the associated wake
turbulence into T empW

25:
else
26:
Add ai to the end of T empA and wi to the end of T empW
27:
end if
28: end for
29: if length of T empA (l) > 0 then
30:
Move the last (3 − l) aircraft from A00 and add them into T empA
31:
Add the related wake turbulence into T empW
32:
Select a F P SMk has a state of T empW
33:
F P SMk generate a new sequence of S
34:
Put the whole sequence S at the end of A00
35: end if

Let us take an example. Assume a sequence of “HSLH”, the
first three aircraft “HSL” will be input to PFSM1 and generate
a new sequence. Assume that the output from PFSM1 is SHL
because the transition probability, p1,11 , between HSL and
SHL is the largest transition probability in the learnt model
(i.e. a maximum likelihood approach). If the step (s) is defined
as 1, then the first aircraft (S) is pushed into a new sequence
(A00 ), and the rest of the aircraft HL and the forth aircraft
(H) in arrival sequence form a new temporary sub-sequence
“HLH”. Therefore, PFSM2 is selected. A final output is one
of “HLH”, “HHL”, and “LHH” based on the given transition
probabilities (p2,4 , p2,5 , and p2,6 ). Let us suppose that state
“HHL” is selected as the output of the second PFSM, and
let us assume that this is the last sub-sequence, this complete
sub-sequence is pushed to the end of A00 . In this way, a new
aircraft landing sequence (SHHL) is constructed.
As demonstrated by the example, the proposed PFSMs
and algorithm is capable of re-constructing aircraft landing
sequencing based only on the arrival sequence of aircraft and
their wake turbulence without any knowledge of the actual
decision module or algorithm being used to generate such
sequence.
Since this is a probabilistic approach, it is necessary to
develop an algorithm to learn the probabilities and as such,
guides the PFMS to learn the real decision module that was
used to generate that sequence. Before we discuss this algorithm, we need to discuss how two sequences are compared
to calculate a measure of merit or a similarity measure.

3) Position based Distance: The third distance used in this
paper is defined as the sum of the distances between the
position of an aircraft in the original position and the shifted
position of the same aircraft in the shifted position. Equation
1 describes the calculation of it.
P osD =

l
X

|Pi − Pi0 |

(1)

i=1

where l is the length of the sequence, Pi is the original position
of aircraft i in the original sequence, and Pi0 is the shifted
position in the shifted sequence. For the giving example, the
position distance is 10 (5 + 1 + 1 + 1 + 1 + 1) for the
two sequences “SLLHLH” and “LLHLHS” because the first
aircraft of ’S’ is shifted to the last position (i.e. distance is
5), then all other five aircraft are shifted to the left by a
single position. It is important to emphasize that because of
the redundancy in the alphabets, when a letter is checked,
it will be compared to the closest position it moved to. In
other words, the first “L” in the first sequence could be the
first, second or fourth “L” in the second sequence. We always
assume it is the closest encounter; as such, it is the first “L”
in the second sequence.
The Position based Distance is the most strict metric to measure the global similarity between two sequences regardless
of their local similarities. The Levenshtein Distance considers
is more local than the other two. The effect of different
metrics on evaluating our PFSM for learning the behavior and
modelling is investigated in Section IV.

B. Sequence Metrics
As the aircraft sequence can be transferred into a string
sequence of aircraft types, string metrics are a suitable measurement to evaluate the performance of the proposed PFSM
when learning and modelling of arrival aircraft sequencing
behavior. Here, we use three string metrics with different
biases as described below.
1) Levenshtein Distance: Levenshtein distance [17] measures the difference between two strings by the minimum
number of single character edits including insertions, deletions
or substitutions required to change one string into another. For
two given aircraft sequences “SLLHLH” and “LLHLHS”, the
Levenshtein distance of them is 2, which includes deleting the
first ’L’ and inserting an ’S’ at the end of the second sequence.
Therefore, the local optimal alignment between two sequences
is considered in Levenshtein distance.
2) Hamming Distance: Hamming distance [18] is a widely
used metric to compare two strings with equal length. In our
case, both original arrival sequence and shifted sequence have
equal length, therefore, it is a suitable measurement for our
PFSM. The Hamming distance is the minimum substitutions
required to change one string to another; in other words, it
is the number of mismatched characters between two strings.
It is classically used for binary domains, but it is a generic
metric independent of the size of the alphabet set. For example,
given two aircraft sequences of “SLLHLH” and “LLHLHS”,
the Hamming distance is 5.

C. PFSM Evolution
In our approach, Genetic Algorithm (GA) is used to train
our proposed PFSM to learn the behavior of aircraft landing
sequencing by evolving the transition probabilities.
The length of each chromosome is equal to the total number
of transitions (90) in all PFSMs as described before. The
locus in the chromosome is associated to a certain transition
probability in a certain PFSM. Each gene is a real number
with a lower boundary of 0 and an upper boundary of 100.
Each chromosome has 7 building blocks which are mapped
to the proposed 7 PFSMs respectively. The length of each
building block depends on the number of transitions in a PFMS
and they are varied, e.g. The length of the building block for
PFSM1 is 36 while the length of the building block for others
is 9. Each building block has several sub-building-blocks
associated with the transitions from one state to others. To
decode such a chromosome into the transitions probabilities,
a group of real numbers belonging to a sub-building-block is
converted into transition probabilities by normalization.
For example, nine probabilities (from p2,1 to p2,9 ) exist
in PFSM2 as shown in Figure 1(b). Therefore, there are
nine loci in a chromosome associated with this PFSM and
form one building block. This building block contains 3
sub-building blocks corresponding to the three groups of
transition probabilities: (p2,1 , p2,2 , p2,3 ), (p2,4 , p2,5 , p2,6 ), and
(p2,7 , p2,8 , p2,9 ). According to the definition of PFSM de-

scribed in Section III-A, the genes (g) on these loci are
normalized into transition probabilities satisfying:
p2,1 + p2,2 + p2,3 = 1
p2,3 + p2,5 + p2,6 = 1
p2,7 + p2,8 + p2,9 = 1
After determining the transition probabilities of PFSMs,
an aircraft landing sequence (A00 ) is produced by a given
aircraft arrival sequence (A). Then A00 is compared against the
corresponding landing sequences A0 from the aircraft landing
sequencing simulator by one of the string metrics (d) as
explained in the last section. As our PFMS is a scholastic
approach for aircraft landing sequencing, it requires multiple
evaluations of each chromosome to approximate the fitness:
1) Construct a PFSM by a chromosome
2) For each pair of given Ai and A0i
a) Generate an aircraft landing sequence (A00i,j ) by PFSM
with the input of Ai
b) Calculate the sequence metric: di,j = Dist(A00i,j , A0i );
c) Repeat Step a and b until a number (T ) of evaluations
researched;
d) Get the mode (Di ) from all di,j ;
3) Get the mode (D) from all Di as the fitness of the
chromosome.
From the above steps, the fitness of a chromosome can be
defined by Equation 2.
F = M odeni=1 (M odeTj=1 (Dist(A00i,j , A0i ))

(2)

Where, i is the index of a pair of aircraft arrival and landing
sequences in a given set, n is the total number of aircraft
sequences in a given set, j is the index of an evaluation for
a chromosome, and T is the total number of evaluations on
a chromosome. The function of Dist can be any one of the
three sequence metrics as mentioned above.
The objective of our GA is to minimize F . Binary tournament selection is used to choose parents and then Uniform
Crossover is applied for producing offspring. When the mutation happens, a random real number between 0 and 100
replaces the old gene. GA stops when a predefined number
of generations is reached.
IV. E XPERIMENT AND R ESULTS
A. Experiment Design
A total of 200 unique aircraft landing sequences (each
sequence has 20 aircraft) are generated randomly. They are all
being fed into the simulator. If the savings on the time span are
at least 5% time savings, the re-scheduled sequence from CPS
is saved otherwise FCFS is chosen. This is consistent with a
realistic operational environment constraints, where there is a
need to balance efficiency and ATC-pilot communications. The
first half of each sequence (100 aircraft) is used for training,
while the second half for testing.
A total of 90 transition probabilities is required to construct
all 7 PFSMs as explained in Section III-A.

GA is then used to evolve transition probabilities for training
the PFSM on the training set in order to learn and model
the aircraft landing sequencing behavior of the simulator. The
parameters used in GA is listed as follows:
• population size: 100
• number of generation: 1000
• crossover rate: 0.9
• mutation rate: 1/l, the reciprocal of the chromosome
length (l), which is 90 in this experiment.
• The initial generation initializes the chromosomes randomly from uniform distributions.
As we have three different sequence metrics for fitness
calculations, we run GA on each metric using ten different
seeds. The training results are presented in the next section.
After training, the best individual in the population is
selected from each of three metrics respectively and is tested
on the test set. The test results are provided in Section IV-C.
B. Training Results
The evolutions of our PFSM from three different sequence
metrics are shown in Figure 2. The first three illustrate the
average fitness values along the generations for three sequence
metrics respectively. Figure 2(d) is showing the comparison of
different sequence metrics.
As expected, the fitness derived from Levenshtein distance
has the lowest magnitude and the fitness from Position distance has the highest magnitude. The fitness from Position
distance shows the largest variations between runs as shown
in Figure 2(d).
Since each metric is providing different magnitudes, it can
happen that the best solution found by each metric appears to
be different in fitness, but it is actually the same in terms of
decision variables (i.e. probabilities). Therefore, we continue
the analysis by taking the best solution found by one metric in
each generation and evaluate it also on the other two metrics.
An example of the best solution found over all runs using
Leveshtein distance is presented in Figure 3. This solution is
also being evaluated on the other two metrics in the figure.
Although the fitness is based on Levenshtein distance, the
other two generally follow the same trend of the fitness function. One interesting point is that the fluctuations of Hamming
distance is quite similar to Position distance, although their
magnitudes are at different levels. Similar circumstances are
also found when we investigated the best runs from Hamming
distance or Position distance.
Since we are evaluating the same individual in the figure at
each generation, the fluctuations in the Levenshtein distance
is due to the stochastic nature of the solution. However,
clearly there are different sources causing different types of
fluctuations when this solution is evaluated on the other two
metrics. To isolate the two sources of fluctuations: those
because of stochastic representation and those because of the
metric itself, we measured the correlation coefficient between
the Levenshtein distance and other two. The correlation coefficient was 0.92 and 0.91 in relation to the Hamming and
Position distances respectively. This indicates that there is a

7.8

10.5

7.6

10

7.4

9.5

7.2
Fitness

Fitness

9
7
6.8

8.5
8

6.6
7.5

6.4

7

6.2
6
0

200

400

600

800

1000

6.5
0

200

400

Generations

17

18

16

16

15

14

14

10

12

8

400

1000

600

800

1000

Levenshtein
Hamming
Position

12

13

200

800

(b) Hamming distance

Fitness

Fitness

(a) Levenshtein distance

11
0

600
Generations

6
0

200

400

600

800

1000

Generations

Generations

(c) Position distance

(d) Comparison of metrics

Fig. 2. The process in average fitness values for all three sequence metrics along with generations

small amount of extra fluctuations that are due to the metrics
themselves.
Three best individuals in terms of their evaluated sequence
metrics from the 30 runs are selected and compared in
Table III.
Sequence Metrics
Levenshtein
Hamming
Position
4
6
10
4
4
12
4
6
6
TABLE III

Individuals

Fitness function

Ind Lev
Ind Ham
Ind Pos

Levenshtein
Hamming
Position

T HE FITNESS OF THE BEST INDIVIDUALS FOUND BY EVOLUTION USING
EACH METRIC AND BEING EVALUATED ON THE OTHER TWO SEQUENCE
METRICS .

The individual evaluated by Levenstein distance has a small
Hamming distance but a larger the Position distance as shown
in the first row in the table. The individual evaluated by
Position distance is also able to produce both small Levenshein
and Hamming distances as listed in the last row. However,
small Hamming distance can’t guarantee a small Position

distance as being demonstrated by the individual evaluated by
Hamming distance in the second row. These three individuals
listed in the table are also used for testing our approach using
the test set in the next section.
When looking at some specific aircraft landing sequencing,
we find that Levenshtein distance prefers to give low error
in two sequences when they have some local matching sequences. For example, “HHLSLLLSHHSLLSSSLHHL” and
“HHSLLLLSSHHSLLSSLHHL”, where Levenshtein distance
is 4 because there are three local sequence that are matched
between two sequence, which are “HH”, “LLLS”, and “SSLHHL”. However the Hamming distance is 6. But the Position
distance is 10 caused by the low global matching between
them.
C. Test Results
The aircraft arrival sequences in the test set is input to the
three individuals (PFSMs), Ind Lev, Ind Ham, and Ind Pos,
respectively. Each PFSM produces only one landing sequence
for a given arrival sequence using a maximum likelihood

Individuals
18
Levenshtein (Fitness)
Hamming
Position
16

Distances

12

mance in terms of high number of sequences below the given
errors for all three sequence metrics.
As demonstrated here, the PFSM approach is capable to
learn and model the aircraft landing sequencing behavior and
produce good matching landing sequences for the test data.

10

8

6
0

100

200

300

400

500
600
Generations

700

800

900

1000

Fig. 3. The best run of fitness calculated by Levenshtein distance and
evaluated also on the other two metrics measured on the same individuals

approach. The new landing sequence is compared against the
sequence from the simulator. Table IV presents the mode of
the test results from three sequence metrics for all three individuals. Similar to the training session, both individuals that
have been evaluated by the Hamming and Position distances
can produce small Levenshtein distance.
Individuals
Ind Lev
Ind Ham
Ind Pos

Sequence Metrics (mode)
Levenshtein
Hamming
Position
6
8
14
7
6
12
4
6
8
TABLE IV

T HE BEST INDIVIDUALS AND THEIR TEST RESULTS ON THREE SEQUENCE
METRICS

The distributions of distances on different sequence metrics
between the new sequences and the target sequence for each
individual are visualized as box charts in Figure 4. Overall,
all the distance distributions from these three individuals are
quite similar to each other in terms of means, 25th percentiles,
and 75th percentiles. The position distances produced by the
three individuals all have large variance but the variance of
Levenshtein distance are always smaller than the other two. As
illustrated in the chart, the individual evaluated by Hamming
distance has the lowest outlier.
The number of produced sequences from each individual
satisfying the following conditions are counted and listed in
Table V:

•
•

P osition ≤ 8
20
31
37

T HE NUMBER OF SEQUENCES FROM EACH INDIVIDUAL

14

•

Ind Lev
Ind Ham
Ind Pos

Number of Sequences
Levenshtein ≤ 6
Hamming ≤ 6
56
20
64
37
63
41
TABLE V

the Levenshtein distance is less than 6 representing the
mode of the Levenshtein distances of Ind Lev
the Hamming distance is less than 6 representing the
mode of the Hamming distances of Ind Ham
the Position distance is less than 8 representing the mode
of the Position distances of Ind Pos

As seen from the table, the individual evolved using Levenshtein distance performed worse than the other two. The
individual evolved using Position distance has the best perfor-

V. C ONCLUSION
In this paper, we proposed a stochastic approach combined
with PFSM and GA to learn and model aircraft landing
sequencing behavior. As the experiment results suggested, this
approach is capable to achieve the learning objective while
only knowing limited information.
Three different sequence metrics are used for the fitness
function in the GA. These metrics showed different preferences when evolving the transition probabilities of PFSM.
Levenshtein distance considers the local matching sequence
more than the other two, while the Position distance is more
strict in terms of global matching. Therefore, the fitness
values of Position distance shown in the training session are
more varied than the other two. All three metrics are able
to guide GA to find a set of good transition probabilities
for the proposed PFSM. However, the global metrics, e.g.
Position distance, has demonstrated the best results on the test
set, where it produced a higher number of aircraft landing
sequencing with lower errors than the other two. The results
show that the proposed approach is capable of learning the
underlying mechanism that generates a landing sequence.
In the future, we will introduce more uncertainty variables
such as weather conditions and emergency situations to disturb
the sequences during training. We will also investigate biased
initialization by relying on statistical estimation methods to
initialize the population in the GA instead of using a purely
random initialization approach. In general, learning the mechanism that generated a solution can contribute to many subfields in evolutionary computation including surrogate models,
simulation-based optimization, and fitness landscape analysis.
ACKNOWLEDGEMENT
This work has been funded by the Australian Research
Council (ARC) discovery grant number, DP140102590: Challenging systems to discover vulnerabilities using computational red teaming.
R EFERENCES
[1] X.-B. Hu and W.-H. Chen, “Genetic algorithm based on receding horizon
control for arrival sequencing and scheduling,” Engineering Applications
of Artificial Intelligence, vol. 18, no. 5, pp. 633–642, 2005.
[2] A. R. Odoni, J.-M. Rousseau, and N. H. Wilson, “Models in urban and
air transportation,” Handbooks in operations research and management
science, vol. 6, pp. 107–150, 1994.

25

20

distance

15

10

5

0
Levenshtein

Hamming

Position

Individual evaluated by Levenshtein

Levenshtein

Hamming

Position

Individual evaluated by Hamming

Levenshtein

Hamming

Position

Individual evaluated by Position

Fig. 4. Whisker-box plots for the test results on three sequence metrics from all three best individuals obtained from training.

[3] R. de Neufville and A. Odoni, Airport Systems: Planning, Design, and
Management, ser. Aviation Week Book. Mcgraw-hill, 2002. [Online].
Available: http://books.google.com.au/books?id=9khd5ns3kz4C
[4] H. Balakrishnan and B. Chandran, “Scheduling aircraft landings under
constrained position shifting,” in AIAA guidance, navigation and control
conference and exhibit, 2006.
[5] F. Neuman and H. Erzberger, Analysis of delay reducing and fuel saving
sequencing and spacing algorithms for arrival traffic. Citeseer, 1991.
[6] C. D. Wickens, A. S. Mavor, and J. P. McGee, Flight to the future:
Human factors in air traffic control. National Academies Press, 1997.
[7] W. Zhao, J. Tang, S. Alam, A. Bender, and H. A. Abbass, “Evolutionarycomputation based risk assessment of aircraft landing sequencing algorithms,” in Distributed, Parallel and Biologically Inspired Systems.
Springer, 2010, pp. 254–265.
[8] H. Abbass, A. Bender, S. Gaidow, and P. Whitbread, “Computational
red teaming: Past, present and future,” Computational Intelligence
Magazine, IEEE, vol. 6, no. 1, pp. 30–42, 2011.
[9] M. O. Rabin, “Probabilistic automata,” Information and control, vol. 6,
no. 3, pp. 230–245, 1963.
[10] D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine
Learning, ser. Artificial Intelligence. Addison-Wesley, 1989. [Online].
Available: http://books.google.com.au/books?id=3 RQAAAAMAAJ
[11] S. Donikian, “Hpts: A behaviour modelling language for autonomous
agents,” in Proceedings of the Fifth International Conference on
Autonomous Agents, ser. AGENTS ’01. New York, NY, USA: ACM,
2001, pp. 401–408. [Online]. Available: http://doi.acm.org/10.1145/
375735.376382
[12] T. M. Mitchell, “Machine learning. 1997,” Burr Ridge, IL: McGraw Hill,
vol. 45, 1997.
[13] E. Vidal, F. Thollard, C. De La Higuera, F. Casacuberta, and R. C.
Carrasco, “Probabilistic finite-state machines-part i,” Pattern Analysis
and Machine Intelligence, IEEE Transactions on, vol. 27, no. 7, pp.
1013–1025, 2005.
[14] D. B. Fogel, “Evolving behaviors in the iterated prisoner’s dilemma,”
Evolutionary Computation, vol. 1, no. 1, pp. 77–97, 1993.
[15] D. Fogel, “An introduction to simulated evolutionary optimization,”
Neural Networks, IEEE Transactions on, vol. 5, no. 1, pp. 3–14, 1994.

[16] H. A. Abbass, “Learning regularities and patterns using probabilistic
finite state machines,” in 7th Asia-Pacific Conference on Complex
Systems, 2004.
[17] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals,” in Soviet physics doklady, vol. 10, 1966, p. 707.
[18] A. M. Steane, “Error correcting codes in quantum theory,” Physical
Review Letters, vol. 77, no. 5, p. 793, 1996.

