NI-MOD-P-RRT*: A threshold-free sampling-based path planning algorithm for unmanned surface vehicles in dynamic environments

Yunlai Fu; Wei Wang; Yongqi Zhang; Yan Liu; Haoran Li; Yunlai Fu; Wei Wang; Yongqi Zhang; Yan Liu; Haoran Li

doi:10.3934/electreng.2025020

AIMS Electronics and Electrical Engineering

2025, Volume 9, Issue 4: 423-447. doi: 10.3934/electreng.2025020

Previous Article Next Article

Research article Special Issues

NI-MOD-P-RRT*: A threshold-free sampling-based path planning algorithm for unmanned surface vehicles in dynamic environments

1.
College of Information Engineering, Dalian Ocean University, Dalian 116023, China
2.
Dalian Key Laboratory of Smart Fisheries, Dalian Ocean University, Dalian 116023, China

Received: 16 May 2025 Revised: 24 July 2025 Accepted: 30 July 2025 Published: 06 August 2025

In this paper, we propose a threshold-free multi-objective dynamic rapidly-exploring random tree algorithm (NI-MOD-P-RRT*) for unmanned surface vehicles in unknown dynamic environments. The algorithm consists of an initial path generation process and a path replanning process. Its major features include: Addressing the issues of slow search speed and excessive inflection points in initial paths of the P-RRT* algorithm by integrating target-biased sampling and constraining the expansion angle of the random tree during sampling, optimizing connection constraints to reduce search time; after obtaining the initial path, employing improved triangle inequality and $ \mathrm{B} $-spline interpolation for path pruning and smoothing to generate an optimized path, with node information stored as prior knowledge; building upon this, designing a topology-sorting-based method to select optimal substitute nodes for path replanning when the current path becomes infeasible. Simulation experiments in various environments demonstrated that the proposed algorithm decreases path length, search time, and iteration counts, while quickly identifying substitute nodes to circumvent newly detected obstacles when needed.
- rapidly-exploring random tree (RRT),
- dynamic environments,
- unmanned surface vehicles,
- triangle inequality,
- topology-sorting
Citation: Yunlai Fu, Wei Wang, Yongqi Zhang, Yan Liu, Haoran Li. NI-MOD-P-RRT*: A threshold-free sampling-based path planning algorithm for unmanned surface vehicles in dynamic environments[J]. AIMS Electronics and Electrical Engineering, 2025, 9(4): 423-447. doi: 10.3934/electreng.2025020

Related Papers:

Abstract

In this paper, we propose a threshold-free multi-objective dynamic rapidly-exploring random tree algorithm (NI-MOD-P-RRT*) for unmanned surface vehicles in unknown dynamic environments. The algorithm consists of an initial path generation process and a path replanning process. Its major features include: Addressing the issues of slow search speed and excessive inflection points in initial paths of the P-RRT* algorithm by integrating target-biased sampling and constraining the expansion angle of the random tree during sampling, optimizing connection constraints to reduce search time; after obtaining the initial path, employing improved triangle inequality and $ \mathrm{B} $-spline interpolation for path pruning and smoothing to generate an optimized path, with node information stored as prior knowledge; building upon this, designing a topology-sorting-based method to select optimal substitute nodes for path replanning when the current path becomes infeasible. Simulation experiments in various environments demonstrated that the proposed algorithm decreases path length, search time, and iteration counts, while quickly identifying substitute nodes to circumvent newly detected obstacles when needed.

References

[1]	Wu Y, Duan Y, Wei Y, An D, Liu J (2022) Application of intelligent and unmanned equipment in aquaculture: A review. Comput Electron Agr 199: 107201. https://doi.org/10.1016/j.compag.2022.107201 doi: 10.1016/j.compag.2022.107201
[2]	Jones M, Djahel S, Welsh K (2023) Path-planning for unmanned aerial vehicles with environment complexity considerations: A survey. ACM Comput Surv 55: 1‒39. https://doi.org/10.1145/3570723 doi: 10.1145/3570723
[3]	Sang H, You Y, Sun X, Zhou Y, Liu F (2021) The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Eng 223: 108709. https://doi.org/10.1016/j.oceaneng.2021.108709 doi: 10.1016/j.oceaneng.2021.108709
[4]	Yu J, Yang M, Zhao Z, Wang X, Bai Y, Wu J, et al. (2022) Path planning of unmanned surface vessel in an unknown environment based on improved D* Lite algorithm. Ocean Eng 266: 112873. https://doi.org/10.1016/j.oceaneng.2022.112873 doi: 10.1016/j.oceaneng.2022.112873
[5]	Miao C, Chen G, Yan C, Wu Y (2021) Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Comput Ind Eng 156: 107230. https://doi.org/10.1016/j.cie.2021.107230 doi: 10.1016/j.cie.2021.107230
[6]	Wang X, Liu Z, Li X (2023) Optimal delivery route planning for a fleet of heterogeneous drones: A rescheduling-based genetic algorithm approach. Comput Ind Eng 179: 109179. https://doi.org/10.1016/j.cie.2023.109179 doi: 10.1016/j.cie.2023.109179
[7]	Gad AG (2022) Particle swarm optimization algorithm and its applications: a systematic review. Arch comput method eng 29: 2531‒2561. https://doi.org/10.1007/s11831-021-09694-4 doi: 10.1007/s11831-021-09694-4
[8]	Charalambopoulos N, Xidias E, Nearchou A (2023) Efficient ship weather routing using probabilistic roadmaps. Ocean Eng 273: 114031. https://doi.org/10.1016/j.oceaneng.2023.114031 doi: 10.1016/j.oceaneng.2023.114031
[9]	LaValle SM, Kuffner Jr, JJ (2001) Randomized kinodynamic planning. The international journal of robotics research 20: 378‒400. http://dx.doi.org/10.1177/02783640122067453 doi: 10.1177/02783640122067453
[10]	Billard A, Kragic D (2019) Trends and challenges in robot manipulation. Science 364: eaat8414. https://doi.org/10.1126/science.aat8414 doi: 10.1126/science.aat8414
[11]	Ganesan S, Ramalingam B, Mohan RE (2024) A hybrid sampling-based RRT* path planning algorithm for autonomous mobile robot navigation. Expert Syst Appl 258: 125206. https://doi.org/10.1016/j.eswa.2024.125206 doi: 10.1016/j.eswa.2024.125206
[12]	Yang Q, Qu W, Wang Y, Song X, Guo Y, Ke Y (2025) Smooth joint motion planning for redundant fiber placement manipulator based on improved RRT. Robot Comput-Int Manuf 91: 102851. https://doi.org/10.1016/j.rcim.2024.102851 doi: 10.1016/j.rcim.2024.102851
[13]	Fan J, Chen X, Liang X (2023) UAV trajectory planning based on bi-directional APF-RRT* algorithm with goal-biased. Expert syst appl 213: 119137. https://doi.org/10.1016/j.eswa.2022.119137 doi: 10.1016/j.eswa.2022.119137
[14]	Liu Y, Li C, Yu H, Song C (2023) NT-ARS-RRT: A novel non-threshold adaptive region sampling RRT algorithm for path planning. J King Saud Univ-Comput Inform Sci 35: 101753. https://doi.org/10.1016/j.jksuci.2023.101753 doi: 10.1016/j.jksuci.2023.101753
[15]	Gu Q, Zhen R, Liu J, Li C (2023) An improved RRT algorithm based on prior AIS information and DP compression for ship path planning. Ocean Eng 279: 114595. https://doi.org/10.1016/j.oceaneng.2023.114595 doi: 10.1016/j.oceaneng.2023.114595
[16]	Zhou Y, Zhang E, Guo H, Fang Y, Li H (2021) Lifting path planning of mobile cranes based on an improved RRT algorithm. Adv Eng Inform 50: 101376. https://doi.org/10.1016/j.aei.2021.101376 doi: 10.1016/j.aei.2021.101376
[17]	Karaman S, Emilio F (2011) Sampling-based algorithms for optimal motion planning. The international journal of robotics research 30: 846‒894. http://dx.doi.org/10.1177/0278364911406761 doi: 10.1177/0278364911406761
[18]	Gammell JD, Srinivasa SS, Barfoot TD (2014) Informed RRT: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In 2014 IEEE/RSJ international conference on intelligent robots and systems,* 2997‒3004. IEEE. https://doi.org/10.1109/IROS.2014.6942976
[19]	Islam F, Nasir J, Malik U, Ayaz Y, Hasan O (2012) Rrt-smart: Rapid convergence implementation of rrt towards optimal solution. In 2012 IEEE international conference on mechatronics and automation, 1651‒1656. IEEE.
[20]	Jeong IB, Lee SJ, Kim JH (2019) Quick-RRT: Triangular inequality-based implementation of RRT with improved initial solution and convergence rate. Expert Syst Appl 123: 82‒90. https://doi.org/10.1016/j.eswa.2019.01.032 doi: 10.1016/j.eswa.2019.01.032
[21]	Qureshi AH, Ayaz Y (2016) Potential functions based sampling heuristic for optimal path planning. Auton Robot 40: 1079‒1093. https://doi.org/10.1007/s10514-015-9518-0 doi: 10.1007/s10514-015-9518-0
[22]	Wang Z, Li P, Wang Z, Li Z (2024) APG-RRT: Sampling-based path planning method for small autonomous vehicle in closed scenarios. IEEE Access 12: 25731‒25739. https://doi.org/10.1109/ACCESS.2024.3359643 doi: 10.1109/ACCESS.2024.3359643
[23]	Liang YM, Zhao HY (2023) CCPF-RRT: An improved path planning algorithm with consideration of congestion. Expert Syst Appl* 228: 120403. https://doi.org/10.1016/j.eswa.2023.120403 doi: 10.1016/j.eswa.2023.120403
[24]	Yu S, Chen J, Liu G, Tong X, Sun Y (2023) SOF-RRT: An improved path planning algorithm using spatial offset sampling. Eng Appl Artif Intell* 126: 106875. https://doi.org/10.1016/j.engappai.2023.106875 doi: 10.1016/j.engappai.2023.106875
[25]	Yang F, Liu J, Li S, Hu X (2025) Minimum jerk motion planning for maritime autonomous surface ships based on Bézier curves. J Mar Eng Technol 24: 85‒97. https://doi.org/10.1080/20464177.2024.2434331 doi: 10.1080/20464177.2024.2434331
[26]	Reda M, Onsy A, Haikal AY, Ghanbari A (2025) A novel reinforcement learning-based multi-operator differential evolution with cubic spline for the path planning problem. Artif Intell Rev 58: 142. https://doi.org/10.1007/s10462-025-11129-6 doi: 10.1007/s10462-025-11129-6
[27]	Huo F, Zhu S, Dong H, Ren W (2024) A new approach to smooth path planning of Ackerman mobile robot based on improved ACO algorithm and B-spline curve. Robot Auton Syst 175: 104655. https://doi.org/10.1016/j.robot.2024.104655 doi: 10.1016/j.robot.2024.104655
[28]	Zhao F, Zhuang C, Wang L, Dong C (2024) An iterative greedy algorithm with Q-learning mechanism for the multiobjective distributed no-idle permutation flowshop scheduling. IEEE Transactions on Systems, Man, and Cybernetics: Systems 54: 3207‒3219. https://doi.org/10.1109/TSMC.2024.3358383 doi: 10.1109/TSMC.2024.3358383

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)