<<展開

RRT

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

RRT(Rapidly-exploring Random Tree)は高次元空間における探索を効率的に比較的高速的に行うことのできる探索手法.これを用いて自由度の高いロボットアームの軌道探索や経路探索などが行われることが多い.アルゴリズムがシンプルで実装も容易.
ー 条件 ー
  • 高次元空間におけるパスの探索などに用いる
ー 効果 ー
  • ロボットのモーションプランニングなどに導入しやすい
ーポイントー
  • 制限や障害物の考慮がしやすい
  • 高次元空間でも高速に探索
  • ランダムに空間上に点を取るため、まだ探索していない領域を優先して探索.(ノードのボロノイ面積に確率が比例)
  • アルゴリズムがシンプルで実装が容易.

解  説

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で新しい点を選ぶときに当然その領域が選ばれやすくなる.
ボロノイ図とは
この章を学んで新たに学べる
Comments

Reasons
>>隠す

知識: ボロノイ図とは
ボロノイ図はある平面に複数の点がばら撒かれているときにそれらの点のどこに最も近いかで領域を分割している図形.