Hernandez Ulloa, C.Baier, J.Asin-Acha, R.2021-09-022021-09-022020IEEE Access, Volume 8, Pages 116724 - 116732, 2020, Article number 91200052169-3536http://repositorio.unab.cl/xmlui/handle/ria/20097Indexación: Scopus.Incremental heuristic search algorithms are a class of heuristic search algorithms applicable to the problem of goal-directed navigation. D∗ and D∗Lite are among the most well-known algorithms for this problem. Recently, two new algorithms have been shown to outperform D∗Lite in relevant benchmarks: Multi-Path Adaptive A∗ (MPAA∗) and D∗ExtraLite. Existing empirical evaluations, unfortunately, do not allow to obtain meaningful conclusions regarding the strengths and weaknesses of these algorithms. Indeed, in the paper introducing D∗ExtraLite, it is shown that D∗Lite outperforms MPAA∗ in benchmarks in which the authors of MPAA∗ claim superiority over D∗Lite. The existence of published contradictory data unfortunately does not allow practitioners to make decisions over which algorithm to use given a specific application. In this paper, we analyze two factors that significantly influence the performance of MPAA∗, explaining why it is possible to obtain very different results depending on such factors. We identify a configuration of MPAA∗ which, in the majority of the benchmark problems we use, exhibits superior performance when compared to both D∗Lite and D∗ExtraLite. We conclude that MPAA∗ should be the algorithm of choice in goal-directed navigation scenarios in which the heuristic is accurate, whereas D∗ExtraLite should be preferred when the heuristic is inaccurate.enDD ExtraLiteDLitegoal-directed navigationincremental heuristic searchMPAAArtículoAttribution 4.0 International (CC BY 4.0)DOI: 10.1109/ACCESS.2020.3003344