|Table of Contents|

Citation:
　Zhaoqi Liu,Jianhui Cui,Fanbin Meng,et al.Research on Intelligent Ship Route Planning Based on the Adaptive Step Size Informed-RRT* Algorithm[J].Journal of Marine Science and Application,2025,(4):829-839.[doi:10.1007/s11804-024-00433-2]
Click and Copy

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

Info

Title:
Research on Intelligent Ship Route Planning Based on the Adaptive Step Size Informed-RRT* Algorithm
Author(s):
Zhaoqi Liu1;  Jianhui Cui1;  Fanbin Meng2;  Huawei Xie2;  Yangwen Dan2;  Bin Li2
Affilations:
Author(s):
Zhaoqi Liu1;  Jianhui Cui1;  Fanbin Meng2;  Huawei Xie2;  Yangwen Dan2;  Bin Li2
1. Maritime College, Tianjin University of Technology, Tianjin 300384, China;
2. Tianjin Navigation Instrument Research Institute, Tianjin 300131, China
Keywords:
Informed-RRT*; Adaptive step size; Route planning technology; Robustness; Automatic obstacle avoidance
分类号:
-
DOI:
10.1007/s11804-024-00433-2
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.

References:

[1] Cao S, Fan P, Yan T (2022) Inland waterway ship path planning based on improved RRT Algorithm. J. Mar. Sci. Eng. 10: 1460. DOI: 10.3390/jmse10101460
[2] Chen J (2021) UAV path planning based on improved RRT * algorithm. Nanjing University of Technology 1: 99. DOI: 10.27241/d.cnki.gnjgu.2021.000261
[3] Chen X, Dai R, Zhao Y (2019) Ship route planning to avoid shallow waters with artificial fish swarm algorithm. China Navigation 42(3): 95-99+120. DOI: CNKI:SUN:ZGHH.0.2019-03-019
[4] Gammell J, Barfoot T, Srinivasa S (2018) Informed sampling for asymptotically optimal path planning. IEEE Transactions on Robotics 34(4): 966-984. DOI: 10.1109/TRO.2018.2830331
[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: 10.1109/IROS.2014.6942976
[6] Han X, Zhang X, Zhang H (2023) 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. 11(1): 153. DOI: 10.3390/jmse11010153
[7] Jang D, Kim J (2022) Development of ship route-planning algorithm based on rapidly-exploring random tree (RRT*) using designated space. J. Mar. Sci. Eng. 10(12): 1800. DOI: 10.3390/jmse10121800
[8] Jhong B, Chen M (2022) An enhanced navigation algorithm with an adaptive controller for wheeled mobile robot based on bidirectional RRT. Actuators 11(10): 303. DOI: 10.3390/act11100303
[9] Jin W, Ma X, Zhao J (2023) Research on path planning algorithm of mobile robot based on improved informed-RRT*. Computer Engineering and Application 59(19): 75-81. https://kns.cnki.net/kcms/detail/11.2127.TP.20230116.1710.012.html
[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: 10.1109/ROBOT.2000.844730
[11] Kim J (2022) Fast route planner considering terrain information. Sensors 22(12): 4518. DOI: 10.3390/s22124518
[12] LaValle S, Kuffner J (1999) Randomized kinodynamic planning. Proceedings of the I999 lEEE International Conference on Robotics & Automation, Detroit, 378. DOI: 10.1177/02783640122067453
[13] Lee HW, Roh MI, Kim KS (2021) Ship route planning in arctic ocean based on POLARIS. Ocean Engineering 234: 109297. DOI: 10.1016/j.oceaneng.2021.109297
[14] Lee S, Roh M, Kim K (2018) Method for a simultaneous determination of the path and the speed for ship route planning problems. Ocean Engineering 157: 301-312. DOI: 10.1016/j.oceaneng.2018.03.068
[15] Liu Y, Hu J (2023) Research on emergency logistics path optimization based on hybrid artificial fish swarm algorithm. China Management Science 1: 15. DOI: 10.16381/j.cnki.issn1003-207x.2022.1672
[16] Liu Y, Wang T, Xu H (2022) PE-A* algorithm for ship route planning based on field theory. IEEE Access 10: 36490-36504. DOI: 10.1109/ACCESS.2022.3164422
[17] Lv C, Cui M, Wu G (2022) Polar ship route planning method based on Dijkstra algorithm. Ship Engineering 44(6): 10-19
[18] Muhammad S, Zhou Y (2023) Path planning for EVs based on RA-RRT* model. Front Energy Res. 10: 996726. DOI: 10.3389/fenrg.2022.996726
[19] Ning J, Ma HR, Li W (2022) Ship path planning and tracking control based on improved RRT algorithm. China Navigation 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: 10.1155/2022/1166968
[21] Tan J, Pan B, Wang Y (2021) Robot path planning based on improved RRT* FN algorithm. Control and Decision 36(8): 1834-1840. DOI: 10.13195/j.kzyjc.2019.1713
[22] Wang H, An L, Ma L (2022a) Study on navigable window navigating through arctic northeast passage based on POLARIS. China Navigation 45(4): 23-29+38
[23] Wang H, Cui Y, Li M (2022b) Mobile robot path planning algorithm based on improved RRT* FN. Journal of Northeast University 43(9): 1217-1224+1249
[24] Wang L, Zhang Z, Zhu Q (2020) Ship route planning based on double-cycling genetic algorithm considering ship maneuverability constraint. IEEE Access 8: 190746-190759. DOI: 10.1109/ACCESS.2020.3031739
[25] Wei J, Liu C, Zheng Y (2022) Research on the reverse recovery vehicle routing problem of hybrid improved artificial fish swarm algorithm. Information and Management Research 7(Z2): 59-72
[26] Wu G, Atilla I, Tahsin T (2021) Long-voyage route planning method based on multi-scale visibility graph for autonomous ships. Ocean Engineering 219: 108242. DOI: 10.1016/j.oceaneng.2020.108242
[27] Yu X, Luo Y, Liu Y (2022) A novel adaptive two-stage approach to dynamic optimal path planning of UAV in 3-D unknown environments. Multimed Tools Applications 82(12): 18761-18779. DOI: 10.1007/s11042-022-14254-4
[28] Zaccone R (2021) COLREG-compliant optimal path planning for real-time guidance and control of autonomous ships. Journal of Marine Science and Engineering 9: 405. DOI: 10.3390/jmse9040405
[29] Zaccone R, Martelli M (2019) A collision avoidance algorithm for ship guidance applications. Journal of Marine Engineering & Technology 19: 62-75. DOI: 10.1080/20464177.2019.1685836
[30] Zhang J, Zhang H, Liu J (2022) 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. 10(10): 1441. DOI: 10.3390/jmse10101441
[31] Zhang Z, Wu D, Gu J (2019) 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. 7(5): 132. DOI: 10.3390/jmse7050132
[32] Zhao W, Wang H, Geng J (2022) Multi-objective weather routing algorithm for ships based on hybrid particle swarm optimization. Journal of Ocean University of China 21: 28-38. DOI: 10.1007/s11802-022-4709-8
[33] Zhao W, Wang Y, Zhang Z (2021) Multicriteria ship route planning method based on improved particle swarm optimization-genetic algorithm. J. Mar. Sci. Eng. 9: 357. DOI: 10.3390/jmse9040357
[34] Zhong F, Yang X, Yuan Z (2022) Route re-planning method of unmanned aerial vehicle based on RRT algorithm. Ship and Sea Engineering 51(6): 130-135

Memo

Memo:
Received date:2023-5-4;Accepted date:2024-2-8。<br>Corresponding author:Jianhui Cui,E-mail:jianhuicui@email.tjut.edu.cn
Last Update: 2025-08-27