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）

Ceres Solver のインストール (Windows8, Visual Studio 2013)

GoogleのCeresは非線形最適化(Non-linear Least square)として広く使われており、昨今、Visionの世界でBundle Adjustmentによく使われています。最近研究している、パスの最適化にも使えるかなってことで導入してみました。Ubuntuだともっと楽なのでしょうが、家と研究室の環境の問題から、Windowsで挑戦。
インストレーションの基本は下。
http://ceres-solver.org/building.html#windows

１． Eigen のインストール。
他のページを参照

２．Google glogのインストール
2-1. ダウンロード
以下のサイトから、glog-0.3.3.tar.gzをダウンロード。
https://code.google.com/archive/p/google-glog/downloads
アンド解凍。

2-1. コンパイル
- google-glog.slnでVisual studioを立ち上げる。
- Congifuration Manager でActive solution Platform をx64に変更する。
　<New...>押してType or select the new platformをx64に変える。
　また、今後のためにReleaseいしておく。
- [Build]->[Batch Build] ですべて選んでコンパイル
- しかし、エラーが。minがないとか言われる。そのため、そのエラーをクリックしたlogging.ccを立ち上げる。
インクルードならどこでもよいが、私の場合、64行目に
#include <algorithm>
を追加する。
無事エラーがなければ、コンパイル成功

３．gflagのインストール
3-1. ダウンロード
昔のバージョンが見つからないため、下記の場所から最新版をダウンロード（執筆時点2.1.2）
https://github.com/gflags/gflags

3-2. Cmake
slnがなくなっているのでcmakeでプロジェクトを作成。但し、ビルド用のフォルダの名前がbuildにすると、元からあるファイルとかぶりフォルダが作れない。そのため、もとからあるBUILDの名前を変えるか消す。

3-3. コンパイル
エラーがなければ。無事成功

４．ceres
4-1. ダウンロード
http://ceres-solver.org/
からlatest stable release をダウンロード。執筆時点１．１１．０．

4-2. プロジェクトの作成
フォルダ作成ceres-bin
cmake起動
Advancedにチェックを入れるとすべてのオプションが出る。
EIGEN_INCUDE_DIR (自分のパス)/eigen-3.2.4
GLOG_INCUDE_DIR (自分のパス)/glog-0.3.3\src\windows
GLOG_LIBRARY_DIR (自分のパス)/glog-0.3.3\Release\libglog.lib
Installation GuideにはGFLAGSに関してもパスを入れなければならないとありましたが、何故か私は必要ありませんでした。
GFLAGS_INCLUDE_DIR
GFLAGS_LIBRARY_DIR

Configure & Generate

4-3. コンパイル
ceres-binの中のCeres.slnでVisual Studioを起動
[BUILD]->[BATCH BUILD]
でALL_BUILDとINSTALLのところにチェックを付けて、ビルド開始。

参考：
http://buaiso.blogspot.com/2013/12/ceres-solver-on-windows.html
http://www.rm.is.ritsumei.ac.jp/~mori/Shohei_Mori_Site/articles/installation/CeresSolver/CeresSolver.html
glogエラー解決
http://stackoverflow.com/questions/19439670/min-max-not-a-member-of-std-errors-when-building-opencv-2-4-6-on-windows-8