Real-Time Adaptive A* with Depression Avoidance

Proceedings of the International Symposium on Combinatorial Search, 4

Volume

Vol. 4 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search

Short Papers

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.

10.1609/socs.v2i1.18215