Real-Time Adaptive A* with Depression Avoidance

Authors

  • Carlos Hernandez Universidad Catolica de la Santisima Concepción
  • Jorge Baier Pontificia Universidad Catolica de Chile

DOI:

https://doi.org/10.1609/socs.v2i1.18215

Keywords:

Real-Time Search, Heuristic Search, Heuristic Depression

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.

Downloads

Published

2021-08-19