RRT-CONNECT

RRT-CONNECT Control GUI

You can move obstacles and add too.

Blue Point : Randomly sampled point
Orange Point : Tree Nodes
Red Point : Goal
Green Point : Start

It is very easy. Diff from RRT is Two Tree and Extend Phase.

1. Prepare two trees. one tree from START, one tree from GOAL
2. Choose less nodes tree
3. Add new node A like RRT
4. [Extend Phase] Get nearest node to added new node A from opposite tree
5. [Extend Phase] Add New Node and Edge between nearest node and node A with max-length for multiple times
6. [Extend Phase] If it collides with obstacle, start from 3. If it reach opposite nearest node finish.

非常に簡単に実現できます.通常のRRTと異なるのはスタートから伸びるツリーとゴールから伸びるツリーを持ち、Extendフェーズがあることです.
詳しくはここ

1. スタートから伸びるツリーとゴールから伸びるツリーを用意します.
2. 二つのツリーのうちノード数が少ない方を選択します.
3. RRTのように新しいノードを一つ追加します.
4. [Extend フェーズ] 反対のツリーで追加したノードに最も近いノードを選択します.
5. [Extend フェーズ] 複数回新しいノードと反対の最も近いノードの間に最大長さを上限にノードを追加していきます.
6. [Extend フェーズ] もし障害物に途中で当たれば3から行い、もし反対のノードに到達すれば終了です.