Bidirectional Heuristic Search for Motion Planning with an Extend Operator

November 2019

Bidirectional Heuristic Search for Motion Planning with an Extend Operator

Conference Paper
Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems

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.
@conference{Cheng-2019-120144,
author = {Allen Cheng And Dhruv Mauria Saxena And Maxim Likhachev},
title = {Bidirectional Heuristic Search for Motion Planning with an Extend Operator},
booktitle = {Proceedings of (IROS) IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2019},
month = {November},
pages = {7425 - 7430},
}
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.