- @ThothChildren
- 2018.10.14
- PV 488
RRT
ー 概要 ー
RRT(Rapidly-exploring Random Tree)は高次元空間における探索を効率的に比較的高速的に行うことのできる探索手法.これを用いて自由度の高いロボットアームの軌道探索や経路探索などが行われることが多い.アルゴリズムがシンプルで実装も容易.
この章を学ぶ前に必要な知識
条件
- 高次元空間におけるパスの探索などに用いる
効果
- ロボットのモーションプランニングなどに導入しやすい
ポイント
- 制限や障害物の考慮がしやすい
- 高次元空間でも高速に探索
- ランダムに空間上に点を取るため、まだ探索していない領域を優先して探索.(ノードのボロノイ面積に確率が比例)
- アルゴリズムがシンプルで実装が容易.
解 説
すぐに理解できるポイントを抑えたわかりやすいRRT解説動画 | |
RRT(Rapidly-exploring Random Tree)は高次元空間における探索を効率的に比較的高速的に行うことのできる探索手法.
これを用いて自由度の高いロボットアームの軌道探索や経路探索などが行われることが多い.
アルゴリズムがシンプルで実装も容易だが、パスを求めた場合などは最適な経路に修正する必要がある.最適なパスとは限らない.
また、障害物などの判定も容易で、制限も入れやすいのも特徴.
| RRTとは |
RRTのアルゴリズムは以下のようにシンプルになっている.
事前
q_init:初期位置
tree : 探索してノードを加えるツリー
distance_max : ノードを加えるときの既存ノードからの最大距離.
K : 探索するノードの数
アルゴリズム
1. 初期のノードを用意する.
2. 以下3.~6.をK回繰り返す.
3. ランダムq_randな点を空間からサンプリングする.
4. 3.で得たランダムな点q_randにもっとも近いノードq_nearをtreeから探す
5. q_nearからq_randに枝を最大distance_maxで伸ばし新しいノードq_newを作る.
6. q_newをtreeに加えて、q_randは捨てる. | RRTのアルゴリズム |
上記アルゴリズムの図解 | |
RRTはランダムな点を打ち、もっとも近いノードから枝を伸ばすことで、
まだ未探索の領域を優先して探索するようになっている.
これはボロノイ面積に比例して新しい点が作られるためである.
また、スタートからゴールまでのパスの探索をするようなタスクにおいては、
ランダム点を取るときに一定の割合でゴールを点として選択することで、ゴールにバイアスをかけた探索を行うようにすることがある.
また、狭いパスを通らなくてはならないような探索においては探索が難しくなる欠点もある. | RRTのポイント |
RRTが行われる様子 | |
ボロノイ図とは、空間をもっとも近い点で分割した図形のこと.
今回のRRTでは新しい点をもっとも近い点に割り当てることになるため、ボロノイ領域の面積が大きい点がRRTで新しい点を選ぶときに当然その領域が選ばれやすくなる. | ボロノイ図とは |
1.デモンストレーション | |
実際にRRTを体験できるページへのリンクを貼っておきます.
こちらでどのように障害物を配置してもランダムに枝を伸ばして、RRTがパスを見つけているのを見れるかと思います. | 外部リンク RRT : 目で見て理解するアルゴリズムThoth Children Visalgo |
この章を学んで新たに学べる
Comments