RRT* (RRT star) アルゴリズムの説明

サンプリングベースの経路探索メソッドで有名なものの一つがRRTです。RRTは経路は見つけてくれるが最適な経路を出力しない点を修正したものがRRT*です。オリジナルのRRTの説明については、Atsushiさんが素晴らしいページを作っているのでそちらを参照。RRT*の説明は日本語ではあまり見つからない（英語でもあまりなく論文を読むしかない）ので、簡単な解説です。

そもそもメリットとしては、RRT*は、最適値に収束することが保証されています（*は最適ってことみたい）。また、かなり複雑な状況でも発散せずパスを生成してくれます。しかし、最適値は無限回をしたらたどり着くよってだけで有限時間では無理。それでもいいので

さてアルゴリズムは、

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.5503&rep=rep1&type=pdf

1. Add sample

2. 最も近い点を見つけて、ある距離（自分で設定）の点を打つ

3. x_newが障害物の中に入っているか？

 4. 円の中に入っているX_near(近傍点のリスト)を作る（7）

5. x_newを点のリストVに追加(8)

6. 円内点と線を引き、線が障害物に接触していないかを見る+最もコストが小さい点を結ぶ。

（Connect along a minimum-cost path）

7. 新しい線を線のリスト（E）に追加

8. 円内の他とx_new に線を引き、自分の親（A)とx_newとコストを比較し、元のコストよりも小さかったら線を引き直す。

（Rewire the tree）