Multipath Adaptive A∗: Factors That Influence Performance in Goal-Directed Navigation in Unknown Terrain

Carlos Hernandez Ulloa, Jorge A. Baier, Roberto Asin-Acha

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva


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.

Idioma originalInglés
Número de artículo9120005
Páginas (desde-hasta)116724-116732
Número de páginas9
PublicaciónIEEE Access
EstadoPublicada - 2020

Áreas temáticas de ASJC Scopus

  • Informática (todo)
  • Ciencia de los materiales (todo)
  • Ingeniería (todo)


Profundice en los temas de investigación de 'Multipath Adaptive A∗: Factors That Influence Performance in Goal-Directed Navigation in Unknown Terrain'. En conjunto forman una huella única.

Citar esto