AAAI Publications, Fourth Annual Symposium on Combinatorial Search

Font Size: 
Real-Time Adaptive A* with Depression Avoidance
Carlos Hernandez, Jorge A Baier

Last modified: 2011-07-05

Abstract


Real-time search is a well known approach to solving search problems under tight time constraints. 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.

Full Text: PDF