RRT*是一種基于采樣的最優(yōu)化路徑規(guī)劃方式,與RRT的區(qū)別是,RRT盡量使新節(jié)點以及其周圍的節(jié)點到起點的cost(可以是路徑或者時間等目標函數(shù))最短,而不是僅僅尋找離它近的節(jié)點,而且在找到路徑后不會停止,而是繼續(xù)進行采樣來優(yōu)化得到的路徑。
盡管RRT算法是一個相對高效率,同時可以較好的處理帶有非完整約束的路徑規(guī)劃問題的算法,并且在很多方面有很大的優(yōu)勢,但是RRT算法并不能保證所得出的可行路徑是相對優(yōu)化的。因此許多關(guān)于RRT算法的改進也致力于解決路徑優(yōu)化的問題,RRT*算法就是其中一個。RRT*算法的主要特征是能快速的找出初始路徑,之后隨著采樣點的增加,不斷地進行優(yōu)化直到找到目標點或者達到設(shè)定的最大循環(huán)次數(shù)。RRT*算法是漸進優(yōu)化的,也就是隨著迭代次數(shù)的增加,得出的路徑是越來越優(yōu)化的,而且永遠不可能在有限的時間中得出最優(yōu)的路徑。因此換句話說,要想得出相對滿意的優(yōu)化路徑,是需要一定的運算時間的。所以RRT*算法的收斂時間是一個比較突出的研究問題。但不可否認的是,RRT*算法計算出的路徑的代價相比RRT來說減小了不少。RRT*算法與RRT算法的區(qū)別主要在于兩個針對新節(jié)點 xnew 的重計算過程,分別為:
·重新為 xnew 選擇父節(jié)點的過程
·重布線隨機樹的過程
在新產(chǎn)生的節(jié)點 xnew 附近以定義的半徑范圍內(nèi)尋找“近鄰”,作為替換 xnew 父節(jié)點的備選。依次計算“近鄰”節(jié)點到起點的路徑代價加上 xnew 到每個“近鄰”的路徑代價,具體過程見上圖。
圖(a)中表現(xiàn)的是隨機樹擴展過程中的一個時刻,節(jié)點標號表示產(chǎn)生該節(jié)點的順序,0節(jié)點是初始節(jié)點,9節(jié)點是新產(chǎn)生的節(jié)點 xnew,6節(jié)點是產(chǎn)生9節(jié)點的 xnear,節(jié)點與節(jié)點之間連接的邊上數(shù)字代表兩個節(jié)點之間的歐氏距離(這里我們用歐氏距離來表示路徑代價)。
在重新找父節(jié)點的過程中,以9節(jié)點 xnew 為圓心,以事先規(guī)定好的半徑,找到在這個圓的范圍內(nèi) xnew 的近鄰,也就是4,5,8節(jié)點。
原來的路徑0 - 4 - 6 - 9代價為10 + 5 + 1 = 16,備選的三個節(jié)點與 xnew 組成的路徑0 - 1 - 5 - 9,0 - 4 - 9和0 - 1 - 5 - 8 - 9代價分別為3 + 5 + 3 = 11,10 + 4 = 14和3 + 5 + 1 + 3 = 12,因此如果5節(jié)點作為9節(jié)點的新父節(jié)點,則路徑代價相對是最小的,因此我們把9節(jié)點的父節(jié)點由原來的節(jié)點4變?yōu)楣?jié)點5,則重新生成的隨機樹如圖(b)所示。
在為xnew 重新選擇父節(jié)點之后,為進一步使得隨機樹節(jié)點間連接的代價盡量小,為隨機樹進行重新布線。過程示意如上圖重布線的過程也可以被表述成:如果近鄰節(jié)點的父節(jié)點改為 xnew 可以減小路徑代價,則進行更改。
如圖(c),9節(jié)點為新生成的節(jié)點 xnew ,近鄰節(jié)點分別為節(jié)點4 , 6 , 8 。它們父節(jié)點分別為節(jié)點0 , 4 , 5。路徑分別為0 - 4,0 - 4 - 6,0 - 1 - 5 - 8,代價分別為10,10 + 5 = 15 和3 + 5 + 1 = 9。
如果將4節(jié)點的父節(jié)點改為9節(jié)點 xnew ,則到達節(jié)點4的路徑變?yōu)? - 1 - 5 - 9 - 4,代價為3 + 5 + 3 + 4 = 15 大于原來的路徑代價10,因此不改變4節(jié)點的父節(jié)點。
同理,改變了8節(jié)點的父節(jié)點,路徑代價將由原來的9變?yōu)?4,也不改變8節(jié)點的父節(jié)點。如果改變6節(jié)點的父節(jié)點為 xnew 則路徑變?yōu)? - 1 - 5 - 9 - 6,代價為3 + 5 + 3 + 1 = 12小于原來的路徑代價15,因此將6的父節(jié)點改為節(jié)點9,生成的新隨機樹如圖(d)。
重布線過程的意義在于每當(dāng)生成了新的節(jié)點后,是否可以通過重新布線,使得某些節(jié)點的路徑代價減少。如果以整體的眼光看,并不是每一個重新布線的節(jié)點都會出現(xiàn)在最終生成的路徑中,但在生成隨機樹的過程中,每一次的重布線都盡可能的為最終路徑代價減小創(chuàng)造機會。
RRT*算法的核心在于上述的兩個過程:重新選擇父節(jié)點和重布線。這兩個過程相輔相成,重新選擇父節(jié)點使新生成的節(jié)點路徑代價盡可能小,重布線使得生成新節(jié)點后的隨機樹減少冗余通路,減小路徑代價。
1、Sampling-based Algorithms for Optimal Motion Planning
2、https://blog.csdn.net/weixin_43795921/article/details/88557317#t0
3、https://zhuanlan.zhihu.com/p/51087819