Does Fast Beat Thorough? Comparing RTAA* and LSS-LRTA*

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Short Papers

The RTAA* algorithm has been proposed as an alternative to the LSS-LRTA* algorithm for heuristic search under hard time constraints. It uses a cruder but faster learning procedure. Experimental results on pathfinding in mazes in the unknown terrain setting indicated that RTAA* was superior to LSS-LRTA*. In this paper, we attempt to replicate those results and we extend the analysis to additional domains. Our results suggest that RTAA* is superior to LSS-LRTA* only in situations where the heuristic is already relatively accurate, either inherently or because of large lookahead. Overall, neither algorithm seems superior to the other.

10.1609/socs.v9i1.18465