Real-Time Adaptive A∗ with Depression Avoidance

Abstract

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