# Leveraging Graph and Deep Learning Uncertainties to Detect Anomalous
Trajectories

Sandeep Kumar Singh, _Member, IEEE_ , Jaya Shradha Fowdur, Jakob Gawlikowski
and Daniel Medina, _Member, IEEE_
1Corresponding author, email<EMAIL_ADDRESS>1Sandeep Kumar Singh was
with the German Aerospace Center, and he is now at the University of
California, Davis, 95616, USA.  Jaya Shradha Fowdur and Daniel Medina are with
Institute of Communications and Navigation, German Aerospace Centre (DLR),
Neustrelitz, 17235, Germany (e-mail: {jaya.fowdur,
daniel.ariasmedina}@dlr.de).  Jakob Gawlikowski is with Institute Of Data
Science, German Aerospace Centre (DLR), Jena, 07745, Germany (e-mail:
jakob.gawlikowski@dlr.de).

###### Abstract

Understanding and representing traffic patterns are key to detecting anomalous
trajectories in the transportation domain. However, some trajectories can
exhibit heterogeneous maneuvering characteristics despite confining to normal
patterns. Thus, we propose a novel graph-based trajectory representation and
association scheme for extraction and confederation of traffic movement
patterns, such that data patterns and uncertainty can be learned by deep
learning (DL) models. This paper proposes the usage of a recurrent neural
network (RNN)-based evidential regression model, which can predict trajectory
at future timesteps as well as estimate the data and model uncertainties
associated, to detect maritime anomalous trajectories, such as unusual vessel
maneuvering, using automatic identification system (AIS) data. Furthermore, we
utilize evidential deep learning classifiers to detect unusual turns of
vessels and the loss of transmitted signal using predicted class probabilities
with associated uncertainties. Our experimental results suggest that the
graphical representation of traffic patterns improves the ability of the DL
models, such as evidential and Monte Carlo dropout, to learn the temporal-
spatial correlation of data and associated uncertainties. Using different
datasets and experiments, we demonstrate that the estimated prediction
uncertainty yields fundamental information for the detection of traffic
anomalies in the maritime and, possibly in other domains.

###### Index Terms:

Anomaly detection, Evidential deep learning, Regression, Classification,
Clustering, Graph, Uncertainty

##  I Introduction

Security is crucial for the transportation domain. As more than 90% of the
world-trade is being carried out at sea, maritime domain in particular is
facing significant challenges from natural and unnatural phenomena, such as
tough environment, collision, illegal fishing, smuggling, pollution, and
piracy [1]. Some of these challenges can be addressed by having a better
understanding of maritime traffic patterns in terms of its representation,
accurate localization, and its forecasting approaches. Nowadays most ships are
equipped with automatic identification system (AIS) transponders to provide
their static and dynamic information [2]. The AIS transponders use global
navigation satellite systems for positioning, with accuracy of up to a few
meters [3]. The vessels’ location, navigational status, and voyage-related
information can be used for collision-avoidance mechanisms, vessel tracking,
along with the detection of loss of AIS signal, and anomalous trajectories.

Despite being equipped with on-board transponders, some vessels meander to
engage in suspicious activities. A vessel can switch-off its AIS transponder,
deviate from normal trajectory and turn in an unusual manner. Such situations
may arise, for instance, during hijacking of ships by pirates, illegal fishing
or rough environment amongst others. Therefore, in addition to correctly
representing traffic patterns, it is necessary to detect anomalous (or
unusual) vessel trajectories, the loss of signal, unusual turns and other
anomalies. As there are different kinds of anomalies in the maritime domain,
they need special attention and mechanisms to be dealt with. In this context,
historical and real-time AIS data provide a valuable source of vessel
trajectories information, and it has been utilized extensively for anomaly
detection in the maritime domain using various methods, such rule-based,
statistical and machine learning (ML) [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17].

Rule-based approaches are simple yet limited by their rigidness [4]. In
contrast, statistical and ML algorithms provide promising and complementary
solutions to deal with maritime security challenges [5, 6]. Statistical
methods, such as Bayesian filtering, Gaussian processes, or Markov models,
have been proven to be very effective in the traffic movement analysis and
potentially useful for anomaly detection [7, 8, 9, 10, 11]. They are generally
robust but do not exploit the short-/long-term inter-dependency of features,
e.g., positional and navigation AIS information. Contrarily, the use of ML
techniques, such as neural networks, long short-term memory (LSTM), have
demonstrated promising results for the anomaly detection problem [12, 13, 14,
15, 16, 17, 18, 19, 20, 21, 22].

ML-models are often not considered as robust under black swan events
(completely unseen scenarios) due to the lack of a model confidence and an
uncertainty estimation. Uncertainty estimation could help dealing with
critical applications, such as anomaly detection, surveillance, and maritime
navigation. We are interested in such applications of ML techniques that
include uncertainty characterization. With DL approaches [23, 24, 25, 26],
uncertainties associated with data and models could be applied to detect
anomalous trajectories and other anomalies. To date and to the authors’ best
knowledge, anomaly detection problem has not been approached with DL-based
uncertainty estimation in maritime domain using AIS data.

This work leverages graph and DL-based uncertainties to deal with maritime
anomaly detection using AIS data. First, we propose a graph-based traffic
representation and association (GTRA) model for extraction of maritime traffic
patterns and association of new data to the patterns. The clustered data is
given as input to an RNN-based regression model, which is integrated with a DL
uncertainty estimator, to predict the localization and dynamics information of
vessels, as well as uncertainties in their predictions. Second, we propose two
different EDL classifiers to learn an unusual turn (i.e., fast maneuvers over
a short time interval) and AIS on-off switching (OOS) anomalies. This article
demonstrates the performance of the RNN regression models for anomalous
trajectory (AT) detection, and the EDL classification models for the detection
of unusual turns (UT) and loss of AIS signal (i.e, OOS) over big and small AIS
historical datasets collected from the Baltic sea region. The trained EDL
classifiers are also shown to be useful in detecting the OOS and the unusual
turn anomalies on a test vessel’s trajectories in a validation campaign in
another region, namely Bremerhaven (Germany).

The rest of the article is organized as follows. We present the related work
in Section II. Section III describes our proposed GTRA, regression and
classification models useful in detecting various anomalies. Section IV
formulates anomalies and detection criteria. We evaluate the performance of
the models in Section V, and conclude the paper in Section VI.

##  II Related Work

Detecting anomalies is a rather difficult problem as these are rare phenomena
and a reference (or ground truth) dataset is generally unavailable.
Traditionally, the anomalous trajectory detection problem has been dealt by
learning and representing motion patterns together with an outlier detection
criterion. Previous studies utilized clustering and graph-based approaches for
traffic pattern characterization, and anomaly or similarity score for outlier
detection across multiple domains and applications [27, 28, 29], including
social networking event mapping [19], tracking of automobiles and anomalous
trajectories [20, 21, 22], and extracting maritime traffic patterns [30, 31,
32, 33]. Numerous studies have used unsupervised learning methods, such as
$k$-means, Gaussian mixture model, density-based spatial clustering of
applications with noise (DBSCAN), etc., for traffic clustering in maritime
domain [30, 32, 34, 35, 36]. Graph-based traffic characterization together
with a similarity model is a promising approach in detecting anomalous
trajectories [30, 37, 35]. Note that the graph approaches from other domains
[19, 22] may not be applied directly to the maritime domain, as the nodes of a
graph need to represent clusters of waypoints, i.e., areas where ships are
more likely to change course, and edges should correspond to sea-lanes.
Although hyper-parameters in these methods and in our GTRA are required to be
tuned– either by trial-and-error or automatically [38], they are able to
represent motion patterns and can be useful in anomaly detection through
similarity models. Nevertheless, they might not detect some complex anomalous
trajectories that lie within sea-lanes, as shown in Sec. V. In contrast, our
GTRA method not only characterizes traffic, but also assigns new AIS data to
the best possible traffic cluster (or sea-lanes) which can be useful in
traffic pre-processing step for the prediction task and in the detection of
heterogeneous anomalous trajectories.

Anomaly detection using either the deviation between a predicted trajectory
and its reported (measured) one, or considering the probabilistic
characteristics of trajectories have also been exploited, using both
statistical and ML-based solutions. Statistical methods, such as Kalman
filter, particle filter, Bayesian networks or Gaussian processes (GPs) have
been used to estimate/predict the vessels’ locations at next time stamp to
reconstruct their trajectories and estimate probabilistic characteristics of
trajectories to detect anomalies [5, 6, 39, 33, 40, 41, 42]. ML (or deep
learning, DL, as being branded lately) algorithms, such as LSTM and LSTM
encoder decoder [43, 44], have been shown to be promising in sequence-to-
sequence or time-series prediction in a number of applications, including
trajectory prediction tasks [14, 45, 46, 34]. In addition, [13] applied the
Variational RNN to learn the probabilistic distribution of trajectories, which
help them to detect anomalous trajectories.

There have also been efforts towards anomaly classification by means of
supervised learning with labeled data. Zhong $et$ $al.$ [15] used a random
forest algorithm to classify vessels using AIS data streams. Mazzarella $et$
$al.$ proposed a one-class support vector machine-based anomaly detection
framework that takes AIS data as well as received signal strength into
consideration for analyzing the AIS OOS anomaly [12]. In the own previous
works [16, 17] we showed that neural networks can be used to detect the AIS
OOS anomaly with a higher accuracy than other traditional ML algorithms.

Classical ML models generally do not indicate any measure of confidence or
uncertainty with their predictions. With datasets across applications evolving
over time and prone to varying noise levels, the lack of uncertainty measures
in those ML models makes their use discouraged in safety-critical applications
such as anomaly detection. Thus, it is highly desirable to quantify model and
data uncertainty in a trustworthy manner. In this paper, we approach the
maritime anomaly detection problem using a novel DL-based learning of model
and data uncertainties. To this end, a promising EDL regression [26] and
classification model [25] are applied. In a nutshell, EDL captures the model
evidence (confidence) in support of its prediction. Note that the
computationally-intensive, non-parametric GPs [47] and parametric Bayesian
neural networks (BNNs) [23, 24] and its approximation, known as MC dropout
[48], are also solid options for the provision of reliability measures and
prediction uncertainty. Orthogonal to GPs and BNNs, EDL enables simultaneous
learning of the desired regression/classification task along with data
(aleatoric) and model (epistemic) uncertainty estimation, by enforcing
evidential priors. Furthermore, an EDL model can be trained to provide
uncertainty measures without leveraging any out-of-distribution (or anomalous)
data. Our work is partially inspired by this concept, wherein we propose an
RNN-EDL model to detect maritime anomalies using the uncertainty estimation,
and compare its performance with the MC dropout model [48] and a graph-based
similarity model [37]. Specifically, this work makes the following
contributions:

  1. 1.

A graph-based trajectory representation and association (GTRA) method;

  2. 2.

DL models for model confidence and data uncertainty estimation towards AT, OOS
and UT anomaly detection;

  3. 3.

Evaluation of anomalous trajectory detection among other anomalies on big and
complex AIS dataset.

Figure 1: A schematic of anomalous trajectory (AT) detection using a
similarity and DL-based regression models, and OOS and UT detection using DL-
based classifier models. The similarity model computes a similarity score
between normal trajectory routes, obtained by a graph $G(V,E)$, and a test
trajectory formed by AIS data*. $G(V,E)$ represents traffic movement patterns
with nodes in $V$ and connecting edges in $E$, computed by our graph-based
trajectory representation (GTR) method using DBSCAN and RDP algorithms on a
given AIS dataset. A regression model tests AT on AIS data* using its trained
model on AIS data and their association to the edges ($e_{j}\in E$) given by
our graph-based trajectory association (GTA) method. Note that the classifier
models use AIS data only (and no input from $G$), during their training and
testing, to detect the OOS and UT anomalies.

##  III Methodology for Anomaly Detection and Modeling

Anomaly detection is a prerequisite for the obtainment of a complete maritime
traffic situational awareness. The question resides on how such anomalous
patterns are defined. In general, we treat a predictable or acceptable
behavior as normal and the rest is classified as anomalies. For example, the
acceptable practice to find an anomalous trajectory is to examine whether the
ship deviates from its well-defined maritime route. This method, also known as
similarity model [37, 30], might not be suitable for vessels that may confine
to maritime route but perform unusual maneuvering. Therefore, we apply DL
techniques to learn data distribution (or patterns) and their underlying
uncertainties, and use them to detect anomalies. Fig. 1 depicts the
methodology adapted in this article to detect various anomalies using our
regression and classification models as well as a similarity model.

Figure 2: Normal trajectories of a vessel are shown using white dots and two
anomalous segments of trajectories (left and right) are shown in red between
two ports Rostock and Gedsar in the Baltic sea.

One can illustrate an anomalous trajectory of a vessel with respect to its
normal trajectories using an example shown in Fig. 2. Here, the anomalous
segments clearly deviate from the bulk of trajectories. They can be detected
by either i) thresholding the maximum allowed deviation between the posterior
ground truth (reported) and the long-term a-priori prediction of a trajectory,
which is not trivial for all types of vessels; or ii) quantifying a measure of
uncertainty in prediction on successive reported data. Therefore, we apply DL
techniques to learn data distribution (or patterns) and their underlying
uncertainties. There could be different sources of uncertainty in the
prediction, when a DL model: i) is trained with in-distribution noisy data,
ii) is tested with mismatched or out-of-order distributed data compared to the
data used in training, and iii) has wrongly estimated weight and network
parameters. The uncertainty caused by the first source can be termed as
aleatoric (data) uncertainty, which is irreducible. The second and third
sources cause a reducible epistemic (model) uncertainty.

Figure 3: A visualization of aleatoric and epistemic uncertainties with
respect to training data and model fit.

For the sake of visualization, Fig. 3 depicts both type of uncertainties with
respect to some training data and a model-fit. With the DL regression we could
estimate the aleatoric or epistemic uncertainty for anomalous trajectory
detection.

Next, we briefly describe the AIS data, and present a GTRA method, EDL
regression model and EDL classification model for anomaly detection modeling.
The anomalous trajectory detection problem is solved by first clustering data
into well-defined routes (or sea-lanes) using the GTRA method, and then
quantifying uncertainties with the clustered data using an EDL regression
model. On the other hand, the EDL classifier models are trained to distinguish
between normal and abnormal data patterns to detect unusual turns, or AIS on-
off switching for instance.

###  III-A AIS data representation

AIS messages constitute the primary source of information for the methodology
developed in this work. Each vessel’s AIS report may include an identifier,
i.e., the maritime mobile service identity ($mmsi$); kinematic information,
i.e., longitude ($lon$), latitude ($lat$), speed over ground ($sog$) and
course over ground $cog$); a UTC timestamp ($time$); and other additional
information, such as voyage, ship name, ship type, navigation status–to name a
few.

Considering a discrete state-space model, the state vector for the navigation
problem for the $i$th vessel at time index $k$ is formulated as

$\mathbf{x}_{k}^{i}\triangleq\begin{bmatrix}lon,lat,cog,sog,time,edge\end{bmatrix}^{\top},$
(1)

with $edge$ ($e_{j}\in E$) being a feature that represents the association of
data $\mathbf{x}_{k}^{i}$ to one of the edges of a graph $G(V,E)$ given by the
GTRA scheme. It is important to note that our anomaly detection models use
different subsets of features in $\mathbf{x}_{k}^{i}$, and unlike the
kinematic information directly obtained from the AIS data, the $edge$ feature
is not known a priori. The notation $\mathbf{X}^{i}_{k:k+T}$ refers to the
state of the $i$th vessel between the time periods $k$ and $k+T$, such that

$\mathbf{X}^{i}_{k:k+T}\triangleq\begin{bmatrix}\mathbf{x}_{k}^{i},\mathbf{x}_{k+1}^{i},\cdots,\mathbf{x}_{k+T-1}^{i}\end{bmatrix},$
(2)

and we use $\mathbf{X}^{i}$ to refer to the complete set of states for the
$i$th vessel along the duration of the dataset. In the sequel, the methodology
related to trajectory clustering and association, trajectory forecasting and
uncertainty estimation, and anomaly classification are detailed.

Algorithm 1 Graph-based Traffic Representation (GTR)

1:Input: Dataset $\mathcal{D}$, parameters:
$\epsilon,\varepsilon,n_{min},\mathcal{M}_{th},e_{th}$

2:for each vessel $i$ in $\mathcal{D}$ do:

3: $\mathbf{WP}^{i}\leftarrow RDP(\mathbf{X}^{i},\epsilon)$

4:end for

5:Clusters $C\leftarrow DBSCAN(\mathbf{WP}{{}^{i}},\varepsilon,n_{min})$

6:for each cluster $j$ in $C$ do:

7: Nodes
$V\leftarrow\mathbf{v}_{j}\equiv(\boldsymbol{\mu}_{j},\boldsymbol{\Sigma}_{j})$

8:end for

9:// define trajectory of a vessel by graph nodes

10:for each vessel $i$ in $\mathbf{WP}$ do:

11: for each waypoint $\mathbf{wp}^{i}_{k}$ in $\mathbf{{WP}}^{i}$ do:

12: $\mathcal{L}^{i}\\!\leftarrow\\!\mathbf{v}_{j}$ if
$\min_{\mathbf{v}_{j}}(\mathbf{wp}^{i}_{k}\\!-\\!\boldsymbol{\mu}_{j})^{\prime}\boldsymbol{\Sigma}_{j}(\mathbf{wp}^{i}_{k}\\!-\\!\boldsymbol{\mu}_{j})\\!<\\!\mathcal{M}_{th}$

13: end for

14: delete duplicate nodes in $\mathcal{L}^{i}$; delete $\mathcal{L}_{i}$, if
$|\mathcal{L}_{i}|=1$

15:end for

16:// compute # of edge visits by vessels

17:$\tilde{E}:=zeros(|V|,|V|)$

18:for each vessel $i$ in $\mathcal{L}$ do:

19: for each successive pair $(\mathbf{v}_{1},\mathbf{v}_{2})$ in
$\mathcal{L}^{i}$ do:

20: $\tilde{E}(\mathbf{v}_{1},\mathbf{v}_{2})+=1$ // increment the visit by 1

21: end for

22:end for

23:// compute the graph edges $E$

24:for each node $\mathbf{v}_{1}$ in $V$ do:

25: for each node $\mathbf{v}_{2}$ in $V$ do:

26: $E\leftarrow(\mathbf{v}_{1},\mathbf{v}_{2})$ if
$\frac{\tilde{E}(\mathbf{v}_{1},\mathbf{v}_{2})}{\sum\tilde{E}(\mathbf{v}_{1},:)}>e_{th}$

27: end for

28:end for

29:Return: $G(V,E)$ for data association

Algorithm 2 Graph-based Traffic Association (GTA)

1:Input: Dataset $\mathcal{D}$, graph $G$, parameters $d_{max},\epsilon$

2:for each vessel $i$ in $\mathcal{D}$ do

3: for each time index $k$ in $\mathbf{X}^{i}$ do

4: $\mathbf{x}_{k}^{i}[edge]\\!\\!=\\!\\!\begin{cases}j,\text{if}\ \min_{1\leq
j\leq|E|}d_{\bot}(\mathbf{e}_{j},\mathbf{x}_{k}^{i})\leq d_{max}\\\
\emptyset,\text{otherwise}\end{cases}$

5: end for

6: $\mathbf{WP}^{i}\leftarrow RDP(\mathbf{X}^{i},\epsilon)$

7: for each $(k_{1},k_{2})$ time pair in $\mathbf{WP}^{i}$ do

8:
$\forall\,k\in[k_{1},k_{2}],\mathbf{E}_{k_{1}:k_{2}}\leftarrow\\{\mathbf{x}^{i}_{k}[edge]\\},$

9: $\mathbf{x}_{k}^{i}[edge]\leftarrow
j,\min_{j\in\mathbf{E}_{k_{1}:k_{2}}}|\nabla\mathbf{e}_{j}-\nabla(\mathbf{x}^{i}_{k_{1}},\mathbf{x}^{i}_{k_{2}})|$

10: end for

11:end for

12:Return: $\mathbf{x}^{i}_{k}[edge],\forall i,k\in\mathcal{D}$

###  III-B Graph-based Trajectory Representation and Association (GTRA) Scheme

Providing an accurate traffic situation awareness requires addressing which
are the usual sea lanes and vessels’ trajectories. Thus, given a real-world
historical AIS dataset $\mathcal{D}$, our GTRA scheme leverages on a graph-
based trajectory representation (GTR) process to conform the trajectories onto
commonly-travelled maritime routes. Then, we can associate (cluster) the
trajectories from any given dataset to the maritime routes via graph-based
trajectory association (GTA). The graph $G$ consists of a set of nodes
$V=\\{\mathbf{v}_{j}\\}_{j=1}^{|V|}$ and a set of edges
$E=\\{\mathbf{e}_{j}\\}_{j=1}^{|E|}$, where $\mathbf{v}_{j}$ is a two-
dimensional (2D) vector containing longitude and latitude values, and each
$\mathbf{e}_{j}$ contains two distinct nodes in $V$. In this work, the graph’s
nodes represent turning points for the vessels’ trajectories, while the edges
joining consecutive nodes represent the sea lanes traversed by vessels.

The GTR process, i.e., the estimation of a graph $G$, is summarized in
Algorithm 1. First, in Steps 2-4 we reduce the trajectory of each vessel
$\mathbf{X}^{i}$ to a set of waypoints $\mathbf{WP}^{i}$
$=\\{\mathbf{wp}_{j}\\}_{j=1}^{|\mathbf{WP}^{i}|}$ using an iterative Ramer-
Douglas-Peucker (RDP) algorithm [49]. $\mathbf{WP}^{i}$ may represent the
trajectory’s start, end and turning points, and the parameter $\epsilon$
limits the maximum distance of any intermediate points to their joining
segments. The above process is repeated for all vessels’ trajectories and then
their associated waypoints are clustered into nodes using the DBSCAN algorithm
(Step 5). DBSCAN iteratively searches for the core points in the neighbourhood
of the waypoints $\mathbf{WP}^{i}$ within a distance of $\varepsilon$, so that
there are at least $n_{min}$ number of density-reachable points. We compute
the mean ($\boldsymbol{\mu}_{j}$) and covariance ($\boldsymbol{\Sigma}_{j}$)
of core points in each cluster $j$ to get the nodes $\mathbf{v}_{j}$ in $V$ in
Step 7. In Steps 9-14, the individual waypoints belonging to a vessel $i$ are
then processed for proximity to the nodes in $V$. In Step 11, should the
Mahalanobis distance between nodes in $V$ and a waypoint be less than
threshold $\mathcal{M}_{th}$, then the closest node $\mathbf{v}_{j}$ for the
waypoint is added to a list $\mathcal{L}^{i}$. Intuitively, $\mathcal{L}^{i}$
represents the set of nodes in $V$ that the vessel $i$ traverses.
$\mathcal{M}_{th}$ represents a maximum likelihood ellipsoidal gate around
node $\mathbf{v}_{j}$ defining points falling within the gate as those most
likely to belong to the node (or trajectory). Its value was chosen based on a
Chi-square distribution at a gate probability of 0.99 with 2 degrees of
freedom. In addition, the nodes in every vessel’s route are checked for
redundancy and thereby eliminated (Step 13). Successive nodes from the
resulting list $\mathcal{L}$ are then used to obtain a matrix $\tilde{E}$ that
counts the number of times each edge (node-pair) is visited by vessels in
Steps 15-19. Finally, in Steps 21-25 the desired edge set $E$ is obtained by
applying a threshold $e_{th}$ on the normalized number of visits of each
possible edge $(\mathbf{v}_{1},\mathbf{v}_{2})$ with respect to the total
number of visits to $\mathbf{v}_{1}$. Thus, the GTR retains essentially the
most visited edges as the trajectory (or traffic) representation. The
computational complexity of the GTR is $\mathcal{O}(nm\log
m+nm+n|V|+|V|^{2})\approx\mathcal{O}(nm\log m)$, scaling with the number of
vessels $n$, and data points per trajectory $m$, with $m>>|V|$.

The GTA process aims at associating (or clustering) all AIS data from
$\mathcal{D}$ to the edges of the graph formed by the GTR, as formulated in
Algorithm 2. This is performed by computing the perpendicular distances
$d_{\bot}$ from an AIS data of a vessel to all edges in Steps 2-5. The edge
with the minimum distance is selected if it lies below a threshold $d_{max}$,
otherwise the point is associated to a so-called outlier edge $\emptyset$.
Note that this process may assign successive points of a trajectory segment to
different edges. Therefore, we compute waypoints $\mathbf{WP}^{i}$ for each
vessel’s trajectory $\mathbf{X}^{i}$ in Step 6 using the RDP algorithm. Next,
we form a set of edges that was associated (in Step 4) to all intermediate AIS
data, i.e., $\mathbf{E}_{k_{1}:k_{2}}$ between each pair of consecutive
waypoints $(\mathbf{x}^{i}_{k_{1}},\mathbf{x}^{i}_{k_{2}})\in\mathbf{WP}^{i}$
in Steps 7-8. At last, these data points are associated to an edge
$\mathbf{e}_{j}$ that has a minimum slope difference from a line formed by
joining the waypoints (Step 9). Note that the Steps 7-11 is irrelevant if all
points of a segment has been associated the same edge, i.e.,
$|\mathbf{E}_{k_{1}:k_{2}}|=1$, which could also be an outlier edge. For a
given dataset with $n$ vessels and $m$ data points per vessel, the
computational complexity of associating all of its data points to the edges of
the graph $G$ is $\mathcal{O}(nm+nm\log m)\approx\mathcal{O}(nm\log m)$.

Our intuition is that a normalcy trajectory prediction model could be learned
more precisely for clustered data, as compared to raw data. Thus, in addition
to AIS data features $(lon,lat,cog,sog)$, we could provide the edge label for
each AIS data point as an input feature to a trajectory forecasting model,
which is described next.

###  III-C An RNN-EDL Regression Model

The aim of an RNN-EDL regression model is to forecast the subsequent $L$
navigation instances for an $i$th vessel, given the last $T$ time instances
prior. Thus, the RNN-EDL regression model produces an estimate as

$f\left(\mathbf{X}^{i}_{k:k+T},\mathbf{W}\right)=\widehat{\mathbf{X}}^{i}_{k+T:k+T+L},$
(3)

with $\mathbf{X}^{i}_{k:k+T}$ the input sequence, $\mathbf{W}$ the model
weights optimized during the training process and $f(\cdot)$ the estimator per
se. The model forecasts the estimates $\widehat{\mathbf{X}}^{i}_{k+T:k+T+L}$
for $L$ time instances. Henceforth, we will omit the vessel index $i$.

Among the recurrent networks, the LSTM encoder-decoder is known for its
superior performance at temporal prediction [44] and it constitutes the
learning algorithm for our work. This architecture learns sequences by first
encoding an input sequence ($\mathbf{X}_{k:k+T}$) into hidden state variables
($\mathbf{h}_{k}=f(\mathbf{x}_{k},\mathbf{h}_{k-1})$), and then maximizing the
posterior log-likelihood of the estimate ($\log
p(\mathbf{X}_{k+T:k+T+L}|\mathbf{h}_{j},\textbf{x}_{j},j\in[k,\dots,k+T-1])$).
Conventional LSTM regression resembles a pointwise maximum-a-posteriori (MAP)
estimation, without uncertainty measures for the estimates. However, the
information on the uncertainty is as valuable as the estimate itself. To that
end, we employ loss functions that support evidential learning [26] to
estimate the actual forecast and the associated epistemic uncertainties over
the estimates. Furthermore, we also implement the RNN-MC dropout model for
comparative analysis, which is relatively computationally intensive because it
does not provide a close-form solution for the likelihood function, and the
integration is generally computed by a Monte Carlo (MC) sampling approach
[48].

The architecture of the proposed model as a trajectory predictor is depicted
in Fig. 4. The LSTM encoder and decoder consist of a multiple stack of LSTM
cells which are connected horizontally and vertically for spatio-temporal
learning. The output of the LSTM decoder part is given to a Dense layer and
forwarded to the Evidential layer. The Evidential layer outputs parameters
$\boldsymbol{m}$ that are used to parameterize a distribution
$p(x|\boldsymbol{m})$, based on which a MAP estimate, the aleatoric
uncertainty and the epistemic uncertainty can be derived. We explain this in
the following.

Figure 4: An architecture of an LSTM Encoder-Decoder-Evidential DL model for
trajectory forecasting and uncertainty estimation.

A basic idea of modelling data uncertainty on a prediction is to output a
probability distribution $p(x|\boldsymbol{\theta})$ instead of a pointwise
prediction [24]. For regression tasks the distribution parameters
$\boldsymbol{\theta}$ might be the mean and the variance value of a normal
distribution. Evidential neural networks extend this idea and model the
epistemic uncertainty by a higher order distribution, i.e. a distribution over
the aleatoric distribution, as $p(\boldsymbol{\theta}|\boldsymbol{m})$. Here,
$\boldsymbol{m}$ again represents the model’s output which is used to
parameterize a probability distribution, in our case this distribution is
given by the normal inverse gamma distribution which is described in more
detail below. The intuitive idea behind this is that if the model receives
data which does not fit the patterns learned during training, the information
that can be extracted from this data are very limited and hence the evidence
for a certain prediction (even when given as mean and variance) is also
limited. As a result, the higher order distribution, which is parameterized by
this evidence, represents the uncertainty as well.

Based on the evidential modelling, the probability of a prediction $x_{k}$ is
given by

$\displaystyle
p(x_{k}|\boldsymbol{m})=\int_{\boldsymbol{\theta}}p(x_{k}|\boldsymbol{\theta})p(\boldsymbol{\theta}|\boldsymbol{m})d\boldsymbol{\theta}.$
(4)

For our approach, we follow [26] and model the aleatoric uncertainty by a
normal distribution with unknown mean and variance, i.e.
$\boldsymbol{\theta}=(\mu,\sigma^{2})$ and use its conjugate prior, i.e.,
Normal Inverse-Gamma (NIG), as a fitting distribution for representing the
epistemic uncertainty. The NIG distribution is parameterized by four scalar
parameters, i.e.

$\boldsymbol{m}=(\hat{x},v,\alpha,\beta)\qquad\text{with}\quad\hat{x}\in\mathbb{R},v>0,\alpha>1,\beta>0.$
(5)
$\mu\sim\mathcal{N}(\hat{x},\sigma^{2}/v)\qquad\text{and}\qquad\sigma^{2}\sim\Gamma^{-1}(\alpha,\beta)$
(6)

where $\Gamma^{-1}$ is the inverse gamma distribution.

For the probability of a prediction we have to consider the marginal
likelihood $p(x_{k}|\boldsymbol{m})$, which is given as the Student’s-t

$p(x_{k}|\boldsymbol{m})=St(x_{k};\hat{x}_{k},\frac{\beta(1+v)}{v\alpha},2\alpha).$
(7)

Please refer to [26] and their supplementary materials for further details and
the derivations.

During the training process the network parameters $W$ are optimized in order
to minimize the negative log-likelihood

$-\log
p\left(\int_{\boldsymbol{\theta}}p(x_{k}|\boldsymbol{\theta})p(\boldsymbol{\theta}|\boldsymbol{m})d\boldsymbol{\theta})\right).$
(8)

Given a $k$th input sequence $\mathbf{X}_{k:k+T}$, the loss function
$\mathcal{L}_{k}$ for a ground-truth output sequence $\mathbf{X}_{k+T:k+T+L}$,
the predicted parameters $\boldsymbol{m}_{j}^{d}$ and an estimated mean
$\hat{x}_{j}^{d}$ can be computed as [26]

$\displaystyle\mathcal{L}_{k}(W)\\!$
$\displaystyle=\\!\mathcal{L}^{NLL}_{k}(W)+\lambda\mathcal{L}^{R}_{k}(W)$
$\displaystyle=\\!\sum_{j=k+T}^{k+T+L-1}\\!\sum_{d=1}^{n}\\!\\!-\log
p(x_{j}^{d}|\boldsymbol{m}_{j}^{d})\\!+\\!\lambda|x_{j}^{d}\\!-\\!\hat{x}_{j}^{d}|(2v_{j}^{d}\\!+\\!\alpha_{j}^{d}),$
(9)

where the first loss component is used for minimizing the negative log-
likelihood (NLL) of an observation $x_{k}$ and the second one is an evidence
regularizer that motivates to collect less evidence when the predictions are
false with a scalar $\lambda$. The RNN-EDL model is trained to output four
evidential distribution parameters for each output
$x_{k}^{d},d=1,2,\ldots,n\in\mathbf{x}_{k}$, i.e.,
$\boldsymbol{m}_{k}^{d}=(\hat{x}_{k}^{d}$, $v_{k}^{d}$,
$\alpha_{k}^{d},\beta_{k}^{d})$ for an $L-$length output sequence
$\mathbf{X}_{k+T:k+T+L}$. Given a NIG distribution and following [26], we can
compute the next timestep prediction at $j=k+T$ for each feature
$d=1,2,\ldots,n$, given an input sequence $\mathbf{X}_{k:k+T}$, as
$\hat{x}_{j}^{d}=\mathbb{E}[\mu_{j}^{d}]$, the aleatoric uncertainty as
$v_{j}^{d}\times\operatorname{var}[\mu_{j}^{d}]$, and the epistemic
uncertainty by

$\operatorname{var}[\mu_{j}^{d}]=\frac{\beta_{j}^{d}}{v_{j}^{d}(\alpha_{j}^{d}-1)}.$
(10)

###  III-D EDL Classifiers for Anomalous OOS and Turn Detection

Figure 5: An architecture of an EDL classifier model that consists of an input
layer, n hidden layers, an output layer, and a Dirichlet parameterization
layer.

A standard neural network outputs
$\boldsymbol{\tilde{y}}=f(\Theta,\mathbf{X}_{0:T})=a_{\text{n}+1}(W_{\text{n}+1}a_{\text{n}}(W_{\text{n}}\ldots
a_{1}(W_{1}\cdot\mathbf{X}_{k:k+T})\ldots))$ with the number of hidden layers
n, activation functions $a_{j}(\cdot),j=1,2,\ldots,\text{n}$, and network
parameters $\Theta=[W_{1:\text{n}+1},\boldsymbol{b}]$, where $W$ is the weight
vector of the connections between two layers, and $\boldsymbol{b}$ is a bias
vector. For classification, generally a softmax activation is used to convert
the predicted values
($\tilde{y}_{1},\tilde{y}_{2},\ldots,\tilde{y}_{K}\in\mathbb{R}$) of the
output layer to class probabilities
$p_{c}=\text{softmax}(\tilde{y}_{c})=\exp(\tilde{y}_{c})/\sum_{j=1}^{K}\exp(\tilde{y}_{j})$.
In doing so it does not take the magnitude of the logits into account and
hence fails to represent the certainty of the predicted probability vector
outputs. Therefore, authors in [25] proposed to replace the softmax activation
with any other continuous operator, for example $ReLU(x)=\max(x,0)$, and
consider $\boldsymbol{\alpha}=f(\Theta,\mathbf{X}_{k:k+T})+1$ (i.e., output+1)
as parameters of a multivariate Dirichlet distribution
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2},\ldots,\alpha_{K})$. An
architecture of EDL classifier is depicted in Fig. 5. Notice that unlike the
evidential regressor, which models outputs with the continuous Gaussian
distribution, the evidential classifier utilizes the categorical Dirichlet’s
distribution, with a sum of squares loss function
$||y_{c}-\tilde{p}_{c}||^{2}_{2}$. Once the network learns the parameters
$\boldsymbol{\alpha}$, its mean, can be taken as an estimate of the class
probabilities, shown in Eq. (11). The epistemic uncertainty on the prediction
is computed as the inverse of total evidence or Dirichlet strength
$S=\sum_{c=1}^{K}\alpha_{c}$, for $K$ output classes in (12)[25].

$\tilde{p}_{c}=\alpha_{c}/S,c=1,2,\ldots,K$ (11) $u=K/S$ (12)

We train two EDL classifiers, one for the UT detection and other for the AIS
OOS detection, with different inputs and networks required for the learning
purposes. The prediction uncertainty in Eq. (12) together with (11) is used to
accept or reject the classification of data patterns (e.g., for UT, OOS) by
setting a threshold on acceptable uncertainty $u_{th}$. In the next section,
we describe how we detect different anomalies using the proposed models.

##  IV Anomaly Definitions and Detection Criteria

The following subsections describes three anomalies and presents the detection
criteria.

###  IV-A Anomalous Trajectory (AT)

For AT detection, we divide a trajectory into smaller segments, each with
$N+T-1$ consecutive AIS messages, and cover it by a sliding window of length
$T$ with a step size of one. This results into $N$ sequences per segment. To
simplify the evaluation of uncertainties, we keep the output sequence length
as $L=1$.

A vessel’s trajectory is termed as anomalous if it contains one or more
anomalous segments. Note that high epistemic uncertainty may represent
anomalous trajectory. However, as the spatial maritime data is noisy and
cluttered, different output features per AIS data are predicted with different
uncertainties and it might not be a good idea to analyze a given track with
respect to the uncertainty-threshold of other normal tracks. Thus, we define a
trajectory segment as anomalous if the predicted sequences of the segment have
an abrupt transition in their epistemic (or aleatoric) uncertainties.
Precisely, a contiguous segment $\mathbf{X}_{0:N+T}$ with $N$ sequences is
termed as anomalous if the minimum segment uncertainty over the normalized
uncertainties obtained over all the predicted outputs is smaller than a
threshold $\Theta_{AT}$, i.e.,

$\min_{d}\left[\frac{\min_{j}(\operatorname{var}[\mu_{j}^{d}])}{\max_{j}(\operatorname{var}[\mu_{j}^{d}])}\right]<\Theta_{AT},$
(13)

where Eq. (13) detects some abrupt transitions in the output uncertainties
$\operatorname{var}[\mu_{j}^{d}]$ over $j=T,T+1,\ldots,N+T-1$ sequences for
each feature $d=1,2,\dots,n$. It selects the feature $d$ and output sequence
$j$ with the minimum normalized uncertainties. If this value is below
$\Theta_{AT}$, then the segment is considered as anomalous. The normalization
of the uncertainties of all $N$ predicted output sequences helps in two ways.
First, it makes a fair comparison of uncertainties on all features. Second,
the normalization of a set of values representing a larger transition leads to
a wider range of scaled values, from closer to 0 to an upper limit of 1. Thus,
setting a maximum threshold $\Theta_{AT}$ in Eq. (13) helps us in detecting
the larger transitions in the uncertainties, which leads to the detection of
anomalous trajectories.

To understand Eq. (13), consider a trajectory segment with $N+T-1=39$
consecutive AIS data, where there are $N=30$ sequences, each with length
$T=10$ data. The regression model iteratively predicts $30$ corresponding
output sequences, each with a predicted sequence of length $L=1$. Let us
assume that the epistemic uncertainties for the features $lon\,(d=1)$ and
$lat\,(d=2)$ using Eq. (10) and for 30 consecutive predictions are
$\operatorname{var}[\mu_{j}^{d}]=[[0.01,0.02],\ldots,[0.30,0.31]],$ $d=1,2;$
$j=10,11,\ldots,39$. The normalized values of uncertainties over all predicted
sequences $j$ are simply
$\operatorname{var}[\mu_{j}^{1}]/0.30,\operatorname{var}[\mu_{j}^{2}]/0.31$.
The minimum over all predictions $j$ would result in $0.01/0.30$ and
$0.02/0.31$ for the $lon$ and $lat$, respectively. Under these settings, the
trajectory segment is detected as anomalous if the threshold $\Theta_{AT}$ is
set larger than 1/30 (i.e., the minimum over all considered features).

Figure 6: Trajectories extracted from dataset $\mathcal{D}_{1}$ are shown in
the left plot, and trajectories from dataset $\mathcal{D}_{2}$ are shown in
the right plot.

###  IV-B Unusual Turn (UT) Anomaly

We are interested in developing an EDL classifier that learns whether a vessel
took a turn of more (or less) than a threshold $\Theta_{UT}$, given an AIS
data sequence of length $T$. To this end, we first compute the change in the
course of a vessel using the $cog\in[0\degree,360\degree)$ values from the
data sequence $\mathbf{X}_{0:T}$ by Eq. (14).

$\theta=\\!\begin{cases}\max(\mathbf{M})-\min(\mathbf{M})+\max(\mathbf{L})-\min(\mathbf{L}),\mathbf{M,L}\neq\emptyset\\\
\max(\mathbf{X}_{0:T}[cog])-\min(\mathbf{X}_{0:T}[cog]),\text{
otherwise}\end{cases}$ (14)

The second line on the right hand side of Eq. (14) computes the course change
by the difference between the maximum and the minimum reported $cog$ values.
However, the condition overlooks a scenario when a vessel turns across true
north, i.e., from 359°to 0°or the other way. The first line in Eq. (14)
captures this scenario by formulating two sets of $cog$ values reported within
$[270\degree,360\degree)$ using
$\mathbf{M}=\\{\mathbf{x}_{k}[cog]\in\mathbf{X}_{0:T}|\mathbf{x}_{k}[cog]\geq
270\degree,k=0,\ldots,T-1\\}$ and within $[0\degree,90\degree]$ using
$\mathbf{L}=\\{\mathbf{x}_{k}[cog]\in\mathbf{X}_{0:T}|\mathbf{x}_{k}[cog]\leq
90\degree,k=0,\dots,T-1\\}$. The sum of the changes in course across the true
north then correctly computes the vessels’ turn using the sample
$\mathbf{X}_{0:T}$.

A sequence $\mathbf{X}_{0:T}$ is termed as anomalous if the turn is larger
than the threshold $i.e.,\theta_{\mathbf{X}_{0:T}}>\Theta_{UT}$. It is
important to mention that Eq. (14) is used to label input data sequences into
the normal and the anomaly categories, which are used for the training of the
EDL unusual turn classifier. A predicted class is accepted or rejected based
on its associated uncertainty.

We consider a flexible approach to define a trajectory segment for the unusual
turn detection, as the duration of a vessel’s turn is unknown. The segment of
a track $\mathbf{X}_{k_{1}:k_{2}}$ with reported times $k_{1}<k_{2}$ is termed
as an unusual turn anomaly if all of its samples are anomalous and the
previous $\mathbf{X}_{k_{1}-1}$ and the following $\mathbf{X}_{k_{2}+1}$
samples are normal. This helps in the minimization of the number of reported
anomalies and the frequency that the maritime authority are to be alerted, as
we noticed during a project validation campaign (results are reported in Sec.
V).

###  IV-C AIS OOS Anomaly

In order to detect an OOS anomaly due to loss of AIS signal, the EDL
classifier model needs to learn the time difference between two consecutive
AIS data. A sample $\mathbf{X}_{k:k+2}$ is termed as an AIS OOS anomaly if the
time difference between two consecutive AIS data reported in the sample is
greater than a threshold $\Theta_{OOS}$, as shown in Eq. (15). We either
accept or reject the predicted class of a given input sample depending on
whether its associated uncertainty $u$ (see Eq. 12) is lower or higher than a
threshold $u_{th}$, respectively.

$\mathbf{x}_{k+1}[time]-\mathbf{x}_{k}[time]>\Theta_{OOS}$ (15)

##  V Experimental Results

In this section the proposed anomaly detection methods are evaluated on
various real-world AIS data. We describe the data preprocessing step,
experimental settings, and present results from various scenarios in the
following subsections.

###  V-A Experimental Setup

Dataset Preparation: The two AIS datasets evaluated were provided by: _i)_ the
German waterways and shipping administration (WSV) for January 2016, and _ii)_
AISHUB for January 2020. Henceforth, they are referred to as $\mathcal{D}_{1}$
and $\mathcal{D}_{2}$, respectively. The data is filtered in the region of
interest (ROI) with a rectangular bounding box from (11.5°, 54.2°) to (12.5°,
54.5°). AIS messages that reported speed over ground within 30 knots, and
navigation status as 0 (i.e., underway using engine) are considered.
Additionally, the ship type is stored (e.g., passenger: 60-69, cargo: 70-79,
tanker: 80-89) for all vessels within the ROI. After these preprocessing
steps, $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ contain $\approx$ 1.2 and 0.1
million AIS positions, respectively. Figure 6 depicts trajectories of vessels
that have been extracted from the datasets. Notice how the trajectories in
$\mathcal{D}_{2}$ (shown in right) contain more missing data segments than
$\mathcal{D}_{1}$ (shown in left). The reason is that $\mathcal{D}_{1}$ is
satellite-based, and data in $\mathcal{D}_{2}$ were collected by AIS base
stations.

Models and Parameters111The source code is at
www.github.com/sansastra/uncertainty_edl_graph.: The graph-based clustering
(GTR) process in Algorithm 1 uses $\epsilon=1000$ in the RDP function (Step
3), and $\varepsilon=20$ and $n_{min}=1500$ in the DBSCAN method (Step 5). A
Mahalanobis threshold $\mathcal{M}_{th}=9.2$ (Step 11) and threshold
$e_{th}=0.3$ are used for the edge selection (Step 23). The data association
(GTA) process in Algorithm 2 uses a distance threshold of 7 km (Step 4), and
$\epsilon=500$ in the RDP function (Step 6).

We use different network architectures and data feature sets for the regressor
and classifiers. The RNN-EDL regressor (see Fig. 4) has an encoder and a
decoder, each with one LSTM layer, one Dropout layer with 0.1 dropout rate,
and 128 neurons per hidden layer. The scalar constant $\lambda$ in the loss
function is set to $0.01$. Moreover, each AIS data is represented by feature
set $\mathbf{x}_{k}=\begin{bmatrix}lon,lat,cog,sog,edge\end{bmatrix}^{\top}$.
The $edge$ feature is omitted if the model is not graph-based. An input sample
consists of a $T=10$ sequential AIS data, and output sequence length $L=1$.
The data of each vessel is resampled and interpolated at $\tau=60$ seconds.
The trajectories are not interpolated for more than one hour of missing data,
to deal with vessel’s re-entry into ROI. For the training (50%) and validation
(10%) of the RNN-EDL model, only cargo, passenger and tanker vessels’
trajectories are used. However, the trained model is applied to test all
vessel types with unseen trajectories. For simplicity and visualization, only
two features $lon$ and $lat$ are used to compute Eq. (13) in the anomalous
trajectory detection. Nevertheless, we also show the uncertainty variation in
all, including $cog$ and $sog$, features for a single trajectory to highlight
their relevance in the anomaly detection and learning process respectively.

Figure 7: Left plot depicts the graph nodes and edges (in black) as created by
the GTR process using the waypoints of trajectories (in red) of maritime
traffic data (in blue). Right plot shows the refined graph (in black), and the
association of the AIS data to one of the edges (in colors) by the GTA
process. Data shown in different colors form different clusters. An outlier
cluster is shown with data points in the grey.

Figure 8: The plots show the CDFs on positional error between prediction and
ground truth for with and without (W/O) graph-based models, as well as for
different unseen vessels of ship types [0, 60) and [60, 90) in the dataset
$\mathcal{D}_{1}$. Left: Results from the RNN-EDL regression model. Right:
Results from the RNN model without the EDL layer.

The EDL classifier uses three hidden layer with 128 neurons for the unusual
turn detection. An input sample has $T=60$ consecutive AIS data with two
outputs classes: normal (labeled as [1, 0]) and anomalous (labeled as [0, 1]).
It uses only the $\textbf{x}_{k}=[cog]$ feature, and a data resampling time of
$\tau=3$ seconds. The missing data in a sample is filled by linear
interpolation. The EDL classifier for AIS OOS detection however, has only one
single hidden layer with 128 neurons, $T=2$ and
$\textbf{x}_{k}=[lon,lat,cog,sog,time]$. The pre-processing of each sample
assigns $\textbf{x}_{k}[time]\leftarrow 0$ and
$\textbf{x}_{k+1}[time]\leftarrow\textbf{x}_{k+1}[time]-\textbf{x}_{k}[time]$,
i.e., time difference between two consecutive data. Unlike the regression
model, the EDL classifiers are trained (and validated) with 50% (and 10%) data
of all ship types, while remaining 40% data is used for testing. To make the
model trained well, the number of normal and anomalous data samples are made
equal, by randomly deleting some excessive normal samples in dataset
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$. All models are trained using an Adam
optimiser.

Baseline: We use an improvised traffic routes extraction and anomaly detection
method [37] as the baseline, which is a similarity model (see Fig. 1)
originally proposed in [30]. The Similarity model uses an extracted graph $G$
to find how similar a test trajectory is as compared to the routes of a graph
$\mathbb{R}(G)$. First, a test trajectory $i$ is represented by its waypoints
$\mathbf{WP}^{i}$, for this we use the RDP with $\epsilon=1000$. Then, it
applies a Longest Common Subsequence (LCS) algorithm [50] to compute a
similarity score $S_{i}$ between the trajectory $i$ and routes of graph
$\mathbb{R}(G)$. $S_{i}$ is the ratio of the maximum LCS of nodes in
$(\mathbb{R}(G),\mathbf{WP}^{i})$ and the maximum route length. Two nodes are
defined as similar if they are within $d_{max}=7$ km range. A test trajectory
is termed as anomalous if the score $S_{i}$ is smaller than a similarity
threshold $S_{AT}$. We also implemented the RNN-MC dropout model [48] with NLL
loss function for heteroscedastic aleatoric uncertainty, keeping all the
parameters same as RNN-EDL exect the EDL and its output layers. The output
layer is replaced by a prediction of the mean and the standard deviation for
each predicted parameter. Furthermore, the dropout is enabled during the
testing phase as well and the model uncertainty is modeled as the deviation in
50 forward passes with different random dropout masks.

Evaluation Metrics: There is no reference dataset for anomalous tracks. A
quantitative analysis in terms of accuracy or a false alarm rate is therefore
not feasible. In contrast, we can evaluate the EDL classifiers for detecting
OOS and UT anomalies using the accuracy measure, confusion matrix, false
detection rate. Nevertheless, since anomalies are subjective in nature, each
detected anomaly must undergo an inspection by data (here, AIS) experts before
raising any alarm.

Figure 9: Left plot shows the ground truth and the corresponding predicted
trajectories for the left, normal, and right trajectory segments by the graph-
based RNN-EDL model. Right plots show the epistemic uncertainties estimated on
successive predictions of output data features $(lon,lat,cog,\text{and }sog)$
for the left, normal, and right trajectory segments by the model.

((a)) ship type=[0,60), $S_{AT}$=0.3

((b)) ship type=[0,60), $S_{AT}$=0.1

((c)) ship type=[60,90), $S_{AT}$=0.3

((d)) ship type=[60,90), $S_{AT}$=0.1

((e)) ship type=[0,60), $\Theta_{AT}$=0.7

((f)) ship type=[0,60), $\Theta_{AT}$=0.4

((g)) ship type=[60,90), $\Theta_{AT}$=0.7

((h)) ship type=[60,90), $\Theta_{AT}$=0.4

((i)) ship type=[0,60), $\Theta_{AT}$=0.7

((j)) ship type=[0,60), $\Theta_{AT}$=0.4

((k)) ship type=[60,90), $\Theta_{AT}$=0.7

((l)) ship type=[60,90), $\Theta_{AT}$=0.4

Figure 10: The figures show anomalous segments of vessels’ trajectories (in
red) obtained for different thresholds and ship types on dataset
$\mathcal{D}_{1}$. Top, middle, and bottom rows show results for the
Similarity, RNN-EDL, and RNN-MC dropout methods, respectively.

((a)) ship type=[0,60), $S_{AT}$=0.3

((b)) ship type=[0,60), $S_{AT}$=0.1

((c)) ship type=[60,90), $S_{AT}$=0.3

((d)) ship type=[60,90), $S_{AT}$=0.1

((e)) ship type=[0,60), $\Theta_{AT}$=0.7

((f)) ship type=[0,60), $\Theta_{AT}$=0.4

((g)) ship type=[60,90), $\Theta_{AT}$=0.7

((h)) ship type=[60,90), $\Theta_{AT}$=0.4

((i)) ship type=[0,60), $\Theta_{AT}$=0.7

((j)) ship type=[0,60), $\Theta_{AT}$=0.4

((k)) ship type=[60,90), $\Theta_{AT}$=0.7

((l)) ship type=[60,90), $\Theta_{AT}$=0.4

Figure 11: The figures show anomalous segments of vessels’ trajectories (in
red) obtained for different thresholds and ship types on dataset
$\mathcal{D}_{2}$. Top, middle, and bottom rows show results for the
Similarity, RNN-EDL, and RNN-MC dropout methods, respectively. Figure 12: Left
and right figures show the accuracy w.r.t. uncertainty threshold by the AIS
OOS classifier and the unusual turn (UT) classifier evaluating all samples and
only the anomalous samples in test datasets $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$, respectively.

Figure 13: The left plot shows the unusual turn ($>30\degree$) segments (red)
detected on a test vessel’s trajectory (black). The right plot shows the OOS
(red) detected on another test vessel moving from bottom to up direction
(black).

###  V-B GTRA Evaluation

Before showing the effectiveness of the GTRA scheme in trajectory prediction
and uncertainty estimation, we present the results on how a graph can
represent vessel movement patterns using dataset $\mathcal{D}_{1}$. Here, we
consider only passenger, cargo and tanker vessels, as they follow well-defined
trajectories. Fig. 7 (left) depicts the original graph in black that is formed
by data plotted in blue. Notice that the nodes are the centred at waypoints
(red dots) with high density. The bidirectional edges very well represent
vessel motion patterns. However, we can also see that the GTR algorithm places
a node around (12.1°, 54.3°) without any further edge connection,
misrepresenting underlying vessel movements.

Note that, since the parameters of RDP and DBSCAN are sensitive to the dataset
in question, the computed graphs might be inadequate to represent all of the
important sea lanes. This is particularly true in scenarios where the AIS-
range is limited. There may be trajectories that are recorded in-between out-
of-range source(s) or destination(s). Therefore, an expert knowledge that
might improve the traffic representation, for example, by manually adding a
node/edge to account for such limitation. Thus, as an offline process we
refined the graph by deleting the node and connecting two edges, as shown in
Fig. 7 (right). The latter additionally shows the association of data points
to one of the edges (clusters) in a color-coded fashion where a so-called
outlier edge is represented in grey. Notice that the majority of movements
show acceptable assignment to edges. Only some segments of trajectories have
been wrongly (though subjective) assigned owing to their complex maneuvers.

Impact of GTRA on prediction accuracy: Trajectory representation and
clustering has huge impact on the accuracy of trajectory prediction as well as
on the corresponding uncertainty estimation. Fig. 8 (left) illustrates this
observation using a cumulative distribution/density function (CDF), which is
obtained on the Euclidean distances (or positional errors) between ground
truth and predicted positions on trajectories of ships in the dataset
$\mathcal{D}_{1}$. Aside from the superior performance of the graph-based
prediction model, we can also notice that it is challenging to predict
trajectories of ships in range [0, 60), as compared to passenger, cargo and
tanker vessels ([60, 90)). More importantly, the RNN-EDL model without graph-
based clustering predicts more than 80% of target positions with deviation by
at least 30 km from the ground-truth data. The reason is that the model fails
to fit targets with the Gaussian distribution, as the maritime data is
dispersed. The clustered data, on the other hand, simplifies the model’s
ability to learn the motion pattern and fit the distribution. To further
investigate the impact of the EDL layer, the latter was removed from the RNN-
EDL model. The trained RNN model is then used for the prediction of
trajectories, and to plot CDFs of positional errors in Fig. 8 (right). We
observe that the prediction error significantly decreased for the RNN model
without GTRA. Nevertheless, RNN-EDL with graph in Fig. 8 (left) outperforms
others. In the next subsection, we show results of only the RNN-EDL model with
GTRA.

###  V-C Anomalous Trajectories Detection

We evaluate three trajectory segments: a _normal_ track and two anomalous
tracks in the _left_ and _right_ to get an insight on the trajectory
prediction in Fig. 9(left). Note that the left and right tracks are synthetic
data based on recorded data from a real-world (or normal) track in the middle
by changing the longitudes and latitudes. We can see from Fig. 9 (left) that
the ground truth data closely follows the predicted ones. Given an input
sequence, the model is able to correctly forecast the vessel’s position at a
future time step not only for the normal track but also for the unseen (left
and right) trajectories, which would not be the case with the other models.

Fig. 9 (right) depicts the epistemic uncertainties on successive predictions
for the three segments and over the $lon,lat,cog,sog$ data features,
respectively. We observe that the left and right tracks show an abrupt
transition (or jump) in epistemic uncertainties with respect to the normal for
all features. The change in epistemic uncertainty for the anomalous tracks are
expected for the out-of-order data distribution. Moreover, as the anomalous
segments deviate from the normal, their data might get assigned to different
edge clusters, including an outlier edge, and produce jumps in uncertainties.
For this reason, aleatoric uncertainties can also show abrupt transitions for
heterogeneous maneuvering. Also, note that despite having the same $cog$ and
$sog$ values in all three segments, the epistemic uncertainties in $cog$ and
$sog$ clearly show the transitions for the left and right tracks. This shows
that the model learnt the correlation among features well. It is also
important to mention that when we trained the RNN-EDL regressor model with
only the Rostock-Gedsar dataset (see trajectories in Fig. 2), the relative
change in the uncertainties is even higher (not shown for sake of brevity), as
it is easier for the model to learn the data distribution of trajectories
between two ports accurately. However, we are interested in developing a
single global model to detect all anomalous trajectories in the ROI.

Next, Figures 10 and 11 show all anomalous segments of each track in red for
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$, respectively. The results are
obtained for two sets of vessels, two detection thresholds using three
different models, the Similarity, RNN-EDL and RNN-MC dropout, and shown on the
top, middle and bottom rows, respectively. The similarity thresholds are
$S_{AT}=\\{0.3,0.1\\}$. The thresholds $\Theta_{AT}=\\{0.7,0.4\\}$, and
segment size $N=30$ are used for both the RNN-EDL and RNN-MC dropout models to
detect anomalous trajectories using Eq. (13). The epistemic (aleatoric)
uncertainty is used for anomalous trajectory detection by the RNN-EDL (RNN-MC
dropout) using Eq. (13). It is important to mention that the epistemic
uncertainty in the MC dropout resulted in detecting many more anomalous
trajectories at these thresholds. Unlike the EDL or MC dropout, the Similarity
model uses complete track or a larger segment to compute waypoints and the
similarity score for anomalous trajectory detection. Obviously, decreasing the
threshold decreases the number of detected anomalous segments, as the
threshold is an upper bound in Eq. (13) and a lower threshold value only
detects larger transitions. This is true for the Similarity model as well,
since two similar tracks have a higher similarity score. As expected, the
Similarity model detects ATs which are non-overlapping and further away from
the commonly traversed routes (formed by graph edges). In contrast, DL models
are able to detect anomalous segments that show unusual maneuvering and lie
across edges. Thus, the similarity and DL models are complementing each other
in finding ATs outside and within clusters. Both DL models perform well at
lower threshold $\Theta_{AT}=0.4$. Additionally, we make the following common
observations about the three models. The passenger, cargo and tanker ships’
trajectories with type [60,90) in the right two plots show lower number of
anomalous segments than other ship types shown in the left two plots at lower
threshold. We can say that the models are able to detect some unusual
maneuvering while missing out on some tracks that seem to show anomalous
behavior. At the same time, some detected anomaly segments do not seem to be
anomalous after a careful look at their tracks. Nevertheless, we observe that
having a common threshold for all ships is not the best solution. Instead, we
can set a lower threshold for passenger, cargo, and tanker vessels, and a
higher threshold for other vessel types. Another possible solution could be to
find uncertainty thresholds of normal tracks, though computationally intensive
and subjective in nature, in smaller grids of the ROI and compare them with
the estimated uncertainty on any trajectory under evaluation.

###  V-D Unusual Turn and OOS Detection

For an unusual turn detection, we choose a threshold $\Theta_{UT}=30\degree$,
considering that larger vessels generally do not take more than $30\degree$ of
turn within a short interval $T\times\tau=3$ minutes, unless constrained by
their geographical locations (which is not considered here). Thus, we evaluate
the model accuracy only for passenger, cargo and tanker vessels. On the other
hand, we set a threshold $\Theta_{OOS}=3$ minutes for the OOS anomaly
detection (Eq. 15).

In Fig. 12 we show the accuracy of the EDL classifiers against the uncertainty
threshold for all samples as well as for only anomalous samples in the
datasets. We accept the classification of a sample into a class (normal or
anomaly) if it has the highest probability and the prediction uncertainty is
below a threshold $u_{th}$. In other words, the sample’s classification by the
model is rejected if the epistemic uncertainty is above a threshold. The
following observations are made. Firstly, increasing the threshold improves
the accuracy, which suggests that the models fits well to the Dirichlet
categorical distribution. Secondly, the UT model classifies most of the
samples with higher uncertainty ($>0.2$) as compared to the OOS classifier
($<0.1$), and it achieves 90% accuracy if the uncertainty threshold
$u_{th}=0.4$. Thirdly, the UT classifier not only misclassifies anomalous
samples as normal, but also other way round, which can be seen from the
accuracy obtained on all samples and only the anomalous samples. Finally, the
OOS classifier achieves an overall accuracy of $\approx$ 99% on all samples
for uncertainty thresholds greater than 0.1. The accuracy of the EDL models
for UT and OOS detection on only anomalous samples are lower at uncertainty
thresholds below 0.4, compared to the accuracy computed on all samples. The
reason is that the models produce larger uncertainties on their predictions.
This suggests that the models find it relatively hard to learn anomalous
samples than the normal samples.

Unlike the RNN-EDL regressor model, the trained EDL classifiers on ROI data
could be used to detect UT and OOS anomalies on AIS data beyond ROI. We,
therefore, evaluate the EDL classifiers on two additional scenarios: one for
the dump cleaning (UT), and other for the AIS blackout (OOS) exercises that
was performed by a test vessel in a validation campaign of a project in July
2020 in the Bremerhaven region in Germany. The uncertainty threshold $u_{th}$
is set to 0.4. Fig. 13 (left) shows all the unusual turn segments detected,
and the right plot shows the detected AIS blackout event in red in the test
vessel’s trajectories. We observe that an unusual turn segment on the upper
left region is undetected in the left plot. Nevertheless, the classifiers are
able to detect all other UT and OOS anomalies well.

##  VI Concluding Remarks

We proposed a novel graph-based trajectory representation and association
(GTRA) method, and deep learning models to detect maritime anomalies using AIS
data. We showed that the traffic representation and association are key for
learning the AIS traffic patterns and the detection of anomalous trajectories
by the DL-based regression models. Furthermore, we evaluated three different
anomalies: anomalous trajectory using the EDL and MC dropout regressor models,
and the loss of AIS signal and unusual turn by EDL classifiers using the
uncertainties in prediction. The anomalous tracks are detected by evaluating
jumps in uncertainties on trajectory segment prediction. Similarly, the
unusual turn anomaly and the loss of AIS signal are detected by taking into
account the class probabilities and prediction uncertainty. In summary, we
make the following observations based on the proposed models and analysis
presented in the paper.

  * •

The GTRA is essential for the RNN-EDL time-series prediction model in order to
learn distribution of maritime trajectories. In contrast to an RNN model
without the EDL layer, the prediction performance of the RNN-EDL model
decreases significantly when trained without the graph-based clustered data.

  * •

The epistemic and aleatoric uncertainties obtained on prediction by the DL
regressor models are very useful in anomalous trajectory detection. These
models together with a similarity model can detect anomalous trajectories
within and outside sea-lanes. While DL classifier models can be useful in
detecting unusual turn and the loss of AIS signal.

  * •

Typically, a lower detection threshold for passenger, cargo and tankers
vessels, and higher for other ship types can be set to detect anomalous
tracks. Additionally, large vessels taking usually fixed routes show lower
number of anomalous track segments than other vessels, for example, fishing.

This work opens deeper research activities within the field of leveraging deep
learning uncertainties in maritime anomaly detection. Moreover, the work might
be useful in detecting anomalies in other domains of transportation. Lastly,
in the absence of reference anomalous routes, expert knowledge will always be
required before taking any action upon detection of anomalies.

## Acknowledgment

We would like to thank Dr. Frank Heymann and Juan C. Machuca for providing
valuable inputs that shaped the paper. This work has been partially funded by
the German federal ministry for economic affairs and energy project
IntelliMar, and the German federal ministry of education and research project
European Maritime Safety III.

## References

  * [1] United Nations Conference on Trade and Development (UNCTAD), “Review of maritime transport 2020,” Tech. Rep., 2021.
  * [2] “Automatic identification system overview,” _The navigation center of excellence_ , 2018. [Online]. Available: https://www.navcen.uscg.gov/?pageName=AISmain
  * [3] D. Medina, C. Lass, E. P. Marcos, R. Ziebold, P. Closas, and J. García, “On GNSS Jamming Threat from the Maritime Navigation Perspective,” in _2019 22th International Conference on Information Fusion (FUSION)_. IEEE, 2019, pp. 1–7.
  * [4] S. Kazemi, S. Abghari, N. Lavesson, H. Johnson, and P. Ryman, “Open data for anomaly detection in maritime surveillance,” _Expert Systems with Applications_ , vol. 40, no. 14, pp. 5719–5729, 2013.
  * [5] E. Tu, G. Zhang, L. Rachmawati, E. Rajabally, and G.-B. Huang, “Exploiting ais data for intelligent maritime navigation: a comprehensive survey from data to methodology,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, no. 5, pp. 1559–1582, 2018.
  * [6] M. Riveiro, G. Pallotta, and M. Vespe, “Maritime anomaly detection: A review,” _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ , vol. 8, no. 5, p. e1266, 2018.
  * [7] E. R. Hruschka, E. R. Hruschka, and N. F. F. Ebecken, “Bayesian networks for imputation in classification problems,” _Journal of Intelligent Information Systems_ , vol. 29, no. 3, pp. 231–252, Dec 2007.
  * [8] M. Guerriero, S. Coraluppi, C. Carthel, and P. Willett, “Analysis of ais intermittency and vessel characterization using a hidden markov model.” in _Gi jahrestagung (2)_ , 2010.
  * [9] K. Kowalska and L. Peel, “Maritime anomaly detection using gaussian process active learning,” in _2012 15th International Conference on Information Fusion_ , July 2012, pp. 1164–1171.
  * [10] L. P. Perera, P. Oliveira, and C. G. Soares, “Maritime traffic monitoring based on vessel detection, tracking, state estimation, and trajectory prediction,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 13, no. 3, pp. 1188–1200, 2012.
  * [11] F. Mazzarella, V. F. Arguedas, and M. Vespe, “Knowledge-based vessel position prediction using historical ais data,” in _2015 Sensor Data Fusion: Trends, Solutions, Applications (SDF)_ , 2015, pp. 1–6.
  * [12] F. Mazzarella, M. Vespe, A. Alessandrini, D. Tarchi, G. Aulicino, and A. Vollero, “A novel anomaly detection approach to identify intentional ais on-off switching,” _Expert Systems with Applications_ , vol. 78, pp. 110–123, 2017.
  * [13] D. Nguyen, R. Vadaine, G. Hajduch, R. Garello, and R. Fablet, “Geotracknet–a maritime anomaly detector using probabilistic neural network representation of ais tracks and a contrario detection,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * [14] Z. Yuan, J. Liu, Y. Liu, and Z. Li, “A novel approach for vessel trajectory reconstruction using ais data,” in _The 29th International Ocean and Polar Engineering Conference_. International Society of Offshore and Polar Engineers, 2019.
  * [15] H. Zhong, X. Song, and L. Yang, “Vessel classification from space-based ais data using random forest,” in _2019 5th International Conference on Big Data and Information Analytics (BigDIA)_. IEEE, 2019, pp. 9–12.
  * [16] S. K. Singh and F. Heymann, “Machine learning-assisted anomaly detection in maritime navigation using ais data,” in _IEEE/ION Position Location and Navigation Symposium (PLANS), USA_ , 2020.
  * [17] S. K. Singh and F. Heymann, “On the effectiveness of ai-assisted anomaly detection methods in maritime navigation,” in _2020 IEEE 23rd International Conference on Information Fusion (FUSION)_ , 2020, pp. 1–7.
  * [18] M. Bensalem, S. K. Singh, and A. Jukan, “On detecting and preventing jamming attacks with machine learning in optical networks,” in _2019 IEEE Global Communications Conference (GLOBECOM)_. IEEE, 2019, pp. 1–6.
  * [19] H. Peng, J. Li, Y. Song, R. Yang, R. Ranjan, P. S. Yu, and L. He, “Streaming social event detection and evolution discovery in heterogeneous information networks,” _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , vol. 15, no. 5, pp. 1–33, 2021.
  * [20] W. Hu, X. Xiao, Z. Fu, D. Xie, T. Tan, and S. Maybank, “A system for learning statistical motion patterns,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 28, no. 9, pp. 1450–1464, 2006.
  * [21] C. Piciarelli, C. Micheloni, and G. L. Foresti, “Trajectory-based anomalous event detection,” _IEEE Transactions on Circuits and Systems for video Technology_ , vol. 18, no. 11, pp. 1544–1554, 2008.
  * [22] J. Wang, Y. Yuan, T. Ni, Y. Ma, M. Liu, G. Xu, and W. Shen, “Anomalous trajectory detection and classification based on difference and intersection set distance,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 3, pp. 2487–2500, 2020.
  * [23] Y. Gal and Z. Ghahramani, “Bayesian convolutional neural networks with bernoulli approximate variational inference,” 2016.
  * [24] A. Kendall and Y. Gal, “What uncertainties do we need in bayesian deep learning for computer vision?” in _Advances in neural information processing systems_ , 2017, pp. 5574–5584.
  * [25] M. Sensoy, L. Kaplan, and M. Kandemir, “Evidential deep learning to quantify classification uncertainty,” in _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 2018, pp. 3183–3193.
  * [26] A. Amini, W. Schwarting, A. Soleimany, and D. Rus, “Deep evidential regression,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * [27] C. Stauffer and W. E. L. Grimson, “Learning patterns of activity using real-time tracking,” _IEEE Transactions on pattern analysis and machine intelligence_ , vol. 22, no. 8, pp. 747–757, 2000.
  * [28] W. Hu, T. Tan, L. Wang, and S. Maybank, “A survey on visual surveillance of object motion and behaviors,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , vol. 34, no. 3, pp. 334–352, 2004.
  * [29] A. Belhadi, Y. Djenouri, J. C.-W. Lin, and A. Cano, “Trajectory outlier detection: Algorithms, taxonomies, evaluation, and open challenges,” _ACM Transactions on Management Information Systems (TMIS)_ , vol. 11, no. 3, pp. 1–29, 2020.
  * [30] G. Pallotta, M. Vespe, and K. Bryan, “Vessel pattern knowledge discovery from ais data: A framework for anomaly detection and route prediction,” _Entropy_ , vol. 15, no. 6, pp. 2218–2245, 2013.
  * [31] V. F. Arguedas, F. Mazzarella, and M. Vespe, “Spatio-temporal data mining for maritime situational awareness,” in _OCEANS 2015-Genova_. IEEE, 2015, pp. 1–8.
  * [32] Z. Xiao, L. Ponnambalam, X. Fu, and W. Zhang, “Maritime traffic probabilistic forecasting based on vessels’ waterway patterns and motion behaviors,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 18, no. 11, pp. 3122–3134, 2017.
  * [33] D. K. Prasad, D. Rajan, L. Rachmawati, E. Rajabally, and C. Quek, “Video processing from electro-optical sensors for object detection and tracking in a maritime environment: a survey,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 18, no. 8, pp. 1993–2016, 2017.
  * [34] S. Capobianco, L. M. Millefiori, N. Forti, P. Braca, and P. Willett, “Deep learning methods for vessel trajectory prediction based on recurrent neural networks,” _arXiv preprint arXiv:2101.02486_ , 2021.
  * [35] P. Coscia, P. Braca, L. M. Millefiori, F. A. Palmieri, and P. Willett, “Multiple ornstein–uhlenbeck processes for maritime traffic graph representation,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 54, no. 5, pp. 2158–2170, 2018.
  * [36] E. d’Afflisio, P. Braca, L. M. Millefiori, and P. Willett, “Detecting anomalous deviations from standard maritime routes using the ornstein–uhlenbeck process,” _IEEE Transactions on Signal Processing_ , vol. 66, no. 24, pp. 6474–6487, 2018.
  * [37] G. B. Karataş, P. Karagoz, and O. Ayran, “Trajectory pattern extraction and anomaly detection for maritime vessels,” _Internet of Things_ , p. 100436, 2021.
  * [38] A. Karami and R. Johansson, “Choosing dbscan parameters automatically using differential evolution,” _International Journal of Computer Applications_ , vol. 91, no. 7, pp. 1–11, 2014.
  * [39] Z. Xiao, X. Fu, L. Zhang, and R. S. M. Goh, “Traffic pattern mining and forecasting technologies in maritime traffic service networks: A comprehensive survey,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 5, pp. 1796–1825, 2019.
  * [40] S. Thombre, Z. Zhao, H. Ramm-Schmidt, J. M. V. García, T. Malkamäki, S. Nikolskiy, T. Hammarberg, H. Nuortie, M. Z. H. Bhuiyan, S. Särkkä _et al._ , “Sensors and ai techniques for situational awareness in autonomous ships: A review,” _IEEE Transactions on Intelligent Transportation Systems_ , 2020.
  * [41] Z. Xiao, X. Fu, L. Zhang, W. Zhang, R. W. Liu, Z. Liu, and R. S. M. Goh, “Big data driven vessel trajectory and navigating state prediction with adaptive learning, motion modeling and particle filtering techniques,” _IEEE Transactions on Intelligent Transportation Systems_ , 2020.
  * [42] A. Aubry, P. Braca, E. d’Afflisio, A. De Maio, L. M. Millefiori, and P. Willett, “Optimal opponent stealth trajectory planning based on an efficient optimization technique,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 270–283, 2020.
  * [43] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [44] K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, “Learning phrase representations using rnn encoder–decoder for statistical machine translation,” in _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 2014, pp. 1724–1734.
  * [45] M. Liang, R. W. Liu, Q. Zhong, J. Liu, and J. Zhang, “Neural network-based automatic reconstruction of missing vessel trajectory data,” in _2019 IEEE 4th International Conference on Big Data Analytics (ICBDA)_ , 2019, pp. 426–430.
  * [46] N. Forti, L. M. Millefiori, P. Braca, and P. Willett, “Prediction oof vessel trajectories from ais data via sequence-to-sequence recurrent neural networks,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 8936–8940.
  * [47] C. E. Rasmussen and C. K. I. Williams, _Gaussian processes formachine learning_. MIT Press, 2006.
  * [48] Y. Gal and Z. Ghahramani, “Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning,” in _international conference on machine learning_. PMLR, 2016, pp. 1050–1059.
  * [49] D. H. Douglas and T. K. Peucker, “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature,” _Cartographica: the international journal for geographic information and geovisualization_ , vol. 10, no. 2, pp. 112–122, 1973.
  * [50] D. S. Hirschberg, “A linear space algorithm for computing maximal common subsequences,” _Communications of the ACM_ , vol. 18, no. 6, pp. 341–343, 1975.

|  Sandeep Kumar Singh (SM’15, M’20) is a postdoctoral researcher in the
department of Electrical and Computer Engineering at the University of
California, Davis, USA. He received his PhD in Computer and Network
Engineering from the Technical University of Braunschweig, Germany in 2019,
and M.S. degree in Electrical Engineering from the Indian Institute of
Technology, Madras, India in 2014. He was a research scientist at the
Institute of Communication and Navigation, at the German Aerospace Center,
Germany from 2019 to 2021. He was a recipient of German Scholarship DAAD in
2011-12 to pursue research at the Technical University of Berlin, Germany. His
research interests include communication and navigation, data center
networking, quantum communication, and machine learning.
---|---
|  Jaya Shradha Fowdur is currently working towards her PhD in Computer
Science with the Institute of Communications and Navigation at the German
Aerospace Centre and the University of Göttingen, Germany since 2018. She
received her Master’s degree in Applied Computer Science with specialisation
in Computational Neuroscience from the University of Göttingen in 2017. Her
research interests include clustering, machine learning, target tracking, and
AIS- and radar- data processing in the maritime domain.
---|---
|  Jakob Gawlikowski received the bachelor’s and master’s degree in
mathematics from the Technical University of Munich, Munich, Germany in 2015
and 2019. He is currently a researcher at the ”Institute of Data Science”,
German Aerospace Center (DLR), Jena, Germany and working towards the Ph.D.
degree with the Technical University of Munich, Munich, Germany, and the
German Aerospace Center in Munich, Munich, Germany. His research interests are
related to multi-modal machine learning, uncertainty quantification and
robustness in deep learning models with a special focus on applications in the
field of remote sensing.
---|---
|  Daniel Medina (SM’16, M’20) his B.S. in Electrical Engineering from the
University of Malaga and his M.S. in Computer Science from University Carlos
III Madrid in 2014 and 2016 respectively. He is at the verge of completing his
PhD on robust filtering and satellite-based precise localization and attitude
estimation. Since 2016, he has been a research fellow at the Institute of
Communications and Navigation of the German Aerospace Center. He is currently
the Vice-Chair for the IEEE ITSS Germany Chapter. His primary areas of
interest include signal processing, estimation theory, nonlinear and robust
filtering with applications to tracking, navigation and remote sensing.
---|---


11institutetext: Laboratoire de Combinatoire et d’Informatique Mathématique,
Université du Québec à Montréal,
CP 8888 Succ. Centre-ville, Montréal (QC) Canada H3C 3P8
11email<EMAIL_ADDRESS>
# An upper bound of the number of distinct powers in binary words

Shuo Li

###### Abstract

A _power_ is a word of the form $\underbrace{uu...u}_{k\;\text{times}}$, where
$u$ is a word and $k$ is a positive integer and a _square_ is a word of the
form $uu$. Fraenkel and Simpson conjectured in 1998 that the number of
distinct squares in a word is bounded by the length of the word. This
conjecture was proven recently by Brlek and Li. Besides, there exists a
stronger upper bound for binary words conjectured by Jonoska, Manea and Seki
stating that for a word of length $n$ over the alphabet
$\left\\{a,b\right\\}$, if we let $k$ be the least of the number of a’s and
the number of b’s and $k\geq 2$, then the number of distinct squares is upper
bounded by $\frac{2k-1}{2k+2}n$. In this article, we prove this conjecture by
giving a stronger statement on the number of distinct powers in a binary word.

##  1 Introduction

A _power_ is a word of the form $\underbrace{uu...u}_{k\;\text{times}}$, where
$u$ is a word and $k$ is a positive integer; the power is also called a
$k$-power and $k$ is its exponent. The upper bound of the number of distinct
$k$-powers in a finite word was studied in [7, 9, 10] and the best known
result is as follows:

######  Theorem 1 (Theorem 1 and Theorem 2 in [10] )

For every finite word $w$, let $m(w)$ denote the number of distinct nonempty
powers of exponent at least 2 in $w$, let $m_{k}(w)$ denote the number of
distinct nonempty $k$-powers in $w$, let $|w|$ denote the length of $w$ and
let $|\hbox{\rm Alph}(w)|$ denote the number of distinct letters in $w$, then
one has

$m(w)\leq|w|-|\hbox{\rm Alph}(w)|;$

Moreover, for any integer $k\geq 2$,

$m_{k}(w)\leq\frac{|w|-|\hbox{\rm Alph}(w)|}{k-1}.$

Particularly, a square is a $2$-power and upper bound of the number of
distinct squares in a finite word was studied in [4, 5, 8, 3, 11, 2]. A
conjecture of Fraenkel and Simpson [4] states that the number of distinct
squares in a word is bounded by the length of the word. This conjecture is
confirmed by the previous theorem. Besides, there exists a stronger upper
bound for binary words conjectured by Jonoska, Manea and Seki [6]:

###### Theorem 2

Let $w$ be a finite word over the alphabet $\left\\{a,b\right\\}$, let $s(w)$
denote the number of distinct squares in $w$ and let $k$ denote the least of
the number of a’s and the number of b’s in $w$. If $k\geq 2$, then one has

$s(w)\leq\frac{2k-1}{2k+2}|w|.$

In this article, we confirm this conjecture by proving the following result:

###### Theorem 3

Let $w$ be a finite word over the alphabet $\left\\{a,b\right\\}$ such that
$w=a^{r_{1}}ba^{r_{2}}ba^{r_{3}}b...a^{r_{k}}ba^{r_{k+1}}$, where
$r_{1},r_{2},...,r_{k+1}$ are nonnegative integers and
$a^{n}=\underbrace{aa...a}_{n\;\text{times}}$. Let $\sigma$ be a permutation
of $1,2,...,k+1$ such that $r_{\sigma(1)}\leq r_{\sigma(2)}\leq...\leq
r_{\sigma(k+1)}$, let $m(w)$ denote the number of distinct nonempty powers of
exponent at least 2 in $w$ and let $|w|$ denote the length of $w$. Then one
has

$m(w)+r_{\sigma(k)}\leq|w|-2.$

##  2 Preliminaries

Let $\sum$ be an _alphabet_ and $\sum^{*}$ be the set of all words over
$\sum$. Let $w\in\sum^{*}$. By $|w|$, we denote its _length_. A word of length
$0$ is called the _empty word_ and it is denoted by $\varepsilon$. A word $u$
is a _factor_ of $w$ if $w=pus$ for some words $p,s$. When $p=\varepsilon$
(resp. $s=\varepsilon$), $u$ is called a _prefix_ (resp. _suffix_) of $w$. The
set of all nonempty factors of $w$ is denoted by $\hbox{\rm Fac}(w)$. The
number of occurrences of a factor $u\in w$ is denoted by $|w|_{u}$.

Let $w$ be a finite word. For any integer $i$ satisfying $1\leq i\leq|w|$, let
$L_{w}(i)$ be the set of all length-$i$ factors of $w$ and let $C_{w}(i)$ be
the cardinality of $L_{w}(i)$. For any natural number $k$, we define the
$k$-th power of a finite word $u$ to be $u^{k}=uu\cdots u$ and it consists of
the concatenation of $k$ copies of $u$. A finite word $w$ is said to be
primitive if it is not a power of another word, that is, $w=u^{k}$ implies
$k=1$. A _square_ is a $2$-power, that is a word $w$ satisfying $w=uu$ for a
certain word $u$.

For a finite word $w$, let $\hbox{\rm Prim}(w)$ denote the set of primitive
factors of $w$, let

$M(w)=\left\\{p^{i}|p^{i}\in\hbox{\rm Fac}(w),p\in\hbox{\rm
Prim}(w),i\in\mathbf{N},i\geq 2\right\\},$
$S(w)=\left\\{p^{2i}|p^{2i}\in\hbox{\rm Fac}(w),p\in\hbox{\rm
Prim}(w),i\in\mathbf{N},i\geq 1\right\\},$
$NS(w)=\left\\{p^{2i+1}|p^{2i+1}\in\hbox{\rm Fac}(w),p\in\hbox{\rm
Prim}(w),i\in\mathbf{N},i\geq 1\right\\},$

and let $m(w)$,$s(w)$ and $ns(w)$ be respectively the cardinality of $M(w)$,
$S(w)$ and $NS(w)$. Obviously, $M(w)=S(w)\cup NS(w)$, $m(w)=s(w)+ns(w)$ and
$s(w)$ is the number of distinct nonempty squares in $w$.

Here we recall some elementary definitions and proprieties concerning graphs
from Berge [1].

A directed graph consists of a nonempty set of vertices $V$ and a set of edges
$E$. A vertex $a$ represents an endpoint of an edge and an edge joins two
vertices $a,b$ in order. A chain is a sequence of edges
$e_{1},e_{2},\cdots,e_{k}$, such that there exists a sequence of vertices
$v_{1},v_{2},\cdots,v_{k+1}$ and that for each $i$ satisfying $1\leq i\leq k$,
$e_{i}$ is either directed from $v_{i}$ to $v_{i+1}$ or from $v_{i+1}$ to
$v_{i}$. A cycle is a finite chain such that $v_{k+1}=v_{1}$. A path is a
sequence of edges $e_{1},e_{2},\cdots,e_{k}$, such that there exists a
sequence of vertices $v_{1},v_{2},\cdots,v_{k+1}$ and that for each $i$
satisfying $1\leq i\leq k$, $e_{i}$ is directed from $v_{i}$ to $v_{i+1}$. A
circuit is a finite path such that $v_{k+1}=v_{1}$.

A cycle or a circuit is called elementary if, apart from $v_{1}$ and
$v_{k+1}$, every vertex which it meets is distinct. A directed graph is called
weakly connected if for any couple of vertices $a,b$ in this graph, there
exists a chain connecting $a$ and $b$.

Let $G$ be a weakly connected graph and let $\left\\{e_{1},e_{2}\cdots
e_{l}\right\\}$, $\left\\{v_{1},v_{2}\cdots v_{s}\right\\}$ denote
respectively the edge set and the vertex set of $G$. The number
$\chi(G)=l-s+1$ is called the cyclomatic number of $G$.

Let $C$ be a cycle in $G$. A vector $\mu(C)=(c_{1},c_{2}\cdots c_{l})$ in the
$l$-dimensional space $\mathbb{R}^{l}$ is called the vector-cycle
corresponding to $C$ if $c_{i}$ is the number of visits of the edge $e_{i}$ in
the cycle $C$ for all $i$ satisfying $1\leq i\leq l$. The cycle
$C_{1},C_{2},\cdots,C_{k},...$ are said to be independent if their
corresponding vectors are linearly independent.

######  Theorem 4 (Theorem 2, Chapter 4 in [1])

the cyclomatic number of a graph is the maximum number of independent cycles
in this graph.

##  3 Rauzy graphs

Let $w$ be a finite word. For any integer $i$ satisfying $1\leq i\leq|w|$, the
$i$-th Rauzy graph $\Gamma_{w}(i)$ of $w$ is defined to be an directed graph
whose vertex set is $L_{w}(i)$ and the edge set is $L_{w}(i+1)$; an edge $e\in
L_{w}(i+1)$ starts at the vertex $u$ and ends at the vertex $v$, if $u$ is a
prefix and $v$ is a suffix of $e$. Let us define
$\Gamma_{w}=\cup_{n=1}^{k-1}\Gamma_{w}(n)$.

Let $\Gamma_{w}(i)$ be a Rauzy graph of $w$ for some $i$, a sub-graph on
$\Gamma_{w}(i)$ is called a small circuit if it is an elementary circuit and
the number of its vertices is no larger than $i$.

######  Lemma 5 (Lemma 8 in [2])

Let $w$ be a finite word and let $\Gamma_{w}(i)$ be a Rauzy graph of $w$ for
some $i$. Then all small circuits on $\Gamma_{w}(i)$ are independent.

######  Lemma 6 (Lemma 6 in [10])

Let $w$ be a finite word, then there exists an injection from $M(w)$ to the
set of all small circuits on $\Gamma_{w}$.

###### Example 7

Let us consider the word $u=abaaabaaaabaaba$, the Rauzy graph $\Gamma_{u}(4)$
is as follows:

$aaab$$aaba$$baaa$$abaa$$baab$$aaaa$$aaaab$$abaaa$$baaab$$aaaba$$aabaa$$baaaa$$abaab$$baaba$

In this graph, there are three circuits:
$C_{1}=\left\\{\left\\{aaab,aaba,abaa,baaa\right\\},\left\\{aaaba,aabaa,abaaa,baaab\right\\}\right\\}$,
$C_{2}=\left\\{\left\\{aaba,abaa,baab\right\\},\left\\{aabaa,abaab,baaba\right\\}\right\\}$
and
$C_{3}=\left\\{\left\\{aaab,aaba,abaa,baaa,aaaa\right\\},\left\\{aaaba,aabaa,abaaa,baaaa,aaaab\right\\}\right\\}$.
Two of them are small, they are $C_{1}$ and $C_{2}$, while $C_{3}$ is not
small. ∎

##  4 Proof of Theorem 3

###### Lemma 8

Let $w\in\left\\{a,b\right\\}^{*}$ and let $i$ be an integer satisfying $1\leq
i\leq|w|$. If there exists an elementary circuit on $\Gamma_{w}(i)$ containing
the edge $a^{i}b$, then this circuit is not a small circuit and it is
independent with all the small circuits on $\Gamma_{w}(i)$. Let $C_{sp}(i)$
denote one of these circuits (if any).

###### Proof

We first prove that, if there exists a small circuit passing through the
vertex $a^{i}$, then it should be the sub-graph
$\left\\{\left\\{a^{i}\right\\},\left\\{a^{i+1}\right\\}\right\\}$ of
$\Gamma_{w}(i)$. In fact, if there exists a path $e_{1},e_{2},...,e_{k}$ from
$a^{i}$ to $a^{i}$ satisfying $k\leq i$, let $p=l_{1}l_{2}...l_{k}$ be a word
such that $l_{j}$ is the last letter of $e_{j}$ for all $j$ satisfying that
$1\leq j\leq k$. From the hypothesis that $e_{1},e_{2},...,e_{k}$ form a
circuit, we can deduce that $a^{i}$ is a suffix of $a^{i}p$. Moreover, as
$|p|=k\leq i$, $l_{j}=a$ for all $j$. Consequently, $e_{j}=a^{i+1}$ for all
$j$. Thus, from the unicity of each edge, we prove that there exists only one
edge on the path and the graph is given by
$\left\\{\left\\{a^{i}\right\\},\left\\{a^{i+1}\right\\}\right\\}$.

If their exists an elementary circuit $C$ on $\Gamma_{w}(i)$ containing the
edge $a^{i}b$, from the fact that $a^{i}b$ cannot be contained in any small
circuit on $\Gamma_{w}(i)$, we conclude that $C$ is not a small circuit and
independent with all the small circuits on $\Gamma_{w}(i)$.∎

###### Lemma 9

Let $w\in\left\\{a,b\right\\}^{*}$ such that
$w=a^{r_{1}}ba^{r_{2}}ba^{r_{3}}b...a^{r_{k}}ba^{r_{k+1}}$ with $r_{j}\geq 0$
for all $j$ satisfying $1\leq j\leq k+1$. Let $\sigma$ be a permutation of
$1,2,...,k+1$ such that $r_{\sigma(1)}\leq r_{\sigma(2)}\leq...\leq
r_{\sigma(k+1)}$. Then for any integer $i$ satisfying $1\leq i\leq\sigma(k)$,
there exists a $C_{sp}(i)$ on $\Gamma_{w}(i)$.

###### Proof

From the hypothesis that $i\leq r_{\sigma(k)}\leq r_{\sigma(k+1)}$, there
exists a nonempty word $X$ such that $a^{i}Xa^{i}\in\hbox{\rm Fac}(w)$ and
that

$X=\begin{cases}bYb\;\text{if $|X|\geq 2$};\\\
b\;\;\;\;\;\text{otherwise}.\end{cases}$

Moreover, we can suppose that $a^{i}\not\in\hbox{\rm Fac}(Y)$. Indeed, there
exists a circuit on $\Gamma_{a^{i}Xa^{i}}(i)$ containing the edge $a^{i}b$ and
$\Gamma_{a^{i}Xa^{i}}(i)$ is a sub-graph of $\Gamma_{w}(i)$. Thus, there
exists a $C_{sp}(i)$ on $\Gamma_{w}(i)$.∎

###### Lemma 10

Let $w\in\left\\{a,b\right\\}^{*}$ and let $I_{w}$ be the cardinality of

$S_{w}=\left\\{i|1\leq i\leq|w|,\;\text{there exists a circuit $C_{sp}(i)$ on
$\Gamma_{w}(i)$}\right\\},$

then

$m(w)+I_{w}\leq|w|-|\hbox{\rm Alph}(w)|.$

###### Proof

Let $\hbox{\rm sc}_{w}(i)$ denote the number of small circuits on
$\Gamma_{w}(i)$. From Lemma 5, Lemma 8 and Theorem 4, for any $i\in S_{w}$,

$\hbox{\rm sc}_{w}(i)+1\leq C_{w}(i+1)-C_{w}(i)+1;$

and for any $i\not\in S_{w}$,

$\hbox{\rm sc}_{w}(i)\leq C_{w}(i+1)-C_{w}(i)+1.$

Consequently,

$\sum_{i=1}^{|w|}\hbox{\rm
sc}_{w}(i)+I_{w}\leq\sum_{i=1}^{|w|}C_{w}(i+1)-C_{w}(i)+1=|w|-|\hbox{\rm
Alph}(w)|.$

Moreover, from 6, $m(w)\leq\sum_{i=1}^{|w|}\hbox{\rm sc}(i)$, thus,
$m(w)+I_{w}\leq|w|-|\hbox{\rm Alph}(w)|$. ∎

######  Proof (of Theorem 3)

It is a direct consequence of Lemma 10 and Lemma 9. ∎

##  5 Proof of Theorem 2

In this section, Let $w\in\left\\{a,b\right\\}^{*}$ such that
$|w|_{a}\geq|w|_{b}$, that $|w|_{b}=k$ and that
$w=a^{r_{1}}ba^{r_{2}}ba^{r_{3}}b...a^{r_{k}}ba^{r_{k+1}}$ with $r_{j}\geq 0$
for all $j$ satisfying $1\leq j\leq k+1$.

Let $\delta$ be an integer such that $|w|_{a}=k+\delta$. From the hypothesis
$|w|_{a}\geq|w|_{b}$, we can suppose $\delta\geq 0$ and $|w|=2k+\delta$. Let
$\delta=n(k+1)+i$ with $n\geq 0$ and $0\leq i\leq k$.

Let $\sigma$ be a permutation of $1,2,...,k+1$ such that $r_{\sigma(1)}\leq
r_{\sigma(2)}\leq...\leq r_{\sigma(k+1)}$.

For any real number $x$, let $\lfloor x\rfloor$ to be the integer part of $x$.

######  Lemma 11 (Proposition 2 in [6] )

Theorem 2 holds if $k\leq 9$.

###### Lemma 12

$s(w)+1+\lfloor\frac{3n}{2}+\frac{3i}{2(k+1)}\rfloor\leq|w|-2\implies
s(w)\leq\frac{2k-1}{2k+2}|w|.$

###### Proof

$\displaystyle s(w)\leq\frac{2k-1}{2k+2}|w|$ $\displaystyle\Longleftarrow$
$\displaystyle s(w)\leq\lfloor\frac{2k-1}{2k+2}|w|\rfloor$
$\displaystyle\Longleftarrow$ $\displaystyle
s(w)\leq|w|-\lfloor\frac{3}{2k+2}(2k+\delta)\rfloor$
$\displaystyle\Longleftarrow$ $\displaystyle
s(w)\leq|w|-\lfloor\frac{3k}{k+1}+\frac{3\delta}{2(k+1)}\rfloor$
$\displaystyle\Longleftarrow$ $\displaystyle
s(w)\leq|w|-2-\lfloor\frac{k-2}{k+1}+\frac{3\delta}{2(k+1)}\rfloor$
$\displaystyle\Longleftarrow$ $\displaystyle
s(w)+\lfloor\frac{k-2}{k+1}+\frac{3\delta}{2(k+1)}\rfloor\leq|w|-2$
$\displaystyle\Longleftarrow$ $\displaystyle
s(w)+1+\lfloor\frac{3\delta}{2(k+1)}\rfloor\leq|w|-2.$

From the definition, $\delta=n(k+1)+i$, thus,

$s(w)+1+\lfloor\frac{3n}{2}+\frac{3i}{2(k+1)}\rfloor\leq|w|-2\implies
s(w)\leq\frac{2k-1}{2k+2}|w|.$

∎

###### Lemma 13

$s(w)+1+\lfloor\frac{3n}{2}+\frac{3i}{2(k+1)}\rfloor\leq
m(w)+r_{\sigma(k)}\implies s(w)\leq\frac{2k-1}{2k+2}|w|.$ (1)

Moreover,

$1+\lfloor\frac{3(n+1)}{2}\rfloor\leq\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor+r_{\sigma(k)}\implies
s(w)\leq\frac{2k-1}{2k+2}|w|.$ (2)

###### Proof

The first part is a direct consequence of Theorem 3 and Lemma 12.
For the second part, from the hypothesis that $i\leq k$, we have

$\lfloor\frac{3n}{2}+\frac{3i}{2(k+1)}\rfloor\leq\lfloor\frac{3(n+1)}{2}\rfloor.$

Moreover, from the fact that

$\left\\{a^{2i+1}|1\leq
i\leq\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor\right\\}\subset NS(w),$

we have

$s(w)+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor\leq m(s).$

∎

###### Lemma 14

If $r_{\sigma(k)}\geq n+2$, then

$1+\lfloor\frac{3(n+1)}{2}\rfloor\leq
r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor.$

###### Proof

If $r_{\sigma(k)}\geq n+2$, then $r_{\sigma(k+1)}\geq n+2$.

If $n$ is odd, let $n=2t+1$, then

$\displaystyle r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\geq(2t+1)+2+\lfloor\frac{(2t+1)+2-1}{2}\rfloor$
$\displaystyle\geq 3t+4$
$\displaystyle\geq\lfloor\frac{3((2t+1)+1)}{2}\rfloor+1.$

If $n$ is even, let $n=2t$, then

$\displaystyle r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\geq(2t)+2+\lfloor\frac{(2t)+2-1}{2}\rfloor$ $\displaystyle\geq
3t+2$ $\displaystyle\geq\lfloor\frac{3((2t)+1)}{2}\rfloor+1.$

∎

###### Lemma 15

If $r_{\sigma(k)}\leq n$ and $k\geq 8$ then

$1+\lfloor\frac{3(n+1)}{2}\rfloor\leq
r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor.$

###### Proof

If $r_{\sigma(k)}\leq n$, let us suppose $r_{\sigma(k)}=m$. Then

$\sum_{j=1}^{k}r_{\sigma(j)}\leq mk.$

From the fact that $\sum_{j=1}^{k+1}r_{\sigma(j)}=k+\delta,$

$r_{\sigma(k+1)}\geq k+\delta-mk\geq n(k+1)-mk+k.$

Thus,

$\displaystyle 1+\lfloor\frac{3(n+1)}{2}\rfloor\leq
r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\Longleftarrow$ $\displaystyle 1+\frac{3(n+1)}{2}\leq
r_{\sigma(k)}+\frac{r_{\sigma(k+1)}-1}{2}-1$ $\displaystyle\Longleftarrow$
$\displaystyle\frac{5}{2}+\frac{3n}{2}\leq m+\frac{n(k+1)-mk+k-1}{2}-1$
$\displaystyle\Longleftarrow$ $\displaystyle 3n+5\leq 2m+n(k+1)-mk+k-1-2$
$\displaystyle\Longleftarrow$ $\displaystyle 3n+5\leq n(k+1)-m(k-2)+k-3$
$\displaystyle\Longleftarrow$ $\displaystyle 3n+5\leq
n(k+1)-n(k-2)+k-3\;\;(*)$ $\displaystyle\Longleftarrow$ $\displaystyle
3n+5\leq 3n+k-3$ $\displaystyle\Longleftarrow$ $\displaystyle 8\leq k.$

The relation (*) holds because $k-2\geq 0$ and $m\leq n$ from hypothesis. ∎

###### Lemma 16

If $r_{\sigma(k)}=n+1$ and $r_{\sigma(k+1)}\geq n+4$, then

$1+\lfloor\frac{3(n+1)}{2}\rfloor\leq
r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor.$

###### Proof

If $n$ is odd, let $n=2t+1$, then

$\displaystyle r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\geq(2t+1)+1+\lfloor\frac{(2t+1)+4-1}{2}\rfloor$
$\displaystyle\geq 3t+4$
$\displaystyle\geq\lfloor\frac{3((2t+1)+1)}{2}\rfloor+1.$

If $n$ is even, let $n=2t$, then

$\displaystyle r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\geq(2t)+1+\lfloor\frac{(2t)+4-1}{2}\rfloor$ $\displaystyle\geq
3t+2$ $\displaystyle\geq\lfloor\frac{3((2t)+1)}{2}\rfloor+1.$

∎

###### Lemma 17

If $r_{\sigma(k)}=n+1,r_{\sigma(k+1)}\leq n+3$ and $k\geq 10$ then

$s(w)+1+\lfloor\frac{3n}{2}+\frac{3i}{2(k+1)}\rfloor\leq
s(w)+r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor\leq
m(w)+r_{\sigma(k)}.$

###### Proof

From the fact that

$\sum_{j=1}^{k+1}r_{\sigma(j)}=|w|_{a}=k+\delta=k+n(k+1)+i,$

we have

$k+n(k+1)+i\leq(\sum_{j=1}^{k}n+1)+n+3.$

Consequently, $i\leq 3$ and $\frac{3i}{2(k+1)}<\frac{1}{2}$. Thus,
$\lfloor\frac{3n}{2}+\frac{3i}{2(k+1)}\rfloor=\lfloor\frac{3n}{2}\rfloor$.
We only need to prove

$\lfloor\frac{3n}{2}\rfloor+1\leq
r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor.$

If $n$ is odd, let $n=2t+1$, then

$\displaystyle r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\geq(2t+1)+1+\lfloor\frac{(2t+1)+1-1}{2}\rfloor$
$\displaystyle\geq 3t+2$ $\displaystyle\geq\lfloor\frac{3(2t+1)}{2}\rfloor+1.$

If $n$ is even, let $n=2t$, then

$\displaystyle r_{\sigma(k)}+\lfloor\frac{r_{\sigma(k+1)}-1}{2}\rfloor$
$\displaystyle\geq(2t)+1+\lfloor\frac{(2t)+1-1}{2}\rfloor$ $\displaystyle\geq
3t+1$ $\displaystyle\geq\lfloor\frac{3((2t))}{2}\rfloor+1.$

∎

######  Proof (of Theorem 2)

From Lemma 13, Lemma 14, Lemma 15, Lemma 16 and Lemma 17, Theorem 2 holds if:

$\displaystyle r_{\sigma(k)}\geq n+2;$ $\displaystyle r_{\sigma(k)}\leq
n\;\text{and}\;k\geq 8;$ $\displaystyle
r_{\sigma(k)}=n+1\;\text{and}\;r_{\sigma(k+1)}\geq n+4;$ $\displaystyle
r_{\sigma(k)}=n+1,\;r_{\sigma(k+1)}\leq n+3\;\text{and}\;k\geq 10.$

Combining with Lemma 11, we conclude.

## References

  * [1] Berge, C.: The Theory of Graphs and Its Applications. Greenwood Press (1982)
  * [2] Brlek, S., Li, S.: On the number of squares in a finite word (2022), https://arxiv.org/abs/2204.10204
  * [3] Deza, A., Franek, F., Thierry, A.: How many double squares can a string contain? Discrete Applied Mathematics 180, 52–69 (2015)
  * [4] Fraenkel, A.S., Simpson, J.: How many squares can a string contain? J. Comb. Theory, Ser. A 82(1), 112–120 (1998)
  * [5] Ilie, L.: A note on the number of distinct squares in a word. In: Brlek, S., Reutenauer, C. (eds.) Proc. Words2005, 5-th International Conference on Words. vol. 36, pp. 289–294. Publications du LaCIM, Montreal, Canada (13–17 Sep 2005)
  * [6] Jonoska, N., Manea, F., Seki, S.: A stronger square conjecture on binary words. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014: Theory and Practice of Computer Science. pp. 339–350. Springer International Publishing, Cham (2014)
  * [7] Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: On the maximum number of cubic subwords in a word. Eur. J. Comb. 34(1), 27–37 (2013)
  * [8] Lam, N.H.: On the number of squares in a string. AdvOL-Report 2 (2013)
  * [9] Li, S.: On the number of $k$-powers in a finite word. Adv. Appl. Math. 139, 102371 (2022)
  * [10] Li, S., Pachocki, J., Radoszewski, J.: A note on the maximum number of $k$-powers in a finite word (2022), https://arxiv.org/abs/2205.10156
  * [11] Thierry, A.: A proof that a word of length n has less than 1.5n distinct squares (2020)