Generalized Adaptive A*

ABSTRACT

Agents often have to solve series of similar search problems. Adaptive A* is a recent incremental heuristic search algorithm that solves series of similar search problems faster than A* because it updates the h-values using information from previous searches. It basically transforms consistent h-values into more informed consistent h-values. This allows it to find shortest paths in state spaces where the action costs can increase over time since consistent h-values remain consistent after action cost increases. However, it is not guaranteed to find shortest paths in state spaces where the action costs can decrease over time because consistent h-values do not necessarily remain consistent after action cost decreases. Thus, the h-values need to get corrected after action cost decreases. In this paper, we show how to do that, resulting in Generalized Adaptive A* (GAA*) that finds shortest paths in state spaces where the action costs can increase or decrease over time. Our experiments demonstrate that Generalized Adaptive A* outperforms breadth-first search, A* and D* Lite for moving-target search, where D* Lite is an alternative state-of-the-art incremental heuristic search algorithm that finds shortest paths in state spaces where the action costs can increase or decrease over time.

REFERENCES

• 1: E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 2: 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.
• 3: C. Hernández and P. Maseguer. LRTA*(k). In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1238--1243, 2005.
• 4: 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]
• 5: T. Ishida and R. Korf. Moving target search. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 204--210, 1991.
• 6: Sven Koenig, A Comparison of Fast Search Methods for Real-Time Situated Agents, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.864-871, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.7]
• 7: S. Koenig and M. Likhachev. A new principle for incremental heuristic search: Theoretical results. In Proceedings of the International Conference on Automated Planning and Scheduling, pages 402--405, 2006.
• 8: 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]
• 9: 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]
• 10: 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]
• 11: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 12: Joseph C. Pemberton , Richard E. Korf, Incremental path planning on graphs with cycles, Proceedings of the first international conference on Artificial intelligence planning systems, p.179-188, May 1992, College Park, Maryland, United States

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
A*, D* Lite, heuristic search, incremental search, moving-target search, shortest paths