Fast Marching Tree: a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions

By Lucas Janson, Edward Schmerling, Ashley A. Clark, Marco Pavone. Int. J. Robotics Res., 2013

625 citations recorded by the source corpus.

In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a ‘lazy’ dynamic programming recursion on a predetermined number of probabilistically drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As such, this algorithm combines features of both single-query algorithms (chiefly RRT) and multiple-query algorithms (chiefly PRM), and is reminiscent of the Fast Marching Method for the solution of Eikonal equations. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds—the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n −1/d+ρ ), where n is the number of sampled points, d is the dimension of the configuration space, and ρ is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our theoretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.

Subfields: Aerospace Engineering, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/5018acc39a0ffb5616949f6eb97ff6aeb9501c29

How researchers see this paper

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

In Aerospace Engineering

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

Citations in the corpus

Motion Planning Networks: Bridging the Gap Between Learning-Based and Classical Motion Planners (2019, background): “[41] proposed conditional variational autoencoders that contextualize on environment information to generate samples through the decoder network for the SMPs such as FMT* [42].”
Learning Sampling Distributions for Robot Motion Planning (2017, methodology): “tic completeness and asymptotic optimality from [23], [24],”
Asymptotically optimal sampling-based kinodynamic planning (2014, background): “Another line of work follows a Lazy PRM∗ approach to improve performance (Janson and Pavone, 2013).”
Perception, Planning, Control, and Coordination for Autonomous Vehicles (2017, background): “Other asymptotically optimal planners have since been suggested, such as Fast Marching Trees (FMT*) [223] and Stable Sparse Trees (SST*) [224], both of which claim speed improvement over RRT*.”
Geometrically Constrained Trajectory Optimization for Multicopters (2021, background): “There are also algorithms [20]–[22] that further improve the efficiency or applicability of randomized motion planning.”