Abstract
To address challenges in agent path planning within complex environments-particularly slow convergence speed, high path redundancy, and insufficient smoothness-this paper proposes KDB-RRT*, a novel algorithm built upon RRT.* This method integrates a bidirectional search strategy with a three-layer optimization framework: ① accelerated node retrieval via KD-tree indexing to reduce computational complexity; ② enhanced exploration efficiency through goal-biased dynamic circle sampling and a bidirectional gravitational field guidance model, coupled with adaptive step size adjustment using a Sigmoid function for directional expansion and obstacle avoidance; and ③ trajectory optimization employing DP algorithm pruning and cubic B-spline smoothing to generate curvature-continuous paths. Additionally, a multi-level collision detection framework integrating Separating Axis Theorem (SAT) pre-judgment, R-tree spatial indexing, and active obstacle avoidance strategies is incorporated, ensuring robust collision resistance. Extensive experiments in complex environments (Z-shaped map, loop-shaped map, and multi-obstacle settings) demonstrate KDB-RRT's superiority over state-of-the-art methods (Optimized RRT*, RRT*-Connect, and Informed-RRT*), reducing average planning time by up to 97.9%, shortening path length by 5.5-21.4%, and decreasing inflection points by 40-90.5%. Finally, the feasibility of the algorithm's practical application was further verified based on the ROS platform. The research results provide a new method for efficient path planning of intelligent agents in unstructured environments, and its three-layer optimization framework has important reference value for mobile robot navigation systems.