close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Tree-Based Planning
Nancy M. Amato
Parasol Lab,Texas A&M University
http://parasol.tamu.edu
‘Single Shot’ Planning
Given Start and Goal configurations, determine a motion plan
connecting them without preprocessing (don’t build roadmap)
Goal
Start
• Also, can be applied when do not have specific goal, but want to find
space reachable from start
Bi-Directional Search: Iteratively grow trees
from start and goal
• Build two trees: one from start and one from goal
•partial progress saved & added to evolving trees
• Original query solved when start & goal trees meet
G0
G2
Obstacle3
G3
S2
Obstacle1
G1
S1
G4
Obstacle2
S0
S3
Ariadne’s Clew Algorithm
[Bessiere et al IROS 1993]
Goal
Start
EXPLORE random walk terminus
new Landmark
SEARCH random walk terminus
[Bessiere et al, IROS 1993]
Rapidly Exploring Random Trees (RRT)
[Kuffner & LaValle ICRA 1999]
Goal
xnear
xrand
Start
Nodes in current RRT-VAR tree
Random configuration
Configurations around closest to random in tree
New node added to the RRT tree
Rapidly Exploring Random Trees (RRT)
[Kuffner & LaValle ICRA 1999]
RRT approaches
GENERATE_RRT(xinit, K, t)
1.
2.
3.
4.
5.
6.
7.
8.
9.
T.init(xinit);
For k = 1 to K do
xrand  RANDOM_STATE();
xnear  NEAREST_NEIGHBOR(xrand, T);
u  SELECT_INTPUT(xrand, xnear);
xnew  NEW_STATE(xnear, u, t);
T.add_vertex(xnew);
T.add_edge(xnear, xnew, u);
Return T;
xrand
xnew
xnear
xinit
The result is a tree rooted at xinit:
LaValle, 1998; LaValle, Kuffner, 1999, 2000; Frazzoli, Dahleh, Feron, 2000; Toussaint, Basar, Bullo,
2000; Vallejo, Jones, Amato, 2000; Strady, Laumond, 2000; Mayeux, Simeon, 2000; Karatas, Bullo,
2001; Li, Chang, 2001; Kuffner, Nishiwaki, Kagami, Inaba, Inoue, 2000, 2001; Williams, Kim,
Hofbaur, How, Kennell, Loy, Ragno, Stedl, Walcott, 2001; Carpin, Pagello, 2002.
1/--страниц
Пожаловаться на содержимое документа