RRT*（あーるあーるてぃーえすたー）

RRT*とは

RRT* (Rapidly-exploring Random Tree*)は、ロボット工学やゲームAIなどの分野で広く利用されている経路計画アルゴリズムです。RRT (Rapidly-exploring Random Tree) を改良したもので、RRTの持つ探索空間の広範囲を効率的に探索する能力を維持しつつ、経路の最適性を向上させることを目的としています。

RRTとの違い

RRTは、ランダムに生成されたサンプル点に向かって木構造を拡張していくことで探索空間を探索します。しかし、RRTは必ずしも最適な経路を見つけるとは限りません。RRTは、RRTの探索過程において、既存の経路よりもコストの低い経路が見つかった場合に、その経路を再配線（rewiring）することで、経路の最適化を図ります。この再配線処理が、RRTが漸近的に最適解に収束する理由です。

アルゴリズムの概要

1. 初期化: 開始地点からなる初期の探索木を作成します。
2. サンプル点の生成: ランダムに探索空間内のサンプル点を生成します。
3. 最近傍点の探索: 探索木の中で、サンプル点に最も近い点（最近傍点）を探索します。
4. 探索木の拡張: 最近傍点からサンプル点に向かって、新しいノードを追加し、探索木を拡張します。
5. 再配線: 新しいノードの追加によって、既存の経路よりもコストの低い経路が見つかった場合、その経路を再配線します。
6. 繰り返し: 2〜5のステップを繰り返し、目標地点に到達する経路が見つかるまで探索を続けます。

利点と欠点

利点:

• 漸近的に最適解に収束する
• 高次元空間でも効率的に探索できる
• 複雑な形状の障害物にも対応できる

欠点:

• 計算コストが高い
• パラメータ調整が難しい
• 狭い通路などの特定の環境では、探索が困難になる場合がある

応用例

• ロボットの経路計画
• ゲームAIのキャラクター制御
• シミュレーションにおける経路探索