Multidimensional cluster analysis of vessel traffic data for route planning

The work is devoted to the problem of planning ship routes in water areas with heavy traffic. In conditions of heavy traffic, navigational safety can be ensured only if ships adhere to a certain traffic pattern. The paper examines the problem of planning a route in such a way that it corresponds to the shipping practices that have developed in a particular area. The route planning method proposed in this work is based on clustering data on vessel traffic. The selected clusters represent areas in three- or four-dimensional phase space with similar speeds and courses of vessels, on the basis of which a graph of possible routes is formed. A feature of the approach for constructing a graph is the reduction in the number of vertices and edges by identifying the location of the selected clusters by covering polygons. The work shows that in many cases not only concave, but also convex polygons can be used, which can further reduce the power of the graph. The paper provides a metric for the distance between points in phase space, which is used to cluster data, and discusses the problem of choosing metric parameters and the clustering algorithm. The promise of using the DBSCAN algorithm is noted. The work is accompanied by calculations of planned vessel routes based on data from real water areas (Tsugaru Strait). The results of clustering traffic data, identifying the location of clusters by constructing enclosing polygons, and calculating the route of the vessel are presented. It is noted that the problem under consideration may be promising in the context of the future development of autonomous vessels navigation. In this case, the calculated route of the vessel will correspond to the movement of other vessels that were previously in the water area. This will reduce the likelihood of dangerous situations occurring when an autonomous vessel moves in the general traffic flow.

1. Ardelyanov N. Intermediate results of the e-navigation concept. Vestnik gosudarstvennogo morskogo universiteta imeni admirala F.F. Ushakova. 2022;(2):8–11. (In Russ.).

2. Rivkin B.S. e-Navigation: Five Years Later. Gyroscopy and Navigation. 2020;11(2):176–187. https://doi.org/10.1134/S2075108720020066

3. Korenev A.S., Khabarov S.P., Shpectorov A.G. A route calculation for unmanned vessel. Morskie intellektual'nye tekhnologii = Marine Intellectual Technologies. 2021;(4 1):158–165. (In Russ.). https://doi.org/10.37220/MIT.2021.54.4.047

4. Dyda A.A., Pushkarev I.I., Chumakova K.N. Static obstacles avoidance algorithm for unmanned ship. Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2021;13(3):307–315. (In Russ.). https://doi.org/10.21821/2309-5180-2021-13-3-307-315

5. Pinskii A.S. Avtonomnoe sudovozhdenie. Morskoi vestnik. 2021;(2):101–105. (In Russ.).

6. Tsolakis A., Benders D., De Groot O., Negenborn R.R., Reppa V., Ferranti L. COLREGs-aware Trajectory Optimization for Autonomous Surface Vessels. IFAC-PapersOnLine. 2022;55(31):269–274. https://doi.org/10.1016/j.ifacol.2022.10.441

7. Wang H.-B., Li X.G., Li P.F., Veremey E.I., Sotnikova M.V. Application of Real-Coded Genetic Algorithm in Ship Weather Routing. The Journal of Navigation. 2018;71(4):989–1010. https://doi.org/10.1017/S0373463318000048

8. Zhao L., Shi G. Maritime Anomaly Detection using Density-based Clustering and Recurrent Neural Network. The Journal of Navigation. 2019;72(4):894–916. https://doi.org/10.1017/S0373463319000031

9. Taratynov V.V. Tselesoobraznost' razdeleniya morskikh putei. Morskoi flot. 1969;(9):19–20. (In Russ.).

10. Zhang B., Hirayama K., Ren H., Wang D., Li H. Ship Anomalous Behavior Detection Using Clustering and Deep Recurrent Neural Network. Journal of Marine Science and Engineering. 2023;11(4). https://doi.org/10.3390/jmse11040763

11. Grinyak V.M., Devyatisilnyi A.S., Ivanenko Yu.S. Decision support for marine traffic control based on route clustering. Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2020;12(3):436–449. (In Russ.). https://doi.org/10.21821/2309-5180-2020-12-3-436-449

12. Grinyak V.M., Shulenina A.V. Marine Traffic Data Clustering for Ships Route Planning. Informatsionnye tekhnologii = Information Technologies. 2021;27(11):607–615. (In Russ.). https://doi.org/10.17587/it.27.607-615

13. Grinyak V.M., Devyatisilny A.S. Vessel route planning based on historical traffic data of marine area. Transport: nauka, tekhnika, upravlenie. Nauchnyi informatsionnyi sbornik = Transport: science, equipment, management. Scientific Information Collection. 2022;(10):34–40. (In Russ.). https://doi.org/10.36535/0236-1914-2022-10-6

14. Grinyak V.M., Prudnikova L.I., Artemiev A.V., Levchenko D.M. Vessel route planning based on historical traffic data and model representations of computational geometry. Modelirovanie, optimizatsiya i informatsionnye tekhnologii = Modeling, Optimization and Information Technology. 2023;11(2). (In Russ.). https://doi.org/10.26102/2310-6018/2023.41.2.015

15. Grinyak V.M., Shurygin A.V.; rightholder Federal State Budgetary Educational Institution of Higher Education «Vladivostok State University of Economics and Service». Programma sbora traektornykh dannykh o dvizhenii sudov iz otkrytykh internet istochnikov: publ. 19.07.2018. The Certificate on Official Registration of the Computer Program № 2018618729 the Russian Federation. This product is registered in the registry of the computer programs.

16. Golovchenko B.S., Grinyak V.M. Information system for vessels traffic data capture. Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S.O. Makarova. 2014;(2):156–162. (In Russ.).

17. Pallotta G., Vespe M., Bryan K. Vessel Pattern Knowledge Discovery from AIS Data: A Framework for Anomaly Detection and Route Prediction. Entropy. 2013;15(6):2218–2245. https://doi.org/10.3390/e15062218

18. Naus K. Drafting Route Plan Templates for Ships on the Basis of AIS Historical Data. The Journal of Navigation. 2020;73(3):726–745. https://doi.org/10.1017/S0373463319000948

19. Zhen R., Jin Y., Hu Q., Shao Zh., Niktakos N. Maritime Anomaly Detection within Coastal Waters Based on Vessel Trajectory Clustering and Naïve Bayes Classifier. The Journal of Navigation. 2017;70(3):648–670. https://doi.org/10.1017/S0373463316000850

20. Tang H., Wei L., Yin Y., Shen H., Qi Y. Detection of Abnormal Vessel Behaviour Based on Probabilistic Directed Graph Model. The Journal of Navigation. 2020;73(5):1014–1035. https://doi.org/10.1017/S0373463320000144