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

An energy-efficient hierarchical algorithm of dynamic obstacle avoidance for unmanned surface vehicle

Wang Jiaqi|Li Shixin|Li Boyang|Zhao Chenyu|Cui Ying
대한조선학회 (The Society Of Naval Architects Of Korea)|2023.12|International Journal of Naval Architecture and Ocean Engineering|제15권 |pp. 1-14|DOI 10.1016/j.ijnaoe.2023.100528

2

조회

0

다운로드

3

인용

0

참고문헌

키워드

Genetic algorithmUnmanned surface vehicleLocal path planningVelocity obstacleGlobal path planning
주제분류조선공학

초록

Most of the existing studies developed and improved local path planning algorithms independently of global planning, i.e., ignoring the global optimal constrains. To meet the requirements of practical applications, this paper presented an energy-efficient hierarchical collision avoidance algorithm for unmanned surface vehicle operating in clustered dynamic environments. For the global level, genetic algorithm was modified by strategies of greedy-inspired population initialization, penalty-based multiobjective fitness function, and joint crossover. For the local level, velocity obstacle was combined with dynamic window approach to provide the kinematic constraints of the vehicle to its admissible velocities and simplified collision avoidance rules to guide the evasive maneuvers. Simulations showed that the proposed global algorithm was superior to three other algorithms in terms of path length, path smoothness, and convergence speed regardless of the environment size. The performance of the local algorithm was also verified for various encounter scenarios and speed ratios. In addition, the combination of the global and local planning can effectively solve the path optimization and dynamic obstacle avoidance in a designed offshore environment of fish cage culture.

Abstract

Most of the existing studies developed and improved local path planning algorithms independently of global planning, i.e., ignoring the global optimal constrains. To meet the requirements of practical applications, this paper presented an energy-efficient hierarchical collision avoidance algorithm for unmanned surface vehicle operating in clustered dynamic environments. For the global level, genetic algorithm was modified by strategies of greedy-inspired population initialization, penalty-based multiobjective fitness function, and joint crossover. For the local level, velocity obstacle was combined with dynamic window approach to provide the kinematic constraints of the vehicle to its admissible velocities and simplified collision avoidance rules to guide the evasive maneuvers. Simulations showed that the proposed global algorithm was superior to three other algorithms in terms of path length, path smoothness, and convergence speed regardless of the environment size. The performance of the local algorithm was also verified for various encounter scenarios and speed ratios. In addition, the combination of the global and local planning can effectively solve the path optimization and dynamic obstacle avoidance in a designed offshore environment of fish cage culture.

참고문헌 (48)

  1. Shubhani Aggarwal, "Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges", Computer Communications, 149, pp.270~299 (2020), Elsevier BV[DOI]
  2. Andrew R. Barron, "Approximation and learning by greedy algorithms", The Annals of Statistics, 36(1) (2008), Institute of Mathematical Statistics[DOI]
  3. Zeqiu Chen, "A new evolving mechanism of genetic algorithm for multi-constraint intelligent camera path planning", Soft Computing, 25(7), pp.5073~5092 (2021), Springer Science and Business Media LLC[DOI]
  4. Do-Hyun Chun, "Deep reinforcement learning-based collision avoidance for an autonomous ship", Ocean Engineering, 234, pp.109216~ (2021), Elsevier BV[DOI]
  5. Marco Cococcioni, "Game Theory for Unmanned Vehicle Path Planning in the Marine Domain: State of the Art and New Possibilities", Journal of Marine Science and Engineering, 9(11), pp.1175~ (2021), MDPI AG[DOI]
  6. Andrzej Felski, "The Ocean-Going Autonomous Ship—Challenges and Threats", Journal of Marine Science and Engineering, 8(1), pp.41~ (2020), MDPI AG[DOI]
  7. Paolo Fiorini, "Motion Planning in Dynamic Environments Using Velocity Obstacles", The International Journal of Robotics Research, 17(7), pp.760~772 (1998), SAGE Publications[DOI]
  8. Xiongfei Geng, "Motion Plan of Maritime Autonomous Surface Ships by Dynamic Programming for Collision Avoidance and Speed Optimization", Sensors, 19(2), pp.434~ (2019), MDPI AG[DOI]
  9. Ha Jisang, "Quantitative calculation method of the collision risk for collision avoidance in ship navigation using the CPA and ship domain", Journal of Computational Design and Engineering, 8(3), pp.894~909 (2021), 한국CDE학회[DOI]
  10. Han, S., "Automatic berthing for an underactuated unmanned surface vehicle : a real-time motion planning approach", Ocean Eng, 235, pp.109352~ (2021)[DOI]
  11. Holland, J. H., "Outline for a logic theory of adaptive systems", J. ACM, 9(3), pp.297~314 (1962)
  12. Yancai Hu, "Collision risk assessment based on the vulnerability of marine accidents using fuzzy logic", International Journal of Naval Architecture and Ocean Engineering, 12, pp.541~551 (2020), 대한조선학회[DOI]
  13. Yamin Huang, "Generalized velocity obstacle algorithm for preventing ship collisions at sea", Ocean Engineering, 173, pp.142~156 (2019), Elsevier BV[DOI]
  14. In-Bae Jeong, "Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate", Expert Systems with Applications, 123, pp.82~90 (2019), Elsevier BV[DOI]
  15. Hanguen Kim, "Angular rate-constrained path planning algorithm for unmanned surface vehicles", Ocean Engineering, 84, pp.37~44 (2014), Elsevier BV[DOI]
  16. Heesu Kim, "A study on path optimization method of an unmanned surface vehicle under environmental loads using genetic algorithm", Ocean Engineering, 142, pp.616~624 (2017), Elsevier BV[DOI]
  17. 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]
  18. Evan Krell, "Autonomous Surface Vehicle energy-efficient and reward-based path planning using Particle Swarm Optimization and Visibility Graphs", Applied Ocean Research, 122, pp.103125~ (2022), Elsevier BV[DOI]
  19. Kairong Li, "Path Planning of Mobile Robot Based on Improved Multiobjective Genetic Algorithm", Wireless Communications and Mobile Computing, 2021, pp.1~12 (2021), Hindawi Limited[DOI]
  20. Dimitrios V. Lyridis, "An improved ant colony optimization algorithm for unmanned surface vehicle local path planning with multi-modality constraints", Ocean Engineering, 241, pp.109890~ (2021), Elsevier BV[DOI]
  21. Yong Ma, "Multi-objective path planning for unmanned surface vehicle with currents effects", ISA Transactions, 75, pp.137~156 (2018), Elsevier BV[DOI]
  22. Michael, Sievers, "Submerged cage aquaculture of marine fish A review of the biological challenges and opportunities", Rev. Aquacult, 14, pp.106~119 (2021)[DOI]
  23. Morten Breivik, "Straight-Line Target Tracking for Unmanned Surface Vehicles", Modeling, Identification and Control: A Norwegian Research Bulletin, 29(4), pp.131~149 (2008), Norwegian Society of Automatic Control[DOI]
  24. Shengke Ni, "A deterministic collision avoidance decision-making system for multi-MASS encounter situation", Ocean Engineering, 266, pp.113087~ (2022), Elsevier BV[DOI]
  25. Jun Ning, "COLREGs-Compliant Unmanned Surface Vehicles Collision Avoidance Based on Multi-Objective Genetic Algorithm", IEEE Access, 8, pp.190367~190377 (2020), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  26. Hanlin Niu, "Energy efficient path planning for Unmanned Surface Vehicle in spatially-temporally variant environment", Ocean Engineering, 196, pp.106766~ (2020), Elsevier BV[DOI]
  27. Ülkü Öztürk, "A review of path planning algorithms in maritime autonomous surface ships: Navigation safety perspective", Ocean Engineering, 251, pp.111010~ (2022), Elsevier BV[DOI]
  28. Ruth G. Patterson, "Uncrewed Surface Vessel Technological Diffusion Depends on Cross-Sectoral Investment in Open-Ocean Archetypes: A Systematic Review of USV Applications and Drivers", Frontiers in Marine Science, 8, pp.1~13 (2022), Frontiers Media SA[DOI]
  29. Ngo-Quoc-Huy Tran, "Safe navigation in a coastal environment of multiple surface vehicles under uncertainties: A combined use of potential field constructions and NMPC", Ocean Engineering, 216, pp.107706~ (2020), Elsevier BV[DOI]
  30. Ahmed Hussain Qureshi, "Potential functions based sampling heuristic for optimal path planning", Autonomous Robots, 40(6), pp.1079~1093 (2015), Springer Science and Business Media LLC[DOI]
  31. José Ricardo Sánchez-Ibáñez, "Path Planning for Autonomous Mobile Robots: A Review", Sensors, 21(23), pp.7898~ (2021), MDPI AG[DOI]
  32. Brual C. Shah, "Long-Distance Path Planning for Unmanned Surface Vehicles in Complex Marine Environment", IEEE Journal of Oceanic Engineering, 45(3), pp.813~830 (2020), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  33. Yogang Singh, "A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents", Ocean Engineering, 169, pp.187~201 (2018), Elsevier BV[DOI]
  34. Yogang Singh, "A Novel Double Layered Hybrid Multi-Robot Framework for Guidance and Navigation of Unmanned Surface Vehicles in a Practical Maritime Environment", Journal of Marine Science and Engineering, 8(9), pp.624~ (2020), MDPI AG[DOI]
  35. Qisong Song, "Intelligent Optimization Algorithm-Based Path Planning for a Mobile Robot", Computational Intelligence and Neuroscience, 2021, pp.1~17 (2021), Hindawi Limited[DOI]
  36. Song Lifei, "Interference intention classification of moving obstacles used for USV collision avoidance", International Journal of Naval Architecture and Ocean Engineering, 14, pp.1~16 (2022), 대한조선학회[DOI]
  37. Adem Tuncer, "Dynamic path planning of mobile robots with improved genetic algorithm", Computers & Electrical Engineering, 38(6), pp.1564~1572 (2012), Elsevier BV[DOI]
  38. Ning Wang, "Dynamics-Constrained Global-Local Hybrid Path Planning of an Autonomous Surface Vehicle", IEEE Transactions on Vehicular Technology, 69(7), pp.6928~6942 (2020), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  39. Lipeng Wang, "Ship Route Planning Based on Double-Cycling Genetic Algorithm Considering Ship Maneuverability Constraint", IEEE Access, 8, pp.190746~190759 (2020), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  40. Ning Wang, "Autonomous Pilot of Unmanned Surface Vehicles: Bridging Path Planning and Tracking", IEEE Transactions on Vehicular Technology, 71(3), pp.2358~2374 (2022), Institute of Electrical and Electronics Engineers (IEEE)[DOI]
  41. Zheng Wang, "Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm", Computer Communications, 166, pp.49~56 (2021), Elsevier BV[DOI]
  42. Guoqing Xia, "Local Path Planning for Unmanned Surface Vehicle Collision Avoidance Based on Modified Quantum Particle Swarm Optimization", Complexity, 2020, pp.1~15 (2020), Hindawi Limited[DOI]
  43. Junfeng Xin, "An Improved Genetic Algorithm for Path-Planning of Unmanned Surface Vehicle", Sensors, 19(11), pp.2640~ (2019), MDPI AG[DOI]
  44. Junfeng Xin, "IMPROVED GENETIC ALGORITHMS BASED ON DATA-DRIVEN OPERATORS FOR PATH PLANNING OF UNMANNED SURFACE VEHICLE", International Journal of Robotics and Automation, 34(6) (2019), ACTA Press[DOI]
  45. Zhang Qiongbing, "A new crossover mechanism for genetic algorithms with variable-length chromosomes for path optimization problems", Expert Systems with Applications, 60, pp.183~189 (2016), Elsevier BV[DOI]
  46. Luman Zhao, "COLREGs-compliant multiship collision avoidance based on deep reinforcement learning", Ocean Engineering, 191, pp.106436~ (2019), Elsevier BV[DOI]
  47. Zhou Jian, "Navigation safety domain and collision risk index for decision support of collision avoidance of USVs", International Journal of Naval Architecture and Ocean Engineering, 13, pp.340~350 (2021), 대한조선학회[DOI]
  48. Xiaomin Zhu, "Velocity Obstacle Based on Vertical Ellipse for Multi-Robot Collision Avoidance", Journal of Intelligent & Robotic Systems, 99(1), pp.183~208 (2020), Springer Science and Business Media LLC[DOI]

관련 논문AI추천

Modified A* Algorithm for Obstacle Avoidance for Unmanned Surface Vehicle류재관, 윤현규, 진택성, Anh Hoa Vo한국해양공학회 · 한국해양공학회지2019 · 제33권 제6호Mission planning and performance verification of an unmanned surface vehicle using a genetic algorithm박지훈, 이대우, 이인원, Kim Hyeongmin, Kim Sukkeun, Noh Geemoon대한조선학회 · International Journal of Naval Architecture and Ocean Engineering2021 · 제13권 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권 Optimal Coverage Path Planning for Unmanned Surface Vehicles Using Flexible Formation Tracking Control남보우, 박민성한국해양공학회 · 한국해양공학회지2025 · 제39권 제3호A path planning algorithm for unmanned surface vessel with pose constraints in an unknown environmentJiabin Yu, Jiping Xu, Meng Yang, Yang Chen, Yang Lu, Zhihao Chen, Zhiyao Zhao대한조선학회 · International Journal of Naval Architecture and Ocean Engineering2024 · 제16권 A cooperative coverage path planning method for multiple USVs with dynamic collision avoidance using heuristic fusion and deep reinforcement learningWang Shixiong, Yi Liang, Zhao Enjiao대한조선학회 · International Journal of Naval Architecture and Ocean Engineering2025 · 제17권

이 간행물의 다른 논문 (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
원문 보기