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

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.