Overview of current algorithms for autonomous vessels route optimization

An overview of multiple current algorithms for optimizing the routes of autonomous surface vessels is provided in the paper. One of the effective methods for route optimization is the implementation of algorithms and software based on graph theory to prevent collisions. Key algorithms include Dijkstra’s algorithm, A*, artificial potential fields, the “dynamic window” method, and the velocity obstacle method. Collision prevention using radar of the maritime autonomous navigation vessel, geometric vessel factors, genetic algorithms, neural network training is also separately discussed. While most algorithms are only considered theoretically, some works describe practical observations: neural networks using deep learning, Markov decision processes, Q-learning; developed autonomous collision avoidance system; heuristic search for optimal ship routes using the A2015 algorithm. Overall research analysis shows that many authors have made significant progress in their work, but the topic is not fully explored. Some works do not consider divergence with multiple vessels, while others do not utilize maneuvers involving speed changes. Certain works face challenges in parameter tuning for algorithm efficiency. The optimality criterion for multiple maneuvering, considering factors beyond minimizing the closest point of approach to another vessel, such as responsibility distribution for maneuver execution, is not fully developed. It is noted that all necessary conditions for creating a universal algorithm in the future already exist due to modern technologies and the research topic relevance.

1. Autonomous shipping. Web. 10 Feb. 2024 <https://www.imo.org/en/MediaCentre/HotTopics/Pages/Autonomous-shipping.aspx>.

2. Tripolets, Oleg Y. “Overview of existing methods of autonomous vessels collision avoidance.” Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova 13.4 (2021): 480–495. DOI: 10.21821/2309-5180-2021-13-4-480-495.

3. Bondy, J. A., and U. S. R. Murty. Graph Theory. 1st. ed. Springer Publishing Company, Incorporated, 2008.

4. Tutte, W. T. Graph Theory. Cambridge University Press, 2001.

5. Wilson, Robin J. Introduction to Graph Theory. 5th Edition. Pearson, 2010.

6. bin Mohamad Rafi, Muhammad Shahrul Afiq, Wahju Sediono, and Zulkifli bin Zainal Abidin. “Radar-Based Collision Avoidance on Unmanned Surface Vehicles (USV).” 2022 IEEE 9th International Conference on Underwater System Technology: Theory and Applications (USYS). IEEE, 2022. DOI: 10.1109/USYS56283.2022.10073415.

7. Mu, Dongdong, Tanghui Li, Xinjie Han, Yunsheng Fan, Xiaojie Sun, and Yanli Liu. “Geometric Collision Avoidance Algorithm for Unmanned Surface Vehicle Based on Multi-objective.” 2022 5th International Conference on Intelligent Autonomous Systems (ICoIAS). IEEE, 2022. DOI: 10.1109/ICoIAS56028.2022.9931210.

8. Fu, Zhongjian, Hongjian Wang, Yingmin Gu, Chengfeng Li, Haiyan Tong, and Haibin Wang. “Method for collision avoidance by USV based on improved genetic algorithm.” Global Oceans 2020: Singapore–US Gulf Coast. IEEE, 2020. DOI: 10.1109/IEEECONF38699.2020.9389254.

9. Tripolets, Oleg Y. “Training a neural network to calculate the closest point of approach.” Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova 14.5 (2022): 713–721. DOI: 10.21821/2309-5180-2022-14-5-713-721.

10. Yan, Hongzhou, Qige Zhu, Yifan Zhang, Zhe Li, and Xiaojia Du. “An Obstacle Avoidance Algorithm for Unmanned Surface Vehicle Based on A Star and Velocity-Obstacle Algorithms.” 2022 IEEE 6th Information Technology and Mechatronics Engineering Conference (ITOEC). Vol. 6. IEEE, 2022. DOI: 10.1109/ITOEC53115.2022.9734642.

11. Sun, Xiaojie, Guofeng Wang, Yunsheng Fan, Dongdong Mu, Bingbing Qiu, and Jian Liu. “Real-time collision avoidance control for unmanned surface vehicle based on velocity resolution method.” 2019 Chinese Control Conference (CCC). IEEE, 2019. DOI: 10.23919/ChiCC.2019.8866486.

12. Zhuang, Jiayuan, Yuhang Zhang, Peihong Xu, Yi Zhao, Jing Luo, and Shengqing Song. “Multiple Moving Obstacles Avoidance for USV using Velocity Obstacle Method.” 2021 IEEE International Conference on Unmanned Systems (ICUS). IEEE, 2021. DOI: 10.1109/ICUS52573.2021.9641331.

13. Li, Yun, and Jian Zheng. “Real-time collision avoidance planning for unmanned surface vessels based on field theory.” ISA transactions 106 (2020): 233–242. DOI: 10.1016/j.satra.2020.07.018.

14. Cho, Yonghoon, Jungwook Han, Jinwhan Kim, Philyeob Lee, and Shin-Bae Park. “Experimental validation of a velocity obstacle based collision avoidance algorithm for unmanned surface vehicles.” IFAC-PapersOnLine 52.21 (2019): 329–334. DOI: 10.1016/j.ifacol.2019.12.328.

15. Johansen, Tor Arne, Tristan Perez, and Andrea Cristofaro. “Ship collision avoidance and COLREGS compliance using simulation-based control behavior selection with predictive hazard assessment.” IEEE transactions on intelligent transportation systems 17.12 (2016): 3407–3422. DOI: 10.1109/TITS.2016.2551780.

16. Zhuang, Jiayuan, Jing Luo, Yuanchang Liu, Richard Bucknall, Hanbing Sun, and Cheng Huang. “Collision avoidance for unmanned surface vehicles based on COLREGS.” 2019 5th International Conference on Transportation Information and Safety (ICTIS). IEEE, 2019. 1418–1425. DOI: 10.1109/ICTIS.2019.8883829.

17. Guan, Wei, and Kuo Wang. “Autonomous collision avoidance of unmanned surface vehicles based on improved A-star and dynamic window approach algorithms.” IEEE Intelligent Transportation Systems Magazine 15.3 (2023): 36–50. DOI: 10.1109/MITS.2022.3229109.

18. Wang, Peiqi, Xiaolan Yao, Qing Fei, and Jiekun Meng. “Research on Local Path Planning for Autonomous Collision Avoidance of USV.” 2022 China Automation Congress (CAC). IEEE, 2022. 5368–5373. DOI: 10.1109/CAC57257.2022.10055154.

19. Chao, Wu, Ma Feng, Wu Qing, and Wang Shuwu. “A situation awareness approach for usv based on artificial potential fields.” 2017 4th International Conference on Transportation Information and Safety (ICTIS). IEEE, 2017. 232–235. DOI: 10.1109/ICTIS.2017.8047770.

20. Chen, Qing-Da, Sheng-Wei Huang, Ming-Hsin Ho, Feng-Yeang Chung, Chun-Han Chu, Chi-Min Liao, and Jenhwa Guo. “Vector Field-Based Guidance Method for Collision Avoidance of Unmanned Surface Vehicles.” 2023 IEEE Underwater Technology (UT). IEEE, 2023. DOI: 10.1109/UT49729.2023.10103386.

21. Naeem, Wasif, Sable Campbell, and Mamun Abu-Tair. “Collision avoidance of maritime vessels.” Navigation and Control of Autonomous Marine Vehicles. 2019. 61–84. DOI: 10.1049/PBTR011E_ch3.

22. Lazarowska, Agnieszka. “Ship’s trajectory planning for collision avoidance at sea based on ant colony optimisation.” The Journal of Navigation 68.2 (2015): 291–307. DOI: 10.1017/S0373463314000708.

23. Yuan-hui, Wang, and Chi Cen. “Research on optimal planning method of USV for complex obstacles.” 2016 IEEE International Conference on Mechatronics and Automation. IEEE, 2016. 2507–2511. DOI: 10.1109/ICMA.2016.7558960.

24. Gamayanti, Nurlita, Rusdhianto Effendi Abdul Kadir, and Abdullah Alkaff. “Global Path Planning for USV Waypoint Guidance System Using Dynamic Programming.” 2020 International Seminar on Intelligent Technology and Its Applications (ISITIA). IEEE, 2020. 248–253. DOI: 10.1109/ISITIA49792.2020.9163712.

25. Ding, Fuguang, Zhaoqing Zhang, Mingyu Fu, Yuanhui Wang, and Chenglong Wang. “Energy-efficient path planning and control approach of USV based on particle swarm optimization.” OCEANS 2018 MTS/IEEE Charleston. IEEE, 2018. DOI: 10.1109/OCEANS.2018.8604920.

26. Kazakova, E.M. “Application of particle swarm method in the optimization problems.” News of the Kabardino-Balkarian Scientific Center of RAS 5(109) (2022): 48–57. DOI: 10.35330/1991-6639-2022-5-109-48-57.

27. Wang, Chengbo, Xinyu Zhang, Longze Cong, Junjie Li, and Jiawei Zhang. “Research on intelligent collision avoidance decision-making of unmanned ship in unknown environments.” Evolving Systems 10.4 (2019): 649–658. DOI: 10.1007/s12530-018-9253-9.

28. Akmaykin, D.A., S. F. Klyueva, and P. A. Salyuk. “Heuristic search for the optimal route ship northern sea route.” Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makarova 5(33) (2015): 55–62. DOI: 10.21821/2309-5180-2015-7-5-55-62.

29. Son, Nam-Sun, and Sun-Young Kim. “On the sea trial test for the validation of an autonomous collision avoidance system of unmanned surface vehicle, ARAGON.” OCEANS 2018 MTS/IEEE Charleston. IEEE, 2018. DOI: 10.1109/OCEANS.2018.8604803.

30. Son, N.S. “On an Autonomous Navigation System for Collision Avoidance of Unmanned Surface Vehicle.” Proceedings of the ION 2013 Pacific PNT Meeting. 2013. 470–476.