Incremental Sampling-based Algorithms for Optimal Motion Planning

By Sertac Karaman, Emilio Frazzoli. 2010

864 citations recorded by the source corpus.

During the last decade, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs), have been shown to work well in practice and to possess theoretical guarantees such as probabilistic completeness. However, no theoretical bounds on the quality of the solution obtained by these algorithms, e.g., in terms of a given cost function, have been established so far. The purpose of this paper is to fill this gap, by designing efficient incremental samplingbased algorithms with provable optimality properties. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path returned by RRT converges almost surely to a non-optimal value, as the number of samples increases. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path returned by RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called RRT∗, which preserves the asymptotic optimality of RRG while maintaining a tree structure like RRT. The analysis of the new algorithms hinges on novel connections between sampling-based motion planning algorithms and the theory of random geometric graphs. In terms of computational complexity, it is shown that the number of simple operations required by both the RRG and RRT∗ algorithms is asymptotically within a constant factor of that required by RRT.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition, Reinforcement Learning

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 Networks and Communications

In Computer Vision and Pattern Recognition

In Reinforcement Learning

Citations in the corpus

Learning Trajectory Preferences for Manipulators via Iterative Improvement (2013, background): “The cost function (or its approximation) we learn can be fed to trajectory optimizers like CHOMP [29] or optimal planners like RRT* [15] to produce reasonably good trajectories. α(s∗(xt, y ∗ t ) − s∗(xt, yt)) − ξt.”
Learning Model Predictive Control for Iterative Tasks. A Data-Driven Control Framework (2016, neutral): “For efficient techniques to compute collision-free trajectories in the presence of obstacle, we refer to [25], [26], and [27].”
Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics (2013, methodology): “In the original RRT* algorithm, the neighbor radius r can be decreased over the course of the algorithm as a function of the number of nodes i currently in the tree, without affecting the asymptotic optimality guarantee, by setting r such that neighbors are selected from a ball with volume γ log[i]/”
Rapidly-exploring Random Belief Trees for motion planning under uncertainty (2011, methodology): “For a thorough discussion on the importance of the ball size see [6].”
Anytime Motion Planning using the RRT* (2011, background): “Karaman and Frazzoli [9] proved that the probability of the RRT algorithm converging to an optimal solution is actually zero.”
Asymptotically optimal sampling-based kinodynamic planning (2014, methodology): “Arguably, both PRM and RRT-Connect are graph-based algorithms.”
Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments (2016, background): “Randomized algorithms such as PRM, RRT and RRT* have enjoyed success due to their simplicity and performance in high-dimensional spaces [14, 17, 12].”
SWIRL: A sequential windowed inverse reinforcement learning algorithm for robot tasks with delayed rewards (2018, methodology): “We generated the initial demonstrations using an RRT* motion planner (assuming deterministic dynamics) (Karaman and Frazzoli, 2010).”
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].”
Sampling-based algorithms for optimal motion planning (2011, methodology): “A preliminary version of this article has appeared in Karaman and Frazzoli (2010b).”
SPENCER: A Socially Aware Service Robot for Passenger Guidance and Help in Busy Airports (2015, positive): “As a further extension to standard motion planning, we investigate RRT*-based planning (Karaman and Frazzoli, 2010) using low-level vehicle constraints in combination with high-level socially compliant cost maps.”
Advanced closed loop visual navigation for micro aerial vehicles (2014, methodology): “made forth and back to a set of near vertices within a certain radius (Bry and Roy, 2011; Karaman and Frazzoli, 2010), which also get propagated.”
Learning objective functions for manipulation (2013, methodology): “Recently introduced motion planning algorithms such as RRT* [24], CHOMP [25], [26] and STOMP [27] attempt to minimize a cost function defined over trajectories, and have successfully been applied to manipulation tasks.”
Learning preferences for manipulation tasks from online coactive feedback (2015, methodology): “Such preferences are often encoded as a cost which planners optimize [26, 50, 63].”
Autonomous multi-floor indoor navigation with a computationally constrained MAV (2011, methodology): “Given the current pose estimate of the robot and map of the environment, we pursue two path planning solutions: naive waypoint following with proportional feedback control based on a desired goal and the current state, and an incremental sampling-based method (RRT ) [18].”