基于改進RRT算法的無人車路徑規劃研究

關鍵詞：RRT算法；目標偏置策略；障礙物膨脹策略；啟發式貪心思想；三次B樣條曲線

0 引言

近些年來，隨著科技的進步，汽車無人駕駛技術得到了迅速發展。新一代智能汽車研究已成為產業革命的重要方向[1]。無人駕駛汽車具有提高道路安全性、減少交通事故和擁堵、降低交通成本、提高出行舒適度、滿足特定出行需求、節能環保等優點，為人類出行帶來更加安全、高效、便捷和環保的體驗。因此，對無人駕駛汽車領域的研究變得越發重要，引起了眾多科研人員的廣泛關注。

路徑規劃是無人車智能駕駛技術中的關鍵技術之一。為了使無人車根據預定地圖到達指定目的地，需要在地圖上進行路徑規劃，并采用合適的路徑規劃算法。常見的全局路徑規劃算法包括Dijkstra算法[2]、A*算法[3]、蟻群算法[4]、RRT 算法[5] 等。其中，RRT（Rapidly-exploring Random Tree） 算法是一種基于樹結構的隨機采樣路徑規劃算法。它通過不斷隨機采樣狀態空間中的點，并將其連接到樹上已有節點的方式，逐步生成一棵覆蓋整個狀態空間的樹。RRT算法具有簡單易實現、適應性強等優點。然而，其缺點也較為明顯，對RRT算法的缺點，盡管國內外學者對其進行了多種改進，以提升其在不同場景下的表現，但仍存在一些共性問題。

文獻[5]采用雙向改進RRT算法并結合人工勢場法，解決了RRT算法在隨機性和計算量較大的問題，從而提高了算法的尋優精度和路徑規劃速度。文獻[6] 將目標導向策略引入RRT，以解決路徑規劃中隨機性較大、容易陷入停滯狀態的問題，通過增加目標點的采樣概率，加快了路徑規劃的收斂速度，提高了效率。文獻[7]將人工勢場法與RRT結合，利用環境信息引導隨機樹向目標點生長，避免陷入局部最優。盡管這一方法改善了路徑生成過程，但由于選用的地圖過于簡單，缺乏代表性，其效果在復雜環境中可能有限。文獻[8]將改進的RRT與動態窗口法相結合，以防止陷入局部最優并實現動態避障，并融合人工勢場法來調整擴展方向，提高了算法的搜索效率和路徑質量。然而，最終生成的路徑依然不夠平滑，不適合實際應用中的移動機器人行駛。文獻[9]提出通過計算從起點到終點的方向向量，并將其作為引導向量，使隨機樹的生長方向更加朝向目標點，減少了節點擴展的隨機性，提高了搜索效率。然而，隨機樹擴展時仍容易陷入障礙物包圍圈，導致路徑規劃失敗。

針對RRT算法搜索效率不高、生成路徑不平滑等缺點，本文提出了一種改進的RRT算法。具體優化過程如下：首先，加入目標偏置策略和障礙物膨脹策略，以減小RRT算法擴展的隨機性，在提升搜索效率的同時，保證規劃路徑的安全和穩定性。其次，引入貪心算法思想，剔除規劃路徑中的冗余節點，使生成的路徑更加簡短和高效。最后，使用三次B樣條曲線對生成的路徑進行平滑處理，使規劃出的路徑更有利于無人車的行駛。

1 傳統RRT 算法

RRT算法具有簡單、高效、無須預處理和適用于非線性約束等優點，因此被廣泛應用于無人駕駛領域。RRT算法的核心思想是通過在搜索空間中隨機采樣，逐步擴展樹結構，從而找到從起點Sinit到目標點Sgoal的路徑，其擴展方式如圖1所示。

算法的主要步驟包括：

（1） 初始化：創建一棵樹 T，樹的根節點為起點Sinit。

（2） 隨機采樣：在搜索空間中隨機生成一個點Srand。

（3） 找到最近節點：在樹 T 中找到離 Srand 最近的節點 Snear。

（4） 擴展新節點：從 Snear 沿著 Srand的方向，以固定步長 A生成新節點 Snew。

（5） 碰撞檢測：檢查從 Snear 到 Snew 的路徑是否與障礙物發生碰撞。如果沒有碰撞，則將 Snew 添加到樹T 中。

（6） 檢查是否到達目標：如果 Snew 到目標點的距離小于預設的閾值，則認為找到了路徑。

（7） 重復：重復上述步驟，直到找到路徑或者達到最大迭代次數。

2 改進RRT 路徑規劃算法

2.1 障礙物虛擬膨脹策略

傳統的RRT算法在規劃路徑時，路徑可能會緊貼障礙物的邊緣，這對于實際應用中的無人車來說并不理想。無人車具有一定的寬度，如果按照傳統RRT算法規劃出的路徑行駛，容易發生碰撞或剮蹭。為了更符合無人車的實際運動要求，我們需要改進RRT算法，使其在規劃路徑時能夠考慮無人車的寬度，從而提高車輛在行駛過程中的安全性。

為此，本文提出了一種障礙物虛擬膨脹策略。在進行延伸節點的碰撞檢測時，將延伸節點與障礙物的虛擬半徑進行比較。當延伸點與障礙物圓心之間的距離小于虛擬半徑時，則認為發生碰撞，剔除該延伸節點。圖2為障礙物虛擬膨脹示意圖，其中rt為真實半徑，rv為虛擬半徑。

2.2 目標偏置策略

傳統RRT算法的搜索效率低下，搜索時間過長。然而，目標偏置策略可以有效降低算法搜索的隨機性，減少對不必要空間的搜索，從而極大提高算法的搜索效率，節省大量搜索時間。因此，在RRT算法中融入目標偏置策略進行隨機采樣是一種有效的選擇。加入目標偏置策略后，隨機點的生成方式如式（1） 所示。

式中設定了兩個概率值Pg和Ptarget。其中，Pg為按照均勻概率分布隨機生成的概率值，范圍在0到1之間。Ptarget 為事先設定好的閾值，通常是一個較小的值。在每次迭代中，筆者隨機生成一個Pg，當Pg小于Ptarget時，選擇目標點Sgoal為采樣點；否則，則在整個地圖范圍內隨機生成一個采樣點。

2.3 結合啟發式貪心思想剔除冗余節點

在通過前面兩種策略對RRT算法進行改進之后，規劃出的路徑仍然存在許多冗余路徑。為此，本文結合啟發式貪心思想，對路徑中的冗余節點進行剔除，使生成的路徑更加簡短，從而有利于無人車高效行駛。冗余節點去除策略的具體步驟如下：

1） 將起點設置為起始索引，將路徑中的最后一個點設置為終點索引，并記錄檢測次數為節點數量減1。

2） 從終點向起點遍歷路徑中的每個節點。對于每個節點，檢查其與父節點之間的路徑是否與障礙物虛擬相交。如果相交，則將終點索引減1，并繼續向上檢測父節點；如果不相交，則將該節點添加到最優路徑中，并更新起始索引和檢測次數。

3） 一旦找到一條最優路徑段（即不與障礙物虛擬相交的路徑段），將其添加到最優路徑中。在找到最優路徑段之后，將該節點作為新的起始節點，從該節點向上重新檢測父節點的路徑段。

4） 當檢測次數為0 時，表示已經遍歷完所有節點，最優路徑生成完成。

在完成啟發式貪心思想優化后，最終得到的最優路徑將不再包含不必要的節點。冗余節點剔除策略的具體實現如圖3所示。

其中，虛線代表去除冗余節點后的優化路徑。

2.4 采用三次B 樣條曲線平滑路徑

在結合啟發式貪心思想去除冗余節點之后，生成的路徑雖然與原始RRT算法相比平滑了很多，但仍存在曲率不連續的問題，這會影響無人車行駛的流暢性和穩定性。為了提高無人車行駛的平順性，需要對得到的折線路徑進行平滑處理。B樣條曲線是一種廣泛應用于路徑平滑的方法，具有幾何不變性和凹凸性等優點。為使規劃路徑具有較好的連續性，使用B樣條曲線對路徑進行平滑處理。k階 B樣條曲線的方程式如式（2） 所示：

公式中：ei ，i=0，1，2，3…n 是B樣條曲線的控制頂點，也就是路徑中的節點；Li，k（z）是第i 個k 次B樣條基函數，由一個稱為節點向量的參數序列U={ p0 ，...，p } m所確定。根據這些節點向量的不同分布形式，可以將B樣條曲線劃分為均勻B樣條曲線、 準均勻 B 樣條曲線和非均勻 B 樣條曲線。其中，準均勻B樣條曲線保留了貝塞爾曲線在兩個端點處的性質，樣條曲線在端點處的切線為兩個端點的連線，更適合應用于折線路徑的光滑處理。基函數確定了B樣條曲線的連續性和相應的次數，其遞推公式為：

由遞推公式可以看出，高次的B樣條基函數是用低次的B樣條基函數的線性組合來表示的，所有的Li，k（z）均為兩個（k-1） 次B 樣條基函數Li，k-1（z）和Li+1，k-1（z）的線性組合。

綜合分析車輛的運動學模型和行駛環境，同時結合算法的運算復雜度，筆者選用三次準均勻B樣條曲線對路徑進行平滑處理，從而可以得到一條曲率連續的平滑路徑。擬合三次B樣條曲線段的示意圖如圖4 所示：

2.5 改進RRT 路徑規劃算法流程

將前文提到的幾種改進策略全部融入傳統RRT 算法之后，繪制出完整的改進RRT算法流程圖。本文改進RRT算法的流程圖如圖5所示。

3 實驗仿真驗證

為驗證改進RRT算法的有效性和適應性，本實驗在MATLAB R2023仿真平臺上進行。在二維環境下，每種算法分別進行50 次實驗，并取平均值將改進RRT算法與傳統RRT算法進行對比。起點設置為 [0，0]，終點為[10， 10]，步長ρ 為 0.5，閾值設置為 0.1，最大迭代次數設置為 5 000。傳統RRT算法及其改進算法在地圖中的路徑仿真結果如圖6至圖10所示。

從圖中可以看出，相較于傳統RRT算法，加入改進點1之后，規劃的路徑更遠離障礙物，提高了無人車行駛的安全性。同時，在加入改進點1和2之后，RRT 算法的探索空間明顯減少，從而提高了搜索效率。進一步地，加入改進點1、2和3后，路徑中的冗余節點顯著減少，路徑變得更加流暢。最終，筆者使用三次B 樣條曲線對路徑進行了平滑處理。

傳統RRT算法與本文最終改進算法的仿真結果如表1所示。從表1中可以明顯看出，在擴展節點數大幅減少的情況下，平均時間減少了78.1%，路徑長度減少了18.6%。

4 結束語

本文主要針對傳統RRT算法在路徑規劃過程中存在的收斂速度慢、搜索隨機性高、冗余節點過多以及路徑安全性較差等問題進行了優化處理。改進算法首先對障礙物采取虛擬膨脹，使得在隨機樹的生成過程中更加遠離障礙物，從而生成的路徑更加安全可靠。其次，采用目標偏置策略，減小搜索范圍，提高搜索效率。再次，結合啟發式貪心思想，對路徑上的冗余節點進行剔除，消除路徑中過大的轉彎角，減少路徑長度。最后，采用三次B樣條曲線對生成的路徑進行平滑處理，降低路徑曲率的突變性，增加車輛的平穩性。

通過在MATLAB進行仿真驗證，結果表明改進后的RRT算法具有較高的可行性和有效性，對無人車的路徑規劃具有一定的參考價值。未來，筆者將繼續深入研究全局路徑規劃，期望將該算法優化得更加完善，同時對局部路徑規劃算法進行優化。隨后，將優化后的局部路徑規劃算法與改進的RRT算法結合起來，通過一系列實驗驗證和分析，以進一步驗證這種融合算法在實際場景中進行路徑規劃的有效性。