RRT*

• 別名: RRT star, RRT-star, optimal RRT
• カテゴリ: Planning & manipulation › Motion planning
• タグ: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

Rapidly-exploring Random Tree プランナーの漸近最適版で、成長しながら木を再配線するため、返す経路が最小コストの経路に向かって改善し続ける。

定義

RRT\（「RRT スター」と読む）は、衝突のない経路を見つけ、十分なサンプルがあれば最適な経路へと収束していく、サンプリングベースの動作計画アルゴリズムである。2011 年に Sertac Karaman と Emilio Frazzoli によって、1998 年に Steven LaValle が提案した Rapidly-exploring Random Tree（RRT）アルゴリズムの拡張として提案された。

元の RRT は、コンフィギュレーション空間内のランダムな点をサンプリングし、木の中で最も近いノードを見つけ、その運動に衝突がなければサンプルに向かって短いステップだけ伸ばす、ということを繰り返して、スタートのコンフィギュレーションから木を成長させる。RRT は、ロボットアームの関節空間のような高次元空間でも実行可能な経路を素早く見つけるが、その経路は通常ぎざぎざで最短からは程遠く、サンプルを増やしても改善しない。

RRT* は二つの点を変える。新しいノードを追加するとき、近傍半径内のすべての木のノードを調べ、単に最も近いノードではなく、スタートからのコストが最も低くなるノードに接続する。次に再配線（rewire）を行う。各近傍ノードについて、新しいノードを経由したほうが安い経路になるなら、その近傍ノードの親を付け替える。Karaman と Frazzoli は、木の成長に応じて近傍半径を適切に縮めれば、サンプル数が無限大に近づくにつれて解のコストが最適値に収束することを示した。この性質は漸近最適性と呼ばれる。

その代償はサンプルあたりの追加の計算であり、RRT は最初の解を見つけるのが RRT より遅い。Informed RRT や BIT* などの派生手法は、サンプリングを絞り込んで収束を速める。

重要な理由

多くのロボットが必要とするのは、単なる経路ではなく、より短い、より滑らかな、あるいはエネルギーコストの低い、よい経路である。RRT* は、高次元のコンフィギュレーション空間にスケールするサンプリングベースのプランナーに、経路の品質へ至る理論的な裏付けのある道筋を与え、動作計画の研究とソフトウェアにおける標準的なベースラインとなっている。

主な用途

• 物が散乱した作業空間でのロボットアームの衝突のない動作計画
• 移動ロボットやドローンの大域的な経路計画
• グリッド探索が現実的でない高次元のコンフィギュレーション空間での計画
• 軌道最適化のための参照経路の生成

実際の使われ方

ロボティクスのチームは通常、RRT を自分で書くのではなく、計画ライブラリを通じて利用する。MoveIt がロボットアーム向けに使っている Open Motion Planning Library（OMPL）には、RRT、RRT-Connect、PRM と並んで、RRT とそのいくつかの派生手法が含まれている。よくあるやり方は、決まった時間予算で RRT を実行し、時間切れの時点で見つかった最良の経路を取り、ショートカットと平滑化を施してから時間パラメータ付きの軌道に変換するというものである。移動ロボットやドローンでは、2D または 3D の占有地図上で RRT を大域プランナーとしても使い、計画時間とステップ幅を選んで経路の品質と応答時間のバランスをとる。

よくある誤解

• RRT* は最適な経路を返す — 漸近最適であるにすぎず、経路のコストが最適値に近づくのはサンプル数が際限なく増えるときだけである
• RRT* の経路は滑らかである — 区分的に線形であり、通常は実行前にショートカットと平滑化が必要である
• RRT* は常に RRT より優れている — 実行可能な経路を素早く得るだけでよい場合は、素の RRT や RRT-Connect のほうがよい選択であることが多い

知っておくべき人

• 動作計画のエンジニア
• ロボットアームとマニピュレーションのソフトウェア開発者
• 自律ドローンや移動ロボットの開発者
• 計画アルゴリズムを学ぶロボティクスの学生

関連技術

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• 衝突チェック（Collision Checking）

関連用語

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

関連プロジェクト

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

動画

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB