Simple optimization techniques for A*-based search

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.

REFERENCES

• 1: P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 2:100--107, 1968.
• 2: R. C. Holte , T. Mkadmi , R. M. Zimmer , A. J. MacDonald, Speeding up problem solving by abstraction: a graph oriented approach, Artificial Intelligence, v.85 n.1-2, p.321-361, Aug. 1996 [doi>10.1016/0004-3702(95)00111-5]
• 3: Sven Koenig , Maxim Likhachev, Real-time adaptive A*, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160682]
• 4: Sven Koenig , Maxim Likhachev , Xiaoxun Sun, Speeding up moving-target search, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329353]
• 5: Sven Koenig , Craig Tovey , Yuri Smirnov, Performance bounds for planning in unknown terrain, Artificial Intelligence, v.147 n.1-2, p.253-279, July 2003 [doi>10.1016/S0004-3702(03)00062-6]
• 6: Richard E. Korf, Real-time heuristic search, Artificial Intelligence, v.42 n.2-3, p.189-211, March 1990 [doi>10.1016/0004-3702(90)90054-4]
• 7: M. Likhachev, G. Gordon, and S. Thrun. ARA*: Anytime A* with provable bounds on sub-optimality. In Proceedings of the Neural Information Processing Systems Conference, 2003.
• 8: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 9: X. Sun, M. Druzdzel, and C. Yuan. Dynamic Weighting A* search-based MAP algorithm for Bayesian networks. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 2385--2390, 2007.
• 10: Xiaoxun Sun , Sven Koenig , William Yeoh, Generalized Adaptive A*, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Experimentation, Theory

Keywords:
A* search, incremental heuristic search, path planning