おべんきょうwiki

RRT

最終更新:

yahirohumpty

- view
管理者のみ編集可

RRT: Rapidly exploring Random Tree


探索手法の一つ.
ランダムに樹状探索を行う.

始点と終点双方向から木を伸ばす方法もある.
BiRRT, RRT-Connectと呼ばれる.
(RRT-Connectは微妙にアルゴリズムが異なる?)


RRTアルゴリズム


元論文から少しわかりやすくした擬似コードは以下の通り.

 BuildRRT(x_init) {
   tree.Init(x_init);  // 初期値x_initをツリーのルートに登録する
   for (k = 1 to K) {  // ゴールに到達したかどうかもここで判定する
     x_rand = RandomState();  // ランダムに目標値を入れる
     // Extend(tree, x_rand);  // 目標に対してツリーを延長する
     Connect(tree, x_rand);  // 目標に対して伸ばせるところまでツリーを延長する
   }
 }
 
 /// @brief 与えられた目標xの方向に伸ばせるところまでツリーを延長する
 Connect(tree, x) {
   do {
     s = Extend(tree, x);
   } while (s == ADVANCED);
   return s;
 }
 
 /// @brief 与えられた目標xの方向にツリーを延長する
 Extend(tree, x) {
   x_near = NearestNeighbor(x, tree);  // 目標に一番近いノードから枝を伸ばす
   if (NewState(x, x_near, x_new, u_new)) {
     Tree.AddVertex(x_new);
     Tree.AddEdge(x_near, x_new, u_new);
     if (x_new == x) {  // 実数空間では十分に近いかどうかを判定
       return REACHED;  // 目標に到達した
     } else {
       return ADVANCED;  // 目標方向に伸びたが到達はしていない
     }
   }
   return TRAPPED;  // 目標方向に延長出来なかった
 }
 
 /// @brief x_newとu_newを生成し,拘束条件の充足判定を行う.
 NewState(x, x_near, x_new, u_new) {
   x_new = (x - x_near) / norm(x - x_near) * DELTA + x_near;  // x の方向にx_nearを少しずらしたのがx_new
   u_new = FK(x_new);  // この行はダミー.x_newの時のu_newを計算
   return SatisfyConstraint(x_new, u_new);  // 拘束条件,衝突判定などが充足されるか否か.
 }

真面目にやるとゴールまでまともに収束しないため,
RandomState()はゴール方向にバイアスをかける.
例えば5%程度の確率でゴールを返すようにする.
このゴールを返す確率が高すぎると簡単に局所解に陥る.

BiRRTアルゴリズム


 RRTBidirectional(x_init, x_goal) {
   tree_a.Init(x_init);  // 初期値x_initをツリーのルートに登録する
   tree_b.Init(x_goal);  // 目標値x_goalを別のツリーのルートに登録する
   for (k = 1 to K) {
     x_rand = RandomState();  // ランダムに目標値を入れる
     if (Extend(tree_a, x_rand) != TRAPPED) {
       if (Extend(tree_b, x_new) == REACHED) {
         return Path(tree_a, tree_b);  // 2つのツリーを連結して完成
       }
     }
     Swap(tree_a, tree_b);  // 2つのツリーを入れ替える
   }
   return false;  // 規定の回数内に終了しなければ失敗
 }

2つのExtendのうち,どちらかあるいは両方をConnectに変えることもできる.
それぞれの場合で異なる挙動を示す.
RRT-Connectの元論文(Kuffner, ICRA2000)では二番目がConnectとなっている.


参考文献



元論文
Steven M. Lavalle , James J. Kuffner , Jr.
Rapidly-Exploring Random Trees: Progress and Prospects
http://msl.cs.uiuc.edu/~lavalle/papers/LavKuf01.pdf

RRT-Connectと言っているものはこのICRA2000の論文
https://personalrobotics.ri.cmu.edu/courses/papers/Kuffner00-rrtconnect.pdf
目安箱バナー