Bidirectional Sampling Based Search Without Two Point Boundary Value Solution
This addresses a bottleneck in motion planning for systems where BVPs are hard to solve, offering an incremental improvement for robotics and autonomous systems.
The paper tackles the challenge of bidirectional motion planning without solving difficult two-point Boundary Value Problems (BVPs) by using the reverse tree's cost information as a heuristic for the forward search, resulting in algorithms (GBRRT and GABRRT) that perform on-par or better than state-of-the-art methods in quickly finding initial feasible solutions in simulations and hardware experiments.
Bidirectional 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 and reverse search trees. Such a tree-tree connection requires solving a two-point Boundary Value Problem (BVP). However, a two-point BVP solution can be difficult or impossible to calculate for many systems. 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 the forward search. This enables the forward search to quickly converge to a feasible solution without solving the two-point BVP. We propose two new algorithms (GBRRT and GABRRT) that use this strategy and run multiple software simulations using multiple dynamical systems and real-world hardware experiments to show that our algorithms perform on-par or better than existing state-of-the-art methods in quickly finding an initial feasible solution.