• Have any questions?
  • info.zbook.org@gmail.com

Robotic Motion Planning: RRT’s

3m ago
17 Views
1 Downloads
976.68 KB
41 Pages
Last View : 3d ago
Last Download : 1m ago
Upload by : Olive Grimm
Share:
Transcription

Robotic Motion Planning:RRT’sRobotics Institute 16-735http://www.cs.cmu.edu/ motionHowie Chosethttp://www.cs.cmu.edu/ chosetRI 16-735, Howie Choset with slides from James Kuffner

Overview Probabilistic RoadMap Planning (PRM) by Kavraki– samples to find free configurations– connects the configurations (creates a graph)– is designed to be a multi-query planner Expansive-Spaces Tree planner (EST) and Rapidly-exploringRandom Tree planner (RRT)– are appropriate for single query problems Probabilistic Roadmap of Tree (PRT) combines both ideasRI 16-735, Howie Choset with slides from James Kuffner

Next HW Assignment Implement a PRM planner for a multi-link (at least four) robot arm.The arm can be a simple planar arm (which will simplify thegraphics), or a 3D arm. The arm can be composed of linesegments (which will make collision checking easier) rather thanfinite volume links. All you need to do is write code to detect theintersection between line segments and polygons. If you want,you can use collision checking software that is available on theweb. How was the previous? This is the last oneRI 16-735, Howie Choset with slides from James Kuffner

Rapidly-Exploring Random Trees (RRTs)[Kuffner, Lavalle]The Basic RRTsingle treebidirectionalmultiple trees (forests)RRTs with Differential Constraintsnonholonomickinodynamic systemsclosed chainsSome Observations and Analysisnumber of branchesuniform convergenceresolution completenessleaf nodes vs. interior nodesPerformance & Implementation IssuesMetrics and Metric sensitivityNearest neighborsCollision CheckingChoosing appropriate step sizesRI 16-735, Howie Choset with slides from James Kuffner

High-Dimensional Planning as of 1999Single-Query:EXAMPLE: Potential-FieldGreedy, can takea long time butgood when youcan dive into thesolutionBarraquand, Latombe ’89; Mazer,Talbi, Ahuactzin, Bessiere ’92;Hsu, Latombe, Motwani ’97;Vallejo, Jones, Amato ’99;Multiple-Query:TENSIONEXAMPLE: PRMKavraki, Svestka, Latombe,Overmars ’95; Amato, Wu ’96;Simeon, Laumound, Nissoux ’99;Boor, Overmars, van der Stappen’99;RI 16-735, Howie Choset with slides from James KuffnerSpreads out likeuniformity butneed lots ofsample to coverspace

Rapidly-Exploring Random TreeRI 16-735, Howie Choset with slides from James Kuffner

Path Planning with RRTs(Rapidly-Exploring Random Trees)BUILD RRT (qinit) {T.init(qinit);for k 1 to K doqrand RANDOM CONFIG();EXTEND(T, qrand)}qnewEXTEND(T, qrand)qinitqnearRI 16-735, Howie Choset with slides from James Kuffner[ Kuffner & LaValle , ICRA’00]qrand

Path Planning with RRTs(Some Details)BUILD RRT (qinit) {T.init(qinit);for k 1 to K doqrand RANDOM CONFIG();EXTEND(T, qrand)}qnewEXTEND(T, qrand)qinitqnearRI 16-735, Howie Choset with slides from James KuffnerSTEP LENGTH: How far to sample1. Sample just at end point2. Sample all along3. Small StepExtend returns1. Trapped, cant make it2. Extended, steps toward node3. Reached, connects to nodeSTEP SIZE1. Not STEP LENGTH2. Small steps along way3. Binary searchqrand

RRT vs. Exhaustive Search DiscreteA* may try all edges Probabilistically subsample all edgesContinuousContinuum of choicesProbabilistically subsample all edgesRI 16-735, Howie Choset with slides from James Kuffner

Naïve Random TreeStart with middleSample near thisnodeThen pick a node atrandom in treeSample near itEnd up Staying inmiddleRI 16-735, Howie Choset with slides from James Kuffner

RRTs andBias toward large Voronoi regionshttp://msl.cs.uiuc.edu/rrt/gallery.htmlRI 16-735, Howie Choset with slides from James Kuffner

Biases Bias toward larger spacesBias toward goal– When generating a random sample, with some probability pick thegoal instead of a random node when expanding– This introduces another parameter– James’ experience is that 5-10% is the right choice– If you do this 100%, then this is a RPPRI 16-735, Howie Choset with slides from James Kuffner

RRT vs. RPPGreedygets youstuck hereRRT’s will pull away and betterapproximate cost-to-gogoalRI 16-735, Howie Choset with slides from James Kuffner

Grow two RRTs towards each otherqnewqtarget[ Kuffner, LaValle ICRA ‘00]qgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

A single RRT-Connect iteration.qgoalqinitRI 16-735, Howie Choset with slides from James Kuffner

1) One tree grown using random targetqgoalqinitRI 16-735, Howie Choset with slides from James Kuffner

2) New node becomes target for other treeqtargetqgoalqinitRI 16-735, Howie Choset with slides from James Kuffner

3) Calculate node “nearest” to targetqtargetqgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

4) Try to add new collision-free branchqnewqtargetqgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

5) If successful, keep extending branchqnewqtargetqgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

5) If successful, keep extending branchqnewqtargetqgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

5) If successful, keep extending branchqnewqtargetqgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

6) Path found if branch reaches targetqgoalqinitqnearRI 16-735, Howie Choset with slides from James Kuffner

7) Return path connecting start and goalqgoalqinitRI 16-735, Howie Choset with slides from James Kuffner

Basic RRT-ConnectRRT CONNECT (qinit, qgoal) {Ta.init(qinit); Tb.init(qgoal);for k 1 to K doqrand RANDOM CONFIG();if not (EXTEND(Ta, qrand) Trapped) thenif (EXTEND(Tb, qnew) Reached) thenReturn PATH(Ta, Tb);SWAP(Ta, Tb);Return Failure;}Instead of switching, use Ta as smaller tree. This helped James a lotRI 16-735, Howie Choset with slides from James Kuffner

qnearq′ f (q, u ) - - - use action u from q to arrive at q′chose u* arg min(d (qrand , q′))Is this the best?qnearqrandqrandMixing position and velocity, actually mixing position, rotation and velocity is hardRI 16-735, Howie Choset with slides from James Kuffner

So, what do they do? Use nearest neighbor anyway As long as heuristic is not bad, it helps(you have already given up completeness and optimality, so what the heck?) Nearest neighbor calculations begin to dominate the collisionavoidance (James says 50,000 nodes)Remember K-D treesRI 16-735, Howie Choset with slides from James Kuffner

Articulated RobotRI 16-735, Howie Choset with slides from James Kuffner

Highly Articulated RobotRI 16-735, Howie Choset with slides from James Kuffner

Hovercraft with 2 ThustersRI 16-735, Howie Choset with slides from James Kuffner

Out of This World DemoRI 16-735, Howie Choset with slides from James Kuffner

Left-turn only forward carRI 16-735, Howie Choset with slides from James Kuffner

AnalysisThe limiting distribution of vertices: THEOREM: Xk converges to X in probability Xk : The RRT vertex distribution at iteration kX : The distribution used for generating samplesKEY IDEA: As the RRT reaches all of Qfree, the probability that qrandimmediately becomes a new vertex approaches one.Rate of convergence: The probability that a path is found increasesexponentially with the number of iterations.“This is the bain or the worst part of the algorithm,” J. KuffnerRI 16-735, Howie Choset with slides from James Kuffner

Open ProblemsOpen Problems Rate of convergence Optimal sampling strategy?Open Issues Metric Sensitivity Nearest-neighbor EfficiencyRI 16-735, Howie Choset with slides from James Kuffner

Applications of RRTsRobotics Applicationsmobile roboticsmanipulationhumanoidsOther Applicationsbiology (drug design)manufacturing and virtual prototyping (assembly analysis)verification and validationcomputer animation and real-time graphicsaerospaceRRT extensionsdiscrete planning (STRIPS and Rubik's cube)real-time RRTsanytime RRTsdynamic domain RRTsdeterministic RRTsparallel RRTshybrid RRTsRI 16-735, Howie Choset with slides from James Kuffner

Diffusion Limited Aggregation Often used to model natural physical processes (e.g. snowaccumulation, rust, etc.)RI 16-735, Howie Choset with slides from James Kuffner

Exploring Infinite SpaceRI 16-735, Howie Choset with slides from James Kuffner

Polar SamplingRI 16-735, Howie Choset with slides from James Kuffner

RRT SummaryAdvantages Single parameter Balance between greedy search and exploration Converges to sampling distribution in the limit Simple and easy to implementDisadvantages Metric sensitivity Nearest-neighbor efficiency Unknown rate of convergence “long tail” in computation time distributionRI 16-735, Howie Choset with slides from James Kuffner

Links to Further Reading Steve LaValle’s online book:“Planning Algorithms” (chapters 5 & 14)http://planning.cs.uiuc.edu/ The RRT page:http://msl.cs.uiuc.edu/rrt/ Motion Planning BenchmarksParasol Group, Texas marks/mp/RI 16-735, Howie Choset with slides from James Kuffner

PRT (Prob. Roadmap of Trees) Basic idea:– Generate a set of trees in the configuration space– Merge the trees by finding nodes that can be connected Algorithm– pick several random nodes– Generate trees T1, T2 . Tn (EST or RRT)– Merge trees generate a representative super-node Using PRS ideas to pick a neighborhood of trees is now the tree-merge algorithm– For planning generate trees from initial and goal nodes towards closest supernodes try to merge with “roadmap” of connected trees Note that PRS and tree-based algorithms are special casesRI 16-735, Howie Choset with slides from James Kuffner

Implement a PRM planner for a multi-link (at least four) robot arm. The arm can be a simple planar arm (which will simplify the graphics), or a 3D arm. The arm can be composed of line segments (which will make collision checking easier) rather than finite vol