基于改進的RRT車輛路徑規劃

戶望力

基于改進的RRT車輛路徑規劃

戶望力

（長安大學 汽車學院，陜西 西安 710000）

文章針對基礎RRT算法的不足即搜索的盲目性與復雜條件下較差的適應性，對基礎RRT算法進行改進，通過對擴展節點的條件進行約束，使得車輛進行路徑規劃時更加具有方向性，能夠實現對物體的繞行，以快速地尋找出可行的路徑。最后通過MATLAB進行仿真，驗證了改進算法在簡單條件與復雜條件（狹小通道）下路徑規劃的有效性。

路徑規劃；RRT算法；智能駕駛

前言

近年來，隨著人們對機器學習與深度學習的深入研究，人工智能進入了快速的發展階段，再加上5G網絡的興起，深度機器學習更是如魚得水，已經滲透到了各種行業之中。對于汽車的研究，更是向著智能駕駛的方向發展。從研究的進展來看，對于智能駕駛的研究大多數企業均已進入了L3階段，甚至有些汽車企業已經進入L4階段的研究。而對于智能汽車的研究，其車輛路徑規劃是高級智能汽車的必經之路。目前，對于車輛路徑規劃具有很多的方法，常見的算法有：Astar、Dstar、RRT、Hybrid Astar等。對于不同的算法都有其優缺點。總體而言，無論哪種算法其最重要的問題就是算法的實時性與精確性這兩者的平衡。一般而言，兩者是呈現負相關的關系，即要想使算法具有較高的精度就必須犧牲相應的時間。好在隨著5G網絡及芯片的快速發展，研發人員研制出了針對不同的處理數據的CPU、GPU，使得對數據的處理能力得到了快速的提高。

車輛路徑規劃包含全局路徑規劃和局部路徑規劃，亦稱靜態規劃、動態規劃。是指車輛在運行的環境中，按照一定的規則，從目標位置尋找一條可行路徑達到目標位置且不與靜態或動態的障礙物發生碰撞[1]。對于靜態的路徑規劃相對簡單，車輛通過傳感器設備或者智能網聯獲取車輛周圍的環境信息，然后通過地圖搜索，尋找出可行路徑。而動態路徑規劃由于周圍環境是時刻變化的，需要實時更新獲取周圍環境信息，對于算法的實時性要求較高。

RRT（Rapidly-Exploring Random Tree）快速擴展隨機樹是一種基于采樣的規劃算法，由Steven.M.LaValle提出。其優點是不必對周圍環境進行建模，而是具有方向性的向目標點進行采樣檢測，從而繞過障礙物達到目標點，系統的復雜性小，所以該方法適合解決高維度空間和復雜約束的機器人路徑規劃問題[2]。但是該算法也具有一定的缺陷：（1）由于采樣的盲目性，所以搜索的效率低；（2）尋求的路徑一般不是最優路徑。（3）對于一些復雜的環境（狹窄的通道），RRT算法很難尋找出路徑[3]。

圖1 RRT的發展歷程

經過幾十年的發展，RRT的缺點得到了很大的改善。圖1為RRT算法的發展歷程，針對其不同的缺點，RRT發展出了不同的變體，其中RRT-connect/B-RRT通過采用兩顆快速擴展隨機樹（從起始點與目標點同時開始）搜索空間，每次選取支點較少的隨機樹進行擴展，直至兩顆隨機樹相連完成搜索，使得搜索的性能有了顯著的提高；RRT*算法主要針對的是路徑優化問題，它能快速地找出初始路徑，隨著采樣點的增加，不斷地進行優化直到程序終止，所以RRT*的缺點就是對運算時間要求較高。B-RRT*相對于B-RRT的區別在于前者能夠在擴展采樣節點的同時能夠對父節點進行重選，通過對比將最短路徑的節點作為待選父節點，從而實現了對搜索路徑的優化。

本文通過對RRT算法進行改進，根據障礙物的位置對擴展節點進行有目的的采樣，實現對障礙物的繞行，已實現對路徑的快速規劃，且在某些復雜的環境下（狹小通道），改進的RRT依舊具有較為明顯的優勢。最后通過MATLAB仿真分析，來驗證該算法的有效性。

1 RRT算法介紹

1.1 RRT算法基本原理

RRT算法基本原理如圖2所示：以起始點qinit作為樹的根節點，然后在自由空間中以設定的概率prand隨機選取采樣點qrand，或者以概率pgoal選取目標點qgoal作為采樣點，選取距離采樣點qrand最近的父節點qnear作為隨機樹的擴展對象，然后按照設定的步長ρ在qnear至qrand方向產生下一個待選父節點qnew，判斷候選節點qnew是否滿足條件（是否在障礙物內，是否超出規劃區域等），若滿足條件，將節點qnew加入到父節點之中，按照此方式繼續擴展隨機樹直至達到目標點qgoal，或者達到最大迭代次數[4]。

圖2 RRT算法路徑規劃過程

1.2 改進的RRT算法

有別于基礎的RRT算法，本文在此基礎上，對RRT算法父節點進行有目的的選取。其目的在于實現障礙物的繞行，然后直接到達目標點位置。其思想是根據人的尋路邏輯進行設計，如圖3所示，行人在目的地已知的條件下，要想達到目的地，必須要繞過河流，即目的地方向內的障礙物，然后才能達到目的地，而對目的地方向以外的障礙物不會給予考慮。根據此原理，本文對RRT算法進行改進，設計了主動繞行路徑上障礙物的方法，從而能夠快速達到目的地。該方法能夠減少基礎RRT算法的盲目性，并且對一些特殊的環境也具有很好的適用性，圖4為改進的RRT算法的工作流程圖。

圖3 行人尋路圖

圖4 改進的RRT工作流程圖

1.3 障礙物繞行決策方法

隨機樹在沿著目標點的方向前進時，如果檢測到前方具有障礙物，樹的節點會根據障礙物的形狀進行自動繞行，其方法采用試探法，在探索方向上分別向左和右側偏離一個角的δ，若仍然具有障礙物，則繼續偏離角度δ，直到產生新的節點qnew1與qnew2。為了增加搜索的速度，本文根據節點下降的梯度對qnear進行有目的的選取。其執行的示意圖如圖5所示。綠點qinit為數根節點，黃色點q2為樹的分叉點，qgoal為目標點。

圖5 障礙物繞行原理圖

2 MATLAB算法仿真驗證

2.1 運行環境

表1 仿真環境

2.2 仿真結果分析

為了驗證提出的改進的RRT算法的有效性，運用MATLAB分別對基礎的RRT算法和改進的RRT算法進行仿真。圖6-9為兩種算法的一種仿真結果。在30次的仿真結果中，基礎RRT算法的平均仿真時長為8.34秒，改進的RRT算法平均仿真時長為3.77秒。從仿真結果可以看出，改進的RRT算法減少了對目標的盲目探索，對簡單環境下的路徑規劃具有很好的適用性。

圖6 基礎RRT仿真圖

圖7 基礎RRT仿真路徑

圖8 改進RRT仿真圖

圖9 改進RRT仿真路徑

為了驗證改進RRT在狹小通道的有效性，本文設置了如圖10-13所示的仿真環境，在30次的仿真結果中，基礎RRT算法失敗次數為3次，改進RRT算法的失敗次數為0。從仿真結果可以看出，在復雜的環境下（狹小通道），改進的RRT依舊具有較為明顯的優勢。

圖10 基礎RRT仿真圖

圖11 基礎RRT仿真路徑

圖12 改進RRT仿真圖

圖13 改進RRT仿真路徑

3 總結

本文通過對基礎RRT算法的改進，優化了基礎算法路徑搜索的隨機性，且在復雜環境下也具有較好的適用性，使得算法的性能得到了較大的提高。但是對于情況較為復雜的環境，如障礙物過多的條件下，使得搜索的路徑較長，所以對于接下來的研究，將會注重對搜索結果的優化之上。

[1] 黃淑彤.淺論車輛路徑規劃的算法[J].中國科技縱橫,2019,003 (000):32-34.

[2] 施楊洋,楊家富,布升強,朱林峰.基于RRT改進的智能車輛路徑規劃算法[J].計算技術與自動化,2019,38(04):81-86.

[3] 劉曉倩,張輝,王英健.基于改進RRT的路徑規劃算法[J].自動化技術與應用,2019(5):96-100.

[4] 劉恩海,高文斌,孔瑞平,等.改進的RRT路徑規劃算法[J].計算機工程與設計,2019,40(8):2253-2258.

Based on Improved RRT Vehicle Path Planning

Hu Wangli

( School of Automobile, Chang’ an University, Shaanxi Xi’an 710000 )

In this paper, aiming at the shortcomings of the basic RRT algorithm under complex conditions, the blindness of the search and poor adaptability, to improve the basic RRT algorithm, based on the extension node constraint conditions, the vehicle for path planning more directional, can achieve the object around, to quickly find out the feasible path.At last, MATLAB is used for simulation to verify the effectiveness of the improved algorithm under simple and complex conditions (narrow channels).

Path planning; RRT algorithm; Intelligent driving

10.16638/j.cnki.1671-7988.2021.06.014

U462

A

1671-7988(2021)06-45-03

U495

A

1671-7988(2021)06-45-03

戶望力，碩士研究生，就讀于長安大學汽車學院交通運輸工程專業，研究方向：載運工具運用工程。