2.1 原理

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

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

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

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

注意：

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

2.2 偽碼

2.3 程序示例

2.4 收斂性分析

雙向RRT的收斂性分析可以應用RRT的收斂性分析

2.5 參考

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

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