改進的RRT算法在路徑規劃中的應用

邵偉偉, 朱云國, 胡 超

(銅陵學院 電氣工程學院,安徽 銅陵 244061)

0 引言

隨著科技的快速發展,移動機器人在日常的應用越來越多,人們對機器人路徑規劃的研究也在逐漸深入,針對不同的應用環境,研究者提出了多種路徑規劃算法,如可視圖法[1]、A*算法[2]、Dijkstra算法[3]、PRM算法[4]、Voronoi 圖法[5]、遺傳算法[6]、柵格法[7]、RRT算法[8]等。其中RRT算法具有簡單、實時性強、適用于三維空間等特點,其在路徑規劃的應用中較多,但RRT算法生成隨機樹的節點具有隨機性,這就決定了RRT算法生成的路徑通常都不是最優路徑,為了提高RRT算法的性能,人們不斷地對RRT算法進行改進,以期得到較優的路徑。

文獻[9]提出通過改變生成節點的概率,生成偏向目標點的節點,即產生目標導向性的節點,從而使隨機樹朝著目標點生成,這樣使得隨機樹的擴展速度加快,但該方法對復雜的環境適應性不強,只適用于較為簡單的環境。文獻[10]提出雙向生成隨機樹的算法,即從起點和目標點同時產生隨機樹,該方法可以縮短隨機樹生成的時間,大大提升隨機樹生成的效率,但該方法仍只適用于簡單環境,對于復雜的環境,可能得不到規劃的路徑,或得到路徑所需要的時間較長。李磊等[11]提出采用貪婪策略的改進算法,讓隨機樹在生成的過程中朝著目標點的方向進行生長,從而得到最優的路徑。文獻[12]提出在隨機樹生成的過程中,通過改變機器人行走的步長和目標點對機器人的吸引力,從而快速地提高隨機樹的擴展。文獻[13] 提出了基于安全場的改進算法,雖然可以大幅減少隨機樹搜索的時間,但機器人規劃的路徑比原始算法要長。

1 RRT算法簡介

1998年La Valle[14]提出RRT(Rapid Random Tree)算法,他提出在機器人的工作空間中,以機器人的起點作為隨機樹的起點,將該點作為隨機樹的父節點,采用隨機函數生成隨機節點。通過函數選取上述隨機生成的節點中的一個節點作為父節點,將生成的父節點作為隨機樹的起點,并重復上述步驟生成多個節點,直至生成的節點靠近目標點。當生成的節點與目標點的距離在設定的區間內,則將該節點作為父節點,終止節點的生成,將生成的父節點與起點和目標點相連接,得到的隨機樹的路徑即為所要規劃的路徑。

RRT算法在生成路徑的過程中,因其具有簡單[15]、實時性強[16]、適用于三維空間[17]等優點,所以在日常的應用中較多。但因其產生的隨機節點具有隨機性,其生成的路徑也是隨機的,很難得到最優路徑[18]。針對上述情況,本文提出了引導隨機樹節點生成的概率,通過引入人工勢場的思想指引隨機樹節點朝目標點方向的生成,從而減少隨機樹產生的時間和隨機樹的長度。

2 改進的RRT算法

隨機樹節點的生成具有較強的隨機性,生成的節點可能在障礙物附近,為了保證機器人的效率,引導隨機樹節點生成的概率,并引入人工勢場法的思想到RRT算法中,篩選隨機樹生成的節點。

2.1 生成隨機樹節點概率的引導

圖1 隨機樹節點的生成圖

圖2 隨機樹節點的柵格圖

(1)若在25個柵格中不存在障礙物,則隨機樹隨機地在所有的柵格中生成節點。

(2)若障礙物占據n個柵格,則剩余(25-n)個柵格內無障礙物。將第1個空白柵格的中心分別與n個障礙物柵格邊沿求歐氏距離,取最小的歐氏距離為該空白柵格與障礙物的歐氏距離,并記為d1,同理分別求剩余空白柵格與n個障礙物柵格邊沿的歐氏距離,分別記為d2,d3,……,d25-n,每個空白柵格中生成節點的概率pi為

(1)

2.2 隨機樹節點的選取

以2.1節的方法引導隨機樹節點生成的概率,在隨機樹節點生成后,采用人工勢場的思想對生成的節點進行篩選,引導隨機樹的生成,避免對全局環境的精準建模,從而減小隨機樹的長度和規劃隨機樹的時間。

如圖2所示,針對柵格中生成的隨機節點,引入人工勢場的思想。由引力勢能

(2)

可以求出隨機節點和目標點的引力為

G=kp·‖xgoal-xnear‖,

(3)

其中,kp為引力系數,‖xgoal-xnear‖為目標點向量Xgoal和隨機節點向量Xrand的幾何距離的絕對值。由式(3)可以得到任意隨機節點的目標引力函數G(n)為

(4)

圖3 增加目標偏向性的隨機樹節點

通過上述操作生成隨機樹節點,直至生成的隨機樹節點與目標點的距離小于設定的閾值,隨機樹節點的生成停止。

2.3 平滑隨機樹路徑

如圖4所示,隨機樹生成節點的隨機性決定了生成的隨機樹節點具有一定的冗余性,因此需要對產生的節點進行平滑處理。從第2個節點起,依次與起始節點Xinit相連接,若節點Xi+1與起始節點Xinit的連線沒穿過障礙物,則將節點Xi刪除;若節點Xi+1與起始節點Xinit的連線穿過障礙物,則將節點Xi作為隨機樹節點,并將節點Xi作為起始節點,重復以上操作。通過上述操作可將冗余的隨機樹節點刪除。

圖4 平滑隨機樹路徑的操作

如圖5為改進RRT算法的流程圖。

圖5 改進RRT算法的流程圖

3 實驗

3.1 實驗平臺和實驗環境簡介

實驗平臺采用的是HCR開源機器人移動平臺作為機器人的硬件搭載平臺,機器人的主控器采用的是三星Exynos 4412 Soc開發板,機器人搭載有激光雷達、防撞傳感器等,它能獲取前方0°～180°的障礙物信息,并將障礙物識別出來。機器人如圖6所示。在室外隨機擺放一些箱子作為障礙物,以一臺機器人作為目標點,讓另一臺機器人進行實驗。

圖6 機器人的實物圖

3.2 隨機障礙物的路徑規劃

隨機擺放的障礙物如圖7所示,為防止機器人在行走的過程中存在碰撞現象,在路徑規劃時需要對障礙物進行適當的膨化處理(障礙物膨脹時需要考慮機器人的大小,即障礙物膨脹時把障礙物的尺寸加上機器人的尺寸后再適當放大,因此機器人在行走時可以看成質點,此時機器人從障礙物周圍經過時,只要不觸碰障礙物就不會發生碰撞)。機器人由起點出發,采用改進的RRT算法進行路徑規劃,機器人按改進后的算法生成節點和路徑,進行路徑規劃,并走完全程。在機器人采用改進的RRT算法走完全程后,再采用未改進的RRT算法做對比實驗,并記錄相關數據,采用Matlab軟件將其運動軌跡表現出來。圖8為其中一次實驗的路徑軌跡,其中實心圓為機器人。在該次實驗完成后,隨機地改變障礙物的位置,重復做20次實驗,實驗結果如表1。

表1 路徑長度實驗數據

圖7 隨機障礙物實驗圖

圖8 機器人的行走軌跡

表1記錄了滾動RRT路徑長度和改進算法路徑長度,為了得到較為直觀的改進算法和未改進算法的數據,根據上述實驗數據可以進一步得到表2。

表2 路徑長度分析表

由表2可知未改進的RRT算法,它的路徑平均長度為336.7 cm,比改進后的RRT算法的路徑平均長度多10.4 cm。未改進的RRT算法,它的路徑長度方差為340.54 cm,比改進后的RRT算法的路徑方差多10 cm。從這里可以看出改進后RRT算法的路徑相對較短,而且相對穩定一些。分析未改進算法和改進后的算法規劃的路徑最值,可以看出改進后RRT算法的路徑比較短。從上述的分析中可知改進后的RRT算法具有可行性。

4 結語

原始RRT算法隨機樹的生成具有隨機性,為了讓隨機樹的生成具有一定的目標導向性,本文提出了改進的算法。本文提出在隨機樹節點生成的過程中引入人工勢場法的思想,降低障礙物附近生成節點的概率,通過人工勢場法的思想篩選節點,從而縮短規劃的路徑。針對生成的隨機樹節點具有冗余性,本文提出將冗余的節點進行剔除的算法,通過該方法可以剔除多余的節點,減少了規劃的節點,從而使規劃的路徑變短。

改進后的RRT算法,具有規劃的路徑短、實時性強、實用性高等特點。雖然本文提出的改進算法比未改進的算法性能具有一定的提升,但隨機樹節點的生成仍具有一定的隨機性,針對該局限性,后續的研究應會朝著隨機樹節點生成的方向研究,盡量讓隨機樹節點的生成具有導向性,使其滿足路徑最短的要求。