Anytime Tree-Restoring Weighted A* Graph Search

August 2014

Anytime Tree-Restoring Weighted A* Graph Search

Authors:

Kalin Gochev, Alla Safonova, and Maxim Likhachev

Abstract:

Incremental graph search methods reuse information from previous searches in order to minimize redundant computation and to find solutions to series of similar search queries much faster than it is possible by solving each query from scratch. In this work, we present a simple, but very effective, technique for performing incremental weighted A∗ graph search in an anytime fashion. On the theoretical side, we show that our anytime incremental algorithm preserves the strong theoretical guarantees provided by the weighted A∗ algorithm, such as completeness and bounds on solution cost sub-optimality. We also show that our algorithm can handle a variety of changes to the underlying graph, such as both increasing and decreasing edge costs, and changes in the heuristic. On the experimental side, we demonstrate the effectiveness of our algorithm in the context of (x,y,z,yaw) navigation planning for an unmanned aerial vehicle and compare our algorithm to popular incremental and anytime graph search algorithms.
@conference{Gochev-2014-109517,
author = {Kalin Gochev And Alla Safonova And Maxim Likhachev},
title = {Anytime Tree-Restoring Weighted A* Graph Search},
booktitle = {Proceedings of 7th International Symposium on Combinatorial Search (SoCS '14)},
year = {2014},
month = {August},
pages = {80 - 88},
}
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.