Generating a Vessel Route Model from AIS Data Using the Fréchet Distance

Abstract

As cars tend to stay on roads and trains rely on rails, their movement paths closely resemble the underlying network. Traffic at sea behaves differently in this regard, as most of the time ships can move freely across the ocean. This increases the difficulty of traffic situation assessment and requires flexible route models. Many ships regularly report their position and navigational information using the Automatic Identification System (AIS). By collecting this data, the movement trajectories of individual ships can be obtained. The Fréchet distance can be used as a measure of similarity between trajectories. It factors in the positional information of the trajectory, but also the direction of movement. In addition, it is a metric distance and does not require trajectories of the same length. In this work, we want to utilize the flexibility of the Fréchet distance to automatically generate a vessel route model from AIS position reports in an area around the Rostock harbor. The model aim is to represent commonly taken ship routes, while at the same time avoiding redundancy in order to enable fast comparisons with test vessels. For this task we collected one year of AIS training data with an antenna located in the Rostock harbor. It contains roughly 80 million position reports. We sort the data into a time series for every unique vessel and further divide the series into segments, each representing a single route taken by the vessel. The trajectories obtained from the segments are clustered into traffic routes using the Fréchet distance as similarity metric. The final model is then composed of representatives of each cluster. In the evaluation step we generate the model multiple times with different model parameters, compare each model to the original training set and a novel set of test trajectories. In addition, the model size and comparison speeds are measured. With a Fréchet distance threshold of 1500 meters, one model achieves 100% similarity to the training trajectories, over 90% similarity to the test trajectories, while at the same time using 83% less space and 76% less time (to compare the test trajectories) than if we would include all training trajectories in our model.