初始化參數(shù)對RRT 算法性能影響研究

馮 蕊，楊雪鋒，2

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

0 引言

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

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

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

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

1 研究現(xiàn)狀

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

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

2 RRT 算法概述

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

（1）將出發(fā)點作為隨機樹T根節(jié)點。

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

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

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

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

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

Fig.1 Relationship structure between RRT algorithm parameters and performance indicators圖1 RRT 算法參數(shù)與性能指標關(guān)系結(jié)構(gòu)

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

3 仿真實驗

3.1 任務(wù)空間

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

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

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

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

Fig.2 Task space with different complexity圖2 不同復(fù)雜度的任務(wù)空間

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

在圖3（b）中，隨著步長增加路徑長度也逐漸增加，這說明降低RRT 算法中的步長有利于獲取更優(yōu)的路徑規(guī)劃結(jié)果（規(guī)劃路徑更短）?？梢钥闯?，仿真時間和路徑長度隨步長的變化規(guī)律剛好相反，步長既不能太大也不能太小，應(yīng)綜合考慮其對耗時和規(guī)劃結(jié)果兩方面的影響。

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

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

3.3 參數(shù)Pg對算法性能影響

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

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

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

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

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

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

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

3.4 實驗結(jié)果分析

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

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

4 結(jié)語

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

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

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

（3）偏置概率的設(shè)置應(yīng)考慮任務(wù)空間的復(fù)雜程度，對復(fù)雜度較高（障礙物個數(shù)較多）的任務(wù)應(yīng)設(shè)置較小（障礙物個數(shù)較少）的任務(wù)空間；若任務(wù)空間復(fù)雜度較低，則可設(shè)置較大的偏置概率。