「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
表示オプション
横に並べて表示:
変化行の前後のみ表示: