Search-Based Planning with Extend Operator

August 2020

Search-Based Planning with Extend Operator

Authors:

Allen Cheng

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.

Notes:

@mastersthesis{Cheng-2020-123558,
author = {Allen Cheng},
title = {Search-Based Planning with Extend Operator},
year = {2020},
month = {August},
school = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-20-35},
keywords = {search, heuristic search, search-based planning, extend operator, motion planning, manipulation},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.