Approaches for heuristically biasing RRT growth

By C. Urmson, Reid G. Simmons. IEEE/RJS International Conference on Intelligent RObots and Systems, 2003

387 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/62a50199c1a64a3b760743c561bcfbaf0d657ad2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Asymptotically optimal sampling-based kinodynamic planning (2014, methodology): “For the worst case, the kth segment of the trajectory returned by RRT-BestNear converges linearly to the near-optimal solution, i.e. limn→∞ |P(E(n+1)k )−1| |P(E(n)k )−1| = ( 1− γρδ→δBN )∈( 0, 1).”
Optimal kinodynamic motion planning using incremental sampling-based methods (2010, background): “However, the quality of the solution returned by the RRT, or by algorithms designed to provably improve the quality of the solution given more computation time, has remained largely open despite the increasing recent interest [15], [17], [18].”
Replanning with RRTs (2006, methodology): “Note that this algorithm can be used for the navigation of either a single robot or a team of robots.”
Planning algorithms (2006, methodology): “For more work on RRTs under differential constraints, see [140, 201, 226, 326, 362, 395, 512, 949].”
Planning human-aware motions using a sampling-based costmap planner (2011, background): “Several approaches have been introduced in former works, in particular RRT variants [6], [19], [3] in the context of field robotics or more recently in [10].”
High Speed Navigation of Unrehearsed Terrain: Red Team Technology for Grand Challenge 2004 (2004, methodology): “The simulation would be used as the feed-forward portion of a randomized dynamics cognizant planning algorithm [19].”
Perception, Planning, Control, and Coordination for Autonomous Vehicles (2017, background): “Some works have proposed to bias tree growth toward regions that resulted in lower cost solutions [222].”
Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs (2014, background): “Optimal variants, such as RRT* and PRM* [23], are also asymptotically optimal, converging asymptotically to the optimal solution with probability one as the number of samples goes to infinity (almost sure asymptotic convergence).”
Sampling-based algorithms for optimal motion planning (2011, background): “Urmson and Simmons (2003) proposed heuristics to bias the tree growth in RRT towards those regions that result in low-cost solutions.”
Sampling-Based Path Planning on Configuration-Space Costmaps (2010, methodology): “T-RRT has been compared with two existing cost-based planners: the maximal Threshold technique proposed by Ettlin and Bleuler [4] and the heuristically-guided RRT ( hRRT ) of Urmson and Simmons [6].”
Sampling-Based Robot Motion Planning: A Review (2014, methodology): “All the previously mentioned approaches assume a uniform cost C-spaces, aside from heuristic method presented in [121].”
Incremental Sampling-based Algorithms for Optimal Motion Planning (2010, background): “In [45], Urmson and Simmons have proposed heuristics to bias the tree growth in the RRT towards those regions that result in low-cost solutions.”
Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic (2014, methodology): “Urmson and Simmons [5] had found that using a heuristic to bias sampling improved RRT solutions, but did not formally quantify the effects.”
Neural RRT*: Learning-Based Optimal Path Planning (2020, neutral): “Urmson and Simmons [18] compute a heuristic quality that is used to evaluate the quality of a path passing through the node.”