/A*-Connect: Bounded Suboptimal Bidirectional Heuristic Search

A*-Connect: Bounded Suboptimal Bidirectional Heuristic Search

Fahad Islam, Venkatraman Narayanan and Maxim Likhachev
Conference Paper, IEEE International Conference on Robotics and Automation (ICRA), May, 2016

Download Publication (PDF)

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.

Abstract

The benefits of bidirectional planning over the unidirectional version are well established for motion planning in high-dimensional configuration spaces. While bidirectional approaches have been employed with great success in the context of sampling-based planners such as in RRT-Connect, they have not enjoyed popularity amongst search-based methods such as A*. The systematic nature of search-based algorithms, which often leads to consistent and high-quality paths, also enforces strict conditions for the connection of forward and backward searches. Admissible heuristics for the connection of forward and backward searches have been developed, but their computational complexity is a deterrent. In this work, we leverage recent advances in search with inadmissible heuristics to develop an algorithm called A*-Connect, much in the spirit of RRT-Connect. A*-Connect uses a fast approximation of the classic front-to-front heuristic from literature to lead the forward and backward searches towards each other, while retaining theoretical guarantees on completeness and bounded suboptimality. We validate A*-Connect on manipulation as well as navigation domains, comparing with popular sampling-based methods as well as state-of-the-art bidirectional search algorithms. Our results indicate that A*-Connect can provide several times speedup over unidirectional search while maintaining high solution quality.

BibTeX Reference
@conference{Islam-2016-5504,
author = {Fahad Islam and Venkatraman Narayanan and Maxim Likhachev},
title = {A*-Connect: Bounded Suboptimal Bidirectional Heuristic Search},
booktitle = {IEEE International Conference on Robotics and Automation (ICRA)},
year = {2016},
month = {May},
}
2017-09-13T10:38:28+00:00