ASD-RRT*: An Enhanced Path Planning Algorithm Based on RRT* for Multi-Obstacle Environments

Chao Wang ; Wenbin Li

Computer Science and Information Systems, Tome 23 (2026) no. 1

Résumé

The efficiency of sampling-based motion planning brings wide application in autonomous vehicles. The conventional rapidly exploring random tree (RRT) algorithm and its variants have gained significant successes, but there are still challenges for the efficient motion planning in complex and multi-obstacles environments. Conventional sampling methods perform unconstrained sampling across the entire search space, often resulting in suboptimal paths. In this paper, we propose a novel algorithm, Adaptive Sampling and Densification RRT* (ASD-RRT*), for path planning in multi-obstacle environments. Our method extends RRT*-based sampling methods by incorporating adaptive sampling to enhance performance in complex environments. The adaptive sampling approach allows the algorithm to focus on effective regions, reducing sampling of irrelevant points and finding feasible solutions with fewer samples while maintaining the asymptotic optimality of RRT*. Further, we introduce a new optimization method for high-curvature paths and a routing strategy that satisfies vehicle dynamics constraints, aiming to improve path quality. The effectiveness and efficiency of the proposed ASD-RRT* are proved through comparative experiments in different environments. Experimental results demonstrates our method offers a reduction of 55.7% in planning times and 18.7% in path lengths over RRT* in a variety of environments.

Détail

Keywords: Motion planning, path planning, RRT*, adaptive sampling, dynamic smoothing