Real-Time Adaptive A∗ with Depression Avoidance


  • Carlos Hernandez Universidad Catolica de la Santisima Concepcion
  • Jorge Baier Pontificia Universidad Catolica de Chile



Real-Time Search, Heuristic Search, Heuristic Depression


RTAA* is probably the best-performing real-time heuristic search algorithm at path-finding tasks in which the environ- ment is not known in advance or in which the environment is known and there is no time for pre-processing. As most real- time search algorithms do, RTAA∗ performs poorly in presence of heuristic depressions, which are bounded areas of the search space in which the heuristic is too low with respect to their border. Recently, it has been shown that LSS-LRTA∗, a well-known real-time search algorithm, can be improved when search is actively guided away of depressions. In this paper we investigate whether or not RTAA∗ can be improved in the same manner. We propose aRTAA∗ and daRTAA∗, two algorithms based on RTAA∗ that avoid heuristic depressions. Both algorithms outperform RTAA∗ on standard path-finding tasks, obtaining better-quality solutions when the same time deadline is imposed on the duration of the planning episode. We prove, in addition, that both algorithms have good theoretical properties




How to Cite

Hernandez, C., & Baier, J. (2011). Real-Time Adaptive A∗ with Depression Avoidance. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 7(1), 146-151.