# An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2015.

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

- [Fast Kinodynamic Planning on the Constraint Manifold with Deep Neural Networks](https://mlsanity.com/paper/2301.04330/) (2023)
- [Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities](https://mlsanity.com/paper/2603.24318/) (2026)

## Abstract (arXiv)

Bi-directional search is a widely used strategy to increase the success and convergence rates of sampling-based motion planning algorithms. Yet, few results are available that merge both bi-directional search and asymptotic optimality into existing optimal planners, such as PRM*, RRT*, and FMT*. The objective of this paper is to fill this gap. Specifically, this paper presents a bi-directional, sampling-based, asymptotically-optimal algorithm named Bi-directional FMT* (BFMT*) that extends the Fast Marching Tree (FMT*) algorithm to bi-directional search while preserving its key properties, chiefly lazy search and asymptotic optimality through convergence in probability. BFMT* performs a two-source, lazy dynamic programming recursion over a set of randomly-drawn samples, correspondingly generating two search trees: one in cost-to-come space from the initial configuration and another in cost-to-go space from the goal configuration. Numerical experiments illustrate the advantages of BFMT* over its unidirectional counterpart, as well as a number of other state-of-the-art planners.