「RRT」の編集履歴(バックアップ)一覧はこちら

RRT」(2014/08/06 (水) 20:14:19) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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となっている. ** 参考文献 http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree 元論文 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
* 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となっている. ** 参考文献 http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree 元論文 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

表示オプション

横に並べて表示:
変化行の前後のみ表示:
目安箱バナー