Bidirectional Sampling-Based Motion Planning Without Two-Point Boundary Value Solution

Sharan Nayak

doi:10.1109/TRO.2022.3181947

Return

Bidirectional Sampling-Based Motion Planning Without Two-Point Boundary Value Solution

2022-12-01

PRE

Sharan Nayak *

Michael Otte

DOI：10.1109/TRO.2022.3181947

Original

Save

Abstract

En 中文

Bidirectional path and motion planning approaches decrease planning time, on average, compared to their unidirectional counterparts. In single-query feasible motion planning, using bidirectional search to find a continuous motion plan requires an edge connection between the forward search tree and the reverse search tree. Such a tree-tree connection requires solving a two-point boundary value problem (BVP). However, obtaining a closed-form two-point BVP solution can be difficult or impossible for many systems. While numerical methods can provide a reasonable solution in many cases, they are often computationally expensive, numerically unstable, or sensitive (to an initial guess) for the purposes of single-query sampling-based motion planning. To overcome this challenge, we present a novel bidirectional search strategy that does not require solving the two-point BVP. Instead of connecting the forward and reverse trees directly, the reverse tree's cost information is used as a guiding heuristic for forward search. This enables the forward search to quickly grow down the reverse tree-converging to a fully feasible solution without a direct tree-tree connection and without the solution to a two-point BVP. In this article, we propose two algorithms that use this strategy for single-query feasible motion planning for various dynamical systems, performing experiments in both simulation and hardware testbeds. We find that these algorithms perform better than or comparable to the existing state-of-the-art methods with respect to quickly finding an initial feasible solution.

Keywords:

Planning

Heuristic algorithms

Convergence

Trajectory

Costs

Search problems

Robot kinematics

Autonomous agents

dynamics

motion and path planning