融合神經網絡GRU和RRT*算法的機械臂路徑規劃*

周 哲,歐陽勇

(湖北工業大學計算機學院,武漢 430064)

0 引言

隨著工業時代的快速發展,機器人在各行各業都得到廣泛應用,包括工業制造、醫療、運輸等[1-2],如何在不觸碰障礙物的條件下完成軌跡規劃任務是研究的重點。

理想的軌跡規劃算法通常具有以下特性:完備性、最優性以及算法效率。目前機械臂軌跡規劃算法通?？梢苑譃榛趫D搜索的規劃算法和基于隨機采樣的規劃算法[3]?；趫D搜索的規劃算法有深度優先搜索[4]、廣度優先搜索[5]、Dijkstra算法[6]和A*算法[7]等。這類基于圖搜索的算法適用于低維空間,具有較好的完備性,但是在高維空間算法效率大大降低。

為了解決維度問題,專家學者們提出了基于采樣的規劃算法,這類算法通過在構型空間(C-space)中隨機采樣構建無碰撞路徑圖,主要算法包括概率路圖算法(PRM)[8]和快速隨機搜索樹算法(RRT)[9],以及RRT算法的衍生,RRT-Connect、RRT*[10]等。這類基于采樣的算法都具備完備性和快速性,但仍有如下缺點:①生成的軌跡主要由折線組成,因此平滑性較差;②由于是隨機采樣,所以每次采樣點較多,造成資源的浪費。

為了解決上述問題,提出了融合神經網絡GRU和RRT*的路徑規劃算法。GRU為了解決其他神經網絡算法存在的梯度下降和梯度爆炸的問題[11],通過重置門和更新門決定哪些信息將最后被門控循環單元輸出,并且能夠長期的保存長期序列中的信息。利用該采樣器,GRU-RRT*算法有效的避免了搜索的隨機性,引導RRT*向著終點延伸,減少規劃次數,增強算法探索能力,提高了算法搜索樹的探索效率,減少規劃的時間。

1 改進RRT*算法

1.1 RRT*算法

RRT*算法是一種基于隨機采樣的規劃算法,傳統的RRT*算法在RRT算法的基礎上增加一個重連的操作,以初始點在配置空間中構建隨機采樣樹擴展,滿足RRT算法快速搜索的同時,達到漸進最優的目的。

RRT*算法流程圖如圖1所示,從初始點qinit出發,構建初始隨機搜索樹Tinit,利用GRU-Sampler進行采樣,選擇無碰撞的節點qrandom,選擇搜索樹中距離qrandom最近的節點qnear,從qnear向qrandom方向延伸一條步長step的路徑,生成最新的節點qnew,同時判斷新生成的節點路徑是否有碰撞,如果有碰撞,再找下一個采樣點,否則,將最新的節點qnew加入隨機搜索樹T中,qnear為其父節點,重復以上過程,直到隨機搜索樹搜索到目標點qgoal為止。在搜索樹插入新節點的過程中,RRT*算法會進行一個重選父節點的操作,在找到qnew節點后,在范圍內重新選擇父節點,如果該父節點代價更小,則以該點作為父節點進行延伸;重選父節點之后,以qnew作為父節點遍歷范圍內的其他點,尋找代價最小的一條為搜索樹的路徑。

1.2 簡單采樣和GRU門控神經網絡集成

1.2.1 GRU門控神經網絡

GRU門控神經網絡是在LSTM神經網絡的基礎上進行的簡化,只留下重置門和更新門,減少了權重參數的個數,GRU門控單元結構如圖2所示。

圖2 GRU門控單元結構圖

圖中,Rt為重置門,Zt是更新門,Xt為輸入序列,Ht-1為上一個時間步的節點狀態,Ht為當前節點狀態,br,bh,bz為偏置項。更新門決定上一節點隱藏狀態的更新,將上一個時間步的Ht-1和輸入序列Xt投入到sigmoid激活函數中,選擇重要的信息進行保留;重置門對當前輸入隱藏狀態的記憶進行重置,忘掉上一個時間步不重要的信息。

Rt=σ(XtWxr+Ht-1Whr+br)

(1)

Zt=σ(XtWxz+Ht-1Whz+bz)

(2)

輸入參數通過重置門與上一個時間步的狀態的哈達瑪乘積得到候選隱藏狀態。

(3)

真正的隱藏狀態是更新門與上一個時間步的狀態和當前步的候選隱藏狀態哈達瑪乘積之和。Zt的值決定上一個時間步的狀態和候選隱藏狀態有多少能夠傳遞下去。

(4)

1.2.2 GRU采樣器

GRU-RRT*算法于RRT*算法的主要區別在于采樣方式的不同,RRT*算法在給定范圍內進行隨機采樣,時間代價大,收斂速度降低,而GRU-RRT*算法采用了一種新的方法生成節點,將GRU應用于基于采樣的規劃器。

GRU采樣器是簡單采樣方法和GRU網絡的集成,這種集成使采樣器能夠從早期的搜索經驗中學習,以生成預測節點,并引導通向目標狀態的路徑,同時更有效的避免障礙。GRU采樣器通過消除不滿足期望的節點來提高路徑規劃過程的效率,如圖3和圖4所示。

圖3 隨機采樣 圖4 GRU采樣

GRU的構圖如圖5所示,將預處理數據(初始點,目標點,障礙物)傳入GRU采樣器中,GRU采樣器包括輸入層和輸出層, GRU神經網絡隱藏層和dropout層,dropout層從GRU神經網絡中獲取輸出并將其轉化為GRU隱藏層期望的格式,最后通過線性輸出層將采樣點傳出到RRT*算法當中,引導算法對生成節點的預測。

圖5 GRU-RRT*算法結構圖

(5)

表1 GRU-RRT*算法偽代碼

圖6 GRU-RRT*算法流程圖

1.3 自適應步長

標準RRT算法不會利用擴展時收集到的信息去動態調整步長,固定步長過大或過小都會影響算法收斂速度,最后在搜索樹接近目標點時,如果qnearest與qgoal的距離大于qgoal的搜索范圍γ,則容易在目標點處振蕩,增加規劃的時間和路徑長度,因此需要對擴展樹步長進行自適應操作。因此,使用文獻[12]的策略去自適應擴展步長提高算法擴展效率。

(6)

式中:s為初始步長,l為qnearest與qgoal的距離。

1.4 三次樣條軌跡平滑

在多項式樣條中,三次樣條是保證加速度和速度的延續以及有限抖動的最低階多項式軌跡。高階多項式會導致更平滑的輪廓,但有更長的運動時間。運用關節空間軌跡規劃方法中的三次樣條插值函數方法,可以得到位置與時間的函數,及其一階導數和二階導數,一階導數和二階導數連續即速度與加速度連續。

分段式三次樣條函數的通式如下:

s(t)={qk(t),t∈[tk,tk+1],k=0,1,2,…,n-1}

(7)

qk(t)=ak0+ak1(t-tk)+ak2(t-tk)2+ak3(t-tk)3

(8)

上式將整條線段分隔出n條線段,構造出n條三次多項式,ak0,ak1,ak2,ak3均為表達式待定系數,每條多項式有4個未知數,因此總共需要確認4n個未知數。每條三次函數必須滿足以下條件:

①區間分隔點xi(xi∈(x0,xn))處的位置,速度和加速度連續;

②初始位置和終點位置的速度為0;

(9)

4n個表達式可以求解出4n個未知系數,利用上述等式,可以得到以下結果:

(10)

(11)

式中:Tk=tk+1-tk,Qk=qk+1-qk。知道每段三次樣條曲線所需時間T,即可利用追趕法可以求出中間的速度值,從而得到分段式三次樣條插值平滑曲線。

2 實驗仿真

為了驗證GRU-RRT*算法的有效性,從二維平面和三維空間兩個角度分別對RRT,RRT*和GRU-RRT*算法進行驗證,通過不同的算法在路徑長度,規劃時間等方面進行算法驗證。

GRU采樣器參數設置如下,GRU神經層設置80個神經元,利用Adam優化器調整學習率,將學習率設置為0.000 1,中間dropout層選擇0.5的丟失率來最小化損失值,激活函數為tanh。

2.1 二維地圖仿真

二維地圖的環境場景大小設置為500×500,初始坐標點qinit為(1,1),目標點qgoal為(19,19),隨機在地圖中擺放障礙物,GRU-RRT*設置起始步長為1,目標點區域半徑設置為0.35。4種算法在二維平面下的規劃如圖7～圖10所示。

圖9 RRT*二維規劃圖 圖10 GRU-RRT*二維規劃圖

圖7 PRM二維規劃圖圖8 RRT二維規劃圖

如表2所示,分別將PRM、RRT、RRT*和GRU-RRT*算法在二維地圖上做20次實驗取平均值,平均路徑長度為31.192 3,耗時0.893 s,相比于PRM、RRT和RRT*,平均路徑長度縮短了11%、18%、6%,在時間損耗上分別降低了1.04 s、0.76 s、0.233 s。在二維柵格地圖中,改進算法無論在長度規劃還是在算法運行時間上,效率都高于原始算法。

表2 算法結果對比圖

2.2 三維地圖仿真

三維地圖的環境場景大小設置為100×100×100,初始坐標點qinit為(1,1,1),目標點qgoal為(99,99,99),隨機在地圖中擺放障礙物,GRU-RRT*設置起始步長為8,目標點區域半徑設置為3,4種算法在二維平面下的規劃如圖11～圖13所示。

圖11 RRT算法三維規劃圖 圖12 RRT*算法三維規劃圖

圖13 GRU-RRT*算法三維規劃圖

由表3可知,在經過20次實驗之后,改進算法平均耗時7.692 s,平均路徑長度為172.961 1,較改進之前快了2.293 s,長度也縮短了17.632 5。

表3 算法結果對比圖

利用睿爾曼機械臂模型在rviz上進行仿真,圖14為GRU-RRT*算法的仿真效果圖,灰色部分為設置5個障礙物a,b,c,d,e。在機械臂從起始點到目標點移動的過程中,GRU-RRT*算法很好的避開了所有的障礙物,同時運行軌跡也十分平滑。

圖14 睿爾曼機械臂軌跡規劃

3 結束語

針對機械臂的軌跡規劃,提出了融合神經網絡GRU的RRT*算法,解決了原始RRT*算法存在的收斂速度慢,路徑質量差的問題。

(1)提出將門控神經網絡算法GRU算法作為采樣器,替代RRT*算法中的隨機采樣來生成節點,預測擴展樹節點生成方向,同時將RRT*算法步長進行自適應,減少軌跡搜索的時間,提高了算法的收斂速度。

(2)利用分段三次樣條曲線對規劃的路徑進行平滑,最后得到一條滿足要求的平滑的曲線。

分別在二維、三維環境下使用不同地圖對該算法進行仿真測試,GRU-RRT算法在軌跡規劃和平滑上都有顯著的效果,驗證了該算法的可行性。