Simple optimization techniques for A*-based search

Xiaoxun Sun, William Yeoh, Po-An Chen, Sven KoenigAAMAS 2009 · OpenReview

Abstract

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.
BibTeX
@inproceedings{sun2009simple,
  author = {Xiaoxun Sun and William Yeoh and Po-An Chen and Sven Koenig},
  title = {{Simple optimization techniques for A*-based search}},
  booktitle = {AAMAS},
  year = {2009},
  url = {https://openreview.net/forum?id=q8zHYzKpWWu},
}

Loading related content...

Figure