Rapidly Exploring Random Trees Data structure/algorithm to facilitate path planning Developed by Steven M. La Valle (1998) Originally designed to handle problems with nonholonomic constraints and high degrees of freedom Rapidly Exploring Random Trees Algorithm: BUILD_RRT(qinit) 1 T.init(qinit); 2 for k=1 to K do 3 qrand ← RANDOM_CONFIG(); 4 EXTEND(T, qrand); 5 Return T; Rapidly Exploring Random Trees EXTEND(T,q) 1 qnear ← Nearest_NEIGHBOUR(q,T); 2 if NEW_CONFIG(q, qnear, qnew) then 3 T.add_vertex(qnew); 4 T.add_edge(qnear, qnew); 5 if qnew = q then 6 Return Reached; 7 else 8 Return Advanced; 9 Return Trapped; Rapidly Exploring Random Trees Rapidly Exploring Random Trees Main advantage: biased towards unexplored regions Probability node selected for extension proportional to size voronoi region Rapidly Exploring Random Trees Nice properties: Expansion heavily biased towards unexplored areas of state space Distribution nodes approaches the sampling distribution (important for consistency), usually uniform but not necessarily! Relatively simple algorithm Always remains connected RRT-Connect Path Planner How to use RRT in a path planner? RRT-Connect: Single shot method Grow two RRTs one from the start position and one from the goal position After every extension try to connect the trees If the trees connect a path has been found RRT-Connect Path Planner Algorithm: RRT_CONNECT_PLANNER(qinit, qgoal) 1 Ta.init(qinit); Tb.init(qgoal); 2 for k=1 to K do 3 qrand ← RND_CFG(); 4 if not(EXTEND(Ta, qrand)= Trapped) then 5 if(CONNECT(Tb, qnew) = Reached) then 6 Return PATH(Ta, Tb); 7 SWAP(Ta, Tb); 8 Return Failure; RRT-Connect Path Planner CONNECT(T, q) 1 repeat 2 S ← EXTEND(T, q) 3 until not (S = Advanced) 4 Return S; RRT-Connect Path Planner RRT-Connect Path Planner Variations: RRT_EXTEND_EXTEND RRT_CONNECT_CONNECT In CONNECT step only add last vertex to graph Grow more RRTs RRT-Connect Path Planner Analysis: RRT-Connect is probabilistic complete Distribution vertices in RRT converges toward sampling distribution No theoretical characterization of the rate of converge! RRT-Connect Path Planner Experiments: Average 100 trials Scene 1: 0.228s Scene 2: 5,94s Scene 3: 2.92s Using 3D non incremental collision checking algorithm RRT-Connect Path Planner Experiments: In uncluttered scenes connect heuristic 3 to 4 times faster than other RRT-based variants Useful for complicated 3D scenes 7-DOF kinematic chain, over 8000 triangle primitives average 2 s for each motion to reach, grasp and move RRT-Connect Path Planner Experiments: over 13.000 triangles 80 s SGI Indigo2 15 s high-end SGI RRT-Connect Path Planner Conclusion: Randomised approach that yields good experimental performances with no parameter tuning no pre-processing simple and consistent behaviour balance between greedy searching and uniform exploration well suited for incremental distance computation and fast nearest neighbour algorithms RRT-Connect Path Planner To do: optimise distance travelled during each step by using the radius of a collision free ball use approximate nearest neighbour methods use incremental collision detection algorithm compare performance to other path planning approaches identify conditions that lead to poor performance RRT-Connect Path Planner Issues: Randomness can cause great variance in runtime due to ‘unlucky instance’ RRT-Connect Path Planner Issues: Ugly paths References RRT-connect: An efficient approach to single-query path planning. J. J. Kuffner and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 995--1001, 2000 On Heavy-tailed Runtimes and Restarts in Rapidly-exploring Random Trees. Nathan A. Wedge and Michael S. Branicky. 2008 Chapter 5: Sampling-Based Motion Planning, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., Rapidly-exploring random trees: A new tool for path planning. S. M. LaValle. TR 98-11, Computer Science Dept., Iowa State University, October 1998 2006. http://msl.cs.uiuc.edu/rrt/gallery.html Rapidly-Exploring Random Trees in Highly Constrained Environments. Amjad Almahairi. 2010.