Patch Exploration-Based Route Planning for Autonomous Vehicles

Route planning is a crucial component of autonomous driving, making it essential to develop efficient planning methods tailored to different scenarios. To address the limitations of the existing RRT∗ methods, we propose a Patch Exploration RRT∗ (PE-RRT∗). First, separating hyperplanes and half-spaces are utilized to construct patch for each node in the tree structure, allowing adaptation to the environmental density. Additionally, during the sampling process, the patches guide the expansion of the random tree, enabling rapid searches and efficient use of sampled points. Moreover, the patches are applied for route pruning, simplifying the route representation. Simulation results demonstrate that the proposed method achieves high search efficiency across various scenarios.