This study introduces a method for determining the optimal number of information exchange messages in the distributed local search algorithm for ship collision avoidance. The cost of determining the movement of a ship is modeled as the sum of the collision risk between ships and the cost of reaching the destination. This total cost is then used to establish the maximum allowable cost, which defines the upper limit of the message exchanges. Experiments were conducted with varying numbers of ships, ranging from two to 20, to analyze the changes in the maximum cost and corresponding number of message exchanges. In all cases, the number of message exchanges was capped at five. Experimental validation using automatic identification system data demonstrated that an upper limit of 25 message exchanges was sufficient to ensure collision-free navigation for five ships, whereas an upper limit of 50 exchanges effectively handled scenarios involving 10 ships.

1. [1] “Review of maritime transport 2024.” https://unctad.org/publication/review-maritime-transport-2024 [Accessed December 9, 2024]
2. [2] J. Li, Y. Xiong, and A. Yu, “Multi-UAV path planning for inspection of target points with stable monitoring frequencies,” J. Adv. Comput. Intell. Intell. Inform., Vol.28, No.5, pp. 1195-1203, 2024. https://doi.org/10.20965/jaciii.2024.p1195
3. [3] S.-H. Li, F.-L. Yan, and Y.-Q. Li, “An improved multi target ship recognition model based on deep convolutional neural network,” J. Adv. Comput. Intell. Intell. Inform., Vol.28, No.1, pp. 216-223, 2024. https://doi.org/10.20965/jaciii.2024.p0216
4. [4] D.-Y. Kim, J.-S. Jeong, G. Kim, H.-Y. Kim, and T. Hong, “Implementation of an intelligent system for identifying vessels exhibiting abnormal navigation patterns,” J. Adv. Comput. Intell. Intell. Inform., Vol.18, No.4, pp. 665-671, 2014. https://doi.org/10.20965/jaciii.2014.p0665
5. [5] “Review of maritime transport 2022.” https://unctad.org/rmt2022 [Accessed December 9, 2024]
6. [6] https://www.kmst.go.kr/web/verdictList.do?menuIdx=121 [Accessed December 9, 2024]
7. [7] S. M. Kim, “Major legal issues on the sinking of hableány,” J. of Int. Business Trans. Law, No.26, pp. 97-117, 2019. https://doi.org/10.31839/ibt.2019.07.26.97
8. [8] J. Akshay and S. Mutreja, “Autonomous Ship Market Research Report,” Allied Market Research, 2020.
9. [9] D.-G. Kim, K. Hirayama, and G.-K. Park, “Collision avoidance in multiple-ship situations by distributed local search,” J. Adv. Comput. Intell. Intell. Inform., Vol.18, No.5, pp. 839-848, 2014. https://doi.org/10.20965/jaciii.2014.p0839
10. [10] S. Li, J. Liu, and R. R. Negenborn, “Distributed coordination for collision avoidance of multiple ships considering ship maneuverability,” Ocean Engineering, Vol.181, pp. 212-226, 2019. https://doi.org/10.1016/j.oceaneng.2019.03.054
11. [11] H. Yasukawa and Y. Yoshimura, “Introduction of MMG standard method for ship maneuvering predictions,” J. of Marine Science and Technology, Vol.20, No.1, pp. 37-52, 2015. https://doi.org/10.1007/s00773-014-0293-y
12. [12] Y. He, Y. Jin, L. Huang, Y. Xiong, P. Chen, and J. Mou, “Quantitative analysis of COLREG rules and seamanship for autonomous collision avoidance at open sea,” Ocean Engineering, Vol.140, pp. 281-291, 2017. https://doi.org/10.1016/j.oceaneng.2017.05.029
13. [13] Y. Xue, B. S. Lee, and D. Han, “Automatic collision avoidance of ships,” Proc. of the Institution of Mechanical Engineers, Part M: J. of Engineering for the Maritime Environment, Vol.223, Issue 1, pp. 33-46, 2009. https://doi.org/10.1243/14750902JEME123
14. [14] F. P. Coenen, G. P. Smeaton, and A. G. Bole, “Knowledge-based collision avoidance,” J. of Navigation, Vol.42, Issue 1, pp. 107-116, 1989. https://doi.org/10.1017/S0373463300015125
15. [15] Y. Ren, J. Mou, Q. Yan, and F. Zhang, “Study on Assessing Dynamic Risk of Ship Collision,” ICTIS 2011: Multimodal Approach to Sustained Transportation System Development: Information, Technology, Implementation, pp. 2751-2757, 2011. https://doi.org/10.1061/41177(415)346
16. [16] S. Ni, N. Wang, Z. Qin, X. Yang, Z. Liu, and H. Li, “A distributed coordinated path planning algorithm for maritime autonomous surface ship,” Ocean Engineering, Vol.271, Article No.113759, 2023. https://doi.org/10.1016/j.oceaneng.2023.113759
17. [17] J. Liu, J. Zhang, M. Zhang, X. Xin, and Z. Yang, “A novel collaborative collision avoidance decision-making methodology based on potential collision areas for intelligent navigation,” Ocean Engineering, Vol.318, Article No.120126, 2025. https://doi.org/10.1016/j.oceaneng.2024.120126
18. [18] Y. Fujii and K. Tanaka, “Traffic capacity,” J. of Navigation, Vol.24, Issue 4, pp. 543-552, 1971. https://doi.org/10.1017/S0373463300022384
19. [19] R. Szlapczynski and J. Szlapczynska, “Review of ship safety domains: Models and applications,” Ocean Engineering, Vol.145, pp. 277-289, 2017. https://doi.org/10.1016/j.oceaneng.2017.09.020
20. [20] H. Lyu and Y. Yin, “Ship’s trajectory planning for collision avoidance at sea based on modified artificial potential field,” 2017 2nd Int. Conf. on Robotics and Automation Engineering (ICRAE), pp. 351-357, 2017. https://doi.org/10.1109/ICRAE.2017.8291409
21. [21] H. Lyu and Y. Yin, “COLREGS-constrained real-time path planning for autonomous ships using modified artificial potential fields,” J. of Navigation, Vol.72, Issue 3, pp. 588-608, 2019. https://doi.org/10.1017/S0373463318000796
22. [22] R. A. Soltan, H. Ashrafiuon, and K. R. Muske, “Trajectory real-time obstacle avoidance for underactuated unmanned surface vessels,” ASME 2009 Int. Design Engineering Technical Conf. and Computers and Information in Engineering Conf., Vol.7, pp. 1059-1067, 2009. https://doi.org/10.1115/DETC2009-86987
23. [23] R. A. Soltan, H. Ashrafiuon, and K. R. Muske, “ODE-based obstacle avoidance and trajectory planning for unmanned surface vessels,” Robotica, Vol.29, Issue 5, pp. 691-703, 2011. https://doi.org/10.1017/S0263574710000585
24. [24] F. Mahini, L. DiWilliams, K. Burke, and H. Ashrafiuon, “An experimental setup for autonomous operation of surface vessels in rough seas,” Robotica, Vol.31, Issue 5, pp. 703-715, 2013. https://doi.org/10.1017/S0263574712000720
25. [25] L. Jiang, L. An, X. Zhang, C. Wang, and X. Wang, “A human-like collision avoidance method for autonomous ship with attention-based deep reinforcement learning,” Ocean Engineering, Vol.264, Article No.112378, 2022. https://doi.org/10.1016/j.oceaneng.2022.112378
26. [26] D.-H. Chun, M.-I. Roh, H.-W. Lee, J. Ha, and D. Yu, “Deep reinforcement learning-based collision avoidance for an autonomous ship,” Ocean Engineering, Vol.234, Article No.109216, 2021. https://doi.org/10.1016/j.oceaneng.2021.109216
27. [27] X. Xu, Y. Lu, G. Liu, P. Cai, and W. Zhang, “COLREGs-abiding hybrid collision avoidance algorithm based on deep reinforcement learning for USVs,” Ocean Engineering, Vol.247, Article No.110749, 2022. https://doi.org/10.1016/j.oceaneng.2022.110749
28. [28] Y. Wang and Y. Zhao, “Multiple ships cooperative navigation and collision avoidance using multi-agent reinforcement learning with communication,” Ocean Engineering, Vol.320, Article No.120244, 2025. https://doi.org/10.1016/j.oceaneng.2024.120244
29. [29] Y. Li, D. Wu, H. Wang, and J. Lou, “Dynamic collision avoidance for maritime autonomous surface ships based on deep Q-network with velocity obstacle method,” Ocean Engineering, Vol.320, Article No.120335, 2025. https://doi.org/10.1016/j.oceaneng.2025.120335
30. [30] Y. Liu, C. Yang, and X. Du, “A multiagent-based simulation system for ship collision avoidance,” D.-S. Huang, L. Heutte, and M. Loog (Eds.), “Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues,” pp. 316-326, Springer, 2007. https://doi.org/10.1007/978-3-540-74171-8_31
31. [31] S. Hornauer and A. Hahn, “Towards marine collision avoidance based on automatic route exchange,” IFAC Proc. Volumes, 9th IFAC Conf. on Control Applications in Marine Systems, Vol.46, Issue 33, pp. 103-107, 2013. https://doi.org/10.3182/20130918-4-JP-3022.00049
32. [32] D. Kim, K. Hirayama, and T. Okimoto, “Distributed stochastic search algorithm for multi-ship encounter situations,” J. of Navigation, Vol.70, Issue 4, pp. 699-718, 2017. https://doi.org/10.1017/S037346331700008X
33. [33] D.-G. Kim, K. Hirayama, and T. Okimoto, “Ship collision avoidance by distributed tabu search,” TransNav, the Int. J. on Marine Navigation and Safety of Sea Transportation, Vol.9, No.1, pp. 23-29, 2015. https://doi.org/10.12716/1001.09.01.03
34. [34] J. Zhang, D. Zhang, X. Yan, S. Haugen, and C. G. Soares, “A distributed anti-collision decision support formulation in multi-ship encounter situations under COLREGs,” Ocean Engineering, Vol.105, pp. 336-348, 2015. https://doi.org/10.1016/j.oceaneng.2015.06.054
35. [35] C. Denker and A. Hahn, “MTCAS – An Assistance System for Maritime Collision Avoidance,” 2th Int. Symp. on Integrated Ship’s Information Systems & Marine Traffic Engineering Conf., 2016.
36. [36] L. Ferranti, R. R. Negenborn, T. Keviczky, and J. Alonso-Mora, “Coordination of multiple vessels via distributed nonlinear model predictive control,” 2018 European Control Conf. (ECC), pp. 2523-2528, 2018. https://doi.org/10.23919/ECC.2018.8550178
37. [37] L. Chen, Y. Huang, H. Zheng, H. Hopman, and R. Negenborn, “Cooperative multi-vessel systems in urban waterway networks,” IEEE Trans. on Intelligent Transportation Systems, Vol.21, Issue 8, pp. 3294-3307, 2020. https://doi.org/10.1109/TITS.2019.2925536
38. [38] T. Yang, C. Han, M. Qin, and C. Huang, “Learning-aided intelligent cooperative collision avoidance mechanism in dynamic vessel networks,” IEEE Trans. on Cognitive Communications and Networking, Vol.6, Issue 1, pp. 74-82, 2020. https://doi.org/10.1109/TCCN.2019.2945790