Bidirectional Heuristic Search for Motion Planning with an Extend Operator

Abstract

Sampling-based approaches are often favored in robotics for high-dimensional motion planning for their fast exploration of the search space. However, at best they offer asymptotic guarantees on solution quality due to their inherent stochasticity. While planning, the majority of effort is often spent near the start and goal configurations with a large amount of free space in between. Bidirectional approaches such as RRT-Connect exploit this fact by greedily extending and connecting search frontiers that simultaneously propagate from the start and goal configurations of a planning problem. In this work, we use such an extend operator for bidirectional heuristic search-based planners, which typically struggle with high-dimensionality. In doing so, we address the difficulty that these bidirectional planners face with connecting frontiers of both search efforts while providing suboptimality bounds on solution quality. We validate our simple approach on high-dimensional manipulation tasks, demonstrating significantly reduced search effort when compared against other popular bidirectional algorithms, both search-based and sampling. Our algorithm maintains theoretical guarantees on suboptimality and completeness for a given resolution. In addition, the solutions found by our planner are of higher quality compared to those found by the other baseline algorithms.