蜜桃av色欲a片精品一区,麻豆aⅴ精品无码一区二区,亚洲人成网站在线播放影院在线,亚洲 素人 字幕 在线 最新

  Rapidly Exploring Random Tree (RRT) and RRT*

發(fā)布日期：2022/9/3 23:59:06      瀏覽量：

什么是RRT算法？

根據(jù)RRT的提出者 Steve LaValle的描述， RRT是用來做motion planning。對于機(jī)器人，給定一個初始狀態(tài)qinitqinit，和一個活動區(qū)域CC，我們可以建立一個樹狀結(jié)構(gòu)GG來探索如何在CC中活動，并最終到達(dá)目的地。

它具有以下幾個屬性：

• single-query planning algorithm
• probabilistically complete

假設(shè)當(dāng)前共有個KK頂點(vertex)。那么RRT可以表示為以下流程

BUILD_RRT(qinit,K,Δqqinit,K,Δq)
1 G.init(qinit);
2 for k = 1 to K
3 qrand←qrand←RAND_CONF();
4 qnear←qnear←NEAREST_VERTEX(qrand,G);
5 qnew←qnew←NEW_CONF(qnear,Δq)(qnear,Δq);
6 G.add_vertex(qnew);
7 G.add_edge(qnear,qnew);
8 End
9 Return G

這里有幾個很有技巧的步驟：

• 第3步中隨機(jī)地選了一個新的狀態(tài),這個狀態(tài)很可能是無法到達(dá)的，比如隨機(jī)數(shù)選取到了墻壁中的一個點，所以需要一個算法來排除這些無法到達(dá)的點。
• 第4步中找了現(xiàn)有樹上離隨機(jī)點最近的點，所以需要定義在上的距離函數(shù)，用這個函數(shù)來決定哪個點最近。對于二維或三維的歐式空間距離函數(shù)可以用歐式空間距離表示，但是對于高維，尤其是configuration space，這個時候并沒有直觀的距離函數(shù)。
• 第5步中把沿著的方向移動了。同樣如何選取，以及如何定義“方向”，都有特殊的技巧。

大家使用RRT的原因，很多時候是因為機(jī)器人只能知曉自己周圍一定距離內(nèi)的信息，或者是機(jī)器人只能分段設(shè)計自己的行為，而無法一次直接找出到目的地的路線。所以機(jī)器人把整個問題分成了在短距離內(nèi)，一次只設(shè)計一小段路徑，最后把這些路徑連起來就得到了到達(dá)目的地的路徑。

RRT的應(yīng)用場合非常多，在無人車上，或者一個機(jī)械臂需要在有障礙物的環(huán)境中運(yùn)動時，RRT都是常用算法。

RRT有很多變形。比如可以想象如果空間CC的維度特別高，那么第三步中的隨機(jī)抽樣需要進(jìn)行非常多次才能覆蓋整個空間。所以有人考慮把高維空間投影到低維來取樣。另外RRT不保證找到的路徑是最優(yōu)的，所以Sertac Karaman提出了RRT*,可以保證趨近于最優(yōu)解。

參考：

• 作者：戴泓楷
  鏈接：https://www.zhihu.com/question/23635653/answer/32256410
  來源：知乎
• 推薦三個研究者的論文可以讀 Steve LaValle, James Kuffner和Sertac Karaman.
• 參考了Steve LaValle的頁面The Rapidly-Exploring Random Tree (RRT) Page

參考

• 《Principles of Robot Motion: Theory, Algorithms and Implementations》7.2.2 Rapidly-Exploring Random Trees