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

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.