はじめに

私がロボットに関して興味を持っており，ロボットの経路を作成したいと思い，経路生成の手法を学んだため，本記事にまとめる．
経路生成の手法は論文として，記載されているがソースコードを探すのに手間がかかったため，自作しようと考えた．
また，私が学生時代にロボットの経路生成に関して研究をしており，理論は理解できてもソースコードを作ることが出来なかった経験をしたため，記事を投稿しようと思った．

本記事に記載すること

・経路生成手法( RRT/RRT-Connect/RRT* )のアルゴリズムをまとめる
・私が作成した経路生成に関する記事の概要およびリンクと将来作成したい記事をまとめる

本記事では記載できないこと (将来作成したい記事)

・RRT/RRT-Connect/RRT* 以外の経路生成手法の記事を作成する

経路生成手法( RRT/RRT-Connect/RRT* )のアルゴリズム

経路生成手法( RRT/RRT-Connect/RRT* )のアルゴリズムをまとめる．
RRTおよびRRT-Connectの参考文献は下記の通りである．
J.Kuffner "RRT-Connect: An Efficient Approach to Single-Query Path Planning.", ICRA 2000.
RRTは始点から終点までの経路を探索するアルゴリズムだが，RRT-Connectは始点と終点の両方から経路を探索するアルゴリズムである．詳細は後ほど説明する．

RRTおよびRRTの参考文献は下記の通りである．
S.Karaman, E.Frazzoli "Incremental Sampling-based Algorithms for Optimal Motion Planning.", arXiv 2010.
RRT はRRTに最適性を付与したアルゴリズムである．詳細は後ほど説明する．

RRTアルゴリズム

RRTのアルゴリズムを説明する．
参考文献に記載されているRRTのアルゴリズムを抜粋して，下記に記す．

RRTは始点から，終点に向かってどんどんノードを増やしていき，終点との距離がある値以下になったら，経路生成を完了する．
RRTは下図のようなアルゴリズムである．

RRT-Connectアルゴリズム

RRT-Connectのアルゴリズムを説明する．

RRT-Connectは始点と終点の両方からノードを増やしていき，始点から終点までノードが繋がれば，経路生成を完了する．
RRT-Connectは下図のようなアルゴリズムである．

上図のRRT-Connectアルゴリズムより，状態遷移図を作成した．状態としては，下図の通りになる．

RRT*アルゴリズム

RRT*のアルゴリズムを説明する．

参考文献に記載されているRRT* のアルゴリズムを抜粋して，下記に記す．
RRTとの差異を赤枠で記載した．

RRT* は始点から，終点に向かってどんどんノードを増やしていき，新規ノードの周辺ノードでコストが最小となるように，親ノードを修正していく．
一定回数実行後に，始点から終点までのコストが最小となる経路を選択する

RRT* は下図のようなアルゴリズムである．

新規ノードを作成した時の近傍ノードを探索する範囲は以下のように定義されている．

\displaylines{
r = R * (\log N / N)^{1/d} \\
r ... 近傍ノードの探索範囲 \\
N ... ツリー内のノード数 \\
d ... 探索空間の次元数 \\
R ... ハイパーパラメータ \\
}

ノード数(N)が多い(探索の試行回数が多い)ほど，近傍ノードの探索範囲(r)は小さくなる．
ハイパーパラメータであるRの値を決めるのが困難である．
Rの値が大きい時のメリット・デメリットは以下の通りである．
　メリット
　・近傍ノードの数が増えるため，コストが最小となる経路を算出しやすい
　デメリット
　・処理時間が増える

経路生成に関する記事の概要およびリンクと将来作成したい記事

私が作成した経路生成に関する記事の概要およびリンクを下表にまとめる．

作成した記事の概要	リンク
2次元空間で干渉物が存在しない経路生成 (RRT)	https://qiita.com/haruhiro1020/items/6eaae645bd638c2b8897
3次元空間で干渉物が存在しない経路生成 (RRT)	https://qiita.com/haruhiro1020/items/b11e63ffcd71311d3390
2次元空間で円形の干渉物が存在する経路生成 (RRT)	https://qiita.com/haruhiro1020/items/4482e0ba2be5f1b835a4
3次元空間で球の干渉物が存在する経路生成 (RRT)	https://qiita.com/haruhiro1020/items/61e477b156daa6b0cc40
2次元空間で円形の干渉物が存在する経路生成 (RRT-Connect)	https://qiita.com/haruhiro1020/items/2b3985495b864a4a7e16
3次元空間で球の干渉物が存在する経路生成 (RRT-Connect)	https://qiita.com/haruhiro1020/items/74ed385c068d4268f4d5
2次元空間で円形の干渉物が存在する経路生成 (RRT*)	https://qiita.com/haruhiro1020/items/7c5bdbe530711c9d331b
3次元空間で球の干渉物が存在する経路生成 (RRT*)	https://qiita.com/haruhiro1020/items/de9fb322dce87588d48d

将来作成したい記事を下表にまとめる．

将来作成したい記事の内容
2次元空間で円形以外の干渉物が存在する経路生成 (RRT)
3次元空間で球以外の干渉物が存在する経路生成 (RRT)
2次元空間で円形以外の干渉物が存在する経路生成 (RRT-Connect)
3次元空間で球以外の干渉物が存在する経路生成 (RRT-Connect)
2次元空間で円形以外の干渉物が存在する経路生成 (RRT*)
3次元空間で球以外の干渉物が存在する経路生成 (RRT*)
RRT/RRT-Connect/RRT*以外の経路生成手法
様々な経路生成手法の比較および組み合わせる

おわりに

本記事では，経路生成手法の自作記事をまとめた

次記事では，下記内容を実装していきます．
・本記事の"将来作成したい記事"に記載した記事を作成する
・ロボットアームに関する記事を作成する
・機械学習に関する記事を作成する