Research on Intelligent Ship Route Planning Based on the Adaptive Step Size Informed-RRT* Algorithm

Abstract

Advancements in artificial intelligence and big data technologies have led to the gradual emergence of intelligent ships, which are expected to dominate the future of maritime transportation. Supporting the navigation of intelligent ships, route planning technologies have developed many route planning algorithms that prioritize economy and safety. This paper conducts an in-depth study of algorithm efficiency for a route planning problem, proposing an intelligent ship route planning algorithm based on the adaptive step size Informed-RRT*. This algorithm can quickly plan a short route according to automatic obstacle avoidance and is suitable for planning the routes of intelligent ships. Results show that the adaptive step size Informed-RRT* algorithm can shorten the optimal route length by approximately 13.05% while ensuring the running time of the planning algorithm and avoiding approximately 23.64% of redundant sampling nodes. The improved algorithm effectively circumvents unnecessary calculations and reduces a large amount of redundant sampling data, thus improving the efficiency of route planning. In a complex water environment, the unique adaptive step size mechanism enables this algorithm to prevent restricted search tree expansion, showing strong search ability and robustness, which is of practical significance for the development of intelligent ships.

Keywords

Informed-RRT* / Adaptive step size / Route planning technology / Robustness / Automatic obstacle avoidance

References

[1] CaoS, FanP, YanT. Inland waterway ship path planning based on improved RRT Algorithm. J. Mar. Sci. Eng., 2022, 101460

[2] ChenJ. UAV path planning based on improved RRT * algorithm. Nanjing University of Technology, 2021, 199

[3] ChenX, DaiR, ZhaoY. Ship route planning to avoid shallow waters with artificial fish swarm algorithm. China Navigation, 2019, 42(3): 95-99+120

[4] GammellJ, BarfootT, SrinivasaS. Informed sampling for asymptotically optimal path planning. IEEE Transactions on Robotics, 2018, 34(4): 966-984

[5] Gammell J, Srinivasa S (2014) Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems: 14–18. DOI: https://doi.org/10.1109/IROS.2014.6942976

[6] HanX, ZhangX, ZhangH. Trajectory planning of USV: online computation of the double S trajectory based on multi-scale A* algorithm with reeds–shepp curves. J. Mar. Sci. Eng., 2023, 111153

[7] JangD, KimJ. Development of ship route-planning algorithm based on rapidly-exploring random tree (RRT*) using designated space. J. Mar. Sci. Eng., 2022, 10121800

[8] JhongB, ChenM. An enhanced navigation algorithm with an adaptive controller for wheeled mobile robot based on bidirectional RRT. Actuators, 2022, 1110303

[9] JinW, MaX, ZhaoJ. Research on path planning algorithm of mobile robot based on improved informed-RRT*. Computer Engineering and Application, 2023, 59(19): 75-81

[10] Kuffner JJ, LaValle SM (2000) RRT-connect: an efficient approach to single-query path planning. Proceedings of the 2000 IEEE International Conference on Robotics & Automation, San Francisco, 995–1001. DOI: https://doi.org/10.1109/ROBOT.2000.844730

[11] KimJ. Fast route planner considering terrain information. Sensors, 2022, 22124518

[12] LaValle S, Kuffner J (1999) Randomized kinodynamic planning. Proceedings of the I999 lEEE International Conference on Robotics & Automation, Detroit, 378. DOI: https://doi.org/10.1177/02783640122067453

[13] LeeHW, RohMI, KimKS. Ship route planning in arctic ocean based on POLARIS. Ocean Engineering, 2021, 234109297

[14] LeeS, RohM, KimK. Method for a simultaneous determination of the path and the speed for ship route planning problems. Ocean Engineering, 2018, 157: 301-312

[15] LiuY, HuJ. Research on emergency logistics path optimization based on hybrid artificial fish swarm algorithm. China Management Science, 2023, 115

[16] LiuY, WangT, XuH. PE-A* algorithm for ship route planning based on field theory. IEEE Access, 2022, 10: 36490-36504

[17] LvC, CuiM, WuG. Polar ship route planning method based on Dijkstra algorithm. Ship Engineering, 2022, 44(6): 10-19

[18] MuhammadS, ZhouY. Path planning for EVs based on RA-RRT* model. Front Energy Res., 2023, 10996726

[19] NingJ, MaHR, LiW. Ship path planning and tracking control based on improved RRT algorithm. China Navigation, 2022, 45(3): 106-112

[20] Qiu X, Li Y, Jin R (2022) Improved F-RRT algorithm for flight-path optimization in hazardous weather. International Journal of Aerospace Engineering: 1166968. DOI: https://doi.org/10.1155/2022/1166968

[21] TanJ, PanB, WangY. Robot path planning based on improved RRT* FN algorithm. Control and Decision, 2021, 36(8): 1834-1840

[22] WangH, AnL, MaL. Study on navigable window navigating through arctic northeast passage based on POLARIS. China Navigation, 2022, 45(4): 23-29+38

[23] WangH, CuiY, LiM. Mobile robot path planning algorithm based on improved RRT* FN. Journal of Northeast University, 2022, 43(9): 1217-1224+1249

[24] WangL, ZhangZ, ZhuQ. Ship route planning based on double-cycling genetic algorithm considering ship maneuverability constraint. IEEE Access, 2020, 8: 190746-190759

[25] WeiJ, LiuC, ZhengY. Research on the reverse recovery vehicle routing problem of hybrid improved artificial fish swarm algorithm. Information and Management Research, 2022, 7(Z2): 59-72

[26] WuG, AtillaI, TahsinT. Long-voyage route planning method based on multi-scale visibility graph for autonomous ships. Ocean Engineering, 2021, 219108242

[27] YuX, LuoY, LiuY. A novel adaptive two-stage approach to dynamic optimal path planning of UAV in 3-D unknown environments. Multimed Tools Applications, 2022, 82(12): 18761-18779

[28] ZacconeR. COLREG-compliant optimal path planning for real-time guidance and control of autonomous ships. Journal of Marine Science and Engineering, 2021, 9405

[29] ZacconeR, MartelliM. A collision avoidance algorithm for ship guidance applications. Journal of Marine Engineering & Technology, 2019, 19: 62-75

[30] ZhangJ, ZhangH, LiuJ. A two-stage path planning algorithm based on rapid-exploring random tree for ships navigating in multi-obstacle water areas considering COLREGs. J. Mar. Sci. Eng., 2022, 10101441

[31] ZhangZ, WuD, GuJ. A path-planning strategy for unmanned surface vehicles based on an adaptive hybrid dynamic stepsize and target attractive force-RRT algorithm. J. Mar. Sci. Eng., 2019, 75132

[32] ZhaoW, WangH, GengJ. Multi-objective weather routing algorithm for ships based on hybrid particle swarm optimization. Journal of Ocean University of China, 2022, 21: 28-38

[33] ZhaoW, WangY, ZhangZ. Multicriteria ship route planning method based on improved particle swarm optimization-genetic algorithm. J. Mar. Sci. Eng., 2021, 9357

[34] ZhongF, YangX, YuanZ. Route re-planning method of unmanned aerial vehicle based on RRT algorithm. Ship and Sea Engineering, 2022, 51(6): 130-135

RIGHTS & PERMISSIONS

Harbin Engineering University and Springer-Verlag GmbH Germany, part of Springer Nature