基礎版本的RRT每次搜索都只有從初始狀態點開始生長，通過快速擴展隨機樹來搜索整個狀態空間。如果從初始狀態點和目標狀態點同時生長兩棵快速擴展隨機樹來搜索狀態空間，效率會更高。為此，基於雙向擴展平衡的連結型Bidirectional RRT算法被提出。
Bidirectional RRT算法偽代碼
Bidirectional RRT算法同時從起點和終點建立擴展樹，然後採樣隨機點進行擴展。在每一次迭代中，擴展完第一棵樹的新節點q(new)後，以這個新目標點作為第二棵樹的擴展方向，如果沒有碰撞，繼續往相同的方向擴展，直到擴展失敗或者′()=()。
在迭代的過程中也同時考慮了兩棵樹的平衡性，即選擇兩棵樹節點少的作為擴展的目標。
Bidirectional RRT的這些屬性使得它相對於原始的RRT算法，搜索效率有了大大提升；其次兩棵樹不斷向著對方交替擴展，這種帶有啟發性的擴展使得樹的擴展使得搜索區域可以逃離各自的約束區域，從而更快的實現算法收斂。代碼實現
代碼實現可以參照原始RRT的算法實現 ，二者的基礎邏輯相同。
分享到:
閱讀更多 半杯茶的小酒杯 的文章
