ランダムツリーを素早く探索

高速探索ランダムツリー（RRT）は、空間充填ツリーをランダムに構築することで、非凸高次元空間を効率的に探索するように設計されたアルゴリズムです。ツリーは、探索空間からランダムに抽出されたサンプルから増分的に構築され、本質的に、問題の未探索の大きな領域に向かって成長する傾向があります。RRTは、Steven M. LaValleとJames J. Kuffner Jr. ^{[1] [2]}によって開発されました。 これらは、障害物や微分制約（非ホロノミックおよびキノダイナミック）のある問題を簡単に処理でき、自律ロボットの動作計画に広く使用されています。

RRTは、状態制約のある非線形システムの開ループ軌道を生成する技術として考えることができます。RRTは、配置空間内のグラフの最大ボロノイ領域に検索をバイアスするモンテカルロ法と見なすこともできます。いくつかのバリエーションは、確率的フラクタルと見なすこともできます。^[3]

RRT は、状態とアクションの制約を持つ高次元の非線形システムを制御するための近似制御ポリシーを計算するために使用できます。

RRT は、探索空間からのランダム サンプルを使用して、開始構成をルートとするツリーを成長させます。各サンプルが抽出されるたびに、そのサンプルとツリー内の最も近い状態との間の接続が試行されます。接続が実行可能である場合 (完全に自由空間を通過し、制約に従う場合)、新しい状態がツリーに追加されます。探索空間の均一なサンプリングでは、既存の状態が拡張される確率は、そのボロノイ領域のサイズに比例します。最大のボロノイ領域は探索の境界にある状態に属するため、ツリーは探索されていない大きな領域に向かって優先的に拡張されます。

ツリーと新しい状態の間の接続の長さは、成長係数によって制限されることがよくあります。ランダム サンプルがツリー内の最も近い状態からこの制限よりも離れている場合、ランダム サンプル自体の代わりに、ツリーからランダム サンプルまでの線に沿って最大距離にある新しい状態が使用されます。ランダム サンプルはツリーの成長方向を制御し、成長係数がその速度を決定すると見なすことができます。これにより、RRT の空間充填バイアスが維持され、増分成長のサイズが制限されます。

RRT の成長は、特定のエリアから状態をサンプリングする確率を上げることによって偏向させることができます。RRT の実際の実装のほとんどは、これを利用して、計画問題の目標に向けて検索を導きます。これは、状態サンプリング手順に目標をサンプリングする小さな確率を導入することで実現されます。この確率が高いほど、ツリーは目標に向かって貪欲に成長します。

一般的な構成空間 Cの場合、疑似コードでのアルゴリズムは次のようになります。

アルゴリズムBuildRRT
    入力: 初期構成q init 、RRT Kの頂点数、増分距離Δq
    出力: RRTグラフG

    G .init( q init )
     、 k = 1から Kまで、q rand ← RAND_CONF()
        を実行します。q near ← NEAREST_VERTEX( q rand、G )、
         q new ← NEW_CONF( q near、q rand、Δq )、
         G .add_vertex( q new )、
         G .add_edge( q near、q new )
     、Gを返します。  
         

上記のアルゴリズムでは、「RAND_CONF 」はC内のランダム構成q _randを取得します。これは、 C _free内のサンプルを使用し、何らかの衝突検出アルゴリズムを使用してC _obs内のサンプルを拒否する関数「RAND_FREE_CONF 」に置き換えることができます。

「NEAREST_VERTEX 」は、グラフG内のすべての頂点vを実行し、何らかの測定関数を使用してq _randとv間の距離を計算し、最も近い頂点を返す 関数です。

「NEW_CONF 」は、 q _nearからq _randの方向に増分距離Δqを移動して、新しい構成q _newを^{選択します。（ [4]}によれば、ホロノミック問題ではこれを省略し、 q _newの代わりにq _randを使用する必要があります。）

• RRT-Rope ^[5]は、決定論的な短縮アプローチを使用して高速で最適な経路計画を行う方法であり、オープンで大規模な環境で非常に効果的です。

• パーティゲーム指向RRT（PDRRT）^[6]は、 RRTとパーティゲーム法^{[7]を組み合わせて、必要な場所（例えば障害物の周り）で探索を絞り込み、RRTよりも速く計画し、より多くの}動作計画問題を解決できるようにする手法である。

• 閉ループ高速探索ランダム（CL-RRT）^[8]は、車両とコントローラで構成される安定した閉ループシステムへの入力をサンプリングするRRTの拡張です。

「軽度の技術的条件」では、RRT における最良パスのコストはほぼ確実に最適でない値に収束することが示されています。^[9]そのため、RRT* のように最適に収束する RRT のバリエーションを見つけることが望ましいです。以下は、RRT* ベースの方法のリストです (RRT* 自体から始まります)。ただし、派生した方法のすべてが最適に収束するわけではありません。

• 高速探索ランダムグラフ（RRG）とRRT* ^{[9] [10] [11]}最適解に向かって収束するRRTの変種

• LQR-RRT [ ^12]複雑な動力学や劣駆動力学のための運動力学の変種

• RRT ^{+ [13]}は、低次元の部分空間を段階的に探索することで、高次元システムのソリューションをリアルタイムで生成することを目的としたRRTベースのプランナーファミリーです。

• RRT*-Smart ^{[14]は、パス最適化（} Theta*と同様の方法）とインテリジェントサンプリング（パス最適化後に障害物に近い可能性が高いパス頂点にサンプリングを偏らせる）を使用してRRT*の収束速度を加速する方法である。

• A*-RRTとA*-RRT* ^[15]は、グラフ探索アルゴリズムを使用して、第1フェーズで低次元空間（完全な状態空間を考慮せずに）で初期の実行可能な経路を探索し、危険領域を回避して低リスクのルートを優先し、次に第2フェーズで連続した高次元空間でRRT*探索に焦点を当てる2フェーズの動作計画方法です。

• RRT*FN、^{[16] [17] [18]}固定数のノードを持つRRT*は、反復ごとにツリー内のリーフノードをランダムに削除します。

• RRT*-AR、^[19]サンプリングベースの代替ルート計画

• インフォームドRRT* ^{[20] [21]は、} A*がダイクストラのアルゴリズムを改良したのと同様に、ヒューリスティックを導入することでRRT*の収束速度を改善します。

• リアルタイムRRT*（RT-RRT*）^[22]は、 RRT*とインフォームドRRT*の変種であり、オンラインツリー再配線戦略を使用して、ツリールートが以前にサンプリングされたパスを破棄せずにエージェントとともに移動できるようにすることで、コンピュータゲームなどの動的環境でリアルタイムのパスプランニングを実現します。

• RRT ^XとRRT ^#、^{[23] [24]}動的環境におけるRRT*の最適化

• Theta*-RRT ^[25]は、 A*-RRT*に似た2段階の運動計画法であり、複雑な非ホロノミック制約のある環境での高速軌道生成のために、任意の角度探索とRRT運動計画の階層的組み合わせを使用する。

• RRT* FND、^{[26] [27]} RRT*の-dynamic環境への拡張
• RRT-GPU、^[28]ハードウェアアクセラレーションを利用した3次元RRT実装

• APF-RRT ^[29]は、 RRTプランナーと人工ポテンシャルフィールド法を組み合わせたもので、再計画タスクを簡素化する。

• CERRT ^[30]は、接触を利用して不確実性を低減するRRTプランナーモデルです。
• MVRRT*、^[31]最小違反RRT*、不安全レベル（交通法規などの環境ルールに違反した「コスト」）を最小限に抑える最短ルートを見つけるアルゴリズム

• RRT-Blossom、^[32]制約の厳しい環境向けのRRTプランナー。

• RRV ^[33]は、ツリーノードの周囲の支配的な固有ベクトルを使用して、障害物の周囲や狭い通路を通るツリーを効率的に拡張します。

• RBT ^[34]は、高価な衝突チェックの代わりにワークスペース内の単純な距離計算を使用してツリーを拡張します。

• TB-RRT、^[35] 2つの動的システムのランデブー計画のための時間ベースRRTアルゴリズム。

• RRdT* ^{[36] [37]}は、複数のローカルツリーを使用してローカルサンプリングを実行することで、空間の探索と利用のバランスを積極的に取るRRT*ベースのプランナーです。

• Tri-RRT-Connect、^{[38] [39]}三角不等式ベースの再配線法とRRT-Connectアルゴリズムを組み合わせて最適解に近づける。

• 適応情報ツリー（AIT*）と努力情報ツリー（EIT*）^[40]

• あらゆる角度の経路計画
• 確率的ロードマップ
• 空間を埋め尽くす木
• モーションプランニング
• ランダム化アルゴリズム

• ウィキメディア・コモンズの「ランダムツリーの高速探索」に関連するメディア
• マップ エディターを含む RRT および RRT* の Java ビジュアライザー
• Dubins の最小時間パスを使用した RRT の C++ 実装
• オープンモーションプランニングライブラリRRT*実装