Search-Based Planning with Extend Operator

Abstract

Sampling-based approaches are often favored in robotics for high-dimensional motion planning for their fast coverage of the search space. However, at best they offer asymptotic guarantees on completeness and solution quality, and returned paths are typically unpredictable due to their inherent stochasticity. By reasoning through the state space in a procedural fashion, heuristic search-based planners offer high-quality solutions with strong theoretical guarantees but struggle with high dimensionality. In complex domains that demand larger branching factors, this exhaustive behavior can result in considerably longer planning times, known as the "curse of dimensionality." The key factor to fast planning times by sampling-based approaches can largely be attributed to the extend operator, which greedily grows the search tree without regard for the problem’s complexity. In this work, we exploit this observation and introduce an extend operator in heuristic search to enable considerable speedups in practice. We explore how this operator directly addresses many difficulties of bidirectional heuristic search and how it naturally extends to the multi-tree setting. We validate our simple approach on high-dimensional manipulation tasks, demonstrating significantly reduced search effort when compared against both search- and sampling-based algorithms. While doing so, we maintain theoretical guarantees on suboptimality and completeness.