Rapidly-exploring random tree

• 別名: RRT
• カテゴリ: Planning & manipulation › Motion planning
• タグ: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

ランダムな状態のサンプリングと、木の最も近いノードをそこへ向けて伸ばすことを繰り返して開始状態から木を成長させ、広い空間を素早く探索するサンプリングベースの動作計画器。

定義

高速探索ランダム木（Rapidly-exploring random tree、RRT）は、開始状態から目標領域までの実行可能な経路を見つけるためのサンプリングベースのアルゴリズムである。1998 年に Steven LaValle が提案した。このアルゴリズムは開始点を根とする木を成長させる。各反復で、コンフィギュレーション空間または状態空間からランダムな状態をサンプリングし、木の中で最も近いノードを見つけ、そのノードからサンプルに向かって短い距離だけ伸ばす。伸ばした部分が衝突しなければ、新しい状態が木に追加される。木が目標領域に達すると探索が終わり、各ノードの親をたどって経路を読み出す。

重要な性質は Voronoi バイアスである。木の最前線にあるノードは最も大きな Voronoi 領域をもつので、ランダムなサンプルに最も近いノードになりやすく、木はすでに覆った領域を埋めるのではなく未探索の空間へと引っ張られる。このため RRT は、ロボットアームの関節空間のような高次元空間で効果的である。RRT は確率的完全性をもつ。解が存在すれば、サンプル数が増えるにつれて解を見つける確率は 1 に近づく。よくある改良には、サンプルの一部を目標で取るゴールバイアスと、開始点と目標の両方から木を成長させ、それらを貪欲につなごうとする RRT-Connect がある。

伸長ステップには、ある状態から別の状態に向かって動く方法さえあればよいので、RRT は、ロボットが状態空間内をまっすぐ動けないキノダイナミック計画（kinodynamic planning）も扱える。その場合、伸長ステップでは LaValle と Kuffner のキノダイナミック RRT のように、サンプリングまたは最適化した制御入力を加えてダイナミクスを前向きにシミュレーションするか、事前に計算した運動プリミティブをつなげる。このため、距離尺度と伸長ステップをダイナミクスに合わせて設計しなければならない車両、脚ロボット、接触の多いマニピュレーションに役立つ。RRT の経路は通常ぎざぎざで最適ではなく、いったん経路が見つかるとサンプルを増やしても改善されない。RRT\ は親を選ぶステップと、より安い経路があれば近くのノードをつなぎ直すリワイヤリングのステップを加えることで、サンプルあたりの計算量が増える代わりに漸近的最適性をもつ。実行可能な経路がすぐに必要な場合は、素の RRT や RRT-Connect に続けてショートカットと平滑化を行うのが今でもよくある選択である。

重要な理由

RRT は、自由度の多いロボットやダイナミクスをもつシステムで動作計画を実用的にし、今でも OMPL や MoveIt などのライブラリの既定のプランナーである。RRT* を含む後続の多くのプランナーがその構造の上に作られている。

主な用途

• 雑然とした作業空間でのロボットアームの動作計画
• 自動車、ドローン、脚ロボットのキノダイナミック計画
• 独自の距離尺度を用いた接触の多いマニピュレーションの計画
• 移動のための運動プリミティブのグラフ上での計画
• 未知環境の探索

実際の使われ方

棚から品物をピッキングする 7 軸ロボットアーム用に MoveIt を設定するチームが、OMPL の RRT-Connect を既定のプランナーとして使う。衝突判定にはロボットモデルと、深度カメラから構築したオクトツリーを使う。チームは計画時間の上限と伸長ステップ幅を棚の開口部のクリアランスに合わせて設定し、各経路をショートカットと時間パラメータ化で後処理して、アームが滑らかに動くようにする。狭い棚の区画の奥まで届く計画に苦労する場合は、ゴールバイアスを大きくするか、狭い通路でより良く振る舞うプランナーを試し、静的なセルで同じような問い合わせを繰り返す場合は、代わりに確率的ロードマップを検討する。

よくある誤解

• RRT は最短経路を見つける — RRT が見つけるのは実行可能な経路であり、良い経路品質には RRT* か後処理が必要である
• RRT は決められた時間内に経路を見つけることが保証されている — RRT は確率的完全性をもつので、サンプリングを続けるにつれて経路を見つける確率が 1 に近づくが、狭い通路では長い時間がかかることがある
• RRT が常に良い選択である — RRT は時間とともに経路を改善するが、最初の解までが遅い。速度が重要なときは、RRT-Connect と平滑化の組み合わせが好まれることが多い

知っておくべき人

• 動作計画のエンジニア
• MoveIt や OMPL を使うマニピュレーションと移動ロボットの開発者
• 自動運転車とドローンの計画エンジニア
• ロボティクスの学生

関連技術

• OMPL
• MoveIt
• RRT-Connect
• キノダイナミック RRT（Kinodynamic RRT）
• Informed RRT*
• 経路のショートカット（Path Shortcutting）

関連用語

• Configuration Space
• Motion Planning
• Obstacle Avoidance
• RRT*
• Probabilistic Roadmap
• Motion Primitive

関連プロジェクト

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

動画

• Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering