<<展開
©2024 Thoth Children All rights reserved.

RRT-Connect

ー 概要 ー

RRT-ConnectはRRTを用いてコンフィギュレーション空間における高次元空間の探索を効率よく行い、スタートからゴールまでのパスを見つけるアルゴリズム.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
効果
  • スタートからゴールまでのパスを見つける
  • モーションプランニングや移動経路探索で用いられる
ポイント
  • 処理の重い最近傍探索を行う回数が多い
  • ベースをRRTとしてパス探索用に改変している
  • スタートとゴールの双方から探索を行う

解 説

RRT-ConnectはRRTを用いてコンフィギュレーション空間における高次元空間の探索を効率よく行い、スタートからゴールまでのパスを見つけるアルゴリズム. RRT-Connectは、RRTのスタートからゴールまでのパスを見つけるように 以下の点を変えている. ・スタートとゴールの双方から探索 ・双方から交互に伸ばす ・障害物がなく伸ばせるなら連続して伸ばしてみる
RRT-connectとは
RRTに関してはこちらでアルゴリズムを確認ください.
RRT
論文にも記載されていますが、RRT-Connectのアルゴリズムを記載します. その図解は以下の画像で示しています. 事前 q_start, q_goal：初期位置 start_tree, goal_tree : 探索してノードを加えるツリー distance_max : ノードを加えるときの既存ノードからの最大距離. K : 探索するノードの数 アルゴリズム 1. 初期のノードq_start, q_goalを用意する. 2. 以下3.~6.をK回繰り返す. 3. start_treeとgoal_treeのノードの少ない方をTree_Target, 多い方をTree_Extendとする. 4. RRTと同様の方法でTree_Targetにq_targetを加える 5. 3.で得たq_targetにもっとも近いノードq_nearをTree_Extendから探す 6. q_nearからq_targetに枝を最大distance_maxで伸ばし新しいノードq_newを作る. これを障害物がない限り同じ方向に伸ばし続ける. 繋がったら終了.
RRT-Connectのアルゴリズム
RRT-Connectの図解
James Kuffner氏の元論文へのリンクを貼っておきます.
外部リンク
元論文はこちら
この章を学んで新たに学べる
Comments

Reasons
>>隠す

知識: RRT
RRT(Rapidly-exploring Random Tree)は高次元空間における探索を効率的に比較的高速的に行うことのできる探索手法.これを用いて自由度の高いロボットアームの軌道探索や経路探索などが行われることが多い.アルゴリズムがシンプルで実装も容易.