初始化參數對RRT 算法性能影響研究

馮 蕊，楊雪鋒，2

（1.重慶交通大學 航運與船舶工程學院，重慶 400074；2.交通安全應急信息技術國家工程實驗室，北京 100011）

0 引言

隨著移動機器人技術的發展，路徑規劃算法得到深入研究和廣泛應用［1-2］。遺傳算法、模擬退火算法等傳統路徑規劃算法需要對障礙物進行精確的數學建模，對于復雜環境中的規劃問題處理效果較差［3］，且多數算法未考慮移動機器人的非完整性約束限制［4］，使得規劃路徑不一定可執行。

針對復雜空間建模困難和非完整性約束考慮不足問題，1998 年LaValle 等［5］、唐華斌等［6］提出快速搜索隨機樹（Rapidly-exploring Random Tree，RRT）算法，該算法采用隨機采樣方法，不需要對狀態空間進行預處理和建模，而且在搜索過程中還考慮了機器人客觀存在的約束條件，如非完整性約束、動力學約束、運動學約束等，從而能有效解決復雜環境問題，得到越來越多研究人員的關注。

RRT 算法通過隨機采樣以逐步迭代的方式進行隨機樹構造，通過從根節點以步長λ不斷擴展出葉子節點的方式構建隨機樹［7］。由于采用隨機采樣的方式進行路徑規劃，RRT 算法中隨機樹的指向性較差，導致收斂速度較慢且規劃結果通常不是最優。針對此問題，2000 年Kuffner等［8］又對隨機樹生長策略進行改進，在生長過程中以一定的概率將目標點直接作為隨機采樣點（以下簡稱偏置概率Pg），這既能提升收斂速度，也能降低規劃路徑長度，大大提高了RRT 算法效率。可見，步長λ和偏置概率Pg這兩個初始化參數與RRT 算法性能密切相關，選擇合理的初始化參數能夠提升收斂速度，優化路徑規劃結果；反之則會增加算法耗時，使規劃結果變差。同時，針對不同復雜程度的規劃任務空間，初始化參數選擇也不盡相同。現有的RRT算法及其改進算法在設置生長步長和偏置概率時主要依據研究人員的經驗，缺乏相應依據。

為揭示初始化參數對RRT 算法性能的影響規律，并為初始化參數選取提供依據，本文通過計算機模擬不同復雜程度的路徑規劃任務空間，對規劃結果進行統計，分析初始化參數對RRT 算法性能的影響。

1 研究現狀

針對RRT 算法收斂速度慢和規劃結果不是最優的不足，相關學者提出了多種基于RRT 算法的改進算法，但關于RRT 算法初始化參數對RRT 算法性能影響的研究還較少。李猛［9］在對無人機任務規劃中的航跡規劃和任務分配問題進行研究時，通過研究不同障礙物環境下RRT 算法中步長對其算法性能的影響，提出利用混沌序列生成隨機節點，利用模糊推理系統動態調整算法參數的改進RRT 算法。這種改進RRT 算法通過查詢模糊推理表，針對不同的障礙物環境更新偏置概率Pg和步長λ這兩個參數來提高RRT 算法的性能，從而優化RRT 算法路徑規劃結果；路引等［10］針對RRT 算法的步長λ對RRT 算法影響進行探討，最后設計了基于RRT 算法的無人機航路在線規劃方法。該項研究通過理論分析說明了RRT 算法步長對其性能的影響；馮來春［11］針對路徑規劃算法的運動學約束和普適性兩方面問題，提出了基于引導域的參數化RRT 運動規劃算法。該算法在節點采樣時以一定的概率采用激進的采樣方式，加快隨機樹向外擴展速度；在節點擴展時以一定概率采用目標偏置擴展策略，加快隨機樹向目標位置擴展的速度，該項研究主要從RRT 算法的參數采樣概率Pg來優化RRT 算法性能。

目前專門針對RRT 算法參數的研究還較少，實際應用中一般通過經驗試湊來選取RRT 參數。因此，本文擬通過計算機模擬方法構造不同復雜程度的任務空間，研究初始化參數步長λ和偏置概率Pg對RRT 算法的耗時t、路徑長度L、規劃失敗概率Pf等5 個方面性能的影響，為RRT 算法在移動機器人技術領域更加廣泛的應用提供依據。

2 RRT 算法概述

采用RRT 算法進行路徑規劃主要步驟如下：

（1）將出發點作為隨機樹T根節點。

（2）產生一個0～1 之間的隨機數x，如果x小于偏置概率Pg則將目標點Cgoal作為隨機采樣點Crand；否則在狀態空間中隨機選擇一點作為Crand。

（3）尋找隨機樹T中與Crand最近的節點Cnear，并根據步長λ計算得到葉子節點Cnew。

（4）判斷Cnear與Cnew之間是否存在障礙物，若不存在障礙物則將Cnew作為T的子節點，添加邊［Cnear，Cnew］；否則，返回步驟（2）。

（5）當隨機樹中存在葉子節點與Cgoal之間的距離小于步長且無障礙物遮擋，便可在隨機樹中找到一條由節點組成的從出發點到目標點的路徑［12］，RRT 算法路徑規劃過程如下：

相對于其他算法，RRT 算法需要設置的參數較少。通過對RRT 算法分析可知路徑的起始點Cinit和目標點Cgoal是固定的，而采樣概率Pg和步長λ的取值將影響Crand、Cnear、Cnew，即影響規劃路徑的長度L和算法耗時t，也影響路徑規劃的失敗概率Pf，從而影響規劃路徑結果好壞和算法的實時性［13-14］。因此，針對不同的任務空間，本文設置不同的λ和Pg，RRT 算法參數與性能指標關系如圖1 所示。

Fig.1 Relationship structure between RRT algorithm parameters and performance indicators圖1 RRT 算法參數與性能指標關系結構

RRT 算法各個性能指標含義如下：①路徑長度L指沿著規劃結果從出發點到目標點連線的長度之和；②算法耗時t指計算機完成1 次路徑規劃所耗費的時間；③規劃失敗概率Pf指進行100 次路徑規劃至算法運行結束時仍未獲得規劃結果的次數。

3 仿真實驗

3.1 任務空間

為揭示初始化參數對RRT 算法性能的影響，本文借鑒文獻［15］的方法構建3 種不同復雜程度的任務空間，分別為簡單任務空間、一般任務空間和復雜任務空間，所有任務空間大小均為100×100 的無量綱二維區域，出發點位置為（0，0），目標點位置為（100，100）。3 種任務空間中障礙物個數分別為20、50 和100，且所有障礙物均為圓形區域。隨機從1、2、5 三個數值中隨機選擇一個作為半徑，圓的位置在任務空間內隨機產生。因此，不同任務空間中障礙物覆蓋區域半徑的均值相同，障礙物個數可以反映任務空間的復雜程度，3 種復雜程度不同的任務空間如圖2 所示。

3.2 步長λ 對算法性能的影響

采用RRT 算法對上述不同任務空間中的路徑規劃進行仿真實驗。仿真軟件平臺為MATLAB2016，在100×100的任務空間內對3 種不同復雜程度的任務空間分別設置步長λ為2～20，間隔為2，共進行10 組仿真實驗，每組分別進行100 次路徑規劃。仿真實驗中，偏置概率Pg設置為0.5。當程序連續產生500 個隨機采樣點均無法進行隨機樹擴展，或者在隨機樹擴展時生長點與障礙物碰撞次數累計達到100 000 次，則認為本次路徑規劃失敗。仿真實驗結束后取各性能指標的平均值作為結果進行統計分析，仿真實驗結果如圖3 所示。

在圖3（a）中，所有任務空間中耗時t均隨著步長λ增大而減小，可見增加步長有利于提高RRT 算法的實時性，而且任務空間復雜程度越高，進行路徑規劃耗時越長，實時性越差，任務空間的復雜程度對RRT 算法實時性存在顯著影響。

Fig.2 Task space with different complexity圖2 不同復雜度的任務空間

Fig.3 Changes of RRT algorithm performance with step size圖3 RRT 算法性能隨步長的變化情況

在圖3（b）中，隨著步長增加路徑長度也逐漸增加，這說明降低RRT 算法中的步長有利于獲取更優的路徑規劃結果（規劃路徑更短）。可以看出，仿真時間和路徑長度隨步長的變化規律剛好相反，步長既不能太大也不能太小，應綜合考慮其對耗時和規劃結果兩方面的影響。

從圖3（c）可以看出，即使對于簡單的任務空間RRT 算法也可能出現路徑規劃失敗的情況。并且隨著步長增加，路徑規劃失敗的概率也進一步增加。對于構建的3 種任務空間，當步長為20 時路徑規劃失敗概率超過80%。同時，隨著任務空間復雜程度的增加，路徑規劃失敗的概率也會增加。

總體上RRT 算法中步長λ對算法耗時、規劃結果（規劃路徑長度）、規劃失敗的概率均有直接影響。增加λ算法耗時會得到一定程度的降低，但路徑長度和規劃失敗的概率會有一定程度的增加，在工程應用中應根據實際需求綜合考慮步長對這3 方面性能的影響。

3.3 參數Pg對算法性能影響

在研究偏置概率Pg對算法性能影響仿真實驗過程中，仿真軟件平臺、任務空間、終止條件等試驗條件與前述內容一樣。

步長λ設置為5，偏置概率Pg大小為0.05～0.95，間隔為0.1，共計10 組仿真實驗，每組分別進行100 次路徑規劃，取各性能指標的平均值進行統計分析，仿真實驗結果如圖4所示。

從圖4（a）可以看出，在一般任務空間（N=50）和復雜任務空間（N=100）中算法耗時隨偏置概率Pg的變化規律幾乎相同，均是先減小再增大，這是因為當偏置概率較小時隨機樹生長的目標性不強，產生了過多的隨機采樣點；當偏置概率較大時，將目標點直接作為隨機采樣點的概率較大。若目標點與出發點之間存在障礙物阻擋，則隨機采樣失敗概率較高，導致耗時增加。對于簡單任務空間（N=20），較大的偏置概率不會引起算法耗時增加，如當Pg=0.95時，耗時t=0.11s，僅比最低耗時0.1s 多0.01s。這是因為在簡單任務空間中，出發點和目標點之間的連線上障礙物較少，將目標點作為隨機采樣點是合理的，有利于提高路徑規劃效率。

Fig.4 Changes of different performances of RRT algorithm with parameter Pg圖4 RRT 算法的不同性能隨參數Pg的變化

在圖4（b）中，3 種復雜程度的任務空間中路徑長度L隨偏置概率的變化趨勢完全一致，均隨著Pg的增大后路徑長度逐漸減小，規劃結果更優。這是因為隨著Pg增大路徑主要朝著目標點進行生長，朝其他方向生長的概率降低，因而路徑的轉向點個數減少。

在圖4（c）中，隨著偏置概率增大，路徑規劃失敗的概率也逐漸增大，因此偏置概率不能設置得太大。尤其是對于復雜的任務空間，較高的偏置概率將導致路徑規劃失敗，如圖4（c）中Pg>0.75 時始終難以獲得路徑規劃結果。

總的來講，偏置概率越大，隨機樹生長的目的性越強，算法消耗時間越短，規劃結果中路徑長度越短。但是，如果偏置概率過大，則隨機樹朝其他方向生長的可能性很小，如果任務空間的障礙物較多就可能導致路徑規劃失敗。綜合考慮算法耗時、路徑長度和規劃失敗率，將偏置概率設置為0.5 比較合理。

3.4 實驗結果分析

根據RRT 算法路徑規劃試驗統計結果可知，隨著步長增大，路徑規劃耗時將減小，但規劃的路徑長度和規劃失敗的概率將提升；隨著偏置概率增大，路徑規劃耗時呈現出先減小再增大的趨勢，規劃路徑長度減小但路徑規劃失敗的概率增大。初始化參數對算法性能影響情況如表1 所示。

Table 1 Influence of initialized parameters of RRT on algorithm performance表1 RRT 算法初始化參數對算法性能的影響

4 結語

為了揭示初始化參數對RRT 算法性能的影響規律并為參數選取提供依據，本文通過計算機模擬不同復雜程度任務空間中的路徑規劃問題，構建3 種不同復雜程度的任務空間。對仿真實驗結果分析得出以下結論：

（1）初始化參數步長和偏置概率對算法的性能存在顯著影響，應根據實際需求和任務空間的復雜程度兩方面確定初始化參數。

（2）算法耗時和路徑長度這兩個性能指標隨步長的變化規律剛好相反，其中一個性能指標變好，則意味著另一個性能指標變差。因此，設置步長時應綜合考慮這兩方面需求。

（3）偏置概率的設置應考慮任務空間的復雜程度，對復雜度較高（障礙物個數較多）的任務應設置較小（障礙物個數較少）的任務空間；若任務空間復雜度較低，則可設置較大的偏置概率。