隨著自動駕駛技術的蓬勃發展，安全、高效的路徑規劃成為核心挑戰之一。快速探索隨機樹（RRT）算法作為一種強大的路徑搜索策略，為自動駕駛汽車在復雜環境下繞過靜態障礙物規劃合理路徑提供了有效解決方案。

RRT 算法基于隨機采樣思想構建樹形結構。從初始狀態點出發，在車輛的狀態空間內反復隨機采樣，將新采樣點與已有樹中的節點依據距離、可達性等規則進行連接拓展，逐步生長形成一棵能夠覆蓋狀態空間大部分區域的樹，向著目標區域快速探索。

在構建樹的過程中，算法實時檢測采樣點與障礙物的碰撞情況。一旦發現新采樣點或連接路徑與靜態障礙物相交，立即舍棄該點或重新規劃連接方式，確保生成的路徑始終位于無碰撞空間內，巧妙地引導車輛繞過障礙物。

首先，確定自動駕駛汽車的初始位置作為樹的根節點，設定目標區域。接著，不斷重復隨機采樣、節點連接、碰撞檢測與規避操作，持續拓展樹結構。當樹的分支成功延伸至目標區域附近，通過回溯從目標點到起始點的連接節點，即可提取出一條從起點繞過障礙物抵達終點的可行路徑。

盡管存在挑戰，但 RRT 算法在自動駕駛路徑規劃領域已展現出巨大潛力。隨著算法改進、硬件算力提升，未來有望更精準、高效地處理各類復雜靜態障礙場景，助力自動駕駛汽車暢行無憂，推動智能交通邁向新高度。

?

% RRT algorithm in 2D with disc obstacle avoidance.
% Anand Patel
% 
% nodes:    contains its coordinates, cost to reach, and its parent.
%           
% 
% How it works: 
% 1. Pick a random node q_rand.
% 2. Find the closest node q_near from nodes list to branch out from
% towards q_rand.
% 3. Move from q_near towards q_rand: interpolate if node is too far away,
% reach q_new. Check for collisions.
% 4. Update cost of reaching q_new from q_near, Cmin. q_near
% acts as the parent node of q_new.
% 5. Add q_new to node list.
% 6. Continue until maximum number of samples is reached or goal region is
% entered.clearvars
close all% make S = [0 100] X [0 100]
x_max = 100;
y_max = 100;% readin obstacles
obstacle_array = csvread('H3_obstacles.txt');
% turn array into struct
for j=1:1:23
obstacle(j).coord = [obstacle_array(j,1) obstacle_array(j,2)];
obstacle(j).rad = obstacle_array(j,3);
end
nodes_id = 1;
EPS = 20;               % epsilon distance ASSIGNED
numNodes = 100000;        % max number of samples taken
del_t = 10;
delta = .5;q_start.coord = [40 40];      % start node's (x,y) coordinate ASSIGNED
q_start.cost = 0;           % cost to reach start node set to 0
q_start.parent = 0;         % parent of start node set to 0
q_start.id = nodes_id;
q_start.time = 0;           % start node begins at t=0
q_start.theta = pi/4;         % start node theta ASSIGNED
q_start.v = 0;              % start node trans vel = 0