title: An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning.
abstract: 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 bidirectional search while preserving its key properties, chiefly lazy search and asymptotic optimality through convergence in probability. BFMT* performs a two-source,lazydynamic 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.
authors.affiliation: Dept. of Aeronautics and Astronautics, Stanford University, Stanford, CA 94305.
authors.forename: Joseph A
authors.initials: JA
authors.lastname: Starek
authors.affiliation: Dept. of Systems Engineering & Automation, Carlos III University of Madrid, Madrid, Spain, 28911.
authors.forename: Javier V
authors.initials: JV
authors.lastname: Gomez
authors.affiliation: Inst. for Computational & Mathematical Engineering, Stanford University, Stanford, CA 94305.
authors.forename: Edward
authors.initials: E
authors.lastname: Schmerling
authors.affiliation: Dept. of Statistics, Stanford University, Stanford, CA 94305.
authors.forename: Lucas
authors.initials: L
authors.lastname: Janson
authors.affiliation: Dept. of Systems Engineering & Automation, Carlos III University of Madrid, Madrid, Spain, 28911.
authors.forename: Luis
authors.initials: L
authors.lastname: Moreno
authors.affiliation: Dept. of Aeronautics and Astronautics, Stanford University, Stanford, CA 94305.
authors.forename: Marco
authors.initials: M
authors.lastname: Pavone