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

Bidirectional path and motion planning ap- proaches 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 infor- mation 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. 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 test- beds. We find that these algorithms perform better than or comparable to existing state-of-the-art methods with respect to quickly finding an initial feasible solution.