Обзор актуальных алгоритмов по оптимизации маршрутов автономных судов

В статье выполнен обзор различных алгоритмов по оптимизации маршрутов морских автономных надводных судов. Отмечается, что актуальным и действенным методом оптимизации маршрутов является внедрение алгоритмов и программной базы по предотвращению столкновения, основанных на теории графов. Основными способами являются алгоритм Дейкстры, А*, искусственные потенциальные поля, метод «динамического окна», метод скоростного препятствия. Также отдельно рассматривается предотвращение столкновения с использованием радара морского автономного навигационного судна, геометрических факторов судов, генетического алгоритма, обучения нейронной сети. При этом большинство алгоритмов рассматривается только как теоретическое решение поставленных задач. Вместе с тем в некоторых работах описаны результаты, полученные при проведении экспериментальных натурных испытаний, а именно: нейронные сети, использующие глубокое обучение, марковский процесс принятия решений, Q-обучение; созданная с нуля система автономного предотвращения столкновения с использованием концепции поиска заменяемого пространства действий; эвристический поиск оптимального маршрута судна по Северному морскому пути с использованием алгоритма А2015. Общий анализ исследований показал, что многие авторы значительно продвинулись в своих исследованиях — в них видна положительная динамика исследования, однако необходимо совершенствовать существующие алгоритмы для решения поставленных задач, поскольку в одних работах не рассматривается расхождение с несколькими судами, в других не используется маневр, связанный с изменением скорости, в отдельных работах существует сложность настройки параметров для эффективной работы алгоритма. Не в полной мере разработан также критерий оптимальности при совместном маневрировании, учитывающий не только обеспечение минимального значения кратчайшей дистанции до судна в системе, но и другие факторы, такие как распределение обязанностей по выполнению маневров судов.

1. Autonomous shipping. IMO [Электронный ресурс]. — Режим доступа: https://www.imo.org/en/MediaCentre/HotTopics/Pages/Autonomous-shipping.aspx (дата обращения 10.02.2024).

2. Триполец О. Ю. Обзор существующих методов расхождения безэкипажных судов / О. Ю. Триполец // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2021. — Т. 13. — № 4. — С. 480–495. DOI: 10.21821/2309-5180-2021-13-4-480-495.

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

4. Татт У. Теория графов: Пер. с англ. / У. Татт. — М.: Мир, 1988. — 424 с.

5. Уилсон Р. Введение в теорию графов / Р. Уилсон; перевод с англ. И. Г. Никитиной; под ред. Г. П. Гаврилова. — М.: Мир, 1977. — 208 с.

6. bin Mohamad Rafi M. S. A. Radar-Based Collision Avoidance on Unmanned Surface Vehicles (USV) / M. S. A. bin Mohamad Rafi, W. Sediono, Z. bin Zainal Abidin // 2022 IEEE 9th International Conference on Underwater System Technology: Theory and Applications (USYS). — IEEE, 2022. — Pp. 1–7. DOI: 10.1109/USYS56283.2022.10073415.

7. Mu D. Geometric Collision Avoidance Algorithm for Unmanned Surface Vehicle Based on Multi-objective / D. Mu, T. Li, X. Han, Y. Fan, X. Sun, Y. Liu // 2022 5th International Conference on Intelligent Autonomous Systems (ICoIAS). — IEEE, 2022. — Pp. 159–165. DOI: 10.1109/ICoIAS56028.2022.9931210.

8. Fu Z. Method for collision avoidance by USV based on improved genetic algorithm / Z. Fu, H. Wang, Y. Gu, C. Li, H. Tong, H. Wang // Global Oceans 2020: Singapore–US Gulf Coast. — IEEE, 2020. — Pp. 01–06. DOI: 10.1109/IEEECONF38699.2020.9389254.

9. Триполец О. Ю. Обучение нейронной сети вычислению дистанции кратчайшего сближения между судами / О. Ю. Триполец // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2022. — Т. 14. — № 5. — С. 713–721. DOI: 10.21821/2309-5180-2022-14-5-713-721.

10. Yan H. An Obstacle Avoidance Algorithm for Unmanned Surface Vehicle Based on A Star and Velocity-Obstacle Algorithms / H. Yan, Q. Zhu, Y. Zhang, Z. Li, X. Du // 2022 IEEE 6th Information Technology and Mechatronics Engineering Conference (ITOEC). — IEEE, 2022. — Vol. 6. — Pp. 77–82. DOI:10.1109/ITOEC53115.2022.9734642.

11. Sun X. Real-time collision avoidance control for unmanned surface vehicle based on velocity resolution method / X. Sun, G. Wang, Y. Fan, D. Mu, B. Qiu, J. Liu // 2019 Chinese Control Conference (CCC). — IEEE, 2019. — Pp. 6668–6673. DOI: 10.23919/ChiCC.2019.8866486.

12. Zhuang J. Multiple Moving Obstacles Avoidance for USV using Velocity Obstacle Method / J. Zhuang, Y. Zhang, P. Xu, Y. Zhao, J. Luo, S. Song // 2021 IEEE International Conference on Unmanned Systems (ICUS). — IEEE, 2021. — Pp. 140–145. DOI: 10.1109/ICUS52573.2021.9641331.

13. Li Y. Real-time collision avoidance planning for unmanned surface vessels based on field theory / Y. Li, J. Zheng // ISA transactions. — 2020. — Vol. 106. — Pp. 233–242. DOI: 10.1016/j.isatra.2020.07.018.

14. Cho Y. Experimental validation of a velocity obstacle based collision avoidance algorithm for unmanned surface vehicles / Y. Cho, J. Han, J. Kim, P. Lee, S. B. Park // IFAC-PapersOnLine. — 2019. — Vol. 52. — Is. 21. — Pp. 329–334. DOI: 10.1016/j.ifacol.2019.12.328.

15. Johansen T. A. Ship collision avoidance and COLREGS compliance using simulation-based control behavior selection with predictive hazard assessment / T. A. Johansen, T. Perez, A. Cristofaro // IEEE transactions on intelligent transportation systems. — 2016. — Vol. 17. — Is. 12. — Pp. 3407–3422. DOI: 10.1109/TITS.2016.2551780.

16. Zhuang J. Collision avoidance for unmanned surface vehicles based on COLREGS / J. Zhuang, J. Luo, Y. Liu, R. Bucknall, H. Sun, C. Huang // 2019 5th International Conference on Transportation Information and Safety (ICTIS). — IEEE, 2019. — Pp. 1418–1425. DOI: 10.1109/ICTIS.2019.8883829.

17. Guan W. Autonomous Collision Avoidance of Unmanned Surface Vehicles Based on Improved A-Star and Dynamic Window Approach Algorithms / W. Guan, K. Wang // IEEE Intelligent Transportation Systems Magazine. — 2023. — Vol. 15. — Is. 3. — Pp. 36–50. DOI:10.1109/MITS.2022.3229109.

18. Wang P. Research on Local Path Planning for Autonomous Collision Avoidance of USV / P. Wang, X. Yao, Q. Fei, J. Meng // 2022 China Automation Congress (CAC) — IEEE, 2022. — Pp. 5368–5373. DOI: 10.1109/CAC57257.2022.10055154.

19. Chao W. A situation awareness approach for USV based on Artificial Potential Fields / W. Chao, M. Feng, W. Qing, W. Shuwu // 2017 4th International conference on Transportation Information and Safety (ICTIS) — IEEE, 2017. — Pp. 232–235. DOI: 10.1109/ICTIS.2017.8047770.

20. Chen Q. D. Vector Field-Based Guidance Method for Collision Avoidance of Unmanned Surface Vehicles / Q. D. Chen, S. W. Huang, M. H. Ho, F. Y. Chung, C. H. Chu, C. M. Liao, J. Guo // 2023 IEEE Underwater Technology (UT). — IEEE, 2023. — Pp. 1–7. DOI: 10.1109/UT49729.2023.10103386.

21. Naeem W. Collision avoidance of maritime vessels / W. Naeem, S. Campbell, M. Abu-Tair // Navigation and Control of Autonomous Marine Vehicles. — 2019. — Pp. 61–84. DOI: 10.1049/PBTR011E_ch3.

22. Lazarowska A. Ship’s Trajectory Planning for Collision Avoidance at Sea Based on Ant Colony Optimisation / A. Lazarowska // The Journal of Navigation. — 2015. — Vol. 68. — Is. 2. — Pp. 291–307. DOI: 10.1017/S0373463314000708.

23. Yuan-hui W. Research on Optimal Planning Method of USV for Complex Obstacles / W. Yuan-hui, C. Cen // 2016 IEEE International Conference on Mechatronics and Automation. — IEEE, 2016. — Pp. 2507–2511. DOI:10.1109/ICMA.2016.7558960.

24. Gamayanti N. Global Path Planning for USV Waypoint Guidance System Using Dynamic Programming / N. Gamayanti, R. E. A. Kadir, A. Alkaff // 2020 International Seminar on Intelligent Technology and Its Applications (ISITIA). — IEEE, 2020. — Pp. 248–253. DOI: 10.1109/ISITIA49792.2020.9163712.

25. Ding F. Energy-efficient Path Planning and Control Approach of USV Based on Particle Swarm Optimization / F. Ding, Z. Zhang, M, Fu, Y. Wang, C. Wang // OCEANS 2018 MTS/IEEE Charleston. — IEEE, 2018. — Pp. 1–6. DOI: 10.1109/OCEANS.2018.8604920.

26. Казакова Е. М. Применение метода роя частиц в задачах оптимизации / Е. М. Казакова // Известия Кабардино-Балкарского научного центра РАН. — 2022. — № 5 (109). — С. 48–57. DOI: 10.35330/1991-6639-2022-5-109-48-57.

27. Wang C. Research on intelligent collision avoidance decision-making of unmanned ship in unknown environments / C. Wang, X. Zhang, L. Cong, J. Li, J. Zhang // Evolving Systems. — 2019. — Vol. 10. — Is. 4. — Pp. 649–658. DOI: 10.1007/s12530-018-9253-9.

28. Акмайкин Д. А. Эвристический поиск оптимального маршрута судна по Северному морскому пути / Д. А. Акмайкин, С. Ф. Клюева, П. А. Салюк // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. — 2015. — № 5 (33). — С. 55–62. DOI: 10.21821/2309-5180-2015-7-5-55-62.

29. Son N. S. On the sea trial test for the validation of an autonomous collision avoidance system of unmanned surface vehicle, ARAGON / N. S. Son, S. Y. Kim // OCEANS 2018 MTS/IEEE Charleston. — IEEE, 2018. — Pp. 1–5. DOI: 10.1109/OCEANS.2018.8604803.

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