Real-Time Adaptive A*

May 2006

Real-Time Adaptive A*

Authors:

Sven Koenig and Maxim Likhachev

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.
@conference{Koenig-2006-109734,
author = {Sven Koenig And Maxim Likhachev},
title = {Real-Time Adaptive A*},
booktitle = {Proceedings of 5th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS '06)},
year = {2006},
month = {May},
pages = {281 - 288},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.