Research on a Bidirectional RRT* Algorithm Integrating Multi-Strategy Sampling and Nonlinear Adaptive Step Size for Ship Path Planning

Runkai Ren, Jianhui Cui, Tongjin Wei, Fei Liu, Yingjun Hu

Advances in Computer and Materials Scienc Research Vol. 5 / No. 1 / pp. 53-60 / January 5, 2026

DOI 10.70114/acmsr.2025.5.1.P53

Full Screen
PDF

Abstract

Addressing the issues of poor path quality, lengthy planning time, low efficiency, and excessively sharp turns in traditional RRT algorithms for ship path planning, this paper proposes a bidirectional Rapidly Expanding Random Tree (RRT) algorithm based on multi-strategy sampling and nonlinear adaptive stride. The algorithm replaces the single-tree expansion of traditional RRT with a dual-tree expansion and incorporates a nonlinear adaptive step size mechanism. This enables the algorithm to autonomously adjust step sizes based on the obstacle environment while mitigating the high randomness inherent in traditional RRT, resulting in more stable output. This paper employs a method that integrates multiple sampling strategies to address long planning time and planning efficiency. When sampling within the obstacle space, 10% of samples are taken directly at target points, 20% near target points, and 40% near the nearest tree node to the target. Through simulation verification on relevant experimental platforms, under identical environments, iteration counts, and consistent variables, the average of 10 experiments shows a 16.54% reduction in average planning time and a 19.69% reduction in average path length compared to the traditional RRT algorithm. Furthermore, considering the maneuverability constraints of actual ships, this paper introduces a minimum turning radius constraint and employs a chamfering method to handle sharp turning points. The improved algorithm achieves higher planning efficiency and superior path quality, and can be used as a reference for autonomous ship path planning.

Keywords

Unmanned ships / Bidirectional Rapidly Expanding Randomized Trees / Path planning / Adaptive stride.

2025 International Conference on Computer Science, Energy, Civil and Environmental Engineering

Full Text

Download PDF

More in This Issue

  1. 25 Hydrotalcite-Based Composite Photothermal Coupling Catalysts: Realizing Green and Efficient Synthesis of High-Value Hydrogen Peroxide pp. 25–31
  2. 32 Modeling of Protoplanetary Disks Based on Radmc-3D pp. 32–39
  3. 11 Late Pleistocene Paleoclimate Oscillations in the Northeast Tarim Basin: Insights from Multi-Proxy Lacustrine Sediment Analysis (72-51 ka B.P.) pp. 11–24
  4. 1 Research on Ship Path Planning Based on Improved Whale Optimization Algorithm pp. 1–10
Full Issue

Cite This Article