Learning-Accelerated RRT* Search for Risk-Aware Path Planning

Safety is the most critical concern for urban flights of autonomous Unmanned Aerial Vehicles (UAVs). Accounting for risk is essential to ensure effective and safe navigation—a process known as risk-aware path planning. This problem can be formulated as a Constrained Shortest Path (CSP) problem, which aims to find the shortest feasible route while satisfying predefined safety constraints. However, CSP is an NP-hard problem and poses significant computational challenges. Traditional methods can yield accurate solutions but are often too slow for real-time or online applications. Rapidly-Exploring Random Tree* (RRT*) is an advanced path-planning algorithm that extends the original RRT to provide asymptotically optimal solutions. In this work, we propose an improved version of RRT* to make it can address the CSP problem efficiently. Additionally, we introduce two learning-based methods—a diffusion model and a reinforcement learning (RL) agent—to further accelerate the improved RRT* algorithm.