2.1 原理

雙樹RRT是在原本RRT的基礎(chǔ)上多加了?顆隨機(jī)探索樹，各自從起點(diǎn)和終點(diǎn)向外探索拓展，直到兩棵樹相遇時(shí)規(guī)劃算法收斂。這種改進(jìn)過的探索策略可以??提?RRT的運(yùn)?效率。 雙樹RRT中存在兩顆隨機(jī)樹，我們將其命名為A和B，A以起點(diǎn)為根節(jié)點(diǎn)，B以終點(diǎn)為根節(jié)點(diǎn)。兩顆隨機(jī)樹的拓展方式和單樹RRT的別無二致，同樣都需要經(jīng)歷隨機(jī)采樣+步?限制+碰撞檢測(cè)這三個(gè)步驟，但是不同的地?在于雙樹RRT的隨機(jī)樹是交替生長(zhǎng)的，??說第?輪迭代中A樹向外??，第?輪便切換為B樹??，如此循環(huán)。 在每輪迭代中，隨機(jī)樹除了向外拓展之外，還會(huì)多出?個(gè)步驟，就是遍歷另一顆隨機(jī)樹中的所有節(jié)點(diǎn)，找出離NewNode最近的節(jié)點(diǎn)，用于判斷兩顆隨機(jī)樹是否相遇。 假設(shè)算法經(jīng)歷了N次迭代以后，已經(jīng)拓展出如下圖所示的兩顆隨機(jī)樹。并且在下?輪迭代中，輪到A樹進(jìn)?拓展，A樹在圖中?綠?線條表示，B樹?黃色線條表示。

當(dāng)進(jìn)?本輪迭代后，算法成功拓展出A樹的新節(jié)點(diǎn)NewNode_A，此時(shí)算法將遍歷B樹中的所有節(jié)點(diǎn)，找出B樹中離NewNode_A最近的節(jié)點(diǎn)ClosestNode_B。并判斷?者是否滿?步?限制以及是否可以通過步?檢測(cè)。如下圖所示，這種情況明顯?法通過碰撞檢測(cè)。那么A樹和B樹在這?輪迭代中?法相遇，需要接著下?輪迭代。

進(jìn)?下?輪迭代，這次便切換為B樹進(jìn)?拓展，假設(shè)算法拓展出的NewNode_B以及遍歷A樹后得到的ClosestNode_A如下圖所示，經(jīng)過判斷發(fā)現(xiàn)?者滿?步?限制并且通過了碰撞檢測(cè)，那么這時(shí)A樹和B樹就成功得相遇了，規(guī)劃算法收斂

當(dāng)算法收斂以后，只需在兩棵樹的相遇處分別沿著?節(jié)點(diǎn)回溯便可以找出從起點(diǎn)到終點(diǎn)的有效路徑。

注意：

雙向RRT和RRT的區(qū)別不僅僅是在于雙向生長(zhǎng)，雙向RRT比RRT更“貪心”，相比于RRT在生長(zhǎng)RRT樹的時(shí)候，是每產(chǎn)生一個(gè)隨機(jī)點(diǎn)，如果能通過碰撞檢測(cè)，就往該隨機(jī)點(diǎn)的方向生長(zhǎng)一次，然后該隨機(jī)點(diǎn)就被廢棄了，下一步想繼續(xù)生長(zhǎng)RRT樹的話，就只能繼續(xù)生成新的隨機(jī)點(diǎn)，每個(gè)隨機(jī)點(diǎn)最多利用一次。而雙向RRT在生長(zhǎng)RRT樹時(shí)，先先生成一個(gè)隨機(jī)點(diǎn)，然后，該樹往該隨機(jī)點(diǎn)的方向生長(zhǎng)，直到碰到障礙物或則生長(zhǎng)到該隨機(jī)點(diǎn)，這樣，一個(gè)隨機(jī)點(diǎn)就被多次利用，加快了速度。

2.2 偽碼

2.3 程序示例

2.4 收斂性分析

雙向RRT的收斂性分析可以應(yīng)用RRT的收斂性分析

2.5 參考

1、RRT-Connect: An Efficient Approach to Single-Query Path Planning

2、https://www.guyuehome.com/9405