Simple Optimization Techniques for A*-Based Search

In this paper, we present two simple optimizations that can reduce the number of priority queue operations for A* and its extensions. Basically, when the optimized search algorithms expand a state, they check whether they will expand a successor of the state next. If so, they do not first insert it into the priority queue and then immediately remove it again. These changes might appear to be trivial but are well suited for Generalized Adaptive A*, an extension of A*. Our experimental results indeed show that they speed up Generalized Adaptive A* by up to 30 percent if its priority queue is implemented as a binary heap.

Authors

• Xiaoxun Sun
• William Yeoh Washington University in St. Louis
• Po-An Chen
• Sven Koenig University of California, Irvine

Keywords

• A* Search
• Incremental Heuristic Search
• Path Planning