Real-time adaptive A*

ABSTRACT

Characters in real-time computer games need to move smoothly and thus need to search in real time. In this paper, we describe a simple but powerful way of speeding up repeated A* searches with the same goal states, namely by updating the heuristics between A* searches. We then use this technique to develop a novel real-time heuristic search method, called Real-Time Adaptive A*, which is able to choose its local search spaces in a fine-grained way. It updates the values of all states in its local search spaces and can do so very quickly. Our experimental results for characters in real-time computer games that need to move to given goal coordinates in unknown terrain demonstrate that this property allows Real-Time Adaptive A* to follow trajectories of smaller cost for given time limits per search episode than a recently proposed real-time heuristic search method [5] that is more difficult to implement.

REFERENCES

• 1: M. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer, and P. Yap. Comparison of different abstractions for pathfinding on maps. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1511--1512, 2003.
• 2: V. Bulitko and G. Lee. Learning in real-time search: A unifying framework. Journal of Artificial Intelligence Research, page (in press), 2005.
• 3: 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.
• 4: Toru Ishida, Real-time search for learning autonomous agents, Kluwer Academic Publishers, Norwell, MA, 1997
• 5: 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]
• 6: Sven Koenig , Maxim Likhachev, D*lite, Eighteenth national conference on Artificial intelligence, p.476-483, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 7: Sven Koenig , Maxim Likhachev, Adaptive A, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082748]
• 8: 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]
• 9: 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]
• 10: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 11: A. Stentz. The focussed D* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1652--1659, 1995.
• 12: Shlomo Zilberstein, Operational rationality through compilation of anytime algorithms, University of California at Berkeley, Berkeley, CA, 1993

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms

Keywords:
A*, D* lite, agent planning, games, heuristic search, incremental search, perception, action and planning in agents, planning with the freespace assumption, real-time decision making