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

arXiv: https://arxiv.org/abs/1306.3532 · HTML: https://mlsanity.com/paper/1306.3532/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2013.

## Built on by (most cited first, 25 of 25)

- [How To Not Train Your Dragon: Training-free Embodied Object Goal Navigation with Semantic Frontiers](https://mlsanity.com/paper/2305.16925/) (2023)
- [Potential Based Diffusion Motion Planning](https://mlsanity.com/paper/2407.06169/) (2024)
- [NTFields: Neural Time Fields for Physics-Informed Robot Motion Planning](https://mlsanity.com/paper/2210.00120/) (2022)
- [Injecting Planning-Awareness into Prediction and Detection Evaluation](https://mlsanity.com/paper/2110.03270/) (2021)
- [Verifiably Following Complex Robot Instructions with Foundation Models](https://mlsanity.com/paper/2402.11498/) (2024)
- [Rethinking Trajectory Forecasting Evaluation](https://mlsanity.com/paper/2107.10297/) (2021)
- [Targeted Adversarial Attacks against Neural Network Trajectory Predictors](https://mlsanity.com/paper/2212.04138/) (2022)
- [Reaching Through Latent Space: From Joint Statistics to Path Planning in Manipulation](https://mlsanity.com/paper/2210.11779/) (2022)
- [Progressive Learning for Physics-informed Neural Motion Planning](https://mlsanity.com/paper/2306.00616/) (2023)
- [USA-Net: Unified Semantic and Affordance Representations for Robot Memory](https://mlsanity.com/paper/2304.12164/) (2023)
- [Reachable Polyhedral Marching (RPM): An Exact Analysis Tool for Deep-Learned Control Systems](https://mlsanity.com/paper/2210.08339/) (2022)
- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [Recent Advancements in Deep Learning Applications and Methods for Autonomous Navigation: A Comprehensive Review](https://mlsanity.com/paper/2302.11089/) (2023)
- [Physics-informed Temporal Difference Metric Learning for Robot Motion Planning](https://mlsanity.com/paper/2505.05691/) (2025)
- [Efficient Motion Planning for Manipulators with Control Barrier Function-Induced Neural Controller](https://mlsanity.com/paper/2404.01184/) (2024)
- [Grasping Trajectory Optimization with Point Clouds](https://mlsanity.com/paper/2403.05466/) (2024)
- [Global Tensor Motion Planning](https://mlsanity.com/paper/2411.19393/) (2024)
- [SOCRATES: Text-based Human Search and Approach using a Robot Dog](https://mlsanity.com/paper/2302.05324/) (2023)
- [CoverLib: Classifiers-equipped Experience Library by Iterative Problem Distribution Coverage Maximization for Domain-tuned Motion Planning](https://mlsanity.com/paper/2405.02968/) (2024)
- [DAA*: Deep Angular A Star for Image-based Path Planning](https://mlsanity.com/paper/2507.09305/) (2025)
- [Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities](https://mlsanity.com/paper/2603.24318/) (2026)
- [Factorization of Multi-Agent Sampling-Based Motion Planning](https://mlsanity.com/paper/2304.00342/) (2023)
- [IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty](https://mlsanity.com/paper/2304.10984/) (2023)
- [PPNet: A Two-Stage Neural Network for End-to-end Path Planning](https://mlsanity.com/paper/2401.09819/) (2024)
- [Convex-Neural RRT*: Fast and Reliable Learning-Guided Sampling for High-Quality Robot Path Planning](https://mlsanity.com/paper/2605.25006/) (2026)

## Abstract (arXiv)

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 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.