AAAI Publications, Seventh Annual Symposium on Combinatorial Search

Font Size: 
Anytime Tree-Restoring Weighted A* Graph Search
Kalin Gochev, Alla Safonova, Maxim Likhachev

Last modified: 2014-07-02


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.


Path Planning; Heuristic Search; Incremental Graph Search; Anytime Graph Search

Full Text: PDF