본문 바로가기
KERD
논문KCI 등재

Ship collision avoidance route planning using CRI-based A∗ algorithm

박선영|노유정|서찬희|Abebe Misganaw|Kang Young-Jin|권철현
대한조선학회 (The Society Of Naval Architects Of Korea)|2023.12|International Journal of Naval Architecture and Ocean Engineering|제15권 |pp. 1-15|DOI 10.1016/j.ijnaoe.2023.100551

1

조회

0

다운로드

5

인용

0

참고문헌

키워드

A* algorithmRoute planningCollision risk indexCOLREGsShip collisionShip domain
주제분류조선공학

초록

This study presents a novel ship route planning algorithm that takes into account both operational economy and safety by integrating the A* algorithm with a collision avoidance algorithm that evaluates the Collision Risk Index (CRI) between the own ship and the target ship. The CRI-based A* algorithm defines a penalty zone, allowing the own ship to explore safe routes based on the International Regulations for Preventing Collisions at Sea 1972 (COLREGs) and performs an adaptive and effective node search on an extended local map grid according to various encounter situations. The proposed algorithm is validated through simulations of head-on, fine-broad crossing, converging crossing, and overtaking encounters, indicating an economical and safe optimum route compared to conventional ship domainbased route planning.

Abstract

This study presents a novel ship route planning algorithm that takes into account both operational economy and safety by integrating the A* algorithm with a collision avoidance algorithm that evaluates the Collision Risk Index (CRI) between the own ship and the target ship. The CRI-based A* algorithm defines a penalty zone, allowing the own ship to explore safe routes based on the International Regulations for Preventing Collisions at Sea 1972 (COLREGs) and performs an adaptive and effective node search on an extended local map grid according to various encounter situations. The proposed algorithm is validated through simulations of head-on, fine-broad crossing, converging crossing, and overtaking encounters, indicating an economical and safe optimum route compared to conventional ship domainbased route planning.

참고문헌 (53)

  1. Abebe, M., "Machine learning approaches for ship speed prediction towards energy efficient shipping", Appl. Sci, 10, pp.2325~ (2020)
  2. Abebe, M., "Developing a ship collision risk index estimation model based on Dempster-Shafer theory", Appl. Ocean Res, 113, pp.102735~ (2021)
  3. Abebe, M., "Ship trajectory planning for collision avoidance using hybrid ARIMA-LSTM models", Ocean Eng, 256, pp.11527~ (2022)
  4. Ahn, J. H., "A study on the collision avoidance of a ship using neural networks and fuzzy logic", Appl. Ocean Res, 37, pp.162~173 (2012)
  5. Blaich, M., "Fast grid based collision avoidance for vessels using A* search algorithm", Proceedings of the 17th International Conference on Methods & Models in Automation &Robotics (MMAR), pp.27~30 (2012)
  6. Bukhari, A. C., "An intelligent real-time multi-vessel collision risk assessment system from VTS view point based on fuzzy inference system", Expert Syst. Appl, 40(4), pp.1220~1230 (2013)
  7. Chen, T., "Xgboost: a scalable tree boosting system", Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.785~794 (2016)
  8. Chun, D. -H., "Deep reinforcement learningbased collision avoidance for an autonomous ship", Ocean Eng, 234, pp.109216~ (2021)
  9. Coldwell, T. G., "Marine traffic behaviour in restricted waters", J. Navig, 36, pp.430~444 (1983)
  10. Davis, P. V., "A computer simulation of marine traffic using domains and arenas", J. Nav, 33(2), pp.215~222 (1980)
  11. Dechter, R., "Generalized best-first search strategies and the optimality of A", J. ACM, 32, pp.505~536 (1985)
  12. Fujii, Y., "Traffic capacity", J. Navig, 24, pp.543~552 (1971)
  13. Gang, L., "Estimation of vessel collision risk index based on support vector machine", Adv. Mech. Eng, 8(11), pp.1~10 (2016)
  14. Gao, P., "Research on ship collision avoidance path planning based on modified potential field ant colony algorithm", Ocean Coast Manag, 235, pp.106482~ (2023)
  15. Goodwin, E. M., "A statistical study of ship domains", J. Navig, 28, pp.328~344 (1975)
  16. Guo, S., "Path planning of coastal ships based on optimized DQN reward function", J. Mar. Sci. Eng, 9(2), pp.210~ (2021)
  17. Hansen, M. G., "Empirical ship domain based on AIS data", J. Navig, 66, pp.931~940 (2013)
  18. Hart, P. E., "A formal basis for the heuristic determination of minimum cost paths", IEEE Trans. Syst. Man Cybern, 4, pp.100~107 (1968)
  19. He, Z., "Dynamic anti-collision A-star algorithm for multi-ship encounter situations", Appl. Ocean Res, 118, pp.102995~ (2022)
  20. Hu, Y., "Multi-ship collision avoidance decision-making based on collision risk index", J. Mar. Sci. Eng, 8, pp.640~ (2020)
  21. Jiang, L., "A human-like collision avoidance method for autonomous ship with attention-based deep reinforcement learning", Ocean Eng, 264, pp.112378~ (2022)
  22. Kearon, J., "Computer program for collision avoidance and track keeping", Proceedings of the International Conference on Mathematics Aspects of Marine Traffic, pp.229~242 (1977)
  23. Kim Jae Hyun, "Collision avoidance based on predictive probability using Kalman filter", International Journal of Naval Architecture and Ocean Engineering, 14, pp.1~23 (2022), 대한조선학회[DOI]
  24. Lee, S. -M., "Method for a simultaneous determination of the path and the speed for ship route planning problems", Ocean Eng, 157, pp.301~312 (2018)
  25. Li, B., "An approach of vessel collision risk assessment based on the DeS evidence theory", Ocean Eng, 74, pp.16~21 (2013)
  26. Liu, C., "An improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning", Appl. Sci, 9, pp.1057~ (2019)
  27. Li, J., "Ship's trajectory planning based on improved multiobjective algorithm for collision avoidance", J. Adv. Transport, 2019, pp.4068783~ (2019)
  28. Moradi, M. H., "Marine route optimization using reinforcement learning approach to reduce fuel consumption and consequently minimize CO2 emissions", Ocean Eng, 259, pp.111882~ (2022)
  29. Nguyen, M., "A novel method for risk assessment and simulation of collision avoidance for vessels based on AIS", Algorithms, 11, pp.204~ (2018)
  30. Ning, J., "COLREGs-Compliant unmanned surface vehicles collision avoidance based on multi-objective genetic algorithm", IEEE Access, 8, pp.190367~190377 (2020)
  31. Sawada, R., "Automatic ship collision avoidance using deep reinforcement learning with LSTM in continuous action spaces", JMST, 26, pp.509~524 (2021)
  32. Shin, Y. W., "Near-optimal weather routing by using improved A* algorithm", Appl. Sci, 10, pp.6010~ (2020)
  33. Szlapczynski, R., "Ship domain applied to determining distances for collision avoidance maneuvers in give-way situations", Ocean Eng, 165, pp.43~54 (2018)
  34. Tanakitkorn, K., "Grid-based GA path planning with improved cost function for an over-actuated hover-capable AUV", Proceedings of the 2014 IEEE, 2014, 1~8
  35. Tsou, M. C., "An ant colony algorithm for efficient ship routing", Pol. Marit. Res, 20, pp.28~38 (2013)
  36. Vlachos, D. S., "Optimal ship routing based on wind and wave forecasts", Appl. Numer. Anal. Comput. Math, 1, pp.547~551 (2004)
  37. Wang, Y., "An empirically-calibrated ship domain as a safety criterion for navigation in confined waters", J. Navig, 69, pp.257~276 (2016)
  38. Wang, L. P., "Ship route planning based on doublecycling genetic algorithm considering ship maneuverability constraint", IEEE Access, 8, pp.190746~190759 (2020)
  39. Wang, H., "Voyage optimization combining algorithm and dynamic programming for fuel", emissions reduction, 2021, pp.90, 102670~
  40. Wang Jiaqi, "An energy-efficient hierarchical algorithm of dynamic obstacle avoidance for unmanned surface vehicle", International Journal of Naval Architecture and Ocean Engineering, 15, pp.1~14 (2023), 대한조선학회[DOI]
  41. Xie, S., "Ship predictive collision avoidance method based on an improved beetle antennae search algorithm", Ocean Eng, 192, pp.106542~ (2019)
  42. Xie, S., "A composite learning method for multi-ship collision avoidance based on reinforcement learning and inverse control", Neurocomputing, 411, pp.375~392 (2020)
  43. Xu, Q., "Collision avoidance strategy optimization based on danger immune algorithm", Comput. Ind. Eng, 76, pp.268~279 (2014)
  44. Xu, Q., "Intelligent evaluation system of ship management", J. Mar. Nav. Safety Sea Transp, 4, pp.479~482 (2010)
  45. Xu, X., "Path planning and dynamic collision avoidance algorithm under COLREGs via deep reinforcement learning", Neurocomputing, 468, pp.181~197 (2022)
  46. Yu, J., "DCA-based collision avoidance path planning for marine vehicles in presence of the multi-ship encounter situation", J. Mar. Sci. Eng, 2022, pp.529~ (2022)
  47. Zaccone, R. Ottaviani, "Ship voyage optimization for safe and energy-efficient navigation : a dynamic programming approach", Ocean Eng, 153, pp.215~224 (2018)
  48. Zaccone, R., "A COLREG-Compliant ship collision avoidance algorithm", Proceedings of the 2019 18th European Control Conference (ECC), pp.2530~2535 (2019)
  49. Zhang, M., "A big data analytics method for the evaluation of ship e ship collision risk reflecting hydrometeorological conditions", Reliab. Eng. Syst. Saf, 213, pp.107674~ (2021)
  50. Zhang, G., "Application of improved multiobjective ant colony optimization algorithm in ship weather routing", J. Ocean Univ. China, 20, pp.45~55 (2021)
  51. Zhao, L., "COLREGs-compliant multiship collision avoidance based on deep reinforcement learning", Ocean Eng, 191, pp.106436~ (2019)
  52. Zhao, Y., "A real-time collision avoidance learning system for unmanned surface vessels", Neurocomputing, 182, pp.255~266 (2016)
  53. Zhou, J., "Construction of the collision risk factor model", J. Ningbo Univ, 170, pp.61~65 (2004)

관련 논문AI추천

Ship route planning for collision avoidance based on the improved isochrone method노명일, 이혜원, 하지상대한조선학회 · International Journal of Naval Architecture and Ocean Engineering2024 · 제16권 Method for anti-collision path planning using velocity obstacle and A* algorithms for maritime autonomous surface ship노명일, 유동훈대한조선학회 · International Journal of Naval Architecture and Ocean Engineering2024 · 제16권 Obstacle Zone by Target 기반 선박 충돌회피 알고리즘 개발에 관한 연구이성욱, 이찬욱대한조선학회 · 대한조선학회 논문집2024 · 제61권 제2호Safe path planning for autonomous ships based on the point of potential collision conceptLazarowska Agnieszka대한조선학회 · International Journal of Naval Architecture and Ocean Engineering2025 · 제17권 A Study on Multi-ship Avoidance System for Unmanned Surface Vehicles Using the Quaternion Ship Domain and Collision Risk Index김상현, 백광준, 서무영, 유원준, 이동훈, 이효근한국해양공학회 · 한국해양공학회지2025 · 제39권 제1호Modified A* Algorithm for Obstacle Avoidance for Unmanned Surface Vehicle류재관, 윤현규, 진택성, Anh Hoa Vo한국해양공학회 · 한국해양공학회지2019 · 제33권 제6호

이 간행물의 다른 논문 (56건)

Experimental study on the propulsion performance of a partially submerged propeller김재훈, 서정화, 박종열, 이신형, 김재헌, 박격포, 하정수pp. 1-13Applicability and reliability of an experimental method measuring underwater acoustic radiation efficiency of floating box-type plate structures in a reverberant water tank박성주, 조대승, 김국현, 이주엽pp. 1-12Extent of damage analysis of naval ships subject to internal explosions윤준영, 곽묘정, 노유정, 신윤호, Park Sayyoon, Kwon Seungminpp. 1-15Entrance and run angle variations of hull form preserving the prismatic coefficient김명수, 김유철, 오민재, Son Eun-Young, Oh Se-Jinpp. 1-12Fatigue assessment for FPSO hawsersWang Fang, Yakimov Vladimir, Gaidai Oleg, Xu Xiaosen, Niu Yuhao, Kelin Wangpp. 1-8
원문 보기