AES-RRT* algorithm: A trajectory planning algorithm for autonomous vehicles in an emergency obstacle avoidance environment

Abstract

The Rapidly-exploring Random Tree (RRT*) and its variants are widely applied in various domains for solving trajectory planning problems in complex environments. However, in emergency obstacle avoidance scenarios, the trajectories generated by these algorithms often fail to satisfy the dynamic constraints of vehicles, rendering them untrackable by actual automobile systems. To address this limitation, this paper proposes an Adaptive Emergency Sampling-based RRT* (AES-RRT*) algorithm. The proposed algorithm employs a greedy strategy to define a dynamic and stable sampling region, concentrating computational resources on areas with higher probability of containing optimal solutions. By integrating a nonlinear two-degree-of-freedom vehicle model with phase plane analysis, it filters out sampling points that violate dynamic constraints, thereby reducing unnecessary path reconnection optimization for non-essential samples. Furthermore, the algorithm incorporates a variable step-size strategy based on obstacle density around new nodes and distance to the target point, enhancing convergence speed. Finally, Catmull-Rom splines are applied to optimize local paths, improving smoothness and continuity of the final trajectory. Experimental results across three scenarios of varying complexity demonstrate that the AES-RRT* algorithm outperforms RRT, RRT*, and Informed-RRT* in both performance and final planning outcomes. Notably, compared to Informed-RRT*, the proposed algorithm maintains probabilistic completeness and asymptotic optimality while achieving approximately 56.5% faster initial convergence speed, 51.1% faster final convergence speed, and a 74.4% reduction in curvature discontinuity according to path smoothness metrics.