戶望力

基于改進的RRT車輛路徑規(guī)劃

戶望力

（長安大學(xué) 汽車學(xué)院，陜西 西安 710000）

文章針對基礎(chǔ)RRT算法的不足即搜索的盲目性與復(fù)雜條件下較差的適應(yīng)性，對基礎(chǔ)RRT算法進行改進，通過對擴展節(jié)點的條件進行約束，使得車輛進行路徑規(guī)劃時更加具有方向性，能夠?qū)崿F(xiàn)對物體的繞行，以快速地尋找出可行的路徑。最后通過MATLAB進行仿真，驗證了改進算法在簡單條件與復(fù)雜條件（狹小通道）下路徑規(guī)劃的有效性。

路徑規(guī)劃；RRT算法；智能駕駛

前言

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

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

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

圖1 RRT的發(fā)展歷程

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

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

1 RRT算法介紹

1.1 RRT算法基本原理

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

圖2 RRT算法路徑規(guī)劃過程

1.2 改進的RRT算法

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

圖3 行人尋路圖

圖4 改進的RRT工作流程圖

1.3 障礙物繞行決策方法

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

圖5 障礙物繞行原理圖

2 MATLAB算法仿真驗證

2.1 運行環(huán)境

表1 仿真環(huán)境

2.2 仿真結(jié)果分析

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

圖6 基礎(chǔ)RRT仿真圖

圖7 基礎(chǔ)RRT仿真路徑

圖8 改進RRT仿真圖

圖9 改進RRT仿真路徑

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

圖10 基礎(chǔ)RRT仿真圖

圖11 基礎(chǔ)RRT仿真路徑

圖12 改進RRT仿真圖

圖13 改進RRT仿真路徑

3 總結(jié)

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

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

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

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

[4] 劉恩海,高文斌,孔瑞平,等.改進的RRT路徑規(guī)劃算法[J].計算機工程與設(shè)計,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

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