[發明專利]一種基于RRT算法改進的車輛規劃算法

有效

• 申請號: 202010104879.X
• 申請日: 2020-02-20
• 公開（公告）號: CN111207767B
• 公開（公告）日: 2023-06-16
• 發明（設計）人: 吳迪;鄭亞楠;王欣;胡順奇
• 申請（專利權）人: 大連理工大學
• 主分類號: G01C21/34
• 分類號: G01C21/34;G01C21/30;G06F16/29
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 李曉亮;潘迅

1.一種基于RRT算法改進的車輛規劃算法MT-RRT，其特征在于，步驟如下：

步驟一：已知障礙物的數量、分布情況、起始節點與目標節點，判斷起始節點到目標節點的距離是否小于步長和是否與障礙物發生碰撞：如果距離小于步長并且沒有與周圍障礙物發生碰撞，直接連接起始節點與目標節點，此時直接連接起始節點，與目標節點，尋路完成；否則調用計算引導根節點的方法得到一定數目的引導根節點，放入集合中；該方法具體步驟如下：

(1.1)輸入起始節點目標節點，地圖上障礙物的數量，分布情況；連接起始節點x_init與目標節點x_goal得到直線l，計算直線的斜率與截距；

(1.2)設置一個間斷值Δx₁，從x_init開始到x_goal以橫坐標每隔Δx₁的距離為單位，開始對直線l上的點進行碰撞檢測，碰撞的n個障礙物，分別求出其碰撞中心點(x_m1,x_m2,x_m3...x_mn)，每個碰撞中心分別做直線l的垂線(l₁,l₂,l₃...l_n)，在每一條垂線上設置間斷值Δx₂，以Δx₂為間隔進行碰撞檢測，得到第一個無碰撞的點，放進引導根節點的集合newRoot中；

步驟二：將起始節點x_init，目標節點x_goal，與new?Root中的引導根節點放入樹列表TreeList中，在while循環中，調用程序中生成多棵生長樹的方法來擴展TreeList中的每一棵樹，該方法需要輸入步長step，根節點列表TreeList，以及地圖有關信息，引導多棵樹的生長直到連接成為一棵樹；方法的具體步驟如下：

(2.1)計算TreeList中樹的個數m，利用for循環，從1到m遍歷TreeList中每一棵樹；

(2.2)在遍歷當前樹T_num時，分別遍歷m棵樹中除當前樹T_num以外的其他樹中的每一個節點，得到與當前樹最近的樹的序號T_{_near}以及樹T_{_near}中相距最近的節點的T_n；

(2.3)隨機生成一個隨機樣本點，設置一個閾值Bias，使新產生的節點朝向最近的樹具有目標偏向性的進行擴展，對新節點進行碰撞檢測，無碰撞則加入到樹中；

(2.4)判斷新節點與最近的樹的根節點并且進行碰撞檢測，如果距離小于步長，則合并兩棵樹；將最近的樹中的所有節點添加到當前樹中，并在樹的列表中刪除最近的樹，退出當前的for循環；

(2.5)在while循環中，計算樹的列表TreeList中樹的個數是否為1，如果是，則結束循環,根據樹中的節點進行尋路，找到一條從起始節點到目標節點的路徑；如果不為1，則繼續進行下一次迭代，返回步驟(2.1)。

2.根據權利要求1所述的一種基于RRT算法改進的車輛規劃算法MT-RRT，其特征在于，步驟(2.3)中，0閾值Bias1。