by Angelica Lo Duca (IIT-CNR) and Andrea Marchetti (IIT-CNR)
The National Research Council in Pisa has been implementing a ship route prediction algorithm based on multiclass classification. The algorithm was developed within the OSIRIS project , which aimed to build a decision support system for maritime surveillance.
Multiclass classification (MC) is a type of supervised learning which measures the attributes of a sample, and based on those attributes, assigns the sample to one of many classes. MC is a generalisation of the binary classification, in which there are only two classes. MC can be exploited to build a ship route prediction (SRP) system , which aims to predict the next position of a ship, given its current status, determined by its current position (latitude, longitude), speed, direction, time and date, as well as a historical database of past routes. The area to be monitored, called “area of interest” (AoI), is split into m rows and n columns, and each cell of the obtained matrix constitutes an output class of the MC algorithm. Thus, the total number of possible classes is m x n. Given the current status of a ship, the SRP system predicts the probability that each cell of the matrix will be occupied after a given period of time (e.g. 30, 45 or 60 minutes).
Different MC algorithms were tested to perform SRP, including naive Bayes, K-nearest neighbours (K-NN), decision trees, linear algorithms and extension from binary. Every MC algorithm was trained and tested with actual data from a historical database of past routes extracted from automatic identification system (AIS) messages sent by other ships around the island of Malta. A web application was then implemented to predict the next position of a ship [L2]. The K-NN and decision tree algorithms outperformed all the other MC algorithms.
The proposed SRP system is a point-based system, which only predicts the next position of a ship, given the current position. Other systems defined in the literature can predict the whole trajectory. To the best of our knowledge, our system is the first SRP algorithm to use time and date as input features.
We performed a qualitative test of the SRP system, which involved testing the SRP performance in the following real scenario: On 30 December 2019 at 11:11, the ship ASTRAEA [PA] was directed towards the Marsaxlokk port and the estimated time of arrival was 12:30. SRP was used to predict the next position after 60 minutes. All the information used for this scenario was extracted from Marine Traffic [L2], a global ship tracking intelligence website. We ran all the implemented MC algorithms to predict the ship’s next position after 60 minutes. Results are shown in Figure 1: only K-NN and decision tree predicted the correct position.
Figure 1: The output of SRP for the ship ASTRAEA [PA]. The position of the destination (Marsaxlokk port) is shown only for K-NN. Predicted probabilities are shown in red. The brighter the red of the cell, the higher the probability value.
The area around the island of Malta was used as the AoI, with periodic satellite images capturing the movement of ships within this region. Low-resolution was used for these initial images, to minimise costs. These images are processed by two modules, identification and classification, in order to extract the ships present in the area and their general status. The extracted status is sent as input to the SRP system, which identifies the position of the ship after a certain time interval. The position extracted from the SRP system is used to direct the satellite to capture a new image in the exact location that the ship is predicted to be found. The new captured image is more fine-grained to allow additional information to be extracted. This information will be used by another system, the behaviour analysis module, which tries to determine if the ships present in the subarea are behaving correctly or not. In summary, the OSIRIS system uses two satellite images, one coarse-grained (larger and less expensive), one fine-grained (smaller and more expensive). For this reason, the SRP system does not need to predict the exact position of a ship, but only a restricted area in which the ship will be after a given time interval.
Although SRP has been widely studied in the literature, this work is the first approach to compare different SRP algorithms based on multiclass classification. The use of machine learning techniques in the maritime field is being consolidated, thus helping decision support systems to profile, the then to identify anomalies, in ships’ behaviours. The naive theoretical framework and apparently over-simplified assumptions of this methodology mean that it can easily be reproduced and used by other researchers to compare other families of algorithms, not limited to the field of SRP.
The SRP system was implemented within the OSIRIS project, funded by the European Space Agency (ESA) .
 M. Reggiannini, et al.: “Remote Sensing for Maritime Prompt Monitoring”, J. of Marine Science and Engineering, 7(7), 202, 2019
 A. Lo Duca, C. Bacciu, A. Marchetti: “A K-Nearest Neighbor Classifier for Ship Route Prediction”, OCEANS 2017 - Aberdeen, UK 2017.
Angelica Lo Duca